Skip to content

MS_RecursiveQuery

Jump to bottom
nishi_74322014 edited this page Aug 19, 2026 · 1 revision

再帰クエリ

  • 戻る（SQL）

概要

SQL は非手続き言語のため、手続き的に解り難いことが多いが、
再帰クエリはより解り難いので、再帰クエリがどういう仕組みで動くか分析してみた。

※ ココでは、DNS の再帰クエリではなく。

補足（何に使うのか）: 再帰クエリが必要になるのは、
階層構造・グラフ構造をテーブルで表現している場合である。

emp テーブル（自己参照）
 empno | ename  | mgr    ← mgr が自分の上司の empno を指す
 ------+--------+------
   1   | 社長   | NULL
   2   | 部長   |  1
   3   | 課長   |  2

この形（隣接リスト）は保存は簡単だが、
「ある人の配下を全部出す」といった問い合わせが
通常の SQL では書けない（何階層あるか分からないため）。
再帰クエリはこれを 1 本のクエリで解く。

典型的な用途は、組織図、部品表（BOM）、カテゴリ ツリー、
フォルダ階層、連続した日付の生成など。

詳細

定義

標準 SQL

標準 SQL では再帰クエリを共通表式の一環として定義している。
以下は、WITH RECURSIVE 形式の構文をサポートする RDBMS

  • Microsoft SQL Server

  • Oracle Database 11gR2

  • IBM DB2

  • PostgreSQL 8.4

  • Firebird

  • H2 Database

移行メモ（SQL Server の構文について）: 一覧に SQL Server が挙がっているが、
SQL Server は RECURSIVE キーワードを取らない（付けるとエラーになる）。
再帰かどうかは、CTE が自分自身を参照しているかで判断される。

-- SQL Server（RECURSIVE を書かない）
WITH r (level, employee, empno, mgr) AS (
    SELECT 1, ename, empno, mgr FROM emp WHERE mgr IS NULL
    UNION ALL
    SELECT r.level + 1, REPLICATE('  ', r.level) + emp.ename, emp.empno, emp.mgr
      FROM emp INNER JOIN r ON emp.mgr = r.empno
)
SELECT * FROM r;

後述の定義例は PostgreSQL のものなので、
SQL Server で試す場合は

  • WITH RECURSIVE → WITH
  • repeat(...) → REPLICATE(...)
  • 文字列連結 || → +

と読み替える必要がある。

共通表式

  • WITH 問い合わせ（共通テーブル式）
  • 次に続く全選択の FROM 文節で表として指定できる 表 ID を持つ結果表を定義する。

補足: CTE (Common Table Expression)。
「一時的に名前を付けた結果セット」で、
サブクエリを読みやすく分割するために使う。
再帰は CTE の特殊な形であり、
CTE そのものは再帰でなくても使える。

定義例

以下が、再帰クエリの定義例（PostgreSQL）

WITH RECURSIVE r(level, employee, empno, mgr) AS (
  SELECT 1, ename, empno, mgr
    FROM emp WHERE mgr IS NULL
UNION ALL
  SELECT r.level + 1, repeat('  ', r.level) || emp.ename, emp.empno, emp.mgr
    FROM emp, r WHERE emp.mgr = r.empno
)
SELECT * FROM r;

分析

ルートのクエリ

以下の部分がルートのクエリ

  SELECT 1, ename, empno, mgr
    FROM emp WHERE mgr IS NULL

ワークのレコード

以下の部分で、

WITH RECURSIVE r(level, employee, empno, mgr) AS (

下記で取得した結果セットを再帰のクエリに渡すレコードに加工

再帰のクエリ

ここで、テーブルをワークの親レコード（＝共通表式）と JOIN する。

  SELECT r.level + 1, repeat('  ', r.level) || emp.ename, emp.empno, emp.mgr
    FROM emp, r WHERE emp.mgr = r.empno

この結果セットは、再び、「再帰のロジックに渡すレコード」に加工される。

結果テーブル（共通表式）

下記を Union したものが共通表式として利用可能。

再帰の度に、再帰のクエリの結果セットが Union で積み上がっていくイメージ。

結果テーブルの SELECT

結果テーブル（共通表式）を SELECT して、射影や集計を行う。

補足（動作を順に追う）: 原文の分析は正確である。
図にすると次のようになる。

① アンカー メンバ（ルートのクエリ）を実行
   → 結果を「作業テーブル」に置く      [社長]

② 再帰メンバを実行（作業テーブルと JOIN）
   → 新しい結果を得る                  [部長]
   → 作業テーブルを新しい結果で置き換える

③ ② を、結果が 0 件になるまで繰り返す  [課長] → [なし] で停止

④ ①②で得た全結果を UNION ALL したものが CTE の中身

重要なのは「作業テーブルは前回の結果だけを持つ」点である。
累積された全体ではないため、
再帰メンバの r は直前の階層のみを指す。
これが理解できると「なぜ無限ループしないのか」も納得できる。

補足（実務上の注意）

無限ループの防止

データに循環参照があると（A の上司が B、B の上司が A など）、
再帰が終わらなくなる。SQL Server では既定で 100 回で打ち切られ、
エラーになる。上限は次で変更できる。

SELECT * FROM r
OPTION (MAXRECURSION 1000);   -- 0 を指定すると無制限（危険）

MAXRECURSION 0（無制限）は、循環データがあると
サーバを巻き込んで停止するため、原則使わない。

経路を持たせて循環を検出する

階層のパスを文字列で持ち回り、
既に通った節点なら止める、という書き方が定石。

-- path 列に経路を積む
CAST(r.path + '/' + CAST(emp.empno AS varchar(10)) AS varchar(4000)) AS path
...
WHERE r.path NOT LIKE '%/' + CAST(emp.empno AS varchar(10)) + '/%'

性能

再帰の各回で JOIN が走るため、
結合キー（この例では emp.mgr）にインデックスが無いと
階層の深さ分だけ全表走査が発生する。
大きな階層を扱う場合は必ず確認すること
（SQL Server のインデックス）。

他の階層表現

隣接リスト以外にも、入れ子集合（left/right 値を持つ）や、
SQL Server の hierarchyid 型という選択肢がある。
「読み取りが圧倒的に多く、階層の変更が稀」なら
後者の方が高速になることもある。

参考

Microsoft Learn

Tags: 移行, データアクセス

このWikiは「Open棟梁Project」,「OSSコンソーシアム 開発基盤部会」によって運営されています。

NetDevInfraWiki

マイクロソフト系技術情報 Wiki
Open 棟梁 Wiki

（未着手）

開発基盤部会 Wiki

移行管理: DONE ／ TODO

Clone this wiki locally