Usando EXCEPT em uma expressão de tabela comum recursiva

A descrição BOL de CTEs recursivos descreve a semântica da execução recursiva da seguinte forma:

1. Divida a expressão CTE em âncora e membros recursivos.
2. Execute o(s) membro(s) âncora criando a primeira invocação ou conjunto de resultados base (T0).
3. Execute o(s) membro(s) recursivo(s) com Ti como entrada e Ti+1 como saída.
4. Repita a etapa 3 até que um conjunto vazio seja retornado.
5. Retorne o conjunto de resultados. Esta é uma UNION ALL de T0 a Tn.

Observe que o acima é uma descrição lógica . A ordem física das operações pode ser um pouco diferente conforme ilustrado aqui

Aplicando isso ao seu CTE, eu esperaria um loop infinito com o seguinte padrão

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

Porque

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

é a expressão Anchor. Isso retorna claramente 1,2,3comoT0

Depois disso, a expressão recursiva é executada

select a
from cte
except
select a
from r

Com 1,2,3a entrada que produzirá uma saída de 4,5as, T1então, reconectando-a para a próxima rodada de recursão, retornará 1,2,3e assim por diante indefinidamente.

Isso não é o que realmente acontece no entanto. Estes são os resultados das primeiras 5 invocações

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

Ao usar OPTION (MAXRECURSION 1)e ajustar para cima em incrementos 1, pode-se ver que ele entra em um ciclo em que cada nível sucessivo alternará continuamente entre saída 1,2,3,4e 1,2,3,5.

Conforme discutido por @Quassnoi nesta postagem do blog . O padrão de resultados observados é como se cada invocação estivesse fazendo (1),(2),(3),(4),(5) EXCEPT (X)onde Xestá a última linha da invocação anterior.

Editar: Depois de ler a excelente resposta do SQL Kiwi , fica claro por que isso ocorre e que essa não é toda a história, pois ainda há muitas coisas na pilha que nunca podem ser processadas.

A âncora emite 1,2,3para o conteúdo da pilha do cliente3,2,1

3 saiu da pilha, conteúdo da pilha2,1

O LASJ retorna 1,2,4,5, Conteúdo da pilha5,4,2,1,2,1

5 retirados da pilha, conteúdo da pilha4,2,1,2,1

O LASJ retorna o 1,2,3,4 conteúdo da pilha4,3,2,1,5,4,2,1,2,1

4 saiu da pilha, conteúdo da pilha3,2,1,5,4,2,1,2,1

O LASJ retorna o 1,2,3,5 conteúdo da pilha5,3,2,1,3,2,1,5,4,2,1,2,1

5 retirados da pilha, conteúdo da pilha3,2,1,3,2,1,5,4,2,1,2,1

O LASJ retorna o 1,2,3,4 conteúdo da pilha 4,3,2,1,3,2,1,3,2,1,5,4,2,1,2,1

Se você tentar substituir o membro recursivo pela expressão logicamente equivalente (na ausência de duplicatas/NULLs)

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

Isso não é permitido e gera o erro "Referências recursivas não são permitidas em subconsultas". então talvez seja um descuido que EXCEPTé permitido neste caso.

Adição: a Microsoft agora respondeu ao meu Connect Feedback conforme abaixo

A suposição de Jack está correta: deve ter sido um erro de sintaxe; referências recursivas não devem ser permitidas em EXCEPTcláusulas. Planejamos resolver esse bug em uma próxima versão do serviço. Enquanto isso, sugiro evitar referências recursivas em EXCEPT cláusulas.

Ao restringir a recursão EXCEPT, seguimos o padrão ANSI SQL, que inclui essa restrição desde que a recursão foi introduzida (em 1999, acredito). Não há um consenso generalizado sobre qual deve ser a semântica para recursão EXCEPT(também chamada de "negação não estratificada") em linguagens declarativas como SQL. Além disso, é notoriamente difícil (se não impossível) implementar essa semântica de forma eficiente (para bancos de dados de tamanho razoável) em um sistema RDBMS.

