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.
źródło
Odpowiedzi:
Opis BOL rekurencyjnych CTE opisuje semantykę wykonywania rekurencyjnego jako:
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 BY
z zapytania, wyniki zostaną uporządkowane w następujący sposóbWynika to z faktu, że plan wykonania działa bardzo podobnie do poniższych
C#
NB1: Jak wyżej, zanim pierwsze dziecko członka kotwicy
3
jest przetwarzane, wszystkie informacje o jego rodzeństwie5
i7
, 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 )
źródło
IterateToDepthFirst
-Iterate(seed,rcsv)->PhysIterate(seed,rcsv)
. Po prostu dla ciebie. Doskonała odpowiedź.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:
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:
źródło
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:
The SQLite wskazuje na nieco inną implementację, a ten algorytm z jednym wierszem na raz może być najłatwiejszy do zrozumienia:
źródło
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.
źródło