PostgreSQLで階層構造を極める：WITH RECURSIVEと代替モデルの選び方

2025-05-27

PostgreSQLの「WITH句：再帰クエリ」とは？

PostgreSQLにおけるWITH句（Common Table Expressions, CTEs）は、SQLクエリ内で一時的な結果セットを定義するための強力な機能です。特に、WITH RECURSIVEを使用することで、再帰的なクエリ、つまり自分自身を参照するクエリを作成することができます。これにより、階層構造やツリー構造のデータを扱う際に非常に役立ちます。

主な用途

再帰的な計算
フィボナッチ数列の生成など、前の結果に基づいて次の結果を計算するような場合に適用できます。
グラフ構造の探索
ネットワーク接続や依存関係など、より複雑なグラフ構造を探索する場合に利用できます。
階層データの走査
組織図、ファイルシステム、カテゴリツリーなど、親子関係を持つデータを上から下、または下から上へ辿る際に使用します。

`WITH RECURSIVE`の基本的な構文

WITH RECURSIVE句は、以下の2つの主要な部分から構成されます。

アンカーメンバー（非再帰項）:
- 再帰の「開始点」となる最初の結果セットを定義します。
- この部分では、自身（CTE名）を参照することはできません。
- 通常、階層構造の最上位（ルートノードなど）や、再帰計算の初期値を設定します。
再帰メンバー:
- アンカーメンバーの結果セットに基づいて、繰り返し実行される部分です。
- この部分では、定義しているCTE名を参照することができます。これにより、前のステップで生成された結果を使って次のステップの結果を生成します。
- UNIONまたはUNION ALL演算子を使ってアンカーメンバーと結合します。

一般的な構文

WITH RECURSIVE cte_name (カラム1, カラム2, ...) AS (
    -- アンカーメンバー (非再帰項)
    SELECT カラム1, カラム2, ...
    FROM テーブル
    WHERE 初期条件

    UNION [ALL]

    -- 再帰メンバー
    SELECT T.カラム1, T.カラム2, ...
    FROM テーブル T
    JOIN cte_name ON T.結合条件 -- ここで自身(cte_name)を参照する
    WHERE 再帰の停止条件
)
SELECT *
FROM cte_name;

UNIONとUNION ALL:
- UNION: 各ステップで重複する行を削除します。階層を辿る際に無限ループを防ぐために役立つ場合があります。
- UNION ALL: 重複を考慮せずにすべての行を結合します。パフォーマンスは通常こちらの方が優れています。
カラム1, カラム2, ...: CTEの出力カラムを定義します。アンカーメンバーと再帰メンバーで同じ数のカラムとデータ型を持つ必要があります。
cte_name: 定義する一時的な結果セットの名前です。

処理の流れ

PostgreSQLは、WITH RECURSIVEクエリを以下のような反復プロセスで実行します。

アンカーメンバーの実行: まず、アンカーメンバーのSELECTステートメントが実行され、その結果が一時的な「ワーキングテーブル」と、最終的なCTEの結果セットに追加されます。
再帰メンバーの繰り返し実行:
- ワーキングテーブルが空になるまで、以下のステップを繰り返します。
- 再帰メンバーのSELECTステートメントが実行されます。この際、cte_nameへの参照は、現在のワーキングテーブルの内容に置き換えられます。
- 再帰メンバーの実行によって得られた新しい行は、一時的な「中間テーブル」に追加されます。
- (UNIONを使用している場合) 中間テーブルの行のうち、すでに最終的なCTEの結果セットに含まれている重複行は破棄されます。
- 中間テーブルの残りの行が、最終的なCTEの結果セットと新しいワーキングテーブルに追加されます。
- ワーキングテーブルの内容が、このステップで追加された新しい行で更新されます。
終了: ワーキングテーブルが空になり、再帰メンバーが新しい行を生成しなくなると、繰り返しが停止します。最終的なCTEの結果セットがクエリの最終結果として返されます。

注意点：無限ループ

再帰クエリでは、無限ループに陥る可能性があります。再帰メンバーが常に新しい行を生成し続けると、クエリが終了しなくなります。これを避けるためには、再帰メンバーの中に適切な停止条件を設けることが非常に重要です。

