Verwenden Sie außer in einer rekursiven gemeinsamen Tabellenexpression

Question

Warum gibt die folgende Abfrage unendliche Zeilen zurück? Ich hätte das erwartet EXCEPT Klausel zur Beendigung der Rekursion ..

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

Ich bin darauf gestoßen, als ich versuchte, a zu antworten Frage auf Stack Overflow.

Answer 1

Sehen Martin Smiths Antwort Informationen zum aktuellen Status von EXCEPT in einem rekursiven CTE.

Um zu erklären, was Sie gesehen haben und warum:

Ich verwende hier eine Tabellenvariable, um die Unterscheidung zwischen den Ankerwerten und rekursivem Elementen klarer zu machen (es ändert die Semantik nicht).

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)

Der Abfrageplan ist:

Die Ausführung beginnt am Wurzel des Plans (der Auswahl) und die Steuerung übergibt den Baum an die Indexspule, die Verkettung und dann an den Tischstab der obersten Ebene.

Die erste Reihe vom Scan übergibt den Baum und wird (a) in der Stapelspule gespeichert und (b) zum Client zurückgekehrt. Welche Zeile zuerst nicht definiert ist, aber nehmen wir an, dass es sich um die Zeile mit dem Wert {1} handelt. Die erste Zeile, die erscheint, ist daher {1}.

Die Steuerung geht erneut zum Tischscan weiter (der Verkettungsoperator verbraucht alle Zeilen aus dem äußersten Eingang, bevor er die nächste öffnet). Der Scan emittiert die zweite Zeile (Wert {2}), und dies gibt den Baum erneut weiter, der auf dem Stapel gespeichert und an den Client ausgegeben wird. Der Client hat jetzt die Sequenz {1}, {2} erhalten.

Der Stapel enthält nun {2, 1}. Da die Steuerung erneut an den Tischscan übergeht, werden keine Zeilen mehr angegeben, und die Steuerung geht an den Verkettungsoperator zurück, wodurch der zweite Eingang geöffnet wird (es benötigt eine Reihe, um an die Stapelspule zu gelangen), und die Steuerung geht an das innere Join über zum ersten Mal.

Der innere Join ruft die Tabellenspule in seiner äußeren Eingabe auf, die die obere Zeile aus dem Stapel {2} liest und sie vom Arbeitstable löscht. Der Stapel enthält jetzt {1}.

Nachdem der innere Join eine Zeile für seine äußere Eingabe erhalten hat, übergibt sie die Kontrolle über den inneren Eingang an das linke Antisemi-Join (LASJ). Dies fordert eine Zeile von der äußeren Eingabe an und übergibt die Kontrolle an die Sortierung. Sortierung ist ein blockierender Iterator, also liest er alle Zeilen aus der Tabellenvariable und sortiert sie aufsteigend (wie es passiert).

Die erste Zeile, die durch die Sortierung emittiert wird, ist daher der Wert {1}. Die innere Seite des Lasj gibt den aktuellen Wert des rekursiven Elements zurück (der Wert ist gerade vom Stapel ausgestattet), nämlich {2}. Die Werte am lasj sind {1} und {2}, also wird {1} emittiert, da die Werte nicht übereinstimmen.

Diese Zeile {1} fließt den Abfrageplan -Baum zum Index (Stapel) Spulen, wo er dem Stapel hinzugefügt wird, der jetzt {1, 1} enthält, und dem Client emittiert. Der Client hat jetzt die Sequenz {1}, {2}, {1} erhalten.

Die Kontrolle geht nun zurück zur Verkettung, die die innere Seite hinunter zurückgeht (es hat das letzte Mal eine Reihe zurückgegeben, möglicherweise wieder), durch die innere Verbindung zum Lasj. Es liest seine innere Eingabe erneut und erhält den Wert {2} aus der Sortierung.

Das rekursive Mitglied ist immer noch {2}, daher findet der Lasj diesmal {2} und {2}, was dazu führt, dass keine Zeile emittiert wird. Wenn Sie keine Zeilen mehr in der inneren Eingabe finden (die Sortierung ist jetzt aus Zeilen), wird die Steuerung wieder bis zum inneren Join übergeht.

Der innere Join liest seine äußere Eingabe, was dazu führt, dass der Wert {1} vom Stapel {1, 1} abgebrochen wird und den Stapel nur {1} hinterlässt. Der Vorgang wiederholt sich nun mit dem Wert {2} aus einem neuen Aufruf des Tabellencans und sortiert den Lasj -Test und wird zum Stapel hinzugefügt und übergibt an den Client, der jetzt {1}, {2} empfangen wurde. {1}, {2} ... und rund gehen wir.

Mein Lieblings Erläuterung Von der Stapelspule, die in rekursiven CTE -Plänen verwendet wird, ist Craig Freedman's.

Answer 2

Die BOL -Beschreibung rekursiver CTEs beschreibt die Semantik der rekursiven Ausführung wie folgt: wie folgt:

