Comment fonctionne la récursivité SQL?

Venant à SQL à partir d'autres langages de programmation, la structure d'une requête récursive semble plutôt étrange. Parcourez-le étape par étape, et il semble s'effondrer.

Prenons l'exemple simple suivant:

CREATE TABLE #NUMS
(N BIGINT);

INSERT INTO #NUMS
VALUES (3), (5), (7);

WITH R AS
(
    SELECT N FROM #NUMS
    UNION ALL
    SELECT N*N AS N FROM R WHERE N*N < 10000000
)
SELECT N FROM R ORDER BY N;

Passons en revue.

Tout d'abord, le membre d'ancrage s'exécute et l'ensemble de résultats est placé dans R. Donc R est initialisé à {3, 5, 7}.

Ensuite, l'exécution tombe en dessous de UNION ALL et le membre récursif est exécuté pour la première fois. Il s'exécute sur R (c'est-à-dire sur le R que nous avons actuellement en main: {3, 5, 7}). Il en résulte {9, 25, 49}.

Que fait-il avec ce nouveau résultat? Ajoute-t-il {9, 25, 49} à l'existant {3, 5, 7}, étiquete l'union résultante R, puis poursuit la récursivité à partir de là? Ou redéfinit-il R pour n'être que ce nouveau résultat {9, 25, 49} et fait-il tout l'union plus tard?

Aucun de ces choix n'a de sens.

Si R est maintenant {3, 5, 7, 9, 25, 49} et que nous exécutons l'itération suivante de la récursivité, nous nous retrouverons avec {9, 25, 49, 81, 625, 2401} et nous avons perdu {3, 5, 7}.

Si R n'est plus que {9, 25, 49}, alors nous avons un problème d'étiquetage erroné. R est compris comme l'union de l'ensemble de résultats de membre d'ancrage et de tous les ensembles de résultats de membre récursif suivants. Alors que {9, 25, 49} n'est qu'une composante de R. Ce n'est pas le R complet que nous avons accumulé jusqu'à présent. Par conséquent, écrire le membre récursif comme sélectionnant dans R n'a aucun sens.

J'apprécie certainement ce que @Max Vernon et @Michael S. ont détaillé ci-dessous. À savoir que (1) tous les composants sont créés jusqu'à la limite de récursivité ou l'ensemble nul, puis (2) tous les composants sont réunis. C'est ainsi que je comprends que la récursion SQL fonctionne réellement.

Si nous repensions SQL, nous appliquerions peut-être une syntaxe plus claire et explicite, quelque chose comme ceci:

WITH R AS
(
    SELECT   N
    INTO     R[0]
    FROM     #NUMS
    UNION ALL
    SELECT   N*N AS N
    INTO     R[K+1]
    FROM     R[K]
    WHERE    N*N < 10000000
)
SELECT N FROM R ORDER BY N;

Un peu comme une preuve inductive en mathématiques.

Le problème avec la récursion SQL telle qu'elle se présente actuellement est qu'elle est écrite de manière confuse. La façon dont il est écrit indique que chaque composant est formé en sélectionnant parmi R, mais cela ne signifie pas le R complet qui a été (ou semble avoir été) construit jusqu'à présent. Cela signifie simplement le composant précédent.

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

1. Divisez l'expression CTE en membres d'ancrage et membres récursifs.
2. Exécutez le ou les membres d'ancrage créant le premier appel ou jeu de résultats de base (T0).
3. Exécutez le ou les membres récursifs avec Ti comme entrée et Ti + 1 comme sortie.
4. Répétez l'étape 3 jusqu'à ce qu'un ensemble vide soit renvoyé.
5. Renvoie l'ensemble de résultats. Il s'agit d'un UNION TOUS de T0 à Tn.

Ainsi, chaque niveau n'a en entrée que le niveau supérieur et non l'ensemble des résultats accumulés jusqu'à présent.

Ce qui précède est la façon dont cela fonctionne logiquement . Les CTE physiquement récursifs sont actuellement toujours implémentés avec des boucles imbriquées et une bobine de pile dans SQL Server. Ceci est décrit ici et ici et signifie que dans la pratique, chaque élément récursif ne fonctionne qu'avec la ligne parent du niveau précédent, pas avec le niveau entier. Mais les diverses restrictions sur la syntaxe autorisée dans les CTE récursifs signifient que cette approche fonctionne.

Si vous supprimez le ORDER BYde votre requête, les résultats sont classés comme suit

+---------+
|    N    |
+---------+
|       3 |
|       5 |
|       7 |
|      49 |
|    2401 |
| 5764801 |
|      25 |
|     625 |
|  390625 |
|       9 |
|      81 |
|    6561 |
+---------+

En effet, le plan d'exécution fonctionne de manière très similaire à ce qui suit C#

using System;
using System.Collections.Generic;
using System.Diagnostics;

public class Program
{
    private static readonly Stack<dynamic> StackSpool = new Stack<dynamic>();

    private static void Main(string[] args)
    {
        //temp table #NUMS
        var nums = new[] { 3, 5, 7 };

        //Anchor member
        foreach (var number in nums)
            AddToStackSpoolAndEmit(number, 0);

        //Recursive part
        ProcessStackSpool();

        Console.WriteLine("Finished");
        Console.ReadLine();
    }

    private static void AddToStackSpoolAndEmit(long number, int recursionLevel)
    {
        StackSpool.Push(new { N = number, RecursionLevel = recursionLevel });
        Console.WriteLine(number);
    }

    private static void ProcessStackSpool()
    {
        //recursion base case
        if (StackSpool.Count == 0)
            return;

        var row = StackSpool.Pop();

        int thisLevel = row.RecursionLevel + 1;
        long thisN = row.N * row.N;

        Debug.Assert(thisLevel <= 100, "max recursion level exceeded");

        if (thisN < 10000000)
            AddToStackSpoolAndEmit(thisN, thisLevel);

        ProcessStackSpool();
    }
}

NB1: comme ci-dessus au moment où le premier enfant du membre d'ancrage 3est en train de traiter toutes les informations sur ses frères 5et sœurs, et7 , et leurs descendants, ont déjà été jetées de la bobine et ne sont plus accessibles.

NB2: Le C # ci-dessus a la même sémantique globale que le plan d'exécution mais le flux dans le plan d'exécution n'est pas identique, car là, les opérateurs travaillent de manière pipeline. Il s'agit d'un exemple simplifié pour démontrer l'essentiel de l'approche. Voir les liens précédents pour plus de détails sur le plan lui-même.

NB3: Le spool de pile lui-même est apparemment implémenté comme un index cluster non unique avec une colonne clé de niveau de récursivité et des uniqueificateurs ajoutés si nécessaire ( source )

C'est juste une supposition (semi) éduquée, et c'est probablement complètement faux. Question intéressante, au fait.

T-SQL est un langage déclaratif; peut-être qu'un CTE récursif est traduit en une opération de style curseur où les résultats du côté gauche de l'UNION ALL sont ajoutés dans une table temporaire, puis le côté droit de l'UNION ALL est appliqué aux valeurs du côté gauche.

Ainsi, nous insérons d'abord la sortie du côté gauche de l'UNION ALL dans le jeu de résultats, puis nous insérons les résultats du côté droit de l'UNION ALL appliqué au côté gauche, et l'insérons dans le jeu de résultats. Le côté gauche est ensuite remplacé par la sortie du côté droit, et le côté droit est appliqué à nouveau au "nouveau" côté gauche. Quelque chose comme ça:

1. {3,5,7} -> jeu de résultats
2. les instructions récursives s'appliquent à {3,5,7}, soit {9,25,49}. {9,25,49} est ajouté au jeu de résultats et remplace le côté gauche de UNION ALL.
3. les instructions récursives s'appliquaient à {9,25,49}, soit {81,625,2401}. {81 625 2401} est ajouté au jeu de résultats et remplace le côté gauche de UNION ALL.
4. les instructions récursives s'appliquaient à {81,625,2401}, qui est {6561,390625,5764801}. {6561,390625,5764801} est ajouté au jeu de résultats.
5. Le curseur est terminé, car la prochaine itération a pour résultat que la clause WHERE renvoie false.

Vous pouvez voir ce comportement dans le plan d'exécution pour le CTE récursif:

C'est l'étape 1 ci-dessus, où le côté gauche de UNION ALL est ajouté à la sortie:

C'est le côté droit de l'UNION ALL où la sortie est concaténée au jeu de résultats:

La documentation de SQL Server , qui mentionne T _i et T _{i + 1} , n'est ni très compréhensible, ni une description précise de l'implémentation réelle.

L'idée de base est que la partie récursive de la requête examine tous les résultats précédents, mais une seule fois .

Il pourrait être utile de voir comment d'autres bases de données implémentent cela (pour obtenir le même résultat). La documentation Postgres indique:

Évaluation des requêtes récursives

1. Évaluez le terme non récursif. Pour UNION(mais pas UNION ALL), supprimez les lignes en double. Incluez toutes les lignes restantes dans le résultat de la requête récursive et placez-les également dans une table de travail temporaire .
2. Tant que la table de travail n'est pas vide, répétez ces étapes:
   1. Évaluez le terme récursif en substituant le contenu actuel de la table de travail à l'auto-référence récursive. Pour UNION(mais pas UNION ALL), supprimez les lignes en double et les lignes qui dupliquent toute ligne de résultat précédente. Incluez toutes les lignes restantes dans le résultat de la requête récursive et placez-les également dans une table intermédiaire temporaire .
   2. Remplacez le contenu de la table de travail par le contenu de la table intermédiaire, puis videz la table intermédiaire.

Remarque
À strictement parler, ce processus est une itération et non une récursivité, mais RECURSIVEc'est la terminologie choisie par le comité des normes SQL.

La documentation SQLite suggère une implémentation légèrement différente, et cet algorithme une ligne à la fois pourrait être le plus simple à comprendre:

L'algorithme de base pour calculer le contenu de la table récursive est le suivant:

1. Exécutez le initial-selectet ajoutez les résultats à une file d'attente.
2. Alors que la file d'attente n'est pas vide:
   1. Extrayez une seule ligne de la file d'attente.
   2. Insérez cette seule ligne dans la table récursive
   3. Imaginez que la seule ligne qui vient d'être extraite est la seule ligne de la table récursive et exécutez le recursive-select, en ajoutant tous les résultats à la file d'attente.

La procédure de base ci-dessus peut être modifiée par les règles supplémentaires suivantes:

• Si un opérateur UNION connecte le initial-selectà recursive-select, alors n'ajoutez des lignes à la file d'attente que si aucune ligne identique n'a été précédemment ajoutée à la file d'attente. Les lignes répétées sont supprimées avant d'être ajoutées à la file d'attente même si les lignes répétées ont déjà été extraites de la file d'attente par l'étape de récursivité. Si l'opérateur est UNION ALL, toutes les lignes générées par le initial-selectet le recursive-selectsont toujours ajoutées à la file d'attente même si elles sont répétées.
  […]

Mes connaissances concernent spécifiquement DB2, mais la lecture des diagrammes d'explication semble être la même avec SQL Server.

Le plan vient d'ici:

Voir sur Coller le plan

L'optimiseur n'exécute pas littéralement une union all pour chaque requête récursive. Il prend la structure de la requête et affecte la première partie de l'union à un "membre d'ancrage", puis il parcourt la seconde moitié de l'union tout (appelé "membre récursif" de manière récursive jusqu'à ce qu'il atteigne les limites définies. Après la récursivité est terminée, l'optimiseur joint tous les enregistrements.

L'optimiseur le prend simplement comme une suggestion pour effectuer une opération prédéfinie.