UNIONを使って重複行を排除する
すでに訪問したノードを追跡し、重複して訪問しないようにする (WHERE NOT node_id = ANY(path_array))
階層の深さの制限 (WHERE level < max_level)

従業員とその上司の関係を管理するemployeesテーブルがあるとします。

CREATE TABLE employees (
    employee_id INTEGER PRIMARY KEY,
    full_name VARCHAR(100),
    manager_id INTEGER
);

INSERT INTO employees (employee_id, full_name, manager_id) VALUES
(1, 'アリス', NULL), -- CEO
(2, 'ボブ', 1),
(3, 'チャーリー', 1),
(4, 'デイジー', 2),
(5, 'エリック', 2),
(6, 'フィオナ', 3);

特定のマネージャー（例: アリス）の下にいるすべての部下を取得する再帰クエリは次のようになります。

WITH RECURSIVE subordinates AS (
    -- アンカーメンバー: アリス (employee_id = 1) から開始
    SELECT
        employee_id,
        full_name,
        manager_id,
        1 AS level -- 階層レベル
    FROM
        employees
    WHERE
        employee_id = 1

    UNION ALL

    -- 再帰メンバー: 現在のsubordinatesの従業員に紐づく部下を探す
    SELECT
        e.employee_id,
        e.full_name,
        e.manager_id,
        s.level + 1 AS level
    FROM
        employees e
    JOIN
        subordinates s ON e.manager_id = s.employee_id
)
SELECT
    employee_id,
    full_name,
    manager_id,
    level
FROM
    subordinates
ORDER BY
    level, employee_id;

解説

アンカーメンバー: employee_id = 1である「アリス」を最初の結果として取得します。levelは1と設定されます。
再帰メンバー:
- 最初のイテレーションでは、subordinatesには「アリス」の情報が入っています。JOIN subordinates s ON e.manager_id = s.employee_idによって、アリス（employee_id = 1）をmanager_idとする従業員（ボブとチャーリー）が検索され、結果に追加されます。これらのlevelはアリスのlevel + 1で2になります。
- 次のイテレーションでは、subordinatesには「アリス、ボブ、チャーリー」の情報が入っています。ボブ（employee_id = 2）をmanager_idとするデイジーとエリック、チャーリー（employee_id = 3）をmanager_idとするフィオナが検索され、結果に追加されます。これらのlevelは3になります。
- さらに次のイテレーションでは、subordinatesにはすでに「デイジー、エリック、フィオナ」の情報がありますが、これらのemployee_idをmanager_idとする従業員は存在しないため、再帰メンバーは何も行を返しません。
- ワーキングテーブルが空になり、クエリが終了します。

このクエリにより、アリスとその下のすべての部下（ボブ、チャーリー、デイジー、エリック、フィオナ）がそれぞれの階層レベルとともに取得されます。

PostgreSQL「WITH句：再帰クエリ」の一般的なエラーとトラブルシューティング

無限ループ（Infinite Loop）

最も一般的で厄介な問題です。再帰クエリが停止条件を満たさず、延々と行を生成し続けてしまう場合に発生します。これにより、クエリが長時間実行されたり、メモリやディスク容量を大量に消費したり、最終的にエラーになったりします。

エラーメッセージ例
明確なエラーメッセージが出ない場合が多いですが、クエリが完了しない、実行計画が非常に大きくなる、または以下のようなエラーが出ることもあります。

disk space exhausted
out of memory

原因

UNION ALLの誤用
UNIONではなくUNION ALLを使用している場合、重複する行が排除されないため、無限ループを招きやすい。
循環参照
階層データに循環（例：AがBの親で、BがAの親でもある）が含まれている場合、再帰が永遠に繰り返される。
停止条件の欠如または誤り
再帰メンバーで、アンカーメンバーから始まったデータがいつ終了するかを正確に定義できていない。

トラブルシューティング

EXPLAIN ANALYZEの利用
クエリの実行計画を確認し、どこで問題が発生しているか、行数が異常に増えていないかなどを分析します。
小さなデータセットでのテスト
まずは数行程度の小さなデータでクエリをテストし、意図通りに動作することを確認します。
UNIONの使用
循環参照の可能性がある場合は、UNIONを使って各イテレーションで重複行を自動的に排除させます。ただし、levelのような再帰で値が変わるカラムを含める場合は、UNIONを使っても重複と見なされないことがあるため注意が必要です。
停止条件の確認と追加
- 階層の深さを追跡するlevelやdepthのようなカラムを追加し、特定の深さで停止するようにWHERE level < max_depthなどの条件を追加します。
- 訪問済みのノードを追跡する配列カラム（例: path_array）を追加し、WHERE NOT node_id = ANY(path_array)のように既に訪問したノードを再度辿らないようにします。

