本記事では、PostgreSQLでバージョン8.4から利用できるようになった、with recursiveというものを最近知ったので紹介いたします。

with recursiveとは？

with recursiveは、自分自身を参照することで、前に行った処理の結果を利用して同じ処理を繰り返す再帰処理を可能にするものです。

例えば、1つのテーブルで以下のような親子関係があるとします。
その場合、rootの子データを全て取得しようとした場合、みなさんどのように取得しますか？

1つずつ取得して、アプリケーション側で頑張る(rootを取得、親を取得、子を取得・・・) ※アプリケーションが複雑になる
left joinとunion を利用して、取得する ※階層が深くなるほど、SQLが複雑になる
階層情報を保存するカラムを用意する ※階層が変わった場合に、データの更新が必要

いずれの方法でも実現は可能ですが、少し複雑になったりします！
そこで、with recursiveでの再帰的取得の出番です！！！

ちなみに、今回のような構造はナイーブツリーと言い、SQLアンチパターンの一つとして有名です。
なので、基本的には単一テーブルにするのではなく、複数テーブルに正規化するようにしましょう。

with recursiveを試してみる

では、実際に試していきます。

データの準備

まずは、テーブルを作成します。
※今回は、idカラムはint型のオートインクリメントではなく、uuid型にしています。

organizationsテーブルの作成

create table organizations (
    id uuid not null primary key default gen_random_uuid(),
    parent_id uuid default null,
    name varchar(255) not null
);

次に、データを投入していきます。

組織テーブルのデータ投入

insert into organizations(name) values
  ('root1'),
  ('親1-root1'),
  ('親2-root1'),
  ('子1-親2-root1'),
  ('子2-親2-root1'),
  ('孫1-子2'),
  ('孫2-子2'),
  ('ひ孫1-孫2'),
  ('ひ孫2-孫2');

update organizations set
  parent_id = (select id from organizations where name = 'root1')
  where name in ('親1-root1', '親2-root1');

update organizations set
  parent_id = (select id from organizations where name = '親2-root1')
  where name in ('子1-親2-root1', '子2-親2-root1');

update organizations set
  parent_id = (select id from organizations where name = '子2-親2-root1')
  where name in ('孫1-子2', '孫2-子2');

update organizations set
  parent_id = (select id from organizations where name = '孫2-子2')
  where name in ('ひ孫1-孫2', 'ひ孫2-孫2');

データを取得してみる

準備が出来たので、データを取得してみましょう。
以下の形式で取得します。

WITH RECURSIVE
  仮想テーブル名 AS 
  -- 仮想テーブルの生成クエリ
  (
    非再帰項（仮想テーブルの先頭行になるレコード）
    UNION ALL
    再帰項（自身を参照・条件設定して抽出されたレコード）
  )
-- 以下、実際にデータを取得するクエリ。さくせい仮想テーブルを呼び出すことができる
SELECT ... FROM ... WHERE ... GROUP BY ...

root以下の子組織を全て取得

以下のSQLを実行すると、rootの子組織データが全て取得出来ていることがわかります。
※depthは階層です(自分自身を階層0としています)

with recursive child(depth, id, parent_id, name) as (
  select
      0 as depth,
      organizations.id,
      organizations.parent_id,
      organizations.name
    from
      organizations
    where
      organizations.id = (select id from organizations where parent_id is null)
  union all
    select
      child.depth + 1,
      organizations.id,
      organizations.parent_id,
      organizations.name
    from
      organizations,
      child
    where
      organizations.parent_id = child.id
)
select depth, id, parent_id, name from child order by depth;

 depth |                  id                  |              parent_id               |     name      
