¿Cómo funciona realmente la recursividad SQL?

Luego de de una extensa selección de información resolvimos esta duda que presentan ciertos usuarios. Te compartimos la solución y deseamos que sea de mucha ayuda.

Solución:

La descripción BOL de las CTE recursivas describe la semántica de la ejecución recursiva como sigue:

1. Divida la expresión CTE en miembros ancla y recursivos.
2. Ejecute los miembros de anclaje creando la primera invocación o conjunto de resultados base (T0).
3. Ejecute los miembros recursivos con Ti como entrada y Ti + 1 como salida.
4. Repita el paso 3 hasta que se devuelva un juego vacío.
5. Devuelve el conjunto de resultados. Esta es una UNIÓN TODOS de T0 a Tn.

Por lo tanto, cada nivel solo tiene como entrada el nivel superior, no todo el conjunto de resultados acumulado hasta ahora.

Lo anterior es como funciona lógicamente. Actualmente, los CTE físicamente recursivos siempre se implementan con bucles anidados y un spool de pila en SQL Server. Esto se describe aquí y aquí y significa que en la práctica cada elemento recursivo está trabajando con el padre hilera del nivel anterior, no del nivel completo. Pero las diversas restricciones sobre la sintaxis permitida en CTE recursivas significan que este enfoque funciona.

Si quita el ORDER BY a partir de su consulta, los resultados se ordenan de la siguiente manera

+---------+
|    N    |
+---------+
|       3 |
|       5 |
|       7 |
|      49 |
|    2401 |
| 5764801 |
|      25 |
|     625 |
|  390625 |
|       9 |
|      81 |
|    6561 |
+---------+

Esto se debe a que el plan de ejecución opera de manera muy similar al siguiente C#

using System;
using System.Collections.Generic;
using System.Diagnostics;

public class Program

    private static readonly Stack StackSpool = new Stack();

    private static void Main(string[] args)
    
        //temp table #NUMS
        var nums = new[]  3, 5, 7 ;

        //Anchor member
        foreach (var number in nums)
            AddToStackSpoolAndEmit(number, 0);

        //Recursive part
        ProcessStackSpool();

        Console.WriteLine("Finished");
        Console.ReadLine();
    

    private static void AddToStackSpoolAndEmit(long number, int recursionLevel)
    
        StackSpool.Push(new  N = number, RecursionLevel = recursionLevel );
        Console.WriteLine(number);
    

    private static void ProcessStackSpool()
    
        //recursion base case
        if (StackSpool.Count == 0)
            return;

        var row = StackSpool.Pop();

        int thisLevel = row.RecursionLevel + 1;
        long thisN = row.N * row.N;

        Debug.Assert(thisLevel <= 100, "max recursion level exceeded");

        if (thisN < 10000000)
            AddToStackSpoolAndEmit(thisN, thisLevel);

        ProcessStackSpool();
    

NB1: Como arriba, cuando el primer hijo del miembro ancla 3 está siendo procesada toda la información sobre sus hermanos, 5 y 7, y sus descendientes, ya se ha descartado del carrete y ya no es accesible.

NB2: El C # anterior tiene la misma semántica general que el plan de ejecución, pero el flujo en el plan de ejecución no es idéntico, ya que allí los operadores trabajan en forma de ejecución canalizada. Este es un ejemplo simplificado para demostrar la esencia del enfoque. Consulte los enlaces anteriores para obtener más detalles sobre el plan en sí.

NB3: El spool de pila en sí aparentemente se implementa como un índice agrupado no único con key columna de nivel de recursividad y exclusivos agregados según sea necesario (fuente)

Esta es solo una suposición (semi) educada, y probablemente sea completamente incorrecta. Interesante pregunta, por cierto.

T-SQL es un lenguaje declarativo; quizás un CTE recursivo se traduce en una operación de estilo de cursor donde los resultados del lado izquierdo de UNION ALL se agregan a una tabla temporal, luego el lado derecho de UNION ALL se aplica a los valores en el lado izquierdo.

