Как работает Recursive CTE, строка за строкой?

Question

Я думаю, что у меня достаточно хорошо отформатирован формат Рекурсивных 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 

Answer 1

Думайте о рекурсивном CTE как о бесконечном 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
…

В вашем случае это будет:

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

Так как abcd6 не даетрезультаты, это подразумевает условие остановки.

Теоретически, рекурсивный CTE может быть бесконечным, но практически SQL Server пытается запретить запросы, которые привели бы к бесконечным наборам записей.

ВыВозможно, вы захотите прочитать эту статью:

• SQL Server: действительно ли рекурсивный CTE основан на множествах?

Answer 2

Алгоритм, который использует CTE:

1. Выполнить якорную часть, получить результат r0
2. Выполнить рекурсивную часть, используя r0 в качестве входных данных, и получить результат r1 (не нуль)
3. Выполнить рекурсивную часть, используя r1 в качестве входных данных, и получить результат r2 (не нуль)
4. Выполнить рекурсивную часть, используя r3 в качестве входных данных, и получить результат r3 (не нуль) ...
5. Выполнить рекурсивную часть, используя r (n-1) в качестве ввода и вывод rn (ноль). На этот раз rn равно нулю, поэтому мы используем 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

Answer 3

Я думаю, что это ломается так:

1. Оператор привязки выполняется.Это дает вам набор результатов, называемый базовым набором, или T0.

2. Рекурсивный оператор выполняется, используя T0 в качестве таблицы для выполнения запроса.Это происходит автоматически при запросе CTE.

3. Если рекурсивный член возвращает некоторые результаты, он создает новый набор T1.Затем рекурсивный элемент выполняется снова , используя T1 в качестве входных данных, создавая T2, если есть какие-либо результаты.

4. Шаг 3 продолжается до тех пор, пока не будет получено больше результатов, ИЛИ не будет достигнуто максимальное количество рекурсий, как установлено параметром MAX_RECURSION.

Эта страница , вероятно, объясняет это лучше всего.Он имеет пошаговое руководство по пути выполнения CTE.

Answer 4

Шаг 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 - это Уровень.На каждом уровне строки добавляются относительно того, что уже доступно.Надеюсь, это поможет.

Answer 5

Возможно, вы хотели эту ссылку . Нет, привязка не выполняется несколько раз (этого не может быть, тогда union all потребует отображения всех результатов). Подробности по предыдущей ссылке.