-------+--------------------------------------+--------------------------------------+---------------
     0 | a767a809-a00e-4cd1-8543-ab66186346bc |                                      | root1
     1 | 0dbdf546-f66c-41bb-8648-65efcdb5634d | a767a809-a00e-4cd1-8543-ab66186346bc | 親1-root1
     1 | ef66fc64-e68f-4273-a3a6-425e05088597 | a767a809-a00e-4cd1-8543-ab66186346bc | 親2-root1
     2 | 097b9d38-6233-4b1d-94e5-7faca8410c53 | ef66fc64-e68f-4273-a3a6-425e05088597 | 子1-親2-root1
     2 | 8bf47e54-82eb-4e7b-bef5-bde6a0906bf3 | ef66fc64-e68f-4273-a3a6-425e05088597 | 子2-親2-root1
     3 | f0ce6c86-0670-483a-bd0a-89bb727ab59a | 8bf47e54-82eb-4e7b-bef5-bde6a0906bf3 | 孫1-子2
     3 | 6a02e90f-e754-4eab-b148-f2474d0c387b | 8bf47e54-82eb-4e7b-bef5-bde6a0906bf3 | 孫2-子2
     4 | cbc2c45e-0925-4fdc-ba4d-b452f6e0c7ce | 6a02e90f-e754-4eab-b148-f2474d0c387b | ひ孫1-孫2
     4 | de15665a-ee0e-4be6-b70d-62686c0e0c6b | 6a02e90f-e754-4eab-b148-f2474d0c387b | ひ孫2-孫2
(9 rows)

指定した組織の子組織を全て取得

以下のSQLを実行すると、子2-親2-root1の子組織データが全て取得出来ていることがわかります。

with recursive child(depth, id, parent_id, name) as (
  select
      0 as depth,
      organizations.id,
      organizations.parent_id,
      organizations.name
    from
      organizations
    where
      organizations.id = (select id from organizations where name = '子2-親2-root1')
  union all
    select
      child.depth + 1,
      organizations.id,
      organizations.parent_id,
      organizations.name
    from
      organizations,
      child
    where
      organizations.parent_id = child.id
)
select depth, id, parent_id, name from child order by depth;

 depth |                  id                  |              parent_id               |     name      
-------+--------------------------------------+--------------------------------------+---------------
     0 | 8bf47e54-82eb-4e7b-bef5-bde6a0906bf3 | ef66fc64-e68f-4273-a3a6-425e05088597 | 子2-親2-root1
     1 | f0ce6c86-0670-483a-bd0a-89bb727ab59a | 8bf47e54-82eb-4e7b-bef5-bde6a0906bf3 | 孫1-子2
     1 | 6a02e90f-e754-4eab-b148-f2474d0c387b | 8bf47e54-82eb-4e7b-bef5-bde6a0906bf3 | 孫2-子2
     2 | cbc2c45e-0925-4fdc-ba4d-b452f6e0c7ce | 6a02e90f-e754-4eab-b148-f2474d0c387b | ひ孫1-孫2
     2 | de15665a-ee0e-4be6-b70d-62686c0e0c6b | 6a02e90f-e754-4eab-b148-f2474d0c387b | ひ孫2-孫2
(5 rows)

指定した組織の親組織を全て取得

以下のSQLを実行すると、子2-親2-root1の親組織データが全て取得出来ていることがわかります。

with recursive parent(depth, id, parent_id, name) as (
   select
      0 as depth,
      organizations.id,
      organizations.parent_id,
      organizations.name
    from
      organizations
    where
      organizations.id = (select id from organizations where name = '子2-親2-root1')
  union all
    select
      parent.depth + 1,
      organizations.id,
      organizations.parent_id,
      organizations.name
    from
      organizations,
      parent
    where
      organizations.id = parent.parent_id
)
select depth, id, parent_id, name from parent order by depth;

 depth |                  id                  |              parent_id               |     name      
-------+--------------------------------------+--------------------------------------+---------------
     0 | 8bf47e54-82eb-4e7b-bef5-bde6a0906bf3 | ef66fc64-e68f-4273-a3a6-425e05088597 | 子2-親2-root1
     1 | ef66fc64-e68f-4273-a3a6-425e05088597 | a767a809-a00e-4cd1-8543-ab66186346bc | 親2-root1
     2 | a767a809-a00e-4cd1-8543-ab66186346bc |                                      | root1
(3 rows)

指定した組織の親組織と子組織を全て取得

