Como a recursão SQL realmente funciona?

A descrição BOL de CTEs recursivos descreve a semântica da execução recursiva da seguinte forma:

1. Divida a expressão CTE em membros âncora e recursivos.
2. Execute o(s) membro(s) âncora(s) criando a primeira chamada ou conjunto de resultados base (T0).
3. Execute o(s) membro(s) recursivo(s) com Ti como entrada e Ti+1 como saída.
4. Repita a etapa 3 até que um conjunto vazio seja retornado.
5. Retorne o conjunto de resultados. Esta é uma UNION ALL de T0 a Tn.

Portanto, cada nível tem como entrada apenas o nível acima e não todo o conjunto de resultados acumulado até o momento.

O acima é como ele funciona logicamente . Atualmente, as CTEs recursivas fisicamente são sempre implementadas com loops aninhados e um spool de pilha no SQL Server. Isso é descrito aqui e aqui e significa que, na prática, cada elemento recursivo está apenas trabalhando com a linha pai do nível anterior, não com o nível inteiro. Mas as várias restrições à sintaxe permitida em CTEs recursivas significam que essa abordagem funciona.

Se você remover o ORDER BYda sua consulta, os resultados serão ordenados da seguinte maneira

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

Isso ocorre porque o plano de execução funciona de maneira muito semelhante ao seguinteC#

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

public class Program
{
    private static readonly Stack<dynamic> StackSpool = new Stack<dynamic>();

    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 acima, no momento em que o primeiro filho do membro âncora 3está sendo processado, todas as informações sobre seus irmãos, 5e 7, e seus descendentes, já foram descartadas do spool e não estão mais acessíveis.

NB2: O C# acima tem a mesma semântica geral do plano de execução, mas o fluxo no plano de execução não é idêntico, pois os operadores trabalham em uma forma de execução em pipeline. Este é um exemplo simplificado para demonstrar a essência da abordagem. Consulte os links anteriores para obter mais detalhes sobre o plano em si.

NB3: O próprio spool de pilha é aparentemente implementado como um índice clusterizado não exclusivo com coluna de chave de nível de recursão e exclusivos adicionados conforme necessário ( source )

Este é apenas um palpite (semi) educado e provavelmente está completamente errado. Pergunta interessante, diga-se de passagem.

T-SQL é uma linguagem declarativa; talvez uma CTE recursiva seja traduzida em uma operação estilo cursor onde os resultados do lado esquerdo de UNION ALL são anexados em uma tabela temporária, então o lado direito de UNION ALL é aplicado aos valores no lado esquerdo.

Então, primeiro inserimos a saída do lado esquerdo do UNION ALL no conjunto de resultados, depois inserimos os resultados do lado direito do UNION ALL aplicado ao lado esquerdo e inserimos isso no conjunto de resultados. O lado esquerdo é então substituído pela saída do lado direito e o lado direito é aplicado novamente ao "novo" lado esquerdo. Algo assim:

1. {3,5,7} -> conjunto de resultados
2. declarações recursivas aplicadas a {3,5,7}, que é {9,25,49}. {9,25,49} é adicionado ao conjunto de resultados e substitui o lado esquerdo de UNION ALL.
3. instruções recursivas aplicadas a {9,25,49}, que é {81,625,2401}. {81.625.2401} é adicionado ao conjunto de resultados e substitui o lado esquerdo de UNION ALL.
4. instruções recursivas aplicadas a {81.625.2401}, que é {6561,390625,5764801}. {6561,390625,5764801} é adicionado ao conjunto de resultados.
5. O cursor está completo, pois a próxima iteração resulta na cláusula WHERE retornando false.

Você pode ver esse comportamento no plano de execução do CTE recursivo:

Este é o passo 1 acima, onde o lado esquerdo de UNION ALL é adicionado à saída:

Este é o lado direito de UNION ALL onde a saída é concatenada ao conjunto de resultados:

A documentação do SQL Server , que menciona T _i e T _i+1 , não é muito compreensível nem uma descrição precisa da implementação real.

A ideia básica é que a parte recursiva da consulta analise todos os resultados anteriores, mas apenas uma vez .

Pode ser útil ver como outros bancos de dados implementam isso (para obter o mesmo resultado). A documentação do Postgres diz:

Avaliação de consulta recursiva

1. Avalie o termo não recursivo. Para UNION(mas não UNION ALL), descarte as linhas duplicadas. Inclua todas as linhas restantes no resultado da consulta recursiva e também as coloque em uma tabela de trabalho temporária .
2. Enquanto a mesa de trabalho não estiver vazia, repita estas etapas:
   1. Avalie o termo recursivo, substituindo o conteúdo atual da tabela de trabalho pela auto-referência recursiva. Para UNION(mas não UNION ALL), descarte linhas duplicadas e linhas que dupliquem qualquer linha de resultado anterior. Inclua todas as linhas restantes no resultado da consulta recursiva e também as coloque em uma tabela intermediária temporária .
   2. Substitua o conteúdo da mesa de trabalho pelo conteúdo da mesa intermediária e esvazie a mesa intermediária.

Nota
Estritamente falando, este processo é iteração e não recursão, mas RECURSIVEé a terminologia escolhida pelo comitê de padrões SQL.

A documentação do SQLite sugere uma implementação ligeiramente diferente, e este algoritmo de uma linha por vez pode ser o mais fácil de entender:

O algoritmo básico para calcular o conteúdo da tabela recursiva é o seguinte:

1. Execute o initial-selecte adicione os resultados a uma fila.
2. Enquanto a fila não estiver vazia:
   1. Extraia uma única linha da fila.
   2. Insira essa única linha na tabela recursiva
   3. Finja que a única linha extraída é a única linha na tabela recursiva e execute o recursive-select, adicionando todos os resultados à fila.

O procedimento básico acima pode ser modificado pelas seguintes regras adicionais:

• Se um operador UNION conectar o initial-selectcom o recursive-select, apenas adicione linhas à fila se nenhuma linha idêntica tiver sido adicionada anteriormente à fila. As linhas repetidas são descartadas antes de serem adicionadas à fila, mesmo que as linhas repetidas já tenham sido extraídas da fila pela etapa de recursão. Se o operador for UNION ALL, todas as linhas geradas por the initial-selecte the recursive-selectserão sempre adicionadas à fila, mesmo que sejam repetidas.
  […]

Meu conhecimento é especificamente em DB2, mas olhando os diagramas de explicação parece ser o mesmo com o SQL Server.

O plano vem daqui:

Veja em Colar o Plano

O otimizador não executa literalmente uma união de todos para cada consulta recursiva. Ele pega a estrutura da consulta e atribui a primeira parte da união all a um "membro âncora" então ele percorrerá a segunda metade da união all (chamada de "membro recursivo" recursivamente até atingir as limitações definidas. a recursão está completa, o otimizador une todos os registros.

O otimizador apenas toma como sugestão fazer uma operação pré-definida.