SQLで学ぶ階層クエリ完全ガイド：WITH RECURSIVEとCONNECT BYでツリー構造を効率的に扱う実践技術

2025年11月20日 最終更新日時 : 2025年11月20日 エバープレイ編集部

階層クエリとは

階層クエリは、親子関係を持つデータ（ツリー構造や有向グラフ）をSQLで再帰的に辿って取得するための技術・手法を指します。組織図、カテゴリー階層、部品表（BOM）、ファイルシステムなど、実務で頻繁に現れる "階層データ" を扱う際に使われます。代表的な実装としては、Oracle の CONNECT BY、SQL:1999 以降の WITH RECURSIVE（再帰共通テーブル式、CTE）、および各データベース製品に固有の機能（SQL Server の hierarchyid や MAXRECURSION など）があります。

なぜ階層クエリが必要か

  • 親子関係の集計や表示：親ノード以下の全子孫を取得したい（例：あるカテゴリ配下の全商品）

  • 経路（パス）の取得：ルートから特定ノードまでの経路を表示したい（例：ファイルのパス表現）

  • 再帰的集計：子要素に依存する集計値を上位に集約したい（例：売上を階層単位で合算）

  • サイクル検出や深さ制限などの安全対策：無限ループ防止や深さ制限が必要

代表的な実装と文法（例）

以下に主要なデータベースでの階層クエリ例を示します。テーブルはシンプルな隣接リスト（adjacency list）形式、employees(id, name, manager_id) を想定します。

Oracle（CONNECT BY）

Oracle 独自の階層クエリ構文。LEVEL、CONNECT_BY_ROOT、SYS_CONNECT_BY_PATH、CONNECT_BY_ISLEAF 等の擬似列が使えるのが特徴。

SELECT id, name, manager_id, LEVEL AS depth,
       SYS_CONNECT_BY_PATH(name, '/') AS path,
       CONNECT_BY_ISLEAF AS is_leaf
FROM employees
START WITH manager_id IS NULL
CONNECT BY NOCYCLE PRIOR id = manager_id
ORDER SIBLINGS BY name;

POINTS：

  • START WITH：ツリーの起点（root）の条件
  • CONNECT BY PRIOR id = manager_id：親→子の接続条件（PRIORは「親側の列」を指す）
  • NOCYCLE：循環参照がある場合でもエラーにせず処理（CONNECT_BY_ISCYCLEで検査可能）
  • LEVEL：ルートを1とする深さ

PostgreSQL / MySQL / SQLite（WITH RECURSIVE）

SQL 標準の再帰CTEを使う方法。多くの RDBMS（PostgreSQL、MySQL 8.0 以降、SQLite 等）がサポートしています。

WITH RECURSIVE emp_tree AS (
  -- アンカー（ルート）
  SELECT id, name, manager_id, 1 AS depth, ARRAY[id] AS path
  FROM employees
  WHERE manager_id IS NULL
  UNION ALL
  -- 再帰部（子を結合）
  SELECT e.id, e.name, e.manager_id, t.depth + 1, t.path || e.id
  FROM employees e
  JOIN emp_tree t ON e.manager_id = t.id
  -- サイクル防止（pathに存在するidがあれば除外）
  WHERE NOT e.id = ANY(t.path)
)
SELECT * FROM emp_tree;

POINTS：

  • 任意の列（配列や文字列）でパスを保持すればサイクル検出が可能
  • 深さを明示的に持たせる必要がある（Oracle の LEVEL 相当）

SQL Server（再帰 CTE + MAXRECURSION, hierarchyid）

再帰 CTE を使った構文は SQL Server でも同様ですが、再帰回数の制限に注意が必要（デフォルト100、0で制限なし）。また専用データ型 hierarchyid を使うとツリー操作が効率的に行えます。

WITH EmpCTE AS (
  SELECT id, name, manager_id, 1 AS depth, CAST(id AS VARCHAR(MAX)) AS path
  FROM employees
  WHERE manager_id IS NULL
  UNION ALL
  SELECT e.id, e.name, e.manager_id, c.depth + 1,
         c.path + ',' + CAST(e.id AS VARCHAR(20))
  FROM employees e
  JOIN EmpCTE c ON e.manager_id = c.id
  WHERE CHARINDEX(',' + CAST(e.id AS VARCHAR(20)) + ',', ',' + c.path + ',') = 0
)
SELECT * FROM EmpCTE
OPTION (MAXRECURSION 0); -- 0 = no limit

代替モデル（階層データの設計パターン）