以下のSQLを実行すると、子2-親2-root1の子組織と親組織データが全て取得出来ていることがわかります。

with recursive parent(depth, id, parent_id, name) as (
  select
      0 as depth,
      organizations.id,
      organizations.parent_id,
      organizations.name
    from
      organizations
    where
      organizations.id = (select id from organizations where name = '子2-親2-root1')
  union all
    select
      parent.depth + 1,
      organizations.id,
      organizations.parent_id,
      organizations.name
    from
      organizations,
      parent
    where
      organizations.parent_id = parent.id
),
child as (
  select
      0 as depth,
      organizations.id,
      organizations.parent_id,
      organizations.name
    from
      organizations
    where
      organizations.id = (select id from organizations where name = '子2-親2-root1')
  union all
    select
      child.depth - 1,
      organizations.id,
      organizations.parent_id,
      organizations.name
    from
      organizations,
      child
    where
      organizations.id = child.parent_id
)
select depth, id, parent_id, name from parent
union
select depth, id, parent_id, name from child
order by depth;

親がいない場合、子がいない場合

ちなみに、親のいない組織で親データを取得したり、子組織がいない組織で子データを取得しようとすると、当たり前ですが自分自身のみ取得されます。

root1の親組織を全て取得

with recursive parent(depth, id, parent_id, name) as (
   select
      0 as depth,
      organizations.id,
      organizations.parent_id,
      organizations.name
    from
      organizations
    where
      organizations.id = (select id from organizations where name = 'root1')
  union all
    select
      parent.depth + 1,
      organizations.id,
      organizations.parent_id,
      organizations.name
    from
      organizations,
      parent
    where
      organizations.id = parent.parent_id
)
select depth, id, parent_id, name from parent order by depth;

 depth |                  id                  | parent_id | name  
-------+--------------------------------------+-----------+-------
     0 | a767a809-a00e-4cd1-8543-ab66186346bc |           | root1
(1 row)

親1-root1の子組織を全て取得

with recursive child(depth, id, parent_id, name) as (
  select
      0 as depth,
      organizations.id,
      organizations.parent_id,
      organizations.name
    from
      organizations
    where
      organizations.id = (select id from organizations where name = '親1-root1')
  union all
    select
      child.depth + 1,
      organizations.id,
      organizations.parent_id,
      organizations.name
    from
      organizations,
      child
    where
      organizations.parent_id = child.id
)
select depth, id, parent_id, name from child order by depth;

 depth |                  id                  |              parent_id               |   name    
-------+--------------------------------------+--------------------------------------+-----------
     0 | 0dbdf546-f66c-41bb-8648-65efcdb5634d | a767a809-a00e-4cd1-8543-ab66186346bc | 親1-root1
(1 row)

再帰的に取得する際の注意と対応

with recursiveを使って簡単に、階層構造のデータを取得することがわかりました。

では、ここで問題です！
仮に以下のように、親子関係がループしているような階層になっていた場合、with recursiveを実行するとどうなるでしょう？
※実際は、そもそもこのようなデータにならないようにするのですが、アプリケーション側の不具合などを想定

１．SQLがエラーになる
２．SQLは成功し、結果が取得できる
３．SQLが終わらない

正解

正解は【３．SQLが終わらない】になります。

親子関係がループしている際の挙動を確認してみる

では、実際に試してみます！

組織を追加

insert into organizations(name) values
  ('子1-親1-root1');

update organizations set
  parent_id = (select id from organizations where name = '親1-root1')
  where name in ('子1-親1-root1');
update organizations set
  parent_id = (select id from organizations where name = '子1-親1-root1')
  where name in ('root1');

組織を追加した状態で、親1-root1の子組織を取得してみましょう。
・親1-root1の子組織は、子1-親1-root1
・子1-親1-root1の子組織は、root1
・root1の子組織は、親1-root1
・・・
と、再帰的に取得していくので、無限ループで終わらないことがわかります。

