it-swarm-eu.dev

Použití EXCEPT v rekurzivním běžném tabulkovém výrazu

Proč následující dotaz vrací nekonečné řádky? Očekával bych, že doložka EXCEPT ukončí rekurzi.

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

Narazil jsem na to, když jsem se snažil odpovědět na otázku otázka na Stack Overflow.

sql-serversql-server-2008execution-planrecursiveexcept
33
Tom Hunter

Viz odpověď Martina Smitha pro informace o aktuálním stavu EXCEPT v rekurzivním CTE.

Vysvětlit, co jste viděli a proč:

Zde používám proměnnou tabulky, abych lépe rozlišil mezi hodnotami ukotvení a rekurzivními položkami (nemění sémantiku).

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)

Plán dotazů je:

Recursive CTE Plan

Provedení začíná v kořenovém adresáři plánu (VYBRAT) a ovládací prvek předává strom do zařazování indexů, zřetězení a poté do nejvyšší úrovně tabulky.

První řádek ze skenování prochází stromem a je (a) uložen v zásobníku cívky a (b) vrácen klientovi. Který řádek je první není definován, ale předpokládejme, že je to řádek s hodnotou {1}, kvůli argumentaci. První řádek, který se má zobrazit, je proto {1}.

Řízení znovu přejde dolů ke skenování tabulky (operátor zřetězení spotřebuje všechny řádky ze svého nejvzdálenějšího vstupu před otevřením dalšího). Skenování vyšle druhý řádek (hodnota {2}), a to opět předá strom, který se má uložit do zásobníku a vydat klientovi. Klient nyní obdržel sekvenci {1}, {2}.

Přijetí konvence, kde horní část zásobníku LIFO je vlevo, obsahuje nyní nyní {2, 1}). Jakmile ovládací prvek znovu přejde do skenování tabulky, nehlásí žádné další řádky a ovládací prvek přejde zpět na operátor zřetězení, který otevře svůj druhý vstup (potřebuje řádek, aby prošel do zásobníku cívky), a ovládací prvek poprvé přejde do vnitřního spojení.

Vnitřní spojení zavolá tabulku zařazování na svůj vnější vstup, který přečte horní řádek ze zásobníku {2} a odstraní jej z pracovní tabulky. Zásobník nyní obsahuje {1}.

Poté, co obdržel řádek na svém vnějším vstupu, vstupy vnitřního spojení řídí jeho vnitřní vstup do levého anti-polospojení (LASJ). To vyžaduje řádek od jeho vnějšího vstupu, předávající ovládání třídění. Třídění je blokující iterátor, takže čte všechny řádky z proměnné tabulky a třídí je vzestupně (jak se to stane).

První řádek vyzařovaný tříděním je proto hodnota {1}. Vnitřní strana LASJ vrací aktuální hodnotu rekurzivního člena (hodnota právě vyskočená ze zásobníku), která je {2}. Hodnoty na LASJ jsou {1} a {2}, takže se vysílá {1}, protože hodnoty se neshodují.

Tento řádek {1} protéká stromem plánu dotazů nahoru do zařazovací oblasti indexu (zásobníku), kde je přidán do zásobníku, který nyní obsahuje {1, 1}, a vyslán klientovi. Klient nyní obdržel sekvenci {1}, {2}, {1}.

Ovládání nyní přechází zpět do zřetězení, zpět dolů z vnitřní strany (naposledy se vrátil řádek, může to udělat znovu), dolů přes vnitřní spojení do LASJ. Znovu načte svůj vnitřní vstup a získá hodnotu {2} z řazení.

Rekurzivní člen je stále {2}, takže tentokrát LASJ najde {2} a {2}, což má za následek, že nebude vydán žádný řádek. Pokud na svém vnitřním vstupu nebudou žádné další řádky (řazení je nyní mimo řádky), ovládací prvek přejde zpět k vnitřnímu spojení.

Vnitřní spojení čte svůj vnější vstup, což má za následek, že hodnota {1} je vyskočena ze zásobníku {1, 1}, přičemž zásobník zůstane pouze {1}. Proces se nyní opakuje s hodnotou {2} z nového vyvolání tabulky Scan and Sort, která prošla testem LASJ a byla přidána do zásobníku, a předána klientovi, který nyní obdržel {1}, {2}, {1}, {2} ... a jdeme.

Moje nejoblíbenější vysvětlení z cívky zásobníku používané v rekurzivních plánech CTE je Craig Freedman.

26
Paul White 9

