Accueil › SQL & bases de données › WITH RECURSIVE : hiérarchies et graphes
WITH RECURSIVE : hiérarchies et graphes
Sous-requêtes et ensemblesintermediaire
Certaines données sont des arbres : catégories imbriquées, hiérarchie d'employés, fil de commentaires, nomenclature de produits. Leur profondeur est variable, donc aucune jointure fixe ne peut les parcourir.
WITH RECURSIVE arbre AS (
-- Cas de base : les catégories racines
SELECT id, nom, parent_id, 1 AS profondeur, nom::text AS chemin
FROM categorie
WHERE parent_id IS NULL
UNION ALL
-- Étape : les enfants du niveau précédent
SELECT c.id, c.nom, c.parent_id, a.profondeur + 1, a.chemin || ' > ' || c.nom
FROM categorie c
JOIN arbre a ON c.parent_id = a.id
)
SELECT repeat(' ', profondeur - 1) || nom AS arborescence, chemin
FROM arbre
ORDER BY chemin;
Le mécanisme est simple : le cas de base produit un premier lot de lignes, l'étape récursive produit le lot suivant à partir de celui-ci, et ainsi de suite jusqu'à ce qu'une étape ne renvoie plus rien.
D'où le danger principal : si les données contiennent un cycle (A pointe vers B qui pointe vers A), la requête ne s'arrête jamais et sature la mémoire puis le disque. Deux protections : accumuler le chemin parcouru pour exclure les nœuds déjà vus, ou borner la profondeur.
Pour une profondeur fixe et connue, restez sur des auto-jointures : c'est plus simple et souvent plus rapide.
Les termes à connaître
- WITH RECURSIVE
Un CTE qui se référence lui-même. Il s'écrit en deux parties reliées par
UNION ALL: un point de départ (cas de base) et une étape qui s'appuie sur le résultat précédent.- Cas de base
La première requête du
UNION ALL: les lignes de départ (la racine d'un arbre, le nœud initial d'un graphe). Sans elle, la récursion n'a rien à traiter.- Étape récursive
La seconde requête, qui référence le CTE lui-même. Elle produit le niveau suivant à partir du niveau courant, jusqu'à ne plus rien renvoyer.
- UNION ALL vs UNION
UNION ALLconserve les doublons et est la forme normale ;UNIONdédoublonne à chaque étape, ce qui coûte cher mais peut arrêter des cycles.- Cycle
Un graphe où un chemin revient sur lui-même : la récursion ne s'arrête jamais. On l'évite en accumulant le chemin parcouru, ou avec la clause
CYCLE(PostgreSQL 14+).- Profondeur
Le niveau atteint dans la hiérarchie. On la calcule en incrémentant un compteur à chaque étape — utile pour afficher l'arborescence et pour se protéger d'une récursion trop profonde.
Cette page présente la partie essentielle de la leçon. Les exemples commentés, les pièges courants et les trois questions de quiz sont dans l'application.