Posted inデータベース

SQLの再帰CTE：PostgreSQLとMySQLでツリー・階層データを扱う

Database tutorial - IT technology blog
Database tutorial - IT technology blog

問題：自己参照するデータのクエリ

バックエンド開発をしていれば、必ず階層データに直面する場面があります。各行にmanager_idで別の従業員を参照する社員テーブル。parent_idで親カテゴリを持つカテゴリテーブル。返信が返信の下にネストされるコメントスレッド。フォルダツリー。部品表（BOM）などが典型例です。

よくある失敗——自分も経験があります——は、これをアプリケーションコードで処理しようとすることです。ルートを取得し、その子を取得し、さらにその子を取得する……を繰り返す。動きはします。でも、N+1クエリでデータベースを叩きまくり、階層が3レベルを超えた瞬間にメンテナンスの地獄になります。

そこで登場するのが再帰CTE（Common Table Expression）です。このパターンを身につけるのに1時間もあれば十分。一度覚えたら、毎回使いたくなるはずです。

基本概念：再帰CTEの仕組み

通常のCTEは名前付きサブクエリです——サブクエリにラベルを付けて後から参照できるようにする、SQLをよりきれいに書くための手法です。再帰CTEはさらに一歩進み、クエリが自分自身を参照できるようになります。展開するものがなくなるまで、1レベルずつ処理を広げていきます。

すべての再帰CTEは3つの要素で構成されます：

  • アンカーメンバー——起点となる行（ルートノード）を返すベースクエリ
  • 再帰メンバー——CTE自身に対してJOINし、1回のイテレーションで1レベルを追加するクエリ
  • 終了条件——暗黙的に、再帰メンバーが0行を返した時点でループが止まる

構文は次のようになります：

WITH RECURSIVE cte_name AS (
    -- アンカー：起点
    SELECT ...
    UNION ALL
    -- 再帰：CTEをソーステーブルにJOIN
    SELECT ... FROM source_table JOIN cte_name ON ...
)
SELECT * FROM cte_name;

RECURSIVEキーワードはPostgreSQLでは必須です。MySQL 8.0以降も同じ構文を使います——再帰CTEのサポートはMySQL 8.0で追加されたため、それより古いバージョンでは動作しません。MySQLとPostgreSQLの機能比較についてはこちらでも詳しく解説しています。

注意すべきポイント

データが汚染されていると循環参照が発生することがあります：AがBの親で、BがAの親、という状態です。再帰CTEはこのケースで無限ループに陥ります。PostgreSQLでは深さカウンターの列を追加して明示的に上限を設定できます。MySQLにはcte_max_recursion_depth（デフォルト：1000回）というシステムレベルの安全網があります。

実践：手を動かして学ぶ

サンプル階層のセットアップ

典型的な出発点として、manager_idで自己参照する社員テーブルを使います。このスキーマはPostgreSQLとMySQL 8.0以降で完全に同じように動作します。

CREATE TABLE employees (
    id       INT PRIMARY KEY,
    name     VARCHAR(100),
    role     VARCHAR(100),
    manager_id INT REFERENCES employees(id)
);

INSERT INTO employees VALUES
    (1, 'Alice',   'CEO',        NULL),
    (2, 'Bob',     'VP Eng',     1),
    (3, 'Carol',   'VP Sales',   1),
    (4, 'Dave',    'Lead Dev',   2),
    (5, 'Eve',     'Developer',  4),
    (6, 'Frank',   'Developer',  4),
    (7, 'Grace',   'Sales Rep',  3);

クエリ1：組織図全体をトップダウンで取得

このクエリはCEOを起点にツリー全体をたどり、すべての従業員を深さレベルとともに返します：

WITH RECURSIVE org_chart AS (
    -- アンカー：ルートノード（上司なし）
    SELECT
        id,
        name,
        role,
        manager_id,
        0 AS depth,
        name::TEXT AS path
    FROM employees
    WHERE manager_id IS NULL

    UNION ALL

    -- 再帰：各従業員を上司にJOIN
    SELECT
        e.id,
        e.name,
        e.role,
        e.manager_id,
        oc.depth + 1,
        oc.path || ' > ' || e.name
    FROM employees e
    JOIN org_chart oc ON e.manager_id = oc.id
)
SELECT
    repeat('  ', depth) || name AS indented_name,
    role,
    depth,
    path
FROM org_chart
ORDER BY path;

path列はAlice > Bob > Dave > Eveのようなパンくずリスト文字列を構築します。デバッグにも表示にも便利で、そのままUIに貼り付けるだけで使えます。

クエリ2：特定の人物の部下を全員取得

権限変更の適用やチームの人数計算のために、Bobに直属・間接を問わず報告している全員が必要な場合を考えます。

WITH RECURSIVE subordinates AS (
    -- アンカー：Bob（id = 2）を起点にする
    SELECT id, name, role, manager_id
    FROM employees
    WHERE id = 2

    UNION ALL

    SELECT e.id, e.name, e.role, e.manager_id
    FROM employees e
    JOIN subordinates s ON e.manager_id = s.id
)
SELECT * FROM subordinates;

結果：Bob、Dave、Eve、Frank。4行。アプリケーション側のループもN+1もありません。

クエリ3：ツリーを上方向にたどる（指揮系統の取得）

逆方向が必要なこともあります。Eveを起点に、CEOまでの管理系統全体を取得する——認可チェックや監査証跡の追跡に役立ちます。