with recursive child(depth, id, parent_id, name) as (
  select
      0 as depth,
      organizations.id,
      organizations.parent_id,
      organizations.name
    from
      organizations
    where
      organizations.id = (select id from organizations where name = '親1-root1')
  union all
    select
      child.depth + 1,
      organizations.id,
      organizations.parent_id,
      organizations.name
    from
      organizations,
      child
    where
      organizations.parent_id = child.id
)
select depth, id, parent_id, name from child order by depth;

親子関係がループしていてもいいようにするためには

無限ループが発生すると、アプリケーションやDBに不都合が発生する原因になりますね。
万が一、このようなデータになっている場合でも正常にデータを取得するにはどうすればいいでしょうか？

CYCLE句

PostgreSQL14から利用できるようになったCYCLE句を利用することで、無限ループを回避することが出来ます。
先ほどのSQLに、CYCLE id SET is_cycle USING pathを追加します。

これは、

idカラムを監視し、同じidの値が出現することを検知 ※監視したい任意のカラムを指定
検知したら、対象レコードのis_cycleカラムがtrueになる
pathカラムには、通過したパスの履歴がセットされる

という意味になります。
よくわからない気もするので、実際に実行してみます。

with recursive child(depth, id, parent_id, name) as (
  select
      0 as depth,
      organizations.id,
      organizations.parent_id,
      organizations.name
    from
      organizations
    where
      organizations.id = (select id from organizations where name = '親1-root1')
  union all
    select
      child.depth + 1,
      organizations.id,
      organizations.parent_id,
      organizations.name
    from
      organizations,
      child
    where
      organizations.parent_id = child.id
) CYCLE id SET is_cycle USING path
select depth, id, parent_id, name, is_cycle, path from child order by depth;

 depth |                  id                  |              parent_id               |     name      | is_cycle |                                                                                                                          
              path