階層データを効率的に扱うために、隣接リスト以外のデータモデルを採ることがあります。代表的なもの：

  • 隣接リスト（Adjacency List） — 各行が parent_id を持つ最も自然な形。実装と保守は簡単だが、子孫全取得は再帰が必要でパフォーマンス課題が出る。

  • ネストセット（Nested Set） — 左右番号（lft, rgt）を振ることで単一クエリで子孫全取得が可能。読み取りが速くなるが、挿入・更新時に再計算が必要でコストが高い。

  • マテリアライズド・パス（Materialized Path） — 各行にルートからのパス文字列を持たせ、LIKE や ltree（Postgres）で検索。パス更新が必要。

  • クロージャーテーブル（Closure Table） — 祖先-子孫の全組み合わせを格納（ancestor, descendant, depth）。クエリが高速で柔軟性が高いが、挿入・削除時に多くの行更新が発生する。

実務上の注意点（パフォーマンス・安全性）

  • インデックス：親参照（parent_id）および id にインデックスを張ることは基本。クエリプランが大きく変わる。

  • 深さ制限：再帰が深くなるとスタックやリソースを圧迫するため、深さ（depth）を制限する、あるいは MAXRECURSION のような仕組みで上限を設ける。

  • サイクル（循環参照）対策：データ不整合や意図せぬループによる無限ループ防止のため、サイクル検出（path に含まれるかチェック、Oracle の NOCYCLE 等）を必ず考慮する。

  • 必要に応じたモデル選択：読み取り中心でほとんど更新しない階層ならネストセットやクロージャーが有効。頻繁に挿入・移動が発生するなら隣接リストやマテリアライズドパスを検討。

  • 大規模データの速度：再帰CTEは遅くなるケースがある。クローザーテーブルを導入する、あるいはアプリ側でキャッシュ・メモリ上のツリーを保持するアプローチも検討する。

  • トランザクションと整合性：ツリー構造保守（ノード移動・削除）時に整合性を担保する仕組み（外部キー、トリガ、トランザクション）を整える。

よくある課題と解決策

  • ノードの並び順（兄弟順）の保持：ORDER SIBLINGS BY（Oracle）やアプリ側でソートする。ネイティブに兄弟順を保持する列（position）を持つと便利。

  • パフォーマンス問題：特に深いツリーでは再帰CTEの繰り返しジョインが重い。インデックス最適化、必要な列だけ取得、あるいはクロージャーテーブルへの移行を検討する。

  • 部分ツリーの更新：大きなネストセットを使っているとノードの挿入・削除で多数の行を更新する必要がある。頻繁な更新なら別モデルを検討。

実用的な設計例（トレードオフ）

小規模〜中規模のシステムで、読み取りが多く更新は少ない場合はネストセットやクローザーテーブルが向きます。逆に、頻繁にノード移動や挿入・削除が発生する場合は隣接リスト＋再帰CTEを採用し、パフォーマンス問題が出たら特定のクエリだけクローザーテーブルで補完する（ハイブリッド）など実装の分離を行うのが現実的です。

実践チェックリスト（導入時）

  • 利用ケース：読み取り中心か更新中心かを分析する

  • クエリパターンの特定：全子孫取得、経路取得、深さ制限など主なクエリを列挙する

  • 各モデルの評価：隣接リスト／ネストセット／マテリアライズドパス／クロージャーのどれが合うか比較

  • インデックスとメンテ戦略：parent_id にインデックス、更新時のコスト試算、整合性維持方法

  • 循環検査と上限設定：NOCYCLE / サイクル検出 / MAXRECURSION などを設ける

まとめ

階層クエリはデータベースで階層構造を扱うための重要な手法です。Oracle の CONNECT BY のような専用機能や、標準の WITH RECURSIVE（再帰 CTE）を用いる方法が広く使われています。設計にあたっては、読み取り頻度・更新頻度・期待される階層の深さ・パフォーマンス要件を踏まえ、隣接リスト、ネストセット、マテリアライズドパス、クロージャーテーブルなどのモデルを比較検討することが重要です。サイクル防止や深さ制限、インデックス設計を怠ると本番でパフォーマンスや安定性の問題に直面するため、導入前に主要なクエリの実行計画を確認することをおすすめします。

参考文献

カテゴリー
IT
前の記事
高階テンソルの基礎と分解法ガイド：CP・Tucker・TTを用いた低ランク近似と実践応用New!!
2025年11月20日
次の記事
ネストセット（Nested Set）徹底解説：階層データを高速に読み取る設計と実装ガイドNew!!
2025年11月20日