Entonces, primero insertamos la salida del lado izquierdo de UNION ALL en el conjunto de resultados, luego insertamos los resultados del lado derecho de UNION ALL aplicado al lado izquierdo, y lo insertamos en el conjunto de resultados. El lado izquierdo luego se reemplaza con la salida del lado derecho, y el lado derecho se aplica nuevamente al "nuevo" lado izquierdo. Algo como esto:

1. 3,5,7 -> conjunto de resultados
2. declaraciones recursivas aplicadas a 3,5,7, que es 9,25,49. 9,25,49 se agrega al conjunto de resultados y reemplaza el lado izquierdo de UNION ALL.
3. declaraciones recursivas aplicadas a 9,25,49, que es 81,625,2401. 81,625,2401 se agrega al conjunto de resultados y reemplaza el lado izquierdo de UNION ALL.
4. declaraciones recursivas aplicadas a 81,625,2401, que es 6561,390625,5764801. Se agrega 6561,390625,5764801 al conjunto de resultados.
5. El cursor está completo, ya que la siguiente iteración da como resultado la devolución de la cláusula WHERE false.

Puede ver este comportamiento en el plan de ejecución para el CTE recursivo:

Este es el paso 1 anterior, donde el lado izquierdo de UNION ALL se agrega a la salida:

Este es el lado derecho de UNION ALL donde la salida se concatena al conjunto de resultados:

La documentación de SQL Server, que menciona T_I y T_{yo + 1}, no es muy comprensible ni una descripción precisa de la implementación real.

La idea básica es que la parte recursiva de la consulta analiza todos los resultados anteriores, pero sólo una vez.

Puede ser útil ver cómo implementan esto otras bases de datos (para obtener el mismo resultado). La documentación de Postgres dice:

Evaluación de consultas recursivas

1. Evalúe el término no recursivo. Para UNION (pero no UNION ALL), descarte filas duplicadas. Incluya todas las filas restantes en el resultado de la consulta recursiva y colóquelas también en un mesa de trabajo.
2. Siempre que la mesa de trabajo no esté vacía, repita estos pasos:
   1. Evalúe el término recursivo, sustituyendo el contenido actual de la tabla de trabajo por la autorreferencia recursiva. Para UNION (pero no UNION ALL), descarte las filas duplicadas y las filas que duplican cualquier fila de resultados anterior. Incluya todas las filas restantes en el resultado de la consulta recursiva y colóquelas también en un mesa intermedia.
   2. Reemplace el contenido de la mesa de trabajo con el contenido de la mesa intermedia, luego vacíe la mesa intermedia.

Nota

Estrictamente hablando, este proceso es iteración, no recursividad, sino RECURSIVE es la terminología elegida por el comité de estándares SQL.

La documentación de SQLite sugiere una implementación ligeramente diferente, y este algoritmo de una fila a la vez podría ser el más fácil de entender:

El algoritmo básico para calcular el contenido de la tabla recursiva es el siguiente:

1. Ejecutar el selección inicial y agregue los resultados a una cola.
2. Mientras la cola no esté vacía:
   1. Extraiga una sola fila de la cola.
   2. Inserte esa única fila en la tabla recursiva
   3. Suponga que la única fila que acaba de extraer es la única fila de la tabla recursiva y ejecute el selección recursiva, agregando todos los resultados a la cola.

El procedimiento básico anterior puede ser modificado por las siguientes reglas adicionales:

• Si un operador UNION conecta el selección inicial con el selección recursiva, luego solo agregue filas a la cola si no se ha agregado previamente una fila idéntica a la cola. Las filas repetidas se descartan antes de agregarse a la cola, incluso si las filas repetidas ya se han extraído de la cola mediante el paso de recursividad. Si el operador es UNION ALL, entonces todas las filas generadas por ambos selección inicial y el selección recursiva siempre se agregan a la cola, incluso si son repeticiones.
  […]

Te mostramos las reseñas y valoraciones de los usuarios

Al final de todo puedes encontrar las referencias de otros usuarios, tú asimismo tienes el poder insertar el tuyo si te apetece.

---

---

Utiliza Nuestro Buscador