Użycie WYJĄTKU w rekurencyjnym wspólnym wyrażeniu tabelowym

Dlaczego poniższe zapytanie zwraca nieskończone wiersze? Oczekiwałbym, że EXCEPTklauzula zakończy rekurencję.

with cte as (
    select *
    from (
        values(1),(2),(3),(4),(5)
    ) v (a)
)
,r as (
    select a
    from cte
    where a in (1,2,3)
    union all
    select a
    from (
        select a
        from cte
        except
        select a
        from r
    ) x
)
select a
from r

Natknąłem się na to, próbując odpowiedzieć na pytanie dotyczące przepełnienia stosu.

Zobacz odpowiedź Martina Smitha, aby uzyskać informacje o bieżącym stanie EXCEPTrekurencyjnej CTE.

Aby wyjaśnić to, co widziałeś i dlaczego:

Używam tutaj zmiennej tabeli, aby rozróżnić między wartościami zakotwiczenia a rekurencyjnym elementem (nie zmienia to semantycznej).

DECLARE @V TABLE (a INTEGER NOT NULL)
INSERT  @V (a) VALUES (1),(2)
;
WITH rCTE AS 
(
    -- Anchor
    SELECT
        v.a
    FROM @V AS v

    UNION ALL

    -- Recursive
    SELECT
        x.a
    FROM
    (
        SELECT
            v2.a
        FROM @V AS v2

        EXCEPT

        SELECT
            r.a
        FROM rCTE AS r
    ) AS x
)
SELECT
    r2.a
FROM rCTE AS r2
OPTION (MAXRECURSION 0)

Plan zapytania to:

Wykonanie rozpoczyna się w katalogu głównym planu (WYBÓR), a kontrola przechodzi w dół drzewa do buforu indeksu, konkatenacji, a następnie do skanowania tabeli najwyższego poziomu.

Pierwszy rząd ze skanowania przechodzi w górę drzewa i jest (a) przechowywany w buforze stosu i (b) zwracany do klienta. Który wiersz jest pierwszy, nie jest zdefiniowany, ale załóżmy, że dla argumentu jest to wiersz o wartości {1}. Pierwszy wiersz, który się pojawi, to {1}.

Kontrola ponownie przechodzi do skanowania tabeli (operator konkatenacji zużywa wszystkie wiersze z najbardziej zewnętrznego wejścia przed otwarciem następnego). Skanowanie emituje drugi wiersz (wartość {2}), a to ponownie przekazuje drzewo do zapisania na stosie i przekazuje do klienta. Klient otrzymał teraz sekwencję {1}, {2}.

Przyjmując konwencję, w której górna część stosu LIFO znajduje się po lewej stronie, stos zawiera teraz {2, 1}. Gdy kontrola ponownie przechodzi do skanowania tabeli, nie zgłasza więcej wierszy, a kontrola przechodzi z powrotem do operatora konkatenacji, który otwiera swoje drugie wejście (potrzebuje rzędu, aby przejść do szpuli stosu), a kontrola przechodzi do połączenia wewnętrznego po raz pierwszy.

Sprzężenie wewnętrzne wywołuje bufor zewnętrzny na zewnętrznym wejściu, który odczytuje górny wiersz ze stosu {2} i usuwa go ze stołu roboczego. Stos zawiera teraz {1}.

Po otrzymaniu rzędu na zewnętrznym wejściu, Łączenie Wewnętrzne przekazuje kontrolę w dół na swoje wewnętrzne wejście do Lewego Łącznika Pół-Pół (LASJ). To żąda rzędu z zewnętrznego wejścia, przekazując kontrolę do Sortowania. Sortowanie jest iteratorem blokującym, więc odczytuje wszystkie wiersze ze zmiennej tabeli i sortuje je rosnąco (jak to się dzieje).

Pierwszy wiersz emitowany przez Sortowanie jest zatem wartością {1}. Wewnętrzna strona LASJ zwraca bieżącą wartość elementu rekurencyjnego (wartość właśnie wyskoczyła ze stosu), czyli {2}. Wartości w LASJ to {1} i {2}, więc emitowane jest {1}, ponieważ wartości nie są zgodne.

Ten wiersz {1} przepływa w górę drzewa planu zapytań do buforu indeksu (stosu), gdzie jest dodawany do stosu, który teraz zawiera {1, 1} i jest wysyłany do klienta. Klient otrzymał teraz sekwencję {1}, {2}, {1}.

Kontrola przechodzi teraz z powrotem do konkatenacji, z powrotem w dół po wewnętrznej stronie (ostatni raz zwrócił rząd, może zrobić to ponownie), w dół poprzez połączenie wewnętrzne, do LASJ. Ponownie odczytuje dane wejściowe, uzyskując wartość {2} z sortowania.

Element rekurencyjny jest nadal {2}, więc tym razem LASJ znajduje {2} i {2}, co powoduje, że wiersz nie jest emitowany. Nie znajdując już żadnych wierszy na swoim wewnętrznym wejściu (sortowanie jest teraz poza rzędami), sterowanie przechodzi z powrotem do sprzężenia wewnętrznego.

Sprzężenie wewnętrzne odczytuje zewnętrzne dane wejściowe, co powoduje, że wartość {1} jest usuwana ze stosu {1, 1}, pozostawiając stos tylko z {1}. Proces powtarza się teraz z wartością {2} z nowego wywołania skanowania i sortowania tabeli, który przechodzi test LASJ i jest dodawany do stosu, i przechodzi do klienta, który otrzymał teraz {1}, {2}, {1}, {2} ... i ruszamy.

