Jak faktycznie działa rekurencja SQL?

W przypadku SQL z innych języków programowania struktura zapytania rekurencyjnego wygląda raczej dziwnie. Przejdź go krok po kroku, a wydaje się, że rozpada się.

Rozważ następujący prosty przykład:

CREATE TABLE #NUMS
(N BIGINT);

INSERT INTO #NUMS
VALUES (3), (5), (7);

WITH R AS
(
    SELECT N FROM #NUMS
    UNION ALL
    SELECT N*N AS N FROM R WHERE N*N < 10000000
)
SELECT N FROM R ORDER BY N;

Przejdźmy przez to.

Najpierw wykonuje się element zakotwiczający, a zestaw wyników jest umieszczany w R. Tak więc R jest inicjowany na {3, 5, 7}.

Następnie wykonanie spada poniżej wartości UNION ALL, a element rekurencyjny jest wykonywany po raz pierwszy. Wykonuje się na R (to znaczy na R, który obecnie mamy pod ręką: {3, 5, 7}). Daje to {9, 25, 49}.

Co to robi z tym nowym wynikiem? Czy dołącza {9, 25, 49} do istniejącego {3, 5, 7}, oznacza wynikowy związek R, a następnie kontynuuje rekursję z tego miejsca? Czy może redefiniuje R tak, aby był to tylko nowy wynik {9, 25, 49} i czy całe połączenie będzie później?

Żaden wybór nie ma sensu.

Jeśli R wynosi teraz {3, 5, 7, 9, 25, 49} i wykonamy następną iterację rekurencji, to skończymy z {9, 25, 49, 81, 625, 2401} i otrzymamy przegrał {3, 5, 7}.

Jeśli R ma teraz tylko {9, 25, 49}, mamy problem z błędnym etykietowaniem. R jest rozumiane jako połączenie zestawu wyników elementów zakotwiczonych i wszystkich kolejnych zestawów wyników elementów rekurencyjnych. Podczas gdy {9, 25, 49} jest tylko składnikiem R. To nie jest pełne R, które dotychczas nagromadziliśmy. Dlatego napisanie elementu rekurencyjnego jako wybranie z R nie ma sensu.

Z pewnością doceniam to, co @Max Vernon i @Michael S. szczegółowo opisali poniżej. Mianowicie, że (1) wszystkie komponenty są tworzone do limitu rekurencji lub zbioru zerowego, a następnie (2) wszystkie komponenty są łączone razem. W ten sposób rozumiem rekurencję SQL, aby faktycznie działać.

Gdybyśmy przeprojektowywali SQL, być może wymuszalibyśmy bardziej przejrzystą i wyraźną składnię, coś w tym rodzaju:

WITH R AS
(
    SELECT   N
    INTO     R[0]
    FROM     #NUMS
    UNION ALL
    SELECT   N*N AS N
    INTO     R[K+1]
    FROM     R[K]
    WHERE    N*N < 10000000
)
SELECT N FROM R ORDER BY N;

Coś jak indukcyjny dowód w matematyce.

Problem z rekurencją SQL w obecnej postaci polega na tym, że jest napisany w sposób mylący. Sposób, w jaki jest napisany, mówi, że każdy komponent jest tworzony przez wybranie z R, ale nie oznacza to pełnego R, który został (lub wydaje się, że został zbudowany) do tej pory. Oznacza tylko poprzedni komponent.

Opis BOL rekurencyjnych CTE opisuje semantykę wykonywania rekurencyjnego jako:

1. Podziel wyrażenie CTE na elementy zakotwiczone i rekurencyjne.
2. Uruchom elementy zakotwiczone, tworząc pierwsze wywołanie lub podstawowy zestaw wyników (T0).
3. Uruchom rekurencyjne elementy z Ti jako wejściem i Ti + 1 jako wyjście.
4. Powtarzaj krok 3, dopóki nie zostanie zwrócony pusty zestaw.
5. Zwraca zestaw wyników. Jest to UNIA WSZYSTKO od T0 do Tn.

Tak więc na każdym poziomie jest tylko poziom wejściowy, a nie cały zestaw wyników zgromadzony do tej pory.

Powyżej jest, jak to działa logicznie . Fizycznie rekurencyjne CTE są obecnie zawsze implementowane za pomocą zagnieżdżonych pętli i buforu stosu w SQL Server. Jest to opisane tu i tutaj i oznacza, że ​​w praktyce każdy element rekurencyjny działa tylko z wierszem nadrzędnym z poprzedniego poziomu, a nie z całego poziomu. Ale różne ograniczenia dopuszczalnej składni w rekurencyjnych CTE oznaczają, że to podejście działa.

Jeśli usuniesz ORDER BYz zapytania, wyniki zostaną uporządkowane w następujący sposób

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

Wynika to z faktu, że plan wykonania działa bardzo podobnie do poniższych C#

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: Jak wyżej, zanim pierwsze dziecko członka kotwicy 3jest przetwarzane, wszystkie informacje o jego rodzeństwie 5i 7, i ich potomkowie, zostały już odrzucone ze szpuli i nie są już dostępne.

NB2: Powyższy C # ma taką samą ogólną semantykę jak plan wykonania, ale przepływ w planie wykonania nie jest identyczny, ponieważ operatorzy pracują w trybie potokowym. To jest uproszczony przykład pokazujący istotę tego podejścia. Zobacz wcześniejsze linki, aby uzyskać więcej informacji na temat samego planu.

NB3: Sama szpula stosu jest najwyraźniej zaimplementowana jako niejednorodny indeks klastrowy z kluczową kolumną poziomu rekurencji i unikatami dodawanymi w razie potrzeby ( źródło )

