Un Common Table Expression (CTE) récursif en SQL vous permet de parcourir des données hiérarchiques en utilisant une requête auto-référentielle qui s'exécute de manière basée sur un ensemble. La structure consiste en un membre d'ancrage (le cas de base, généralement les nœuds racines où manager_id EST NULL) et un membre récursif (la partie itérative qui rejoint le CTE sur la relation parent-enfant). Le moteur de base de données exécute de manière répétée le membre récursif jusqu’à ce qu'aucunes nouvelles lignes ne soient retournées, construisant ainsi l'ensemble de résultats de manière incrémentielle sans constructions d'itération explicites.
Cette approche exploite la nature déclarative de SQL, permettant à l'optimiseur de choisir des algorithmes de jointure efficaces (généralement des jointures par hachage ou des jointures par fusion) plutôt que le traitement ligne par ligne inhérent aux CURSOR ou aux boucles WHILE. La syntaxe utilise WITH RECURSIVE dans PostgreSQL et MySQL, ou simplement WITH dans SQL Server (où la récursivité est implicite), suivie du nom du CTE et de la liste des colonnes.
Une multinationale avec 12 000 employés devait générer des chaînes de reporting complètes pour les audits de conformité SOX. Le système existant utilisait un CURSOR T-SQL qui itérait à travers chaque employé, appelait récursivement une fonction scalaire pour trouver leur manager, et construisait la hiérarchie chaîne par chaîne. Ce processus prenait 47 minutes pour se terminer, maintenait des verrous sur la table Employees empêchant les mises à jour des RH pendant les heures de travail, et échouait fréquemment avec des erreurs de débordement de pile lors du traitement de hiérarchies profondes dépassant 100 niveaux (courantes dans la structure matricielle du département d'ingénierie).
Solution A : Optimisation du CURSOR avec des tables temporaires. L'équipe a envisagé de réécrire le curseur pour d'abord déverser les résultats dans une table temporaire, puis d'insérer en masse à la fin. Cela réduirait le temps de verrouillage de 47 minutes à environ 40 minutes. Avantages : Modifications minimales du code, modèle familier pour l'équipe existante. Inconvénients : Toujours un traitement ligne par ligne, toujours vulnérable aux débordements de pile de récursion profonds, atténue simplement plutôt que de résoudre le problème de performance.
Solution B : Type de données HierarchyID. La migration de la table pour utiliser le type HierarchyID natif de SQL Server, qui stocke les positions d'arbre sous forme de chemins encodés optimisés pour le parcours. Avantages : Récupération d'arborescence O(1), méthodes intégrées comme GetAncestor() et GetDescendant(), extrêmement rapide pour des charges de travail lourdes en lecture. Inconvénients : Nécessite une migration massive du schéma (12 000 lignes plus des données historiques), complexe à maintenir lors des réorganisations (mettre à jour un manager nécessite de recalculer tous les chemins descendants), verrouillé au fournisseur SQL Server alors que l'entreprise envisageait une migration vers PostgreSQL.
Solution C : CTE récursif avec détection de cycle. La mise en œuvre d'un CTE récursif qui joint la table des employés à elle-même sur manager_id, utilisant un tableau de chemins pour suivre les nœuds visités afin de prévenir les boucles infinies en cas de références circulaires (qui s'étaient produites deux fois en raison d'erreurs de saisie de données). Avantages : Standard ANSI SQL pur (portable vers PostgreSQL lors de la migration), exécution basée sur un ensemble réduisant le temps d'exécution à 4 minutes 12 secondes, aucun verrou de table maintenu pendant l'exécution (utilise l'isolation par instantané), gère une profondeur arbitraire sans débordement de pile, détecte automatiquement les problèmes de qualité des données (cycles).
L'équipe a choisi la Solution C. L'implémentation a utilisé un CTE récursif avec une colonne path accumulant les ID des employés en utilisant l'agrégation de tableau de PostgreSQL (ou la concaténation de chaînes dans SQL Server), avec une clause WHERE vérifiant que le nouveau manager_id n'existait pas dans le chemin accumulé. Le résultat a été une amélioration de performance de 91 %, l'élimination des verrous de production, et une détection précoce des relations de reporting circulaires qui causaient auparavant des plantages d'application.
Pourquoi un CTE récursif se termine et que se passe-t-il si les données contiennent une référence circulaire ?
Les candidats croient souvent que les CTE récursifs ont une détection de cycle intégrée, mais la récursivité standard en SQL se termine uniquement lorsque le membre récursif retourne zéro nouvelle ligne. Si l'employé A report à B, B à C, et C de retour à A, le CTE s'exécute indéfiniment (ou jusqu'à atteindre des limites d'implémentation comme les 100 niveaux de récursion par défaut de SQL Server). La solution nécessite une détection de cycle manuelle en accumulant les ID de nœuds visités dans une colonne de chemin (en utilisant des tableaux ou des chaînes délimitées) et en filtrant WHERE new_id != ALL(path_array). Les versions modernes de PostgreSQL (14+) et SQL Server (2022+) supportent la clause standard SQL:1999 CYCLE : WITH RECURSIVE cte AS (...) CYCLE id SET is_cycle USING path, qui gère cela automatiquement.
Comment le plan d'exécution diffère-t-il entre un CTE récursif et une approche basée sur un curseur, et pourquoi cela importe-t-il pour la concurrence ?
Les candidats juniors prétendent souvent que les CTE sont "plus rapides" sans comprendre le modèle d'exécution. Un CURSOR dans SQL Server ou PostgreSQL force le moteur à matérialiser un ensemble de résultats et à itérer ligne par ligne, généralement en utilisant un type de curseur Keyset ou Static qui nécessite des verrous ou des ressources de tempdb pendant toute la durée de l'itération. Cela crée des Verrous Partagés (ou des Verrous de Mise à jour) sur les tables sous-jacentes pendant toute la durée de 47 minutes dans l'exemple ci-dessus. En revanche, un CTE récursif est une seule instruction SELECT. Sous Read Committed Snapshot Isolation (RCSI) ou Snapshot Isolation, il lit une vue cohérente des données à un moment donné sans maintenir de verrous, utilisant le magasin de version à la place. L'optimiseur choisit généralement des Jointures à Boucle Imbriquée pour le membre récursif avec des opérations de Recherche d'Index sur l'index parent-enfant, rendant cela O(n log n) plutôt que O(n²) pour les approches basées sur un curseur.
Quelle est la différence entre un CTE récursif et le Modèle des Ensembles Imbriqués pour les données hiérarchiques, et quand choisir l'un plutôt que l'autre ?
Les candidats confondent souvent les méthodes de parcours avec les modèles de stockage. Un CTE récursif est une technique de parcours au moment de la requête qui fonctionne sur des Listes de Parenté (clé étrangère parent_id). Le Modèle des Ensembles Imbriqués (valeurs gauche/droite) est un modèle de conception de stockage qui pré-calcule les chemins de parcours d'arbre. Pour les charges de travail lourdes en écriture (changements fréquents de manager), les CTE récursifs sur les listes de parenté sont supérieurs car mettre à jour un seul parent_id est O(1), tandis que les ensembles imbriqués nécessitent O(n) mises à jour de toutes les valeurs de droite à droite du nœud déplacé. Pour des hiérarchies statiques lourdes en lecture (organigrammes qui changent mensuellement), les ensembles imbriqués fournissent O(1) pour la récupération de sous-arbres (WHERE left BETWEEN parent.left AND parent.right) par rapport à O(n) pour les CTE récursifs. Une approche hybride utilise des Tables de Fermeture (table séparée stockant toutes les paires ancêtres-descendants), qui offre O(1) tant pour le parcours que pour la recherche de tous les enfants, au prix de O(n²) de stockage et d'une maintenance plus complexe. Le choix dépend du ratio lecture/écriture : utilisez des CTE récursifs lorsque les écritures > 5 % des opérations ; utilisez des ensembles imbriqués ou des tables de fermeture pour des arbres principalement statiques.