L'utilisation SAUF dans une expression de table commune récursive

Question

Pourquoi le retour des requêtes suivantes lignes d'infinies? Je me serais attendu à la clause de EXCEPT de mettre fin à la récursion ..

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

Je suis tombé sur ce tout en essayant de répondre à une question sur débordement de la pile.

Answer 1

Voir réponse de Martin Smith pour plus d'informations sur l'état actuel de EXCEPT dans un CTE récursive.

Pour expliquer ce que vous voyez, et pourquoi:

J'utilise une variable de table ici, de faire la distinction entre les valeurs d'ancrage et le point récursive plus clair (il ne change pas la sémantique).

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)

Le plan de requête est:

exécution commence à la racine du plan (SELECT) et le contrôle passe dans l'arbre à l'Spool Index, Enchaînement, puis au plus haut niveau balayage de table.

La première ligne de balayage passe l'arbre et est (a) stockée dans la bobine d'usine, et (b) renvoyée au client. Quelle ligne est tout d'abord ne définit pas, mais supposons qu'il est la ligne avec la valeur {1}, pour les besoins du raisonnement. La première ligne à apparaître est donc {1}.

La commande passe à nouveau vers le bas à la table de numérisation (l'opérateur de concaténation consomme toutes les lignes de son entrée la plus externe avant l'ouverture de la suivante). Les émet la deuxième ligne de balayage (valeur {2}), ce qui passe à nouveau dans l'arbre pour être stockés sur la pile et une sortie pour le client. Le client a reçu la séquence {1}, {2}.

