Utilizzando salvo in ricorsiva tabella comune

Question

Perché le seguenti ritorno interrogazione infinite righe? Mi sarei aspettato la clausola EXCEPT per terminare la ricorsione ..

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

mi sono imbattuto in questo durante il tentativo di rispondere a una domanda su Stack Overflow.

Answer 1

Martin Smith risposta per informazioni sullo stato attuale del EXCEPT in una CTE ricorsiva.

Per spiegare quello che stavano vedendo, e perché:

Io sto usando una variabile di tabella qui, per fare la distinzione tra i valori di ancoraggio e la voce più chiara ricorsiva (non cambia la semantica).

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)

Il piano di query è:

Esecuzione inizia alla radice del piano (SELECT) e il controllo passa l'albero all'Indice Spool, concatenazione, e poi al primo livello di scansione da tavolo.

La prima riga dalla scansione passa l'albero ed è (a) immagazzinate nella Stack Spool, e (b) restituito al client. Quale riga è un primo momento non è definito, ma supponiamo che è la riga con il valore {1}, per amor di discussione. La prima riga visualizzata è quindi {1}.

Il controllo passa nuovamente fino alla tabella di scansione (l'operatore di concatenazione consuma tutte le righe dal suo ingresso esterno prima di aprire il successivo). I emette scansione della seconda fila (valore {2}), e questa passa nuovamente l'albero da memorizzare nella pila e output al client. Il cliente ha ora ricevuto la successione {1}, {2}.

L'adozione di una convenzione dove la cima della pila LIFO è sulla sinistra, lo stack contiene ora {2, 1}. Quando il controllo passa nuovamente alla scansione di tabella, riporta più righe, e il controllo torna all'operatore di concatenazione, che apre del secondo ingresso (necessita una riga per passare alla bobina stack), e il controllo passa al join interno per la prima volta.

Il join interno chiamate rocchetto Tabella sul suo ingresso esterno, che legge la riga superiore dallo stack {2} e lo elimina dal piano di lavoro. Lo stack contiene ora {1}.

Dopo aver ricevuto una riga sul suo ingresso esterno, l'Inner Join passa il controllo verso il basso il suo ingresso interno alla sinistra anti-Semi Join (LASJ). Questo richiede una riga dal suo ingresso esterno, passando il controllo al ordine. Sorta è un blocco iteratore, quindi legge tutte le righe della variabile di tabella e ordina loro ascendente (come accade).

La prima riga emessa dal Sort è quindi il valore {1}. Il lato interno della LASJ restituisce il valore corrente del membro ricorsivo (il valore appena estratto dallo stack), che è {2}. I valori alla LASJ sono {1} e {2} in modo {1} viene emesso, dal momento che i valori non corrispondono.

Questa riga {1} scorre l'albero piano di query per l'indice (Stack) Spool dove viene aggiunto alla pila, che ora contiene {1, 1}, ed emessa al cliente. Il cliente ha ora ricevuto la successione {1}, {2}, {1}.

Controllo ora passa di nuovo alla concatenazione, di nuovo lungo il lato interno (è tornato di fila l'ultima volta, potrebbe fare di nuovo), giù attraverso l'INNER JOIN, al LASJ. Si legge ancora una volta il suo ingresso interno, ottenendo il valore {2} dal Sort.

L'elemento ricorsivo è ancora {2}, quindi questa volta reperti LASJ {2} e {2}, con conseguente nessuna riga che sono emessi. Trovare più righe sul suo ingresso interno (Sort è ormai fuori di righe), il controllo passa indietro fino alla join interno.

L'Inner Join legge il suo ingresso esterno, che si traduce in valore {1} viene estratto dallo stack {1, 1}, lasciando lo stack con solo {1}. Il processo ora si ripete, con il valore {2} da una nuova invocazione del Scan Tavola e Ordina superamento della prova LASJ e di essere aggiunto alla pila, e passa al cliente, che ha ora ricevuto {1}, {2}, {1}, {2} ... e rotondo andiamo.

Il mio preferito spiegazione Stack del rocchetto utilizzato nei piani di CTE ricorsiva è di Craig Freedman.

Answer 2

La descrizione BOL del CTE ricorsive descrive la semantica di esecuzione ricorsiva come essere come segue:

1. Spalato l'espressione CTE in ancoraggio e membri ricorsivi.
2. Esegui l'elemento di ancoraggio (s) creando il set prima chiamata o di base risultato (T0).
3. Esegui l'elemento ricorsivo (s) con Ti come input e Ti + 1 come uscita.
4. Ripetere passaggio 3 finché viene restituito un insieme vuoto.
5. Ritorna il set di risultati. Si tratta di un'UNION ALL di T0 Tn.

Si noti la cui sopra è un logico descrizione. L'ordine fisico di operazioni può essere diverso, come illustrato qui

L'applicazione di questo al vostro CTE mi aspetterei un ciclo infinito con il seguente schema

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

A causa

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

è l'espressione di ancoraggio. Ciò restituisce chiaramente 1,2,3 come T0

Dopo questa data, le piste di espressione ricorsive

select a
from cte
except
select a
from r

Con 1,2,3 come input che produrrà una potenza di 4,5 come T1 ricollegando che nel lontano per il prossimo ciclo di ricorsione tornerà 1,2,3 e così via all'infinito.

Questo non è ciò che effettivamente accade comunque. Questi sono i risultati dei primi 5 invocazioni

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

Dall'utilizzo OPTION (MAXRECURSION 1) e regolazione verso l'alto in incrementi di 1 si può osservare che essa entra in un ciclo in cui ogni livello successivo sarà continuamente commutazione tra uscita 1,2,3,4 e 1,2,3,5.

Come discusso da @Quassnoi in questo post del blog . Il modello di risultati osservati è come se ogni invocazione fa (1),(2),(3),(4),(5) EXCEPT (X) dove X è l'ultima riga dalla chiamata precedente.

Modifica Dopo aver letto la risposta eccellente del SQL Kiwi è chiaro sia il motivo per cui questo si verifica e che questa non è tutta la storia in che c'è ancora un sacco di roba lasciata sullo stack che non può ottenere elaborati.

Ancora Emette 1,2,3 al client Stack Contenuto 3,2,1

3 spuntato fuori pila, Stack Contenuto 2,1

Il rendimento LASJ 1,2,4,5, Stack Contenuto 5,4,2,1,2,1

5 pila spuntato fuori, Stack Contenuto 4,2,1,2,1

I rendimenti LASJ 1,2,3,4 Stack Contenuto 4,3,2,1,5,4,2,1,2,1

4 spuntato fuori pila, Stack Contenuto 3,2,1,5,4,2,1,2,1

I rendimenti LASJ 1,2,3,5 Stack Contenuto 5,3,2,1,3,2,1,5,4,2,1,2,1

5 pila spuntato fuori, Stack Contenuto 3,2,1,3,2,1,5,4,2,1,2,1

I rendimenti LASJ 1,2,3,4 Stack Contenuto 4,3,2,1,3,2,1,3,2,1,5,4,2,1,2,1

Se si tenta di sostituire il membro ricorsivo con l'logicamente equivalente (in assenza di duplicati / NULL) espressione

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

Questa non è consentito e genera l'errore "riferimenti ricorsivi non sono accettati in sottoquery." quindi forse è una svista che EXCEPT è nemmeno consentito in questo caso.

Aggiunta: Microsoft ha ora risposto alla mia Connect in come di seguito

indovinare Jack s 'è corretta: questo avrebbe dovuto essere un errore di sintassi; riferimenti ricorsivi non dovrebbero infatti essere consentitonelle clausole EXCEPT. Abbiamo in programma di affrontare questo problema in un service release imminente. Nel Intanto, vorrei suggerire di evitare riferimenti ricorsivi in ??EXCEPT clausole.

nel limitare la ricorsione oltre EXCEPT seguiamo lo standard ANSI SQL, che ha incluso questa restrizione da allora era ricorsione introdotto (nel 1999 credo). Non c'è accordo diffusa su ciò che la semantica dovrebbe essere per la ricorsione over EXCEPT (chiamato anche "Negazione non stratificato") in linguaggi dichiarativi come SQL. Nel Inoltre, è notoriamente difficile (se non impossibile) per attuare tale la semantica in modo efficiente (per i database di dimensioni ragionevoli) in un RDBMS sistema.

e si presenta come l'eventuale implementazione è stata fatta nel 2014 per i database con livello di compatibilità 120 o superiore .

riferimenti ricorsivi in ??una clausola except genera un errore in conformità con lo standard ANSI SQL.