Usar EXCEPT en una expresión de tabla común recursiva

¿Por qué la siguiente consulta devuelve filas infinitas? Hubiera esperado que la EXCEPTcláusula terminara la recursión.

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

Encontré esto al intentar responder una pregunta sobre Stack Overflow.

Consulte la respuesta de Martin Smith para obtener información sobre el estado actual de EXCEPTun CTE recursivo.

Para explicar lo que estaba viendo y por qué:

Estoy usando una variable de tabla aquí, para hacer la distinción entre los valores de anclaje y el elemento recursivo más claro (no cambia la 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)

El plan de consulta es:

La ejecución comienza en la raíz del plan (el SELECCIONAR) y el control pasa por el árbol hacia el Spool de índice, la Concatenación y luego al Escaneo de tabla de nivel superior.

La primera fila del escaneo pasa por el árbol y (a) se almacena en el Stack Spool, y (b) se devuelve al cliente. La primera fila no está definida, pero supongamos que es la fila con el valor {1}, en aras de la discusión. La primera fila que aparece es, por lo tanto, {1}.

El control vuelve a pasar a la exploración de tabla (el operador de concatenación consume todas las filas desde su entrada más externa antes de abrir la siguiente). El escaneo emite la segunda fila (valor {2}), y esto nuevamente pasa el árbol para ser almacenado en la pila y enviado al cliente. El cliente ahora ha recibido la secuencia {1}, {2}.

Adoptando una convención donde la parte superior de la pila LIFO está a la izquierda, la pila ahora contiene {2, 1}. Cuando el control vuelve a pasar a la exploración de tabla, no informa más filas, y el control vuelve al operador de concatenación, que abre su segunda entrada (necesita una fila para pasar al carrete de la pila), y el control pasa a la unión interna por primera vez.

La unión interna llama al Table Spool en su entrada externa, que lee la fila superior de la pila {2} y la elimina de la mesa de trabajo. La pila ahora contiene {1}.

Después de haber recibido una fila en su entrada externa, la unión interna pasa el control hacia abajo por su entrada interna a la unión anti-semi-izquierda (LASJ). Esto solicita una fila desde su entrada externa, pasando el control al Ordenar. Sort es un iterador de bloqueo, por lo que lee todas las filas de la variable de la tabla y las ordena de forma ascendente (como sucede).

La primera fila emitida por Sort es, por lo tanto, el valor {1}. El lado interno del LASJ devuelve el valor actual del miembro recursivo (el valor que acaba de salir de la pila), que es {2}. Los valores en el LASJ son {1} y {2} por lo que se emite {1}, ya que los valores no coinciden.

Esta fila {1} fluye hacia arriba del árbol del plan de consulta al Spool de índice (pila) donde se agrega a la pila, que ahora contiene {1, 1}, y se emite al cliente. El cliente ahora ha recibido la secuencia {1}, {2}, {1}.

El control ahora vuelve a la Concatenación, baja por el lado interno (regresó una fila la última vez, podría volver a hacerlo), baja a través de la Unión interna, al LASJ. Lee su entrada interna nuevamente, obteniendo el valor {2} de la Clasificación.

El miembro recursivo sigue siendo {2}, por lo que esta vez el LASJ encuentra {2} y {2}, lo que resulta en que no se emite ninguna fila. Al no encontrar más filas en su entrada interna (la Clasificación ahora está fuera de filas), el control pasa de nuevo a la Unión interna.

La unión interna lee su entrada externa, lo que da como resultado que el valor {1} se extraiga de la pila {1, 1}, dejando la pila con solo {1}. El proceso ahora se repite, con el valor {2} de una nueva invocación de Table Scan and Sort que pasa la prueba LASJ y se agrega a la pila, y pasa al cliente, que ahora ha recibido {1}, {2}, {1}, {2} ... y alrededor vamos.

Mi explicación favorita del carrete Stack utilizado en los planes recursivos de CTE es Craig Freedman.

La descripción de BOL de los CTE recursivos describe la semántica de la ejecución recursiva de la siguiente manera:

