Usando excepto en una expresión de tabla común recursiva

Question

¿Por qué la siguiente consulta devuelve las filas infinitas? Hubiera esperado el EXCEPT cláusula para terminar 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 mientras intentaba responder a un pregunta En el desbordamiento de la pila.

Answer 1

Ver Respuesta de Martin Smith Para obtener información sobre el estado actual de EXCEPT En un 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 (la selección) y el control pasa por el árbol al carrete de índice, la concatenación y luego al escaneo de tabla de nivel superior.

La primera fila del escaneo pasa por el árbol y está (a) almacenada en el carrete de pila, y (b) regresó al cliente. La fila primero no está definida, pero supongamos que es la fila con el valor {1}, en aras del argumento. La primera fila que aparece es, por lo tanto, {1}.

El control nuevamente pasa al escaneo de la tabla (el operador de concatenación consume todas las filas de 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 almacenarse en la pila y salida 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}. A medida que el control pasa nuevamente al escaneo de la 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 carrete de la mesa 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 por su entrada interna a la unión antisemi izquierda (LASJ). Esto solicita una fila de su entrada externa, pasando el control al tipo. Sort es un iterador de bloqueo, por lo que lee todas las filas de la variable de la tabla y las clasifica ascendiendo (como sucede).

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

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

El control ahora vuelve a la concatenación, regresa por el lado interno (devolvió una fila la última vez, podría volver a funcionar), a través de la unión interna, al LASJ. Se lee nuevamente su entrada interna, obteniendo el valor {2} del tipo.

El miembro recursivo sigue siendo {2}, por lo que esta vez el LASJ encuentra {2} y {2}, lo que da como resultado que no se emita una fila. Al encontrar más filas en su entrada interna (el tipo que 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 aparte 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 del escaneo de la tabla y ordene pasar la prueba LASJ y agregarse a la pila, y pasa al cliente, que ahora ha recibido {1}, {2}, {1}, {2} ... y redondeamos.

Mi favorito explicación del carrete de pila utilizado en los planes recursivos de CTE es el de Craig Freedman.

Answer 2

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

1. Divida la expresión de CTE en ancla y miembros recursivos.
2. Ejecute los miembros del ancla (s) creando el primer conjunto de resultados de invocación o 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 un lógico descripción. 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 vuelve claramente 1,2,3 como T0

A partir de entonces la expresión recursiva funciona

select a
from cte
except
select a
from r

Con 1,2,3 como entrada que producirá una salida de 4,5 como T1 Luego, enchufar eso de nuevo para la próxima ronda de recursión regresará 1,2,3 y así sucesivamente 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 |
+-----------+---------+---+---+---+

De usar OPTION (MAXRECURSION 1) y ajustarse hacia arriba en incrementos de 1 Se puede ver que ingresa a un ciclo en el que cada nivel sucesivo se alternará continuamente entre la salida 1,2,3,4 y 1,2,3,5.

Como se discutió por @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 X es la última fila de la invocación anterior.

Editar: Despues 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 quedan muchas cosas en la pila que nunca pueden procesarse.

Anchor emite 1,2,3 AL CONTENIDO DEL CLIENTE DE LA PISTA DEL CLIENTE 3,2,1

3 salieron de pila, contenido de la pila 2,1

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

5 salió de pila, contenido de la pila 4,2,1,2,1

El LASJ regresa 1,2,3,4 Contenido de pila 4,3,2,1,5,4,2,1,2,1

4 salió de pila, contenido de la pila 3,2,1,5,4,2,1,2,1

El LASJ regresa 1,2,3,5 Contenido de pila 5,3,2,1,3,2,1,5,4,2,1,2,1

5 salió de pila, contenido de la pila 3,2,1,3,2,1,5,4,2,1,2,1

El LASJ regresa 1,2,3,4 Contenido de pila 4,3,2,1,3,2,1,3,2,1,5,4,2,1,2,1

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

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

Esto no está permitido y plantea el error "Las referencias recursivas no están permitidas en las subconsules". Entonces, tal vez sea un descuido que EXCEPT incluso está permitido en este caso.

Suma:Microsoft ahora ha respondido a mi Conecte la retroalimentación como a continuación

JacoboLa suposición es correcta: esto debería haber sido un error de sintaxis; Las referencias recursivas no deben permitirse en EXCEPT cláusulas. Planeamos abordar este error en un próximo lanzamiento del servicio. Mientras tanto, sugeriría evitar referencias recursivas en EXCEPTcláusulas.

En restringir la recursión sobre EXCEPT Seguimos el estándar ANSI SQL, que ha incluido esta restricción desde que se introdujo la recursión (en 1999, creo). No hay un acuerdo generalizado sobre cuál debería ser la semántica para la recursión sobre EXCEPT (también llamado "negación no estratificada") en idiomas 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 eventual se realizó en 2014 para bases de datos con nivel de compatibilidad de 120 o más.

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