L'adoption d'une convention où le haut de la pile LIFO est à gauche, la pile contient maintenant {2, 1}. Comme la commande passe à nouveau à la table de balayage, il signale pas d'autres lignes, et la commande passe à l'opérateur de concaténation, qui ouvre la seconde entrée de (a besoin d'une rangée pour laisser passer à la bobine de la pile), et la commande passe à la jointure interne pour la première fois.

La jointure de la table des appels bobine sur son entrée externe, qui lit la ligne de sommet de la pile {2} et le supprime de la table de travail. La pile contient maintenant {1}.

Après avoir reçu une ligne sur son entrée externe, la jointure interne passe la commande vers le bas de son entrée à l'intérieur Anti-Semi jointure gauche (LASJ). Cela demande une rangée à partir de son entrée externe, le contrôle passe au tri. Trier est un blocage iterator, il lit toutes les lignes de la variable de table et les trie par ordre croissant (comme il arrive).

La première rangée émise par le tri est donc la valeur {1}. Le côté intérieur de la LASJ retourne la valeur courante de l'élément récursif (la valeur juste sauté hors de la pile), qui est {2}. Les valeurs au LASJ sont {1} et {2} si {1} est émis, étant donné que les valeurs ne correspondent pas.

Cette ligne {1} flux de l'arbre plan de requête à l'indice (Stack) Spool où il est ajouté à la pile, qui contient maintenant {1, 1} et émis au client. Le client a reçu la séquence {1}, {2}, {1}.

Le contrôle passe maintenant à la Concaténation, vers le bas de la face interne (il est revenu une dernière fois la ligne, pourrait faire à nouveau), à travers la jointure interne, à la LASJ. Il lit son entrée intérieure à nouveau, obtenir la valeur {2} du tri.

Le membre récursif est encore {2}, cette fois les trouvailles de LASJ {2} et {2}, résultant en aucune ligne étant émis. Trouver plus de lignes sur son entrée intérieure (le tri est maintenant hors de lignes), la commande revient à l'intérieur d'inscription.

La jointure interne lit son entrée externe, qui se traduit par la valeur {1} étant extraites de la pile {1, 1}, en laissant la pile avec seulement {1}. Le processus se répète à présent avec la valeur {2} à partir d'un nouvel appel de la table de numérisation et la transmission Trier le test de LASJ et étant ajouté à la pile, et transmet au client, qui a maintenant reçu {1}, {2}, {1}, {2} ... et rond nous allons.

Mon préféré explication de la pile Spool utilisé dans les plans de CTE récursives est de Craig Freedman.

Answer 2

La description BOL de CTE récursives décrit la sémantique de l'exécution récursive comme étant comme suit:

1. Sépare l'expression CTE dans l'ancre et les membres récursives.
2. Exécuter l'élément d'ancrage (s) la création du premier résultat d'appel ou d'une base ensemble (T0).
3. Exécuter l'élément récursif (s) avec Ti comme entrée et Ti + 1 en tant que sortie.
4. Répétez l'étape 3 jusqu'à ce qu'un ensemble vide est retourné.
5. Retour le jeu de résultats. Ceci est un UNION ALL de T0 à Tn.

Notez ce qui précède est un logique description. L'ordre physique des opérations peut être quelque peu différent, comme illustré ici

Appliqué à votre CTE j'attendre une boucle infinie avec le motif suivant:

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

Comme

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

est l'expression Anchor. Cela renvoie clairement 1,2,3 comme T0

Ensuite, les pistes d'expression récursives

select a
from cte
except
select a
from r

1,2,3 en entrée qui donnera une sortie 4,5 comme T1 puis de brancher ce avant pour le prochain tour de récursion retournera 1,2,3 et ainsi de suite indéfiniment.

Ce n'est pas ce qui se passe en fait cependant. Ce sont les résultats des 5 premiers invocations

+-----------+---------+---+---+---+
| 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 l'aide OPTION (MAXRECURSION 1) et en ajustant vers le haut par incréments de 1 on peut voir qu 'il entre dans un cycle où chaque niveau successif alterne continuellement entre 1,2,3,4 et délivrer en sortie 1,2,3,5.

Comme indiqué par @Quassnoi ce billet de blog . Le modèle des résultats observés est comme si chaque appel fait (1),(2),(3),(4),(5) EXCEPT (X) où X est la dernière ligne de l'invocation.

Modifier Après avoir lu une excellente réponse SQL Kiwi il est clair à la fois pourquoi ce se produit et que ce n'est pas toute l'histoire en ce qu'il est encore plein de choses à gauche sur la pile qui ne peut se traiter.

ancre Emet 1,2,3 au client Stack Table des matières 3,2,1

3 pile sauté hors tension, Stack matières 2,1

Le rendement de LASJ 1,2,4,5, Stack Table des matières 5,4,2,1,2,1

5 pile sauté hors tension, Stack matières 4,2,1,2,1

Les retours LASJ 1,2,3,4 Sommaire Stack 4,3,2,1,5,4,2,1,2,1

4 pile sauté hors tension, Stack matières 3,2,1,5,4,2,1,2,1

Les retours LASJ 1,2,3,5 Sommaire Stack 5,3,2,1,3,2,1,5,4,2,1,2,1

5 pile sauté hors tension, Stack matières 3,2,1,3,2,1,5,4,2,1,2,1

Les retours LASJ 1,2,3,4 Sommaire Stack 4,3,2,1,3,2,1,3,2,1,5,4,2,1,2,1

Si vous essayez de remplacer le membre récursive avec l'expression logique équivalente (en l'absence de doublons / NULLs)

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

Ce n'est pas autorisé et soulève l'erreur « références récursives ne sont pas autorisés dans les sous-requêtes. » alors peut-être il est un oubli qui EXCEPT est même permis dans ce cas.

Addition: Microsoft a maintenant répondu à mon Connect Feedback comme ci-dessous

guess Jack de est correct: cela aurait été une erreur de syntaxe; références récursives doivent en effet pas être autorisésdans les clauses EXCEPT. Nous prévoyons de résoudre ce bogue dans une version de service à venir. dans le Entre-temps, je vous suggère d'éviter des références récurrentes dans EXCEPT clauses.

Dans récursion sur EXCEPT restriction, nous suivons la norme ANSI SQL, qui a inclus cette restriction depuis la récursivité introduit (en 1999 je crois). Il n'y a pas d'accord sur grande échelle ce que la sémantique devrait être la récursivité sur EXCEPT (également appelé « Négation non stratifiées ») dans les langues déclaratives telles que SQL. Dans De plus, il est notoirement difficile (voire impossible) de mettre en œuvre cette sémantique efficace (pour les bases de données de taille raisonnable) dans un SGBDR système.

Et ressemble à la mise en œuvre éventuelle a été faite en 2014 pour les bases de données avec le niveau de compatibilité des 120 ou plus .

références récursives dans une clause except génère une erreur conforme à la norme ANSI SQL.