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.