PostgreSQL8.4から使えるwith recursiveとは？

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

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

例えば、1つのテーブルで以下のような**親子関係**があるとします。
その場合、rootの子データを全て取得しようとした場合、みなさんどのように取得しますか？
<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/87924/b5cad0ca-14d5-41db-ad77-dd18cc83cbae.png" width=50%>

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

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

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


# with recursiveを試してみる
では、実際に試していきます。

## データの準備
まずは、テーブルを作成します。
※今回は、idカラムはint型のオートインクリメントではなく、uuid型にしています。
```sql:organizationsテーブルの作成
create table organizations (
    id uuid not null primary key default gen_random_uuid(),
    parent_id uuid default null,
    name varchar(255) not null
);
```

次に、データを投入していきます。
```sql:組織テーブルのデータ投入
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');
```

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

### root以下の子組織を全て取得
<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/87924/296604e4-de25-4871-97c0-99b1fdde3d06.png" width=50%>

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

```sql
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)
```

### 指定した組織の子組織を全て取得
<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/87924/c7654e6d-3909-4206-a9e4-2cc60c4e9e64.png" width=50%>

以下のSQLを実行すると、**子2-親2-root1**の子組織データが全て取得出来ていることがわかります。
```sql
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)
```


### 指定した組織の親組織を全て取得
<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/87924/75297792-f141-43a2-a384-9e593f99a1f7.png" width=50%>

以下のSQLを実行すると、**子2-親2-root1**の親組織データが全て取得出来ていることがわかります。
```sql
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)
```

### 指定した組織の親組織と子組織を全て取得
<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/87924/bab1f829-2dfc-424f-a996-4dfcd3abc599.png" width=50%>

以下のSQLを実行すると、**子2-親2-root1**の子組織と親組織データが全て取得出来ていることがわかります。
```sql
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;
```




### 親がいない場合、子がいない場合
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/87924/daf33a69-bace-4eba-802b-53456d585dfc.png)

ちなみに、親のいない組織で親データを取得したり、子組織がいない組織で子データを取得しようとすると、当たり前ですが自分自身のみ取得されます。
```sql: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)

```

```sql:親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が終わらない**
<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/87924/ec648acf-9bd5-4737-a863-bb0f2ff2d02e.png" width=50%>

<details><summary>正解</summary>

正解は【**３．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
・・・
と、再帰的に取得していくので、無限ループで終わらないことがわかります。

```sql
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;
```
</details>



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

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

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

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

```sql
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**を使って、簡単に親子関係のデータを取得することを確認しました。
利用シーンは限られるとは思いますが、知っておくと便利な機能ですね:smile: