CTE récursive SQL : interroger des hiérarchies

Leçon 6.5 · Temps de lecture : ~9 min · Exercices pratiques ↓

Une CTE récursive SQL est une expression de table commune qui fait référence à elle-même : une seule requête peut ainsi parcourir une hiérarchie de n'importe quelle profondeur, comme un organigramme, un arbre de catégories ou un fil de commentaires. Dans cette leçon, vous apprendrez la syntaxe WITH RECURSIVE, comment le membre d'ancrage et le membre récursif fonctionnent ensemble, comment trouver tous les subordonnés ou tous les responsables d'un employé, comment construire un chemin dans l'arbre et comment arrêter une récursion qui s'emballe.

Dans la leçon précédente, une CTE était une étape nommée de la requête, exécutée une seule fois. Les données hiérarchiques demandent davantage. Si chaque ligne d'employé stocke l'id de son responsable, un JOIN trouve les subordonnés directs, un deuxième JOIN le niveau suivant, et ainsi de suite, mais on ne sait pas à l'avance combien il y a de niveaux. Une CTE récursive répète la jointure pour vous jusqu'à ce qu'il n'y ait plus rien à trouver.

Les exemples utilisent la syntaxe de MySQL 8.0 et fonctionnent aussi dans MariaDB 10.2+. Les bases d'exemple de SQLtest sont en lecture seule : exécutez les exemples dans le bac à sable sur une base sans données d'exemple, chacun crée sa propre table.

Comment fonctionne une CTE récursive

Une CTE récursive comporte deux parties reliées par UNION ALL :

WITH RECURSIVE cte_name AS (
    -- Membre d'ancrage : les lignes de départ
    SELECT ...
    FROM table_name
    WHERE start_condition

    UNION ALL

    -- Membre récursif : le niveau suivant, trouvé à partir du précédent
    SELECT ...
    FROM table_name
    INNER JOIN cte_name ON join_condition
)
SELECT * FROM cte_name;

• WITH RECURSIVE indique à la base de données que la CTE fait référence à elle-même.
• Le membre d'ancrage s'exécute une fois et renvoie les lignes de départ, par exemple le dirigeant.
• Le membre récursif fait référence à la CTE par son nom. À chaque exécution, il ne voit que les lignes produites par l'itération précédente.
• La récursion s'arrête quand une itération ne renvoie aucune ligne. Les lignes de toutes les itérations forment le résultat.

L'exemple le plus simple : une suite de nombres

WITH RECURSIVE numbers AS (
    SELECT 1 AS n
    UNION ALL
    SELECT n + 1
    FROM numbers
    WHERE n < 5
)
SELECT n FROM numbers;

Résultat : 5 lignes avec les nombres 1, 2, 3, 4, 5.

L'ancrage renvoie 1. La première itération lit 1 et renvoie 2, la suivante renvoie 3, et ainsi de suite. Quand l'itération précédente a produit 5, la condition n < 5 est fausse, le membre récursif ne renvoie rien et la requête se termine. La condition WHERE est la condition d'arrêt : sans elle, la récursion ne s'arrêterait jamais.

Données d'exemple : un organigramme

Une hiérarchie est généralement stockée comme une liste d'adjacence : chaque ligne référence son parent dans la même table. Ici, manager_id pointe vers un autre employé, et le PDG n'a pas de responsable :

CREATE TABLE employee (
    employee_id INT PRIMARY KEY,
    employee_name VARCHAR(100) NOT NULL,
    manager_id INT,
    title VARCHAR(100)
);

INSERT INTO employee VALUES
    (1, 'Alice Johnson', NULL, 'CEO'),
    (2, 'Bob Smith', 1, 'VP of Engineering'),
    (3, 'Carol White', 1, 'VP of Sales'),
    (4, 'David Brown', 2, 'Engineering Manager'),
    (5, 'Eve Davis', 2, 'Engineering Manager'),
    (6, 'Frank Miller', 3, 'Sales Manager'),
    (7, 'Grace Wilson', 4, 'Senior Developer'),
    (8, 'Henry Moore', 4, 'Developer'),
    (9, 'Ivy Taylor', 5, 'Developer'),
    (10, 'Jack Anderson', 6, 'Sales Representative');

Trouver tous les subordonnés

Qui dépend de Bob Smith, directement ou indirectement ? L'ancrage sélectionne Bob ; le membre récursif trouve les employés dont le responsable est au niveau précédent :