1. Divide la expresión CTE en miembros ancla y recursivos.
2. Ejecute los miembros de anclaje que crean la primera invocación o el conjunto de resultados base (T0).
3. Ejecute los miembros recursivos con Ti como entrada y Ti + 1 como salida.
4. Repita el paso 3 hasta que se devuelva un conjunto vacío.
5. Devuelve el conjunto de resultados. Esta es una UNIÓN TODO de T0 a Tn.

Tenga en cuenta que lo anterior es una descripción lógica . El orden físico de las operaciones puede ser algo diferente, como se ilustra aquí.

Aplicando esto a su CTE, esperaría un bucle infinito con el siguiente patrón

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

es la expresión de anclaje. Esto claramente regresa 1,2,3comoT0

A partir de entonces se ejecuta la expresión recursiva

select a
from cte
except
select a
from r

Con una 1,2,3entrada como que producirá una salida de 4,5as T1, volverá a enchufarla para la próxima ronda de recursión 1,2,3y así continuará indefinidamente.

Sin embargo, esto no es lo que realmente sucede. Estos son los resultados de las primeras 5 invocaciones.

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

Al usar OPTION (MAXRECURSION 1)y ajustar hacia arriba en incrementos, 1se puede ver que entra en un ciclo donde cada nivel sucesivo alternará continuamente entre la salida 1,2,3,4y 1,2,3,5.

Como lo discutió @Quassnoi en esta publicación de blog . El patrón de resultados observados es como si cada invocación estuviera haciendo (1),(2),(3),(4),(5) EXCEPT (X)dónde Xestá la última fila de la invocación anterior.

Editar: Después de leer la excelente respuesta de SQL Kiwi, está claro por qué ocurre esto y que esta no es toda la historia, ya que todavía hay un montón de cosas en la pila que nunca se pueden procesar.

El ancla se emite 1,2,3al contenido de la pila del cliente3,2,1

3 saltaron de la pila, Contenido de la pila 2,1

El LASJ regresa 1,2,4,5, Contenido de la pila5,4,2,1,2,1

5 saltaron de la pila, Contenido de la pila 4,2,1,2,1

El LASJ devuelve 1,2,3,4 Contenido de la pila4,3,2,1,5,4,2,1,2,1

4 saltaron de la pila, contenido de la pila 3,2,1,5,4,2,1,2,1

El LASJ devuelve 1,2,3,5 Contenido de la pila5,3,2,1,3,2,1,5,4,2,1,2,1

5 saltaron de la pila, Contenido de la pila 3,2,1,3,2,1,5,4,2,1,2,1

El LASJ devuelve 1,2,3,4 Contenido de la pila 4,3,2,1,3,2,1,3,2,1,5,4,2,1,2,1

Si intenta reemplazar el miembro recursivo con la expresión lógicamente equivalente (en ausencia de duplicados / NULL)

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

Esto no está permitido y genera el error "No se permiten referencias recursivas en subconsultas". entonces quizás es un descuido que EXCEPTincluso se permite en este caso.

Adición: Microsoft ha respondido a mis comentarios de Connect como se muestra a continuación

La suposición de Jack es correcta: esto debería haber sido un error de sintaxis; las referencias recursivas no deberían permitirse en las EXCEPTcláusulas. Planeamos abordar este error en una próxima versión del servicio. Mientras tanto, sugeriría evitar referencias recursivas en EXCEPT cláusulas.

Al restringir la recursión EXCEPT, seguimos el estándar ANSI SQL, que ha incluido esta restricción desde que se introdujo la recursividad (en 1999, creo). No existe un acuerdo generalizado sobre cuál debería ser la semántica para la recursión EXCEPT(también llamada "negación no estratificada") en lenguajes declarativos como SQL. Además, es notoriamente difícil (si no imposible) implementar dicha semántica de manera eficiente (para bases de datos de tamaño razonable) en un sistema RDBMS.

Y parece que la implementación final se realizó en 2014 para bases de datos con un nivel de compatibilidad de 120 o superior .

Las referencias recursivas en una cláusula EXCEPT generan un error de conformidad con el estándar ANSI SQL.