Pourquoi un CTE récursif dans Transact-SQL nécessite-t-il un UNION ALL et non un UNION ?

Question

Je comprends qu'une ancre est nécessaire, c'est logique. Et je sais qu'une UNION ALL est nécessaire, si votre CTE récursif n'en a pas, il ne fonctionnera tout simplement pas... mais je n'arrive pas à trouver une bonne explication de la raison pour laquelle c'est le cas. Toute la documentation indique simplement que vous en avez besoin.

Pourquoi ne peut pas nous utilisons un UNION au lieu d'un UNION ALL dans une requête récursive ? Il semble que ce serait une bonne idée de ne pas inclure les doublons lors d'une récursion plus profonde, n'est-ce pas ? Quelque chose comme ça devrait déjà fonctionner sous le capot, je pense.

Answer 1

Je suppose que la raison en est qu'ils n'ont tout simplement pas considéré cette fonctionnalité comme prioritaire et digne d'être mise en œuvre. Il semble que Postgres fait soutenir à la fois UNION y UNION ALL .

Si vous avez des arguments solides en faveur de cette fonctionnalité, vous pouvez fournir des informations à l'adresse suivante Connectez-vous à (ou quelle que soit l'URL de son remplacement).

Empêcher l'ajout de doublons pourrait être utile, car une ligne en double ajoutée dans une étape ultérieure à une précédente finira presque toujours par provoquer une boucle infinie ou par dépasser la limite de récursivité maximale.

Il y a pas mal d'endroits dans le Normes SQL où le code est utilisé démontrant UNION comme ci-dessous

Cet article explique comment ils sont mis en œuvre dans SQL Server . Ils ne font rien de tel "sous le capot". Le spool de la pile supprime les lignes au fur et à mesure, il ne serait donc pas possible de savoir si une ligne ultérieure est le double d'une ligne supprimée. Support de UNION nécessiterait une approche quelque peu différente.

Entre-temps, vous pouvez facilement réaliser la même chose avec un TVF à déclarations multiples.

Pour prendre un exemple stupide ci-dessous ( Fiddle de Postgres )

WITH R
     AS (SELECT 0 AS N
         UNION
         SELECT ( N + 1 )%10
         FROM   R)
SELECT N
FROM   R 

Changer le UNION a UNION ALL et l'ajout d'un DISTINCT à la fin ne vous sauvera pas de la récursion infinie.

Mais vous pouvez l'implémenter comme

CREATE FUNCTION dbo.F ()
RETURNS @R TABLE(n INT PRIMARY KEY WITH (IGNORE_DUP_KEY = ON))
AS
  BEGIN
      INSERT INTO @R
      VALUES      (0); --anchor

      WHILE @@ROWCOUNT > 0
        BEGIN
            INSERT INTO @R
            SELECT ( N + 1 )%10
            FROM   @R
        END

      RETURN
  END

GO

SELECT *
FROM   dbo.F () 

Les utilisations ci-dessus IGNORE_DUP_KEY pour éliminer les doublons. Si la liste des colonnes est trop large pour être indexée, il faut utiliser la méthode suivante DISTINCT y NOT EXISTS au lieu de. Vous voudrez probablement aussi un paramètre pour définir le nombre maximum de récursions et éviter les boucles infinies.

Answer 2

C'est une pure spéculation, mais je dirais que l'UNION ALL garantit que le résultat de chaque itération peut être calculé individuellement. Essentiellement, il garantit qu'une itération ne peut pas interférer avec une autre.

Une UNION nécessiterait une opération de tri en arrière-plan qui pourrait modifier le résultat des itérations précédentes. Le programme ne devrait pas modifier l'état d'un appel précédent dans la pile d'appels, il devrait interagir avec lui en utilisant des paramètres d'entrée et le résultat de l'itération suivante (dans un cadre procédural). Ceci devrait probablement s'appliquer aux opérations basées sur des ensembles, donc aux CTE récursifs de SQL Server.

Je peux me tromper, les brain-dumps de fin de soirée ne sont pas fiables à 100% :)

Edit (juste une autre pensée) :

Quand une récursion commence, on a une pile d'appels. Chaque niveau de cette pile commence à calculer son résultat, mais doit attendre le résultat de tous les appels suivants avant de pouvoir terminer et renvoyer son résultat. L'UNION essaierait d'éliminer la duplication, mais vous n'avez aucun enregistrement jusqu'à ce que vous atteigniez la condition de terminaison (et la finale serait construite de bas en haut), mais le résultat de l'appel suivant est requis par ceux qui sont au-dessus de lui. L'UNION serait réduite à un DISTINCT à la toute fin.