WITH RECURSIVE subordinates AS (
    SELECT employee_id, employee_name, title, 0 AS level
    FROM employee
    WHERE employee_name = 'Bob Smith'

    UNION ALL

    SELECT e.employee_id, e.employee_name, e.title, s.level + 1
    FROM employee AS e
    INNER JOIN subordinates AS s ON e.manager_id = s.employee_id
)
SELECT employee_id, employee_name, title, level
FROM subordinates
ORDER BY level, employee_name;

Résultat : 6 lignes : Bob Smith au niveau 0, David Brown et Eve Davis au niveau 1, Grace Wilson, Henry Moore et Ivy Taylor au niveau 2.

La colonne level compte les itérations : elle vaut 0 dans l'ancrage et augmente de un à chaque niveau. Pour exclure Bob lui-même, ajoutez WHERE level > 0 à la requête finale.

Construire l'arbre complet avec un chemin

Pour afficher tout l'organigramme, partez de l'employé sans responsable et collectez le chemin depuis le sommet jusqu'à chaque personne :

WITH RECURSIVE org_chart AS (
    SELECT
        employee_id,
        employee_name,
        title,
        0 AS level,
        CAST(employee_name AS CHAR(500)) AS path
    FROM employee
    WHERE manager_id IS NULL

    UNION ALL

    SELECT
        e.employee_id,
        e.employee_name,
        e.title,
        oc.level + 1,
        CONCAT(oc.path, ' > ', e.employee_name)
    FROM employee AS e
    INNER JOIN org_chart AS oc ON e.manager_id = oc.employee_id
)
SELECT
    CONCAT(REPEAT('- ', level), employee_name) AS hierarchy,
    title,
    path
FROM org_chart
ORDER BY path;

Résultat : les 10 employés dans l'ordre de l'arbre, chacun avec la chaîne de responsables au-dessus de lui.

Deux détails font fonctionner la requête :

• Le tri par chemin place chaque employé juste après son responsable : le résultat se lit comme un arbre.
• CAST(... AS CHAR(500)) dans l'ancrage. Les types des colonnes d'une CTE récursive viennent du membre d'ancrage. Sans conversion, path aurait le type de employee_name, VARCHAR(100), et dès qu'un chemin dépasserait 100 caractères, MySQL s'arrêterait avec l'erreur « Data too long for column 'path' ». Rendez assez larges, dès l'ancrage, les colonnes de texte qui grandissent pendant la récursion.

Remonter : tous les responsables d'un employé

La même technique fonctionne dans l'autre sens. Pour trouver la chaîne de responsables au-dessus d'Ivy Taylor, partez d'elle et joignez chaque ligne à son parent : la condition de jointure est inversée.

WITH RECURSIVE managers AS (
    SELECT employee_id, employee_name, manager_id, 0 AS steps_up
    FROM employee
    WHERE employee_name = 'Ivy Taylor'

    UNION ALL

    SELECT e.employee_id, e.employee_name, e.manager_id, m.steps_up + 1
    FROM employee AS e
    INNER JOIN managers AS m ON e.employee_id = m.manager_id
)
SELECT employee_name, steps_up
FROM managers
ORDER BY steps_up;

Résultat : 4 lignes : Ivy Taylor (0), Eve Davis (1), Bob Smith (2), Alice Johnson (3).

La récursion s'arrête à Alice Johnson : son manager_id vaut NULL, la jointure ne trouve donc rien.

Arrêter une récursion qui s'emballe

Une CTE récursive se termine quand une itération ne renvoie aucune ligne. Deux situations enfreignent cette règle : une condition d'arrêt manquante, comme une suite de nombres sans WHERE, et les cycles dans les données, par exemple quand A est par erreur le responsable de B et B celui de A. Les mêmes lignes sont alors trouvées encore et encore.

Limiter la profondeur

Ajoutez une condition sur le niveau dans le membre récursif :

WITH RECURSIVE subordinates AS (
    SELECT employee_id, employee_name, 0 AS level
    FROM employee
    WHERE manager_id IS NULL

    UNION ALL

    SELECT e.employee_id, e.employee_name, s.level + 1
    FROM employee AS e
    INNER JOIN subordinates AS s ON e.manager_id = s.employee_id
    WHERE s.level < 2
)
SELECT employee_name, level
FROM subordinates;

Résultat : 6 lignes : le PDG, deux vice-présidents et trois managers ; les niveaux au-delà de 2 ne sont pas développés.