E parece que a eventual implementação foi feita em 2014 para bancos de dados com nível de compatibilidade de 120 ou superior .

As referências recursivas em uma cláusula EXCEPT geram um erro em conformidade com o padrão ANSI SQL.

Consulte a resposta de Martin Smith para obter informações sobre o status atual de EXCEPTum CTE recursivo.

Para explicar o que você estava vendo e por quê:

Estou usando uma variável de tabela aqui, para tornar mais clara a distinção entre os valores âncora e o item recursivo (não altera a semântica).

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)

O plano de consulta é:

A execução começa na raiz do plano (o SELECT) e o controle passa pela árvore para o Index Spool, Concatenation e, em seguida, para o Table Scan de nível superior.

A primeira linha da varredura passa pela árvore e é (a) armazenada no Stack Spool e (b) retornada ao cliente. Qual linha é a primeira não está definida, mas vamos supor que seja a linha com o valor {1}, por causa do argumento. A primeira linha a aparecer é, portanto, {1}.

O controle passa novamente para o Table Scan (o operador Concatenation consome todas as linhas de sua entrada mais externa antes de abrir a próxima). A varredura emite a segunda linha (valor {2}), e isso novamente passa pela árvore a ser armazenada na pilha e enviada ao cliente. O cliente agora recebeu a sequência {1}, {2}.

Adotando uma convenção em que o topo da pilha LIFO está à esquerda, a pilha agora contém {2, 1}. À medida que o controle passa novamente para o Table Scan, ele não relata mais linhas e o controle passa de volta para o operador Concatenation, que abre sua segunda entrada (precisa de uma linha para passar para o spool da pilha) e o controle passa para o Inner Join pela primeira vez.

A junção interna chama o Table Spool em sua entrada externa, que lê a linha superior da pilha {2} e a exclui da tabela de trabalho. A pilha agora contém {1}.

Tendo recebido uma linha em sua entrada externa, o Inner Join passa o controle de sua entrada interna para o Left Anti-Semi Join (LASJ). Isso solicita uma linha de sua entrada externa, passando o controle para o Sort. Sort é um iterador de bloqueio, então ele lê todas as linhas da variável de tabela e as classifica em ordem crescente (como acontece).

A primeira linha emitida pelo Sort é, portanto, o valor {1}. O lado interno do LASJ retorna o valor atual do membro recursivo (o valor que acabou de sair da pilha), que é {2}. Os valores no LASJ são {1} e {2}, então {1} é emitido, pois os valores não correspondem.

Essa linha {1} sobe na árvore do plano de consulta para o spool de índice (pilha) onde é adicionada à pilha, que agora contém {1, 1} e emitida para o cliente. O cliente agora recebeu a sequência {1}, {2}, {1}.

O controle agora passa de volta para a Concatenação, de volta para o lado interno (retornou uma linha da última vez, pode retornar), para baixo através da Inner Join, para o LASJ. Ele lê sua entrada interna novamente, obtendo o valor {2} do Sort.

O membro recursivo ainda é {2}, então desta vez o LASJ encontra {2} e {2}, resultando em nenhuma linha sendo emitida. Não encontrando mais linhas em sua entrada interna (o Sort agora está sem linhas), o controle passa de volta para o Inner Join.

O Inner Join lê sua entrada externa, o que resulta no valor {1} sendo retirado da pilha {1, 1}, deixando a pilha com apenas {1}. O processo agora se repete, com o valor {2} de uma nova invocação do Table Scan and Sort passando no teste LASJ e sendo adicionado à pilha e passado para o cliente, que agora recebeu {1}, {2}, {1}, {2}...e voltamos.

Minha explicação favorita sobre o spool Stack usado em planos CTE recursivos é a de Craig Freedman.