¿Cómo funciona un CTE recursivo, línea por línea?

Question

Creo que tengo el formato de Recursive CTE lo suficientemente bien como para escribir uno, pero aún así me siento frustrado al no poder procesarlo (pretender ser el motor de SQL y alcanzar el conjunto de resultados con el lápiz y papel). I've found this, que está cerca de lo que estoy buscando, pero no lo suficientemente detallado. No tengo problemas para rastrear a través de una función recursiva de C++ y entender cómo se ejecuta, pero para SQL no entiendo por qué o cómo el motor sabe para detenerse. ¿El bloque de anclaje y recursivo recibe una llamada cada vez, o se omite el anclaje en iteraciones posteriores? (Lo dudo pero estoy tratando de expresar mi confusión sobre la forma en que parece saltar). Si se llama el anclaje cada vez, ¿cómo no aparece el anclaje varias veces en el resultado final? Espero que alguien pueda hacer un desglose de la línea 1, línea 2, etc., qué sucede y qué es "en la memoria" a medida que se acumula el conjunto de resultados.

Me he tomado la libertad de robar mi example from this page, ya que parece ser la más fácil de entender.

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

Piense en un recursivo CTE como de un sinfín 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 
… 

En su caso, que sería:

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 

Desde abcd6 produce ningún resultado, esto implica una parada condición.

Teóricamente, un CTE recursivo puede ser infinito, pero prácticamente, SQL Server intenta prohibir las consultas que conducirían a conjuntos de registros infinitos.

Es posible que desee leer este artículo:

• SQL Server: are the recursive CTE’s really set-based?

Answer 2

Probablemente estabas deseando this link. No, el ancla no se ejecuta varias veces (no podría ser, entonces union all requeriría que aparezcan todos los resultados). Detalles en el enlace anterior.

Answer 3

creo que se descompone así: se ejecuta

1. La declaración de anclaje. Esto le da un conjunto de resultados, llamado conjunto base, o T0.

2. La instrucción recursiva se ejecuta, utilizando T0 como la tabla para ejecutar la consulta en contra. Esto sucede automáticamente cuando consulta un CTE.

3. Si el miembro recursivo arroja algunos resultados, crea un nuevo conjunto, T1. El miembro recursivo se ejecuta nuevamente, usando T1 como entrada, creando T2 si hay algún resultado.

4. El paso 3 continúa hasta que no se generen más resultados, O se haya alcanzado el número máximo de recursiones, como lo establece la opción MAX_RECURSION.

This page probablemente lo explique mejor. Tiene un recorrido paso a paso de la ruta de ejecución de un CTE.

Answer 4

Paso 1:

1 Europe NULL Europe 
2 Asia NULL Asia 

Paso 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 

Paso 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 

Paso 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 

Paso 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 

La última columna en el paso 5 es el nivel. Durante cada nivel, las filas se agregan con respecto a lo que ya está disponible. Espero que esto ayude.

Answer 5

El algoritmo que el uso de CTE es:

1. Ejecutar la parte de anclaje, obtener como resultado r0
2. Ejecutar la parte recursiva, utilizando r0 como entrada, y obtener el resultado r1 (no nulo)
3. Ejecute la parte recursiva, usando r1 como entrada, y obtenga el resultado r2 (no nulo)
4. Ejecutar la parte recursiva, utilizando r3 como entrada, y obtener el resultado r3 (no nulo) ...
5. Ejecutar la parte recursiva, utilizando r (n-1) como entrada, y salida rn (nulo). Esta vez rn es nula, de manera que usamos UNION ALL combinar r0, r1, r2 r ... (n-1) y ese es el resultado final

Tomemos un ejemplo:

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

El resultado de esta consulta es:

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

(4 row(s) affected) 

Vamos a examinar paso a paso:

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