MySQL a aussi une limite de sécurité : la variable cte_max_recursion_depth (1000 par défaut). Une requête qui a besoin de plus d'itérations échoue avec « Recursive query aborted after 1001 iterations ». Pour une récursion légitimement profonde, augmentez-la avec SET SESSION cte_max_recursion_depth = 10000;. MariaDB se comporte autrement : quand elle atteint max_recursive_iterations, elle s'arrête sans erreur et renvoie les lignes trouvées jusque-là, si bien qu'un résultat incomplet peut passer inaperçu.

Ignorer les lignes déjà visitées

Une limite de profondeur arrête un cycle, mais renvoie quand même des lignes répétées. Pour empêcher le cycle lui-même, conservez la liste des id visités et n'entrez pas dans une ligne déjà présente dans le chemin :

WITH RECURSIVE org_chart AS (
    SELECT employee_id, employee_name, CAST(employee_id AS CHAR(500)) AS visited
    FROM employee
    WHERE manager_id IS NULL

    UNION ALL

    SELECT e.employee_id, e.employee_name, CONCAT(oc.visited, ',', e.employee_id)
    FROM employee AS e
    INNER JOIN org_chart AS oc ON e.manager_id = oc.employee_id
    WHERE FIND_IN_SET(e.employee_id, oc.visited) = 0
)
SELECT employee_name, visited
FROM org_chart;

Résultat : 10 lignes ; par exemple, Ivy Taylor a visited = 1,2,5,9.

FIND_IN_SET() renvoie la position d'une valeur dans une liste séparée par des virgules, ou 0 si elle n'y est pas. PostgreSQL 14+ propose pour cela une clause intégrée CYCLE.

Règles et différences entre bases

• Le membre récursif doit faire référence à la CTE exactement une fois, dans FROM ou JOIN, pas dans une sous-requête.
• Dans MySQL, le membre récursif ne peut pas utiliser de fonctions d'agrégation ou de fenêtrage, ni GROUP BY, ORDER BY ou DISTINCT. Agrégez plutôt dans la requête finale.
• UNION ALL garde toutes les lignes et c'est le choix habituel. UNION supprime les lignes en double et, par effet de bord, arrête un cycle quand les lignes répétées sont identiques.

Pour de meilleures performances, indexez la colonne utilisée dans la jointure récursive, comme manager_id.

Points clés :

• Une CTE récursive fait référence à elle-même et parcourt une hiérarchie de n'importe quelle profondeur avec WITH RECURSIVE.
• Le membre d'ancrage renvoie les lignes de départ ; le membre récursif trouve le niveau suivant à partir du précédent ; la récursion s'arrête quand une itération ne renvoie aucune ligne.
• La jointure e.manager_id = cte.employee_id descend dans l'arbre ; e.employee_id = cte.manager_id remonte.
• Un compteur level et une colonne path montrent la position de chaque ligne ; convertissez dès l'ancrage les colonnes de texte qui grandissent.
• Protégez les requêtes par une limite de profondeur ou une liste d'id visités ; MySQL s'arrête après cte_max_recursion_depth itérations.

Questions fréquentes

Qu'est-ce qu'une CTE récursive en SQL ?

C'est une expression de table commune qui fait référence à elle-même. Elle se compose d'un membre d'ancrage qui renvoie les lignes de départ et d'un membre récursif exécuté de façon répétée, chaque fois sur les lignes de l'itération précédente, jusqu'à ce qu'aucune nouvelle ligne n'apparaisse. On l'utilise pour les hiérarchies et les graphes : organigrammes, arbres de catégories, itinéraires.

Comment arrêter une récursion infinie dans une CTE récursive ?

Ajoutez une condition d'arrêt au membre récursif, comme WHERE level < 10, et protégez-vous des cycles dans les données en suivant les id visités. MySQL interrompt aussi une requête après cte_max_recursion_depth itérations (1000 par défaut) et SQL Server après MAXRECURSION (100 par défaut) ; MariaDB s'arrête silencieusement après max_recursive_iterations.

MySQL prend-il en charge les CTE récursives ?

Oui, depuis MySQL 8.0 et MariaDB 10.2, avec la syntaxe WITH RECURSIVE. Les anciennes versions de MySQL n'ont pas de CTE ; on y parcourait les hiérarchies avec des procédures stockées ou un nombre fixe d'auto-jointures.

Pourquoi ma CTE récursive échoue-t-elle avec « Data too long for column » ?

Les colonnes d'une CTE récursive prennent leurs types du membre d'ancrage. Si le membre récursif construit une chaîne plus longue, comme un chemin, elle ne tient plus. Convertissez la colonne dans l'ancrage vers un type plus large, par exemple CAST(name AS CHAR(500)).