カラムの型不一致（Column Type Mismatch）

アンカーメンバーと再帰メンバーで、対応するカラムのデータ型が一致しない場合に発生します。

エラーメッセージ例
ERROR: recursive query "cte_name" column X has type Y in non-recursive term but type Z overall

原因

特に、文字列連結などを行う場合、結果のデータ型が予期せず異なる型になることがある。
アンカーメンバーと再帰メンバーで、同じ順序の同じ位置にあるカラムのデータ型が異なる。

トラブルシューティング

カラムの定義の確認
WITH RECURSIVE cte_name (col1, col2, ...)のように、CTEの定義時にカラム名を明示的に指定することで、型の一貫性を確認しやすくなります。

明示的なキャスト (CAST) の使用
データ型が異なる場合、CAST()関数を使って明示的に型を揃えます。

WITH RECURSIVE my_cte AS (
    SELECT id, '初期値'::text AS path -- アンカーメンバー
    FROM my_table
    WHERE ...

    UNION ALL

    SELECT t.id, (c.path || '->' || t.name)::text AS path -- 再帰メンバーで型を揃える
    FROM my_table t
    JOIN my_cte c ON t.parent_id = c.id
)
SELECT * FROM my_cte;

不適切なSQL構文（Incorrect SQL Syntax）

再帰クエリでは、通常のSELECT文では許されるいくつかの構文が制限されます。

エラーメッセージ例

ERROR: recursive query "cte_name" does not allow aggregate functions, window functions, GROUP BY, ORDER BY, or DISTINCT in the recursive term
ERROR: recursive query "cte_name" contains a non-recursive term that contains a UNION, INTERSECT, EXCEPT, or WITH clause

原因

複数のアンカーメンバーの制限
複数のアンカーメンバーを定義する場合、それらはUNION ALLなどで結合されている必要があり、かつ再帰メンバーの前に配置されている必要があります。
再帰メンバー内の制限
再帰メンバー内で集約関数 (SUM(), COUNT())、ウィンドウ関数、GROUP BY、ORDER BY、DISTINCT句を使用している。これらは、再帰の各ステップで状態が変化するため、直接使用できません。

トラブルシューティング

ORDER BY
- ORDER BYは再帰メンバーでは使用できません。もし特定の順序で結果を結合したい場合は、最終的なSELECT文でORDER BYを使用します。
- もし階層の順序を維持したい場合は、pathのようなカラムにパス情報を文字列として蓄積し、そのpathカラムでソートする方法が有効です。
集約/ウィンドウ関数/GROUP BY/DISTINCT
- これらを再帰メンバー内で直接使用するのではなく、再帰クエリの最終的なSELECT文や、別のCTEとして適用します。
- 例えば、再帰で階層を辿った後に、その結果に対してGROUP BYや集約を行うようにします。

パフォーマンス問題（Performance Issues）

クエリが終了しても、実行に非常に時間がかかる場合があります。

原因

複雑な計算
再帰メンバー内で重い計算や関数呼び出しを行っている。
UNIONの使用
UNIONは重複排除のために追加の処理オーバーヘッドが発生します。重複排除が不要な場合はUNION ALLを使用するべきです。
非効率なJOIN条件
再帰メンバー内のJOIN条件が適切にインデックスを使用していない、または非常に多くの行を処理している。
巨大な結果セット
再帰によって生成される行数が非常に多い場合。

トラブルシューティング

LIMITの使用（注意）
最終的なSELECT文にLIMIT句を追加することで、PostgreSQLは必要な行数に達した時点で再帰処理を停止しようと試みます。ただし、これはSQL標準の動作ではないため、他のデータベースシステムへの移植性には注意が必要です。
中間結果の削減
必要に応じて、再帰クエリの前にデータをフィルタリングするなどして、処理する行数を減らします。
停止条件の最適化
無駄な再帰が行われないよう、できるだけ早く再帰を停止させる条件を検討します。
EXPLAIN ANALYZEの利用
実行計画を詳細に分析し、どの部分がボトルネックになっているかを特定します。特に「CTE Scan」の部分や、JOINにかかるコストを確認します。
UNION ALLの利用
重複排除が本当に必要な場合を除き、UNION ALLを使用します。
インデックスの確認と追加
再帰メンバーのJOIN条件で使用されるカラムに適切なインデックス（特に外部キー）があることを確認します。