-------+--------------------------------------+--------------------------------------+---------------+----------+------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
     0 | 0dbdf546-f66c-41bb-8648-65efcdb5634d | a767a809-a00e-4cd1-8543-ab66186346bc | 親1-root1     | f        | {(0dbdf546-f66c-41bb-8648-65efcdb5634d)}
     1 | 41a7306b-3333-4c7a-a663-9173939b85aa | 0dbdf546-f66c-41bb-8648-65efcdb5634d | 子1-親1-root1 | f        | {(0dbdf546-f66c-41bb-8648-65efcdb5634d),(41a7306b-3333-4c7a-a663-9173939b85aa)}
     2 | a767a809-a00e-4cd1-8543-ab66186346bc | 41a7306b-3333-4c7a-a663-9173939b85aa | root1         | f        | {(0dbdf546-f66c-41bb-8648-65efcdb5634d),(41a7306b-3333-4c7a-a663-9173939b85aa),(a767a809-a00e-4cd1-8543-ab66186346bc)}   
     3 | 0dbdf546-f66c-41bb-8648-65efcdb5634d | a767a809-a00e-4cd1-8543-ab66186346bc | 親1-root1     | t        | {(0dbdf546-f66c-41bb-8648-65efcdb5634d),(41a7306b-3333-4c7a-a663-9173939b85aa),(a767a809-a00e-4cd1-8543-ab66186346bc),(0dbdf546-f66c-41bb-8648-65efcdb5634d)}
     3 | ef66fc64-e68f-4273-a3a6-425e05088597 | a767a809-a00e-4cd1-8543-ab66186346bc | 親2-root1     | f        | {(0dbdf546-f66c-41bb-8648-65efcdb5634d),(41a7306b-3333-4c7a-a663-9173939b85aa),(a767a809-a00e-4cd1-8543-ab66186346bc),(ef66fc64-e68f-4273-a3a6-425e05088597)}
     4 | 097b9d38-6233-4b1d-94e5-7faca8410c53 | ef66fc64-e68f-4273-a3a6-425e05088597 | 子1-親2-root1 | f        | {(0dbdf546-f66c-41bb-8648-65efcdb5634d),(41a7306b-3333-4c7a-a663-9173939b85aa),(a767a809-a00e-4cd1-8543-ab66186346bc),(ef66fc64-e68f-4273-a3a6-425e05088597),(097b9d38-6233-4b1d-94e5-7faca8410c53)}
     4 | 8bf47e54-82eb-4e7b-bef5-bde6a0906bf3 | ef66fc64-e68f-4273-a3a6-425e05088597 | 子2-親2-root1 | f        | {(0dbdf546-f66c-41bb-8648-65efcdb5634d),(41a7306b-3333-4c7a-a663-9173939b85aa),(a767a809-a00e-4cd1-8543-ab66186346bc),(ef66fc64-e68f-4273-a3a6-425e05088597),(8bf47e54-82eb-4e7b-bef5-bde6a0906bf3)}
     5 | f0ce6c86-0670-483a-bd0a-89bb727ab59a | 8bf47e54-82eb-4e7b-bef5-bde6a0906bf3 | 孫1-子2       | f        | {(0dbdf546-f66c-41bb-8648-65efcdb5634d),(41a7306b-3333-4c7a-a663-9173939b85aa),(a767a809-a00e-4cd1-8543-ab66186346bc),(ef66fc64-e68f-4273-a3a6-425e05088597),(8bf47e54-82eb-4e7b-bef5-bde6a0906bf3),(f0ce6c86-0670-483a-bd0a-89bb727ab59a)}
     5 | 6a02e90f-e754-4eab-b148-f2474d0c387b | 8bf47e54-82eb-4e7b-bef5-bde6a0906bf3 | 孫2-子2       | f        | {(0dbdf546-f66c-41bb-8648-65efcdb5634d),(41a7306b-3333-4c7a-a663-9173939b85aa),(a767a809-a00e-4cd1-8543-ab66186346bc),(ef66fc64-e68f-4273-a3a6-425e05088597),(8bf47e54-82eb-4e7b-bef5-bde6a0906bf3),(6a02e90f-e754-4eab-b148-f2474d0c387b)}
     6 | cbc2c45e-0925-4fdc-ba4d-b452f6e0c7ce | 6a02e90f-e754-4eab-b148-f2474d0c387b | ひ孫1-孫2     | f        | {(0dbdf546-f66c-41bb-8648-65efcdb5634d),(41a7306b-3333-4c7a-a663-9173939b85aa),(a767a809-a00e-4cd1-8543-ab66186346bc),(ef66fc64-e68f-4273-a3a6-425e05088597),(8bf47e54-82eb-4e7b-bef5-bde6a0906bf3),(6a02e90f-e754-4eab-b148-f2474d0c387b),(cbc2c45e-0925-4fdc-ba4d-b452f6e0c7ce)}
     6 | de15665a-ee0e-4be6-b70d-62686c0e0c6b | 6a02e90f-e754-4eab-b148-f2474d0c387b | ひ孫2-孫2     | f        | {(0dbdf546-f66c-41bb-8648-65efcdb5634d),(41a7306b-3333-4c7a-a663-9173939b85aa),(a767a809-a00e-4cd1-8543-ab66186346bc),(ef66fc64-e68f-4273-a3a6-425e05088597),(8bf47e54-82eb-4e7b-bef5-bde6a0906bf3),(6a02e90f-e754-4eab-b148-f2474d0c387b),(de15665a-ee0e-4be6-b70d-62686c0e0c6b)}
(11 rows)

先ほどと違い、無限ループせずに正常にデータを取得することが出来ました！

取得したデータも見てみましょう。
nameが親1-root1のレコードが2つ取得出来ますが、4行目の方はis_cycleがtrueになっていますね。
pathも{(0dbdf546-f66c-41bb-8648-65efcdb5634d),(41a7306b-3333-4c7a-a663-9173939b85aa),(a767a809-a00e-4cd1-8543-ab66186346bc),(0dbdf546-f66c-41bb-8648-65efcdb5634d)}
となっていて、ループしていることがわかります。

おわりに

本記事では、PostgreSQL8.4から使えるwith recursiveを使って、簡単に親子関係のデータを取得することを確認しました。
利用シーンは限られるとは思いますが、知っておくと便利な機能ですね