WITH RECURSIVE chain_of_command AS (
    -- アンカー：Eve（id = 5）を起点にする
    SELECT id, name, role, manager_id
    FROM employees
    WHERE id = 5

    UNION ALL

    SELECT e.id, e.name, e.role, e.manager_id
    FROM employees e
    JOIN chain_of_command c ON e.id = c.manager_id
)
SELECT * FROM chain_of_command;

Eve → Dave → Bob → Aliceの順で返ります。再帰JOINが逆転していることに注目してください：子を辿る（e.manager_id = oc.id）のではなく、親を辿る（e.id = c.manager_id）ようにしています。このたった一つの逆転がすべてのコツです。

実践的なヒント：無限ループを防ぐ

データに循環参照がある可能性があれば、深さカウンターを追加して明示的に上限を設けましょう：

WITH RECURSIVE safe_tree AS (
    SELECT id, name, manager_id, 0 AS depth
    FROM employees
    WHERE manager_id IS NULL

    UNION ALL

    SELECT e.id, e.name, e.manager_id, st.depth + 1
    FROM employees e
    JOIN safe_tree st ON e.manager_id = st.id
    WHERE st.depth < 10  -- 安全上限：深さ10で停止
)
SELECT * FROM safe_tree;

実務パターン：カテゴリツリー

ECサイトのカテゴリツリーは常にこの問題に直面します。parent_idを持つcategoriesテーブルは、構造的に社員テーブルとまったく同じです。SEOパンくずリスト用のフルパス取得も、再帰CTEなら約2分で書けます：

WITH RECURSIVE category_path AS (
    SELECT id, name, parent_id, name::TEXT AS full_path
    FROM categories
    WHERE parent_id IS NULL

    UNION ALL

    SELECT c.id, c.name, c.parent_id,
           cp.full_path || ' / ' || c.name
    FROM categories c
    JOIN category_path cp ON c.parent_id = cp.id
)
SELECT id, full_path FROM category_path ORDER BY full_path;

データ準備に関する補足

CSVエクスポートからサンプルデータでこれらのクエリをプロトタイピングする際——たとえばECプラットフォームからのカテゴリエクスポートなど——テストデータベースに読み込む前にCSVをSQL INSERT文や構造化JSONに変換する必要がよく出てきます。CSV→JSONの変換にはtoolcraft.app/ja/tools/data/csv-to-jsonを使っています。完全にブラウザ上で動作するため、データが外部に送信されません——顧客情報や商品データなど、サードパーティのサービスに送りたくないエクスポートを扱うときに重宝します。

パフォーマンスのヒント

再帰CTEは大きなテーブルでコストが高くなることがあります。実務で効果があったいくつかのポイントを紹介します：

  • 外部キー列にインデックスを張る。この例ではmanager_idにインデックスが必要です。PostgreSQLは外部キーを自動的にインデックス化しません——CREATE INDEXで手動で追加します。100k行以上のテーブルでは、これだけでクエリ時間が数秒からミリ秒単位に短縮されることがあります。インデックスの仕組みと活用方法についてはこちらで詳しく解説しています。
  • CTE内では必要な列だけを選択する。再帰メンバーはレベルごとに1回実行されます。使わない幅の広いテキスト列を含めると、イテレーションのたびにそのデータを再読み込みします。CTE内では最小限の列を選択し、外部クエリで追加の列をJOINしましょう。
  • UNIONではなくUNION ALLを使う。UNIONは行の重複を排除するためソートステップが追加されます。重複排除が明示的に必要でなければ、再帰CTE内では常にUNION ALLを使いましょう。
  • EXPLAIN ANALYZEで確認する。PostgreSQLのプランナーは再帰CTEを通常のクエリほど積極的に最適化しないことがあります。ステートメント全体にEXPLAIN ANALYZEを実行して、どこに時間がかかっているかを正確に把握しましょう。実行計画の読み方を習得すると、ボトルネックの特定がより的確になります。

使いどころと使わないケース

再帰CTEが適しているのは：

  • 階層の深さが不明、または行によって異なる場合
  • ツリー全体または大部分が必要な場合
  • N+1クエリではなく、1回のデータベースラウンドトリップで済ませたい場合

設計上常に2〜3レベル固定の階層であれば、通常の自己JOINの方がシンプルです。深さが動的になった瞬間に、再帰CTEが真価を発揮します。

知っておく価値のある代替手段として、PostgreSQLのltree拡張があります。マテリアライズドパスをネイティブデータ型として保存し、高速で特化した演算子を提供します。非常に深いツリーや高頻度でクエリされるツリーでは、ltreeが再帰CTEを大幅に上回るパフォーマンスを発揮することがあります。トレードオフとして、INSERTとUPDATEのロジックが複雑になります。再帰CTEはスキーマ変更が不要なため、ほぼすべてのプロジェクトで最初の選択肢として適切です——測定可能なパフォーマンス問題が出て初めてltreeを検討しましょう。

パターンのまとめ

アンカーメンバー、再帰メンバー、終了条件。以上です。最初に書くときは違和感があるかもしれませんが、3つ目のクエリを書く頃には自然に読めるようになります。

今から身につけるべき4つの習慣：親キー・外部キー列にインデックスを張る、UNIONではなくUNION ALLを使う、完全にコントロールできないデータには深さ上限を追加する、パフォーマンスが重要なときはEXPLAIN ANALYZEを実行する。これらを押さえておけば、アプリケーション側のループなしに、ほとんどの階層データの問題を1つのSQL文で解決できるようになります。

Share:
Tags: