46

再帰的 CTE の形式を十分に理解して記述できるようになったと思いますが、手動で処理できないことに不満を感じています (SQL エンジンのふりをして、ペンと紙で結果セットに到達します)。 . 私はこれを見つけました、これは私が探しているものに近いですが、十分に詳細ではありません. C++ の再帰関数をトレースして、それがどのように実行されるかを理解するのに問題はありませんが、SQL の場合、エンジンが停止する理由や方法がわかりません。アンカーと再帰ブロックは毎回呼び出されますか、それともアンカーは後の反復でスキップされますか? (私はそれを疑いますが、私はそれが飛び回るように見える方法についての私の混乱を表現しようとしています.) アンカーが毎回呼び出される場合、アンカーが最終結果に複数回表示されないのはなぜですか? 結果セットが蓄積されると、何が起こり、何が「メモリ内」にあるかを、誰かが1行目、2行目などの内訳を実行できることを願っています。

このページが最も理解しやすいと思われるため、自由にこのページから例を盗み出しました。

DECLARE @tbl TABLE ( 
      Id INT 
    , [Name] VARCHAR(20) 
    , ParentId INT 
) 

INSERT INTO @tbl( Id, Name, ParentId ) 
VALUES 
     (1, 'Europe', NULL) 
    ,(2, 'Asia',   NULL) 
    ,(3, 'Germany',   1) 
    ,(4, 'UK',        1) 
    ,(5, 'China',     2) 
    ,(6, 'India',     2) 
    ,(7, 'Scotland',  4) 
    ,(8, 'Edinburgh', 7) 
    ,(9, 'Leith',     8)  
; 

WITH abcd 
    AS ( 
        -- anchor 
        SELECT  id, Name, ParentID, 
                CAST(Name AS VARCHAR(1000)) AS Path 
        FROM    @tbl 
        WHERE   ParentId IS NULL 
        UNION ALL 
          --recursive member 
        SELECT  t.id, t.Name, t.ParentID, 
                CAST((a.path + '/' + t.Name) AS VARCHAR(1000)) AS "Path"
        FROM    @tbl AS t 
                JOIN abcd AS a 
                  ON t.ParentId = a.id 
       )
SELECT * FROM abcd
4

5 に答える 5

43

Think of a recursive CTE as of an endless UNION ALL:

WITH    rows AS
        (
        SELECT  *
        FROM    mytable
        WHERE   anchor_condition
        ),
        rows2 AS
        (
        SELECT  *
        FROM    set_operation(mytable, rows)
        ),
        rows3 AS
        (
        SELECT  *
        FROM    set_operation(mytable, rows2)
        ),
        …
SELECT  *
FROM    rows
UNION ALL
SELECT  *
FROM    rows2
UNION ALL
SELECT  *
FROM    rows3
UNION ALL
…

In your case, that would be:

WITH    abcd1 AS
        ( 
        SELECT  *
        FROM    @tbl t
        WHERE   ParentId IS NULL 
        ),
        abcd2 AS
        ( 
        SELECT  t.*
        FROM    abcd1
        JOIN    @tbl t
        ON      t.ParentID = abcd1.id
        ),
        abcd3 AS
        ( 
        SELECT  t.*
        FROM    abcd2
        JOIN    @tbl t
        ON      t.ParentID = abcd2.id
        ),
        abcd4 AS
        ( 
        SELECT  t.*
        FROM    abcd3
        JOIN    @tbl t
        ON      t.ParentID = abcd3.id
        ),
        abcd5 AS
        ( 
        SELECT  t.*
        FROM    abcd4
        JOIN    @tbl t
        ON      t.ParentID = abcd4.id
        ),
        abcd6 AS
        ( 
        SELECT  t.*
        FROM    abcd5
        JOIN    @tbl t
        ON      t.ParentID = abcd5.id
        )
SELECT  *
FROM    abcd1
UNION ALL
SELECT  *
FROM    abcd2
UNION ALL
SELECT  *
FROM    abcd3
UNION ALL
SELECT  *
FROM    abcd4
UNION ALL
SELECT  *
FROM    abcd5
UNION ALL
SELECT  *
FROM    abcd6

Since abcd6 yields no results, this implies a stopping condition.

Theoretically, a recursive CTE can be infinite, but practically, SQL Server tries to forbid the queries that would lead to infinite recordsets.

You may want to read this article:

于 2010-07-06T15:53:02.237 に答える
40