RECURSIVEキーワードの忘れ

再帰クエリを使用する際には、WITH句の直後にRECURSIVEキーワードを付ける必要があります。

エラーメッセージ例
ERROR: relation "cte_name" does not exist （CTEが自身を参照しているにもかかわらず、それが再帰CTEとして認識されないため、存在しないテーブルとして扱われる）

原因

WITH RECURSIVEと記述すべきところを単にWITHと記述してしまった。

WITHの後にRECURSIVEキーワードを追加します。

ドキュメントの参照
PostgreSQLの公式ドキュメントは非常に詳細で、再帰クエリに関する具体的な制限や動作について詳しく説明されています。
ログの確認
PostgreSQLのログファイルに、エラーメッセージや詳細な情報が出力されている場合があります。
デバッグ用のカラム追加
再帰の過程を追跡するために、level（深さ）やpath（辿ってきたパス）のようなデバッグ用のカラムをCTEに追加します。これにより、無限ループの原因やデータの流れを把握しやすくなります。
段階的な開発
複雑な再帰クエリを一気に書くのではなく、まずアンカーメンバーが正しく機能するかを確認し、次に再帰メンバーを段階的に構築していくのが良いプラクティスです。

例1：組織図の階層を辿る（上下方向）

最も一般的なユースケースです。従業員とその直属の上司の関係が格納されたテーブルから、ある従業員から始まる（またはあるマネージャーの下にいる）すべての部下、あるいはある従業員から始まる（またはある部下から始まる）すべての上司を辿ります。

テーブル定義

CREATE TABLE employees (
    employee_id SERIAL PRIMARY KEY,
    full_name VARCHAR(100) NOT NULL,
    manager_id INTEGER REFERENCES employees(employee_id) -- 自身への外部キー
);

INSERT INTO employees (employee_id, full_name, manager_id) VALUES
(1, 'アリス', NULL), -- CEO (上司なし)
(2, 'ボブ', 1),
(3, 'チャーリー', 1),
(4, 'デイジー', 2),
(5, 'エリック', 2),
(6, 'フィオナ', 3),
(7, 'ジョージ', 4);

a) 特定のマネージャー（例：アリス）の下にいるすべての部下を取得する

これは「下方向」への走査です。

WITH RECURSIVE subordinates AS (
    -- アンカーメンバー: 再帰の開始点 (アリス)
    SELECT
        employee_id,
        full_name,
        manager_id,
        1 AS level, -- 階層レベルを追跡
        ARRAY[employee_id] AS path_ids -- 辿ったパスのIDを追跡 (無限ループ防止にも役立つ)
    FROM
        employees
    WHERE
        employee_id = 1 -- アリスのID

    UNION ALL

    -- 再帰メンバー: 現在の subordinates の従業員の直属の部下を探す
    SELECT
        e.employee_id,
        e.full_name,
        e.manager_id,
        s.level + 1 AS level,
        s.path_ids || e.employee_id AS path_ids -- パスに現在のIDを追加
    FROM
        employees e
    INNER JOIN
        subordinates s ON e.manager_id = s.employee_id
    WHERE
        NOT (e.employee_id = ANY(s.path_ids)) -- 無限ループ防止: 既に辿ったIDは除外 (このケースでは不要だが、循環参照がある場合は重要)
)
SELECT
    employee_id,
    full_name,
    manager_id,
    level,
    path_ids
FROM
    subordinates
ORDER BY
    level, employee_id;

出力例

 employee_id | full_name  | manager_id | level | path_ids
-------------+------------+------------+-------+----------
           1 | アリス     |            |     1 | {1}
           2 | ボブ       |          1 |     2 | {1,2}
           3 | チャーリー |          1 |     2 | {1,3}
           4 | デイジー   |          2 |     3 | {1,2,4}
           5 | エリック   |          2 |     3 | {1,2,5}
           6 | フィオナ   |          3 |     3 | {1,3,6}
           7 | ジョージ   |          4 |     4 | {1,2,4,7}