To tylko (częściowo) wykształcone przypuszczenie i prawdopodobnie jest całkowicie błędne. Nawiasem mówiąc, interesujące pytanie.

T-SQL jest językiem deklaratywnym; być może rekurencyjna CTE jest tłumaczona na operację typu kursor, w której wyniki z lewej strony UNION ALL są dołączane do tabeli tymczasowej, a następnie prawa strona UNION ALL jest stosowana do wartości po lewej stronie.

Tak więc najpierw wstawiamy wynik z lewej strony UNION ALL do zestawu wyników, a następnie wstawiamy wyniki z prawej strony UNION ALL zastosowane do lewej strony i wstawiamy to do zestawu wyników. Lewa strona jest następnie zastępowana wyjściem z prawej strony, a prawa strona jest ponownie nakładana na „nową” lewą stronę. Coś takiego:

1. {3,5,7} -> zestaw wyników
2. instrukcje rekurencyjne zastosowane do {3,5,7}, czyli {9, 25, 49}. {9, 25, 49} jest dodawane do zestawu wyników i zastępuje lewą stronę UNION ALL.
3. instrukcje rekurencyjne zastosowane do {9, 25, 49}, czyli {81, 625,2401}. {81 625 401} jest dodawany do zestawu wyników i zastępuje lewą stronę UNION ALL.
4. instrukcje rekurencyjne zastosowane do {81 625 24040}, czyli {6561,390625,5764801}. {6561,390625,5764801} jest dodawany do zestawu wyników.
5. Kursor jest zakończony, ponieważ następna iteracja powoduje, że klauzula WHERE zwraca wartość false.

To zachowanie można zobaczyć w planie wykonania rekurencyjnej CTE:

Jest to krok 1 powyżej, w którym do wyniku dodawana jest lewa strona UNION ALL:

To jest prawa strona UNION ALL, w której dane wyjściowe są konkatenowane z zestawem wyników:

Dokumentacja programu SQL Server , w której wspomniane są T _i i T _{i + 1} , nie jest ani bardzo zrozumiała, ani nie jest dokładnym opisem faktycznej implementacji.

Podstawową ideą jest to, że rekurencyjna część zapytania sprawdza wszystkie poprzednie wyniki, ale tylko raz .

Przydatne może być sprawdzenie, jak implementują to inne bazy danych (aby uzyskać ten sam wynik). Dokumentacja Postgres mówi:

Ocena kwerend rekurencyjnych

1. Oceń termin nierekurencyjny. W przypadku UNION(ale nie UNION ALL) odrzuć zduplikowane wiersze. Uwzględnij wszystkie pozostałe wiersze w wyniku zapytania rekurencyjnego, a także umieść je w tymczasowej tabeli roboczej .
2. Dopóki stół roboczy nie jest pusty, powtarzaj następujące kroki:
   1. Oceń termin rekurencyjny, zastępując bieżącą zawartość tabeli roboczej odwołaniem cyklicznym. DlaUNION (ale nie UNION ALL) odrzuć zduplikowane wiersze i wiersze, które duplikują poprzedni wiersz wyników. Uwzględnij wszystkie pozostałe wiersze w wyniku zapytania rekurencyjnego, a także umieść je w tymczasowej tabeli pośredniej .
   2. Zamień zawartość stołu roboczego na zawartość stołu pośredniego, a następnie opróżnij stół pośredni.

Uwaga
Ściśle mówiąc, proces ten jest iteracją, a nie rekurencją, ale RECURSIVEterminologią wybraną przez komitet ds. Standardów SQL.

The SQLite wskazuje na nieco inną implementację, a ten algorytm z jednym wierszem na raz może być najłatwiejszy do zrozumienia:

Podstawowy algorytm obliczania zawartości tabeli rekurencyjnej jest następujący:

1. Uruchom initial-select i dodaj wyniki do kolejki.
2. Podczas gdy kolejka nie jest pusta:
   1. Wyodrębnij pojedynczy wiersz z kolejki.
   2. Wstaw ten pojedynczy wiersz do tabeli rekurencyjnej
   3. Udawaj, że właśnie wyodrębniony pojedynczy wiersz jest jedynym wierszem w tabeli rekurencyjnej i uruchom recursive-select, dodając wszystkie wyniki do kolejki.

Podstawową procedurę powyżej można zmodyfikować według następujących dodatkowych zasad:

• Jeśli operator UNION połączy się initial-selectz recursive-select, to dodaj wiersze do kolejki tylko wtedy, gdy do kolejki nie został wcześniej dodany żaden identyczny wiersz. Powtarzane wiersze są odrzucane przed dodaniem do kolejki, nawet jeśli powtarzane wiersze zostały już wyodrębnione z kolejki przez krok rekurencji. Jeśli operatorem jest UNION ALL, wówczas wszystkie wiersze generowane zarówno przez, jak initial-selecti recursive-selectsą zawsze dodawane do kolejki, nawet jeśli są powtarzane.
  […]

Moja wiedza dotyczy konkretnie DB2, ale przeglądanie diagramów wyjaśniających wydaje się być takie samo w przypadku SQL Server.

Plan pochodzi stąd:

Zobacz to w Wklej plan

Optymalizator nie dosłownie uruchamia unii dla każdego zapytania rekurencyjnego. Pobiera strukturę zapytania i przypisuje pierwszą część unii wszystkim „członkom zakotwiczenia”, a następnie przechodzi przez drugą połowę unii wszystkich (nazywanych rekurencyjnie „członem rekurencyjnym”, aż osiągnie zdefiniowane ograniczenia. rekursja jest zakończona, optymalizator łączy wszystkie rekordy razem.

Optymalizator po prostu traktuje to jako sugestię wykonania wstępnie zdefiniowanej operacji.