CTE が使用するアルゴリズムは次のとおりです。

  1. アンカー部分を実行し、結果r0を取得
  2. r0を入力として再帰部分を実行し、結果r1 (not null)を取得します。
  3. r1を入力として再帰部分を実行し、結果r2 (not null)を取得します。
  4. r3を入力として再帰部分を実行し、結果r3 (not null) を取得します ...
  5. r(n-1)を入力として再帰部分を実行し、rn (null) を出力します。今回はrnが null なので、UNION ALLを使用してr0、r1、r2 ... r(n-1)を結合し、それが最終結果です

例を見てみましょう：

WITH    cte ( value )
          AS (
               SELECT   1
               UNION ALL
               SELECT   value + 1
               FROM     cte
               WHERE    value < 4
             )
    SELECT  *
    FROM    cte

このクエリの結果は次のとおりです。

value
-----------
1
2
3
4

(4 row(s) affected)

順を追って調べてみましょう。

Execute anchor query (SELECT 1), we got:
  r0 = 1
  cte = r0 = 1

    |
    |
    V

Now we execute
SELECT value + 1 FROM cte WHERE value < 4
Since cte is r0 (only has 1), we got:
  r1 = 2
  cte = r1 = 2

    |
    |
    V

Now we execute
SELECT value + 1 FROM cte WHERE value < 4
Since cte is r1 (only has 2), we got:
  r2 = 3
  cte = r2 = 3

    |
    |
    V

Now we execute
SELECT value + 1 FROM cte WHERE value < 4
Since cte is r2 (only has 3), we got:
  r3 = 4
  cte = r3 = 4

    |
    |
    V

Now we execute
SELECT value + 1 FROM cte WHERE value < 4
Since cte is r3 (only has 4), we got:
  r4 = NULL (because r3 (4) is equal to 4, not less than 4)
Now we stop the recursion!

    |
    |
    V

Let's calculate the final result:
R = r0 union all
    r1 union all
    r2 union all
    r3 union all
  = 1 union all
    2 union all
    3 union all
    4 union all
  = 1
    2
    3
    4
于 2010-07-06T16:19:36.930 に答える
8

次のように分解できると思います。

  1. アンカー ステートメントが実行されます。これにより、基本セットまたは T0 と呼ばれる一連の結果が得られます。

  2. クエリを実行するテーブルとして T0 を使用して、再帰ステートメントが実行されます。これは、CTE を照会すると自動的に行われます。

  3. 再帰メンバーが何らかの結果を返す場合、新しいセット T1 が作成されます。その後、再帰メンバーが再度実行され、T1 を入力として使用し、結果があれば T2 を作成します。

  4. ステップ 3 は、結果が生成されなくなるまで、または MAX_RECURSION オプションで設定された再帰の最大数に達するまで続行されます。

このページがおそらく最もよく説明されています。CTE の実行パスの段階的なウォークスルーがあります。

于 2010-07-06T15:58:52.497 に答える
1

ステップ1：

1 Europe NULL Europe
2 Asia   NULL Asia

ステップ2：

1 Europe  NULL Europe
2 Asia    NULL Asia
3 Germany 1    Europe/Germany
4 UK      1    Europe/UK
5 China   2    Asia/China
6 India   2    Asia/India

ステップ3：

1 Europe   NULL Europe
2 Asia     NULL Asia
3 Germany  1    Europe/Germany
4 UK       1    Europe/UK
5 China    2    Asia/China
6 India    2    Asia/India
7 Scotland 4    Europe/UK/Scotland

ステップ4：

1 Europe    NULL Europe
2 Asia      NULL Asia
3 Germany   1    Europe/Germany
4 UK        1    Europe/UK
5 China     2    Asia/China
6 India     2    Asia/India
7 Scotland  4    Europe/UK/Scotland
8 Edinburgh 7    Europe/UK/Scotland/Edinburgh

ステップ5：

1 Europe    NULL Europe                             0
2 Asia      NULL Asia                               0
3 Germany   1    Europe/Germany                     1
4 UK        1    Europe/UK                          1
5 China     2    Asia/China                         1
6 India     2    Asia/India                         1
7 Scotland  4    Europe/UK/Scotland                 2
8 Edinburgh 7    Europe/UK/Scotland/Edinburgh       3
9 Leith     8    Europe/UK/Scotland/Edinburgh/Leith 4

手順5の最後の列はレベルです。各レベルで、すでに使用可能な行に関して行が追加されます。お役に立てれば。

于 2010-07-06T16:03:40.380 に答える
1

You were probably wanting this link. No, the anchor is not executed multiple times (it couldn't be, then union all would require that all of the results appear). Details at previous link.

于 2010-07-06T15:53:42.760 に答える