(7 rows)

b) 特定の従業員（例：ジョージ）のすべての上司を取得する

WITH RECURSIVE managers AS (
    -- アンカーメンバー: 再帰の開始点 (ジョージ)
    SELECT
        employee_id,
        full_name,
        manager_id,
        1 AS level,
        ARRAY[employee_id] AS path_ids
    FROM
        employees
    WHERE
        employee_id = 7 -- ジョージのID

    UNION ALL

    -- 再帰メンバー: 現在の managers の従業員の上司を探す
    SELECT
        e.employee_id,
        e.full_name,
        e.manager_id,
        m.level + 1 AS level,
        m.path_ids || e.employee_id AS path_ids
    FROM
        employees e
    INNER JOIN
        managers m ON e.employee_id = m.manager_id -- ここでJOIN条件が逆になる
    WHERE
        NOT (e.employee_id = ANY(m.path_ids)) -- 無限ループ防止
)
SELECT
    employee_id,
    full_name,
    manager_id,
    level,
    path_ids
FROM
    managers
ORDER BY
    level;

出力例

 employee_id | full_name | manager_id | level | path_ids
-------------+-----------+------------+-------+----------
           7 | ジョージ  |          4 |     1 | {7}
           4 | デイジー  |          2 |     2 | {7,4}
           2 | ボブ      |          1 |     3 | {7,4,2}
           1 | アリス    |            |     4 | {7,4,2,1}
(4 rows)

例2：ファイルシステムの階層を表現する

ディレクトリとファイルの階層構造を表現します。

テーブル定義

CREATE TABLE fs_items (
    item_id SERIAL PRIMARY KEY,
    item_name VARCHAR(255) NOT NULL,
    item_type VARCHAR(10) NOT NULL, -- 'directory' or 'file'
    parent_id INTEGER REFERENCES fs_items(item_id)
);

INSERT INTO fs_items (item_name, item_type, parent_id) VALUES
('root', 'directory', NULL),
('documents', 'directory', 1),
('images', 'directory', 1),
('report.docx', 'file', 2),
('memo.txt', 'file', 2),
('photo1.jpg', 'file', 3),
('subdir', 'directory', 2),
('notes.txt', 'file', 7);

特定のディレクトリ（例：root）以下のすべてのアイテムを取得し、フルパスを表示する

WITH RECURSIVE fs_tree AS (
    -- アンカーメンバー: root ディレクトリから開始
    SELECT
        item_id,
        item_name,
        item_type,
        parent_id,
        item_name AS full_path, -- フルパス
        1 AS depth -- 階層の深さ
    FROM
        fs_items
    WHERE
        item_id = 1 -- root のID

    UNION ALL

    -- 再帰メンバー: 子アイテムを探す
    SELECT
        i.item_id,
        i.item_name,
        i.item_type,
        i.parent_id,
        (f.full_path || '/' || i.item_name) AS full_path, -- フルパスを構築
        f.depth + 1 AS depth
    FROM
        fs_items i
    INNER JOIN
        fs_tree f ON i.parent_id = f.item_id
)
SELECT
    item_id,
    item_name,
    item_type,
    full_path,
    depth
FROM
    fs_tree
ORDER BY
    depth, full_path;

出力例

 item_id |  item_name  | item_type |     full_path      | depth
---------+-------------+-----------+--------------------+-------
       1 | root        | directory | root               |     1
       2 | documents   | directory | root/documents     |     2
       3 | images      | directory | root/images        |     2
       4 | report.docx | file      | root/documents/report.docx |     3
       5 | memo.txt    | file      | root/documents/memo.txt |     3
       7 | subdir      | directory | root/documents/subdir |     3
       6 | photo1.jpg  | file      | root/images/photo1.jpg |     3
       8 | notes.txt   | file      | root/documents/subdir/notes.txt |     4
(8 rows)

例3：フィボナッチ数列の生成

再帰クエリは、前の結果に基づいて次の結果を計算するような、より抽象的な再帰にも使用できます。