1. Teilen Sie den CTE -Ausdruck in Anker und rekursive Mitglieder.
2. Führen Sie die Ankerelemente aus (n) Erstellen Sie den ersten Aufruf oder die Basisgebnismenge (T0).
3. Führen Sie das rekursive Element (en) mit TI als Eingang und Ti+1 als Ausgang aus.
4. Wiederholen Sie Schritt 3, bis ein leerer Satz zurückgegeben wird.
5. Geben Sie das Ergebnissatz zurück. Dies ist eine Gewerkschaft, die alle T0 zu TN sind.

Beachten Sie, dass das obige ist a logisch Bezeichnung. Die physische Reihenfolge der Operationen kann etwas anders sein, wie hier dargestellt

Wenn Sie dies auf Ihren CTE anwenden Ich würde eine unendliche Schleife mit dem folgenden Muster erwarten

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

Da

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

ist der Ankerausdruck. Dies kehrt eindeutig zurück 1,2,3 wie T0

Danach läuft der rekursive Ausdruck

select a
from cte
except
select a
from r

Mit 1,2,3 als Eingang, der einen Ausgang von ergibt 4,5 wie T1 Dann kehrt das Einschalten für die nächste Rekursionsrunde zurück 1,2,3 und so weiter auf unbestimmte Zeit.

Dies passiert jedoch nicht tatsächlich. Dies sind die Ergebnisse der ersten 5 Aufrufe

+-----------+---------+---+---+---+
| 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 |
+-----------+---------+---+---+---+

Von der Verwendung OPTION (MAXRECURSION 1) und in Schritten von nach oben einstellen 1 Es ist ersichtlich, dass es in einen Zyklus eingeht, in dem jede aufeinanderfolgende Ebene ständig zwischen Ausgabe umschaltet 1,2,3,4 und 1,2,3,5.

Wie diskutiert von @Quassnoi in Dieser Blog -Beitrag. Das Muster der beobachteten Ergebnisse ist, als ob jeder Aufruf ausfällt (1),(2),(3),(4),(5) EXCEPT (X) wo X ist die letzte Zeile aus dem vorherigen Aufruf.

Bearbeiten: Nach dem Lesen SQL Kiwis ausgezeichnete Antwort Es ist klar, warum dies geschieht und dass dies nicht die ganze Geschichte ist, da noch viele Dinge auf dem Stapel übrig sind, die nie verarbeitet werden können.

Anker emittiert 1,2,3 Inhalt des Kunden stapeln 3,2,1

3 stapelte Stack, Stapelinhalt 2,1

Der Lasj kehrt zurück 1,2,4,5, Stapelinhalt 5,4,2,1,2,1

5 von Stack, Stapelinhalte ausgestattet 4,2,1,2,1

Der Lasj kehrt zurück 1,2,3,4 Stapelinhalt 4,3,2,1,5,4,2,1,2,1

4 stapelte Stack, Stapelinhalt 3,2,1,5,4,2,1,2,1

Der Lasj kehrt zurück 1,2,3,5 Stapelinhalt 5,3,2,1,3,2,1,5,4,2,1,2,1

5 von Stack, Stapelinhalte ausgestattet 3,2,1,3,2,1,5,4,2,1,2,1

Der Lasj kehrt zurück 1,2,3,4 Stapelinhalt 4,3,2,1,3,2,1,3,2,1,5,4,2,1,2,1

Wenn Sie versuchen, das rekursive Mitglied durch das logisch äquivalente Ausdruck (ohne Duplikate / Nulls) zu ersetzen

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

Dies ist nicht erlaubt und erhöht den Fehler "rekursive Referenzen sind in Unterabfragen nicht zulässig". Vielleicht ist es ein Versehen, das EXCEPT ist in diesem Fall sogar erlaubt.

Zusatz:Microsoft hat jetzt auf meine geantwortet Feedback anschließen wie nachstehend

JackDie Vermutung ist korrekt: Dies sollte ein Syntaxfehler sein; Rekursive Referenzen sollten in der Tat nicht zugelassen werden EXCEPT Klauseln. Wir planen, diesen Fehler in einer bevorstehenden Serviceveröffentlichung anzusprechen. In der Zwischenzeit würde ich empfehlen, rekursive Referenzen in zu vermeiden EXCEPTKlauseln.

Bei der Einschränkung der Überwachung über EXCEPT Wir folgen dem ANSI SQL Standard, der diese Einschränkung seit der Einführung der Rekursion einbezogen hat (ich glaube, 1999). Es gibt keine weit verbreitete Vereinbarung darüber, wie die Semantik für eine Übernahme sein sollte EXCEPT (auch als "unstratifizierte Negation" bezeichnet) in deklarativen Sprachen wie SQL. Darüber hinaus ist es notorisch schwierig (wenn nicht unmöglich), solche Semantik effizient (für angemessene Datenbanken) in einem RDBMS -System zu implementieren.

Und sieht so aus, als ob die eventuelle Implementierung 2014 für Datenbanken durchgeführt wurde mit Kompatibilitätsniveau von 120 oder höher.

Rekursive Referenzen in einer Aussichtsklausel erzeugen einen Fehler in Übereinstimmung mit dem ANSI SQL -Standard.