BOL popis rekurzivních CTE popisuje sémantiku rekurzivního provádění následovně:

  1. Rozdělte výraz CTE na kotvící a rekurzivní členy.
  2. Spusťte kotevní členy a vytvořte první vyvolání nebo základní sadu výsledků (T0).
  3. Spusťte rekurzivní člen (y) s Ti jako vstup a Ti + 1 jako výstup.
  4. Opakujte krok 3, dokud se nevrátí prázdná sada.
  5. Vraťte sadu výsledků. Toto je UNIE VŠECH T0 až Tn.

Všimněte si, že výše je logický popis. Fyzické pořadí operací se může poněkud lišit, jak je znázorněno zde

Při použití tohoto na váš CTE bych očekával nekonečnou smyčku s následujícím vzorcem

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

Protože

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

je Anchor výraz. To jasně vrátí 1,2,3 Jako T0

Poté běží rekurzivní výraz

select a
from cte
except
select a
from r

S 1,2,3 Jako vstupem, který vyprodukuje výstup 4,5 Jako T1, Připojením, které se vrátí pro další kolo rekurze, se vrátí 1,2,3 Atd. na dobu neurčitou.

To se však ve skutečnosti nestane. Toto jsou výsledky prvních 5 vyvolání

+-----------+---------+---+---+---+
| 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 použití funkce OPTION (MAXRECURSION 1) a úpravy směrem nahoru v krocích po 1 Je vidět, že vstupuje do cyklu, kde se každá následující úroveň bude neustále přepínat mezi výstupem 1,2,3,4 A 1,2,3,5.

Jak diskutoval @ Quassnoi v tento blogový příspěvek . Vzor pozorovaných výsledků je, jako by každé vyvolání dělalo (1),(2),(3),(4),(5) EXCEPT (X), Kde X je poslední řádek z předchozího vyvolání.

Edit: Po přečtení vynikající odpověď SQL Kiwi je jasné, proč k tomu dochází a že to není celý příběh v tom Na zásobníku stále zbývá spousta věcí, které se nikdy nemohou zpracovat.

Anchor Emits 1,2,3 Do klientského zásobníku Obsah 3,2,1

3 vyskočený zásobník, obsah zásobníku 2,1

LASJ vrátí 1,2,4,5, Obsah zásobníku 5,4,2,1,2,1

5 vyskočený zásobník, obsah zásobníku 4,2,1,2,1

LASJ vrátí 1,2,3,4 Obsah zásobníku 4,3,2,1,5,4,2,1,2,1

4 vyskočený zásobník, obsah zásobníku 3,2,1,5,4,2,1,2,1

LASJ vrátí 1,2,3,5 Obsah zásobníku 5,3,2,1,3,2,1,5,4,2,1,2,1

5 vyskočený zásobník, obsah zásobníku 3,2,1,3,2,1,5,4,2,1,2,1

LASJ vrátí 1,2,3,4 Obsah zásobníku 4,3,2,1,3,2,1,3,2,1,5,4,2,1,2,1

Pokud se pokusíte nahradit rekurzivního člena logicky ekvivalentním (v případě absence duplikátů/NULL) výrazu

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

To není povoleno a zvyšuje se chyba „Rekurzivní odkazy nejsou povoleny v poddotazech.“ takže snad je to dohled, že v tomto případě je EXCEPT dokonce povolen.

Navíc: Microsoft nyní odpověděl na můj Connect Feedback , jak je uvedeno níže

Jack odhad je správný: měla to být chyba syntaxe; rekurzivní odkazy by neměly být povoleny v klauzulích EXCEPT. Tuto chybu plánujeme řešit v nadcházejícím vydání služby. Mezitím bych doporučil vyhnout se rekurzivním odkazům v klauzulích EXCEPT.

Při omezování rekurze nad EXCEPT se řídíme standardem ANSI SQL, který toto omezení zahrnoval od doby, kdy byla rekurze zavedena (v roce 1999 věřím). V deklarativních jazycích, jako je SQL, neexistuje žádná všeobecná shoda o tom, jaká by měla být sémantika pro rekurzi nad EXCEPT (také nazývaná „unstratified negation“). Navíc je notoricky obtížné (ne-li nemožné) účinně implementovat takovou sémantiku (pro databáze přiměřeně velké velikosti) v systému RDBMS.

A vypadá to, že případná implementace byla provedena v roce 2014 pro databáze s úrovní kompatibility 120 nebo vyšší .

Rekurzivní odkazy v klauzuli EXCEPT generují chybu v souladu se standardem ANSI SQL.

31
Martin Smith