WITH RECURSIVE fibonacci (n, fib_n, next_fib_n) AS (
    -- アンカーメンバー: フィボナッチ数列の最初の2項
    SELECT
        1 AS n,
        0 AS fib_n,
        1 AS next_fib_n

    UNION ALL

    -- 再帰メンバー: 次のフィボナッチ数を計算
    SELECT
        n + 1 AS n,
        next_fib_n AS fib_n,
        fib_n + next_fib_n AS next_fib_n
    FROM
        fibonacci
    WHERE
        n < 10 -- 10番目までのフィボナッチ数を生成
)
SELECT
    n,
    fib_n
FROM
    fibonacci;

出力例

 n  | fib_n
----+-------
  1 |     0
  2 |     1
  3 |     1
  4 |     2
  5 |     3
  6 |     5
  7 |     8
  8 |    13
  9 |    21
 10 |    34
(10 rows)

解説

next_fib_n: 次のフィボナッチ数
fib_n: 現在のフィボナッチ数
n: 項の番号

再帰メンバーでは、fib_nには前のステップのnext_fib_nが入り、next_fib_nには前のステップのfib_n + next_fib_n（つまり、前のステップの2つの数の合計）が入ります。n < 10という停止条件がなければ、無限にフィボナッチ数を生成し続けます。

例4：グラフのパス探索（より高度な例）

交通ネットワークのようなグラフ構造で、ある地点から到達可能なすべての地点や最短パスを探索するような場合にも使用できます。

テーブル定義

CREATE TABLE roads (
    road_id SERIAL PRIMARY KEY,
    from_city VARCHAR(50) NOT NULL,
    to_city VARCHAR(50) NOT NULL,
    distance_km INTEGER NOT NULL
);

INSERT INTO roads (from_city, to_city, distance_km) VALUES
('A', 'B', 10),
('A', 'C', 15),
('B', 'D', 20),
('C', 'E', 25),
('D', 'F', 5),
('E', 'F', 10),
('F', 'G', 8);

都市Aから到達可能なすべての都市と、そのパスおよび総距離を取得する

WITH RECURSIVE reachable_cities AS (
    -- アンカーメンバー: 開始都市 A
    SELECT
        from_city AS current_city,
        to_city AS next_city,
        distance_km AS total_distance,
        ARRAY[from_city, to_city] AS path, -- 辿った都市のパス
        1 AS hops -- 経由した道路の数
    FROM
        roads
    WHERE
        from_city = 'A'

    UNION ALL

    -- 再帰メンバー: 現在の都市から次の都市へ移動
    SELECT
        r.from_city AS current_city,
        r.to_city AS next_city,
        rc.total_distance + r.distance_km AS total_distance,
        rc.path || r.to_city AS path,
        rc.hops + 1 AS hops
    FROM
        roads r
    INNER JOIN
        reachable_cities rc ON r.from_city = rc.next_city
    WHERE
        NOT (r.to_city = ANY(rc.path)) -- 無限ループ防止: 既に辿った都市は除外
)
SELECT DISTINCT -- 重複パスを除外する場合
    next_city AS destination_city,
    total_distance,
    path,
    hops
FROM
    reachable_cities
ORDER BY
    destination_city, total_distance;

出力例

 destination_city | total_distance |    path     | hops
------------------+----------------+-------------+------
 A                |             10 | {A,B}       |    1
 A                |             15 | {A,C}       |    1
 B                |             30 | {A,B,D}     |    2
 C                |             40 | {A,C,E}     |    2
 D                |             35 | {A,B,D,F}   |    3
 E                |             50 | {A,C,E,F}   |    3
 F                |             43 | {A,B,D,F}   |    4
 F                |             60 | {A,C,E,F}   |    4
 G                |             51 | {A,B,D,F,G} |    5
 G                |             68 | {A,C,E,F,G} |    5
(10 rows)

この例では、pathカラムで辿った都市の配列を保持し、NOT (r.to_city = ANY(rc.path))という条件で循環参照を避けています。total_distanceも再帰的に計算されるため、各パスの総距離が分かります。

隣接リストモデル（Adjacency List Model）

これは最も基本的なモデルであり、WITH RECURSIVEが最もよく利用されるデータの格納方法です。各ノードが親ノードへの参照（parent_idなど）を持つ形式です。

特徴