Moje ulubione wytłumaczenie szpuli stosowanej w rekurencyjnych planach CTE to Craig Freedman.

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.

Uwaga: powyższy jest logicznym opisem. Fizyczna kolejność operacji może być nieco inna, jak pokazano tutaj

Stosując to do CTE, oczekiwałbym nieskończonej pętli o następującym wzorze

+-----------+---------+---+---+---+
| Invocation| Results             |
+-----------+---------+---+---+---+
|         1 |       1 | 2 | 3 |   |
|         2 |       4 | 5 |   |   |
|         3 |       1 | 2 | 3 |   |
|         4 |       4 | 5 |   |   |
|         5 |       1 | 2 | 3 |   |
+-----------+---------+---+---+---+ 

Dlatego

select a
from cte
where a in (1,2,3)

to wyrażenie Anchor. To wyraźnie zwraca 1,2,3jakoT0

Następnie uruchomione zostanie wyrażenie rekurencyjne

select a
from cte
except
select a
from r

Z 1,2,3jako dane wejściowe, które dadzą wynik, 4,5a T1następnie podłączenie z powrotem do następnej rundy rekurencji powróci 1,2,3i tak dalej w nieskończoność.

Jednak tak się nie dzieje. Są to wyniki pierwszych 5 inwokacji

+-----------+---------+---+---+---+
| Invocation| Results             |
+-----------+---------+---+---+---+
|         1 |       1 | 2 | 3 |   |
|         2 |       1 | 2 | 4 | 5 |
|         3 |       1 | 2 | 3 | 4 |
|         4 |       1 | 2 | 3 | 5 |
|         5 |       1 | 2 | 3 | 4 |
+-----------+---------+---+---+---+

Z użycia OPTION (MAXRECURSION 1)i regulacji w górę w przyrostach 1można zauważyć, że wchodzi on w cykl, w którym każdy kolejny poziom będzie ciągle przełączał się między wyjściem 1,2,3,4a 1,2,3,5.

Jak omówiono przez @Quassnoi w tym poście na blogu . Wzór obserwowanych wyników wygląda tak, jakby każde wywołanie odbywało się (1),(2),(3),(4),(5) EXCEPT (X)tam, gdzie Xjest ostatni wiersz z poprzedniego wywołania.

Edycja: Po przeczytaniu doskonałej odpowiedzi SQL Kiwi jasne jest, dlaczego tak się dzieje, i że nie jest to cała historia, ponieważ na stosie wciąż jest mnóstwo rzeczy, których nigdy nie można przetworzyć.

Anchor Emituje 1,2,3do zawartości stosu klienta3,2,1

3 odpadły stos, zawartość stosu 2,1

LASJ zwraca 1,2,4,5zawartość stosu5,4,2,1,2,1

5 wysuniętych stosów, zawartość stosu 4,2,1,2,1

LASJ zwraca 1,2,3,4 zawartość stosu4,3,2,1,5,4,2,1,2,1

4 odpadły stos, zawartość stosu 3,2,1,5,4,2,1,2,1

LASJ zwraca 1,2,3,5 zawartość stosu5,3,2,1,3,2,1,5,4,2,1,2,1

5 wysuniętych stosów, zawartość stosu 3,2,1,3,2,1,5,4,2,1,2,1

LASJ zwraca 1,2,3,4 zawartość stosu 4,3,2,1,3,2,1,3,2,1,5,4,2,1,2,1

Jeśli spróbujesz zastąpić element rekurencyjny logicznie równoważnym wyrażeniem (przy braku duplikatów / wartości NULL)

select a
from (
    select a
    from cte
    where a not in 
    (select a
    from r)
) x

Jest to niedozwolone i powoduje błąd „Odwołania rekurencyjne nie są dozwolone w podkwerendach”. więc być może jest to niedopatrzenie, które EXCEPTw tym przypadku jest dozwolone.

Dodanie: Firma Microsoft odpowiedziała teraz na moją opinię związaną z Connect jak poniżej

Zgadnięcie Jacka jest poprawne: powinien to być błąd składniowy; rekurencyjne odniesienia nie powinny być dozwolone w EXCEPTklauzulach. Ten błąd chcemy rozwiązać w nadchodzącym wydaniu usługi. Tymczasem proponuję unikać rekurencyjnych odniesień w EXCEPT klauzulach.

Ograniczając rekurencję EXCEPTpostępujemy zgodnie ze standardem ANSI SQL, który obejmuje to ograniczenie od czasu wprowadzenia rekurencji (wydaje mi się, że w 1999 r.). Nie ma powszechnej zgody co do semantyki rekurencji EXCEPT(zwanej także „niestratyfikowaną negacją”) w deklaratywnych językach, takich jak SQL. Ponadto notorycznie trudne (jeśli nie niemożliwe) jest wydajne wdrożenie takiej semantyki (w przypadku baz danych o rozsądnych rozmiarach) w systemie RDBMS.

I wygląda na to, że ostateczna implementacja została wykonana w 2014 roku dla baz danych o poziomie zgodności 120 lub wyższym .

Odwołania rekurencyjne w klauzuli EXCEPT generują błąd zgodny ze standardem ANSI SQL.