recursiva - consultas jerarquicas postgresql

¿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 de que no puedo procesar uno manualmente (pretendo ser el motor de SQL y llegar al conjunto de resultados con lápiz y papel) . Encontré esto , 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 memoria" a medida que se acumula el conjunto de resultados.

Me tomé la libertad de robar mi ejemplo de esta página , ya que parece ser el 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

Creo que se descompone así:

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

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

3. Si el miembro recursivo devuelve algunos resultados, crea un nuevo conjunto, T1. El miembro recursivo se ejecuta de nuevo , 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, tal como lo establece la opción MAX_RECURSION.

Esta página probablemente lo explica mejor. Tiene un recorrido paso a paso de la ruta de ejecución de un CTE.

Answer 2

El algoritmo que usa CTE es:

1. Ejecute la parte de anclaje, obtenga el resultado r0
2. Ejecute la parte recursiva, usando r0 como entrada, y obtenga el resultado r1 (no nulo)
3. Ejecute la parte recursiva, usando r1 como entrada, y obtenga el resultado r2 (no nulo)
4. Ejecute la parte recursiva, usando r3 como entrada, y obtenga el resultado r3 (no nulo) ...
5. Ejecute la parte recursiva, usando r (n-1) como entrada y salida rn (nulo). Esta vez rn es nula, entonces usamos UNION ALL para 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)

Examinemos 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

Answer 3

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

Etapa 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 4

Piense en un CTE recursivo como un UNION ALL interminable:

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 tu caso, eso 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

Como abcd6 no produce resultados, esto implica una condición de detenció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: ¿son los CTE recursivos realmente basados ​​en conjuntos?

Answer 5

Probablemente querías este enlace . No, el anclaje no se ejecuta varias veces (no podría ser así, entonces, la union all requeriría que aparezcan todos los resultados). Detalles en el enlace anterior.