ユースケース
データが頻繁に更新され、階層の走査があまり頻繁でない場合。
欠点
特定のノードのすべての子孫や先祖、または特定の深さのノードを検索するには、再帰クエリが必要になります。深い階層の場合、WITH RECURSIVEのパフォーマンスが問題になることがあります。
利点
データの挿入（INSERT）や削除（DELETE）が非常にシンプルで高速です。既存の階層の変更（親の付け替えなど）も容易です。

基本的なクエリ

複数レベルの階層走査: WITH RECURSIVE (前述の例を参照)
単一レベルの親子関係の取得: JOIN

具象パスモデル（Materialized Path Model）

各ノードが、ルートノードからそのノードまでの完全なパスを示す文字列（または配列）を保持するモデルです。パスは、区切り文字（例: /や.）で区切られたノードIDのシーケンスとして格納されます。

特徴

ユースケース
データが比較的静的で、階層の走査が非常に頻繁に行われる場合（例: ファイルシステム、カテゴリツリーの表示）。
欠点
データの挿入や更新（特に既存ノードの親の変更）が複雑になります。そのノード以下のすべてのパスを更新する必要があるため、パフォーマンスに影響が出る可能性があります。
利点
特定のノードの子孫や先祖、特定のサブツリーを検索するのが非常に高速です。文字列のLIKE演算子やLEFT()、SUBSTRING()関数、またはPostgreSQLのltree型拡張を使うことで効率的に検索できます。WITH RECURSIVEを使わずに多くの階層クエリを実行できます。

テーブル定義例

CREATE TABLE categories_materialized_path (
    category_id SERIAL PRIMARY KEY,
    category_name VARCHAR(100) NOT NULL,
    path TEXT NOT NULL UNIQUE -- 例: '1.2.5' のようにIDを結合
);

クエリ例
特定のカテゴリ（例: path = '1.2'）の子カテゴリをすべて取得する。

SELECT *
FROM categories_materialized_path
WHERE path LIKE '1.2.%' OR path = '1.2'; -- 自身とそのすべての子孫

PostgreSQLのltree拡張
ltreeは、具象パスモデルをPostgreSQLでより効率的に扱うための特別なデータ型と演算子を提供するモジュールです。ツリー構造のパスを表現し、専用のインデックス（GiSTインデックス）で高速な検索を可能にします。

ltreeを使用したテーブル定義例

CREATE EXTENSION IF NOT EXISTS ltree;

CREATE TABLE products_ltree (
    product_id SERIAL PRIMARY KEY,
    product_name VARCHAR(100),
    path Ltree NOT NULL -- 例: 'Electronics.Computers.Laptops'
);

ltreeを使用したクエリ例

-- 'Electronics.Computers' 以下すべての子孫を取得
SELECT *
FROM products_ltree
WHERE path ~ 'Electronics.Computers.*';

-- 特定の深さのノードを取得
SELECT *
FROM products_ltree
WHERE nlevel(path) = 3; -- 3階層目のノード

閉包テーブルモデル（Closure Table Model）

このモデルでは、元のテーブルに加えて、すべてのノード間の「到達可能性」（直接的または間接的な親子関係）を格納する別のテーブル（閉包テーブル）を作成します。閉包テーブルは、ancestor_idとdescendant_idの2つのカラムを持ち、すべてのancestor -> descendantの関係を記録します。各ノード自身も自分自身の子孫と見なされるため、(node_id, node_id)というエントリも追加します。

特徴

ユースケース
階層構造の検索が非常に頻繁で、データ更新が比較的稀な場合。非常に深い階層や複雑なグラフ構造に適しています。
欠点
データの挿入、更新、削除が最も複雑になります。新しいノードが追加されるたびに、閉包テーブルに複数の新しい関係を追加する必要があり、TRIGGERを使用することが一般的です。データ量が増える傾向があります。
利点
ほとんどの階層クエリが非常に高速です。特定のノードの子孫や先祖、あるいは2つのノード間のすべてのパスなどを、シンプルなJOIN操作で取得できます。

テーブル定義例

CREATE TABLE comments (
    comment_id SERIAL PRIMARY KEY,
    comment_text TEXT,
    parent_comment_id INTEGER REFERENCES comments(comment_id)
);

-- 閉包テーブル
CREATE TABLE comment_paths (
    ancestor_id INTEGER NOT NULL REFERENCES comments(comment_id),
    descendant_id INTEGER NOT NULL REFERENCES comments(comment_id),
    depth INTEGER NOT NULL, -- ancestorからdescendantまでの深さ
    PRIMARY KEY (ancestor_id, descendant_id)
);

クエリ例
特定のコメント（例: comment_id = 1）の子孫コメントをすべて取得する。

SELECT c.*
FROM comments c
INNER JOIN comment_paths cp ON c.comment_id = cp.descendant_id
WHERE cp.ancestor_id = 1 AND cp.depth > 0; -- 自身を除外する場合

新しいコメントが追加された際に閉包テーブルを更新するロジックは、トリガー関数やアプリケーションロジックで実装する必要があります。

ネストセットモデル（Nested Set Model）

各ノードに「左右」の境界値を割り当てることで、ツリー構造を数値の範囲として表現するモデルです。これはツリー走査アルゴリズム（Preorder Traversal）に基づいています。

特徴

ユースケース
階層構造がほとんど変更されず、サブツリーの選択が非常に頻繁に行われる場合に限定されます。
欠点
データの挿入や更新（特にツリーの中間への挿入や削除）が非常に複雑で、多くの行の左右の値を更新する必要があるため、非常にコストがかかります。
利点
サブツリー全体の取得が非常に高速です（WHERE left_val >= parent_left_val AND right_val <= parent_right_val）。

テーブル定義例

CREATE TABLE products_nested_set (
    product_id SERIAL PRIMARY KEY,
    product_name VARCHAR(100) NOT NULL,
    lft INTEGER NOT NULL, -- 左の値
    rgt INTEGER NOT NULL  -- 右の値
);

クエリ例
特定の製品（例: product_id = 1）の子孫製品をすべて取得する。

SELECT p_child.*
FROM products_nested_set p_parent
JOIN products_nested_set p_child ON p_child.lft BETWEEN p_parent.lft AND p_parent.rgt
WHERE p_parent.product_id = 1 AND p_child.product_id != 1; -- 自身を除外

モデル名	`WITH RECURSIVE`	挿入/更新の複雑さ	検索の複雑さ	検索パフォーマンス	主な利点	主な欠点
隣接リスト	必要	低	高	再帰の深さに依存	シンプルな実装、更新が容易	深い階層での検索が遅い場合がある
具象パス (`ltree`含む)	不要	中～高	低	高速	サブツリー検索が高速	更新が複雑、パス文字列の管理
閉包テーブル	不要	高	低	高速	あらゆる階層クエリが高速	実装が複雑、データ量増加、更新が最も複雑
ネストセット	不要	高	低	非常に高速	サブツリー選択が極めて高速	中間への挿入/削除が非常に複雑でコストが高い

ネストセットは特定のサブツリー検索に特化していますが、更新コストが高すぎるため、現代ではあまり推奨されません。
非常に大規模で複雑な階層、頻繁な全方向の階層クエリが必要で、データ更新が非常に稀な場合は、閉包テーブルが最適解となることがあります。ただし、実装の複雑さを受け入れる必要があります。
もし、階層構造がほとんど変更されず、頻繁にサブツリー全体の検索やパスの表示が必要な場合は、具象パス (ltreeが推奨) を検討する価値があります。
最も一般的でバランスが良いのは「隣接リスト + WITH RECURSIVE」です。 大半のユースケースで十分なパフォーマンスを発揮し、実装も比較的シンプルです。

PostgreSQLで階層構造を極める：WITH RECURSIVEと代替モデルの選び方

PostgreSQLの「WITH句：再帰クエリ」とは？

WITH RECURSIVEの基本的な構文

処理の流れ

注意点：無限ループ

PostgreSQL「WITH句：再帰クエリ」の一般的なエラーとトラブルシューティング

無限ループ（Infinite Loop）

カラムの型不一致（Column Type Mismatch）

不適切なSQL構文（Incorrect SQL Syntax）

パフォーマンス問題（Performance Issues）

RECURSIVEキーワードの忘れ

例1：組織図の階層を辿る（上下方向）

例2：ファイルシステムの階層を表現する

例3：フィボナッチ数列の生成

例4：グラフのパス探索（より高度な例）

隣接リストモデル（Adjacency List Model）

具象パスモデル（Materialized Path Model）

閉包テーブルモデル（Closure Table Model）

ネストセットモデル（Nested Set Model）

`WITH RECURSIVE`の基本的な構文