Docs SQLite exécutables : CTE récursives

Q: Qu'est-ce qu'une CTE récursive en SQLite ?

Une CTE récursive est une requête WITH RECURSIVE qui construit son résultat en se référant à elle-même de façon répétée. Elle se compose de deux parties reliées par un UNION ALL : une requête d'ancrage qui produit les lignes de départ, et une requête récursive qui génère de nouvelles lignes à partir de l'étape précédente. SQLite réexécute la partie récursive jusqu'à ce qu'elle ne renvoie plus aucune nouvelle ligne.

Q: Quand utiliser WITH RECURSIVE en SQLite ?

Dès que vous devez parcourir un arbre ou un graphe (employés et managers, catégories et sous-catégories, fils de commentaires) ou générer une suite (toutes les dates d'une plage, les nombres de 1 à 100). Les jointures classiques suffisent pour un ou deux niveaux ; une CTE récursive gère une profondeur arbitraire, sans la connaître à l'avance.

Q: Comment éviter une boucle infinie dans une CTE récursive SQLite ?

Assurez-vous que la requête récursive a une condition d'arrêt : une clause WHERE qui finit par ne renvoyer aucune ligne, ou un compteur que vous plafonnez. Pour les graphes contenant des cycles, gardez le chemin déjà visité dans une colonne et excluez les lignes qui s'y trouvent déjà. Et par sécurité, ajoutez un LIMIT à la requête englobante pour qu'une récursion qui s'emballe ne puisse pas saturer la mémoire.

La récursivité en SQL paraît bizarre — jusqu'à ce qu'on la voie en action

La plupart des requêtes renvoient des lignes à partir de données qui existent déjà. Une CTE récursive en SQLite, c'est tout autre chose : elle construit ses lignes en réinjectant sa propre sortie comme entrée, étape après étape, jusqu'à ce qu'il n'y ait plus rien à ajouter. C'est comme ça qu'on parcourt un arbre de profondeur inconnue, ou qu'on génère les nombres de 1 à 100 sans avoir de table de nombres sous la main.

La structure reste toujours la même :

WITH RECURSIVE name(columns) AS (
    -- ancre : les lignes de départ
    SELECT ...
    UNION ALL
    -- récursif : lignes dérivées de l'étape précédente
    SELECT ... FROM name WHERE ...
)
SELECT * FROM name;

L'ancre en haut, UNION ALL, puis la requête récursive en dessous. SQLite exécute l'ancre une seule fois, puis enchaîne la partie récursive — à chaque tour, elle réutilise les lignes produites au tour précédent — jusqu'à ce qu'aucune nouvelle ligne ne soit renvoyée. Là, elle s'arrête.

Compter de 1 à 10

La CTE récursive la plus simple sert à générer une série de nombres. Pas besoin de table :

WITH RECURSIVE counter(n) AS (
    SELECT 1
    UNION ALL
    SELECT n + 1 FROM counter WHERE n < 10
)
SELECT n FROM counter;

Déroulons-le étape par étape :

L'ancre produit une ligne : n = 1.
L'étape récursive prend cette ligne, calcule n + 1 = 2, et comme 2 < 10 est vrai, elle conserve la ligne.
L'itération suivante part de n = 2 et produit n = 3. Et ainsi de suite.
Quand n atteint 10, 10 < 10 devient faux : l'étape récursive ne renvoie plus aucune ligne et SQLite s'arrête.

Le WHERE n < 10 joue le rôle de condition d'arrêt. Sans lui, la requête tourne indéfiniment.

Générer une plage de dates avec WITH RECURSIVE

Même principe, mais très pratique pour les rapports du quotidien : remplir chaque jour d'une période, y compris ceux où il ne s'est rien passé.

WITH RECURSIVE days(d) AS (
    SELECT date('2024-01-01')
    UNION ALL
    SELECT date(d, '+1 day') FROM days WHERE d < '2024-01-07'
)
SELECT d FROM days;

Pour bien compter les jours sans événement, on fait généralement un LEFT JOIN avec une table d'événements. Un simple GROUP BY date saute purement et simplement les jours vides ; avec la série de dates, vous obtenez une ligne par jour, qu'il y ait eu de l'activité ou non.

Parcourir un arbre parent-enfant

Le cas d'école par excellence. Voici une table d'employés où chaque ligne pointe vers son manager :

CREATE TABLE employees (
    id INTEGER PRIMARY KEY,
    name TEXT NOT NULL,
    manager_id INTEGER REFERENCES employees(id)
);

INSERT INTO employees VALUES
    (1, 'Ada',    NULL),
    (2, 'Boris',  1),
    (3, 'Carla',  1),
    (4, 'Diego',  2),
    (5, 'Elena',  2),
    (6, 'Farouk', 3);

WITH RECURSIVE org(id, name, manager_id, depth) AS (
    SELECT id, name, manager_id, 0
    FROM employees
    WHERE manager_id IS NULL
    UNION ALL
    SELECT e.id, e.name, e.manager_id, org.depth + 1
    FROM employees e
    JOIN org ON e.manager_id = org.id
)
SELECT printf('%.*c%s', depth * 2, ' ', name) AS arbre
FROM org;

L'ancre sélectionne la racine (la personne sans manager). L'étape récursive rejoint la table employees avec la CTE elle-même pour retrouver toutes les lignes dont le manager_id correspond à un id déjà présent dans la CTE. Chaque itération descend d'un niveau supplémentaire. La colonne depth n'est qu'un compteur ajouté pour indenter l'affichage.

Cette approche fonctionne pour des arbres de n'importe quelle profondeur. Deux niveaux, dix niveaux — la requête reste identique.

Remonter tous les ancêtres d'une ligne donnée

Inversons le sens du parcours. Plutôt que de descendre depuis la racine, on remonte vers le haut à partir d'un employé précis pour reconstituer toute sa chaîne hiérarchique :

CREATE TABLE employees (
    id INTEGER PRIMARY KEY,
    name TEXT NOT NULL,
    manager_id INTEGER REFERENCES employees(id)
);

INSERT INTO employees VALUES
    (1, 'Ada',    NULL),
    (2, 'Boris',  1),
    (3, 'Carla',  1),
    (4, 'Diego',  2),
    (5, 'Elena',  2),
    (6, 'Farouk', 3);

WITH RECURSIVE chain(id, name, manager_id) AS (
    SELECT id, name, manager_id
    FROM employees
    WHERE name = 'Diego'
    UNION ALL
    SELECT e.id, e.name, e.manager_id
    FROM employees e
    JOIN chain ON chain.manager_id = e.id
)
SELECT name FROM chain;

L'ancre, c'est l'employé de départ. À chaque étape récursive, on remonte vers le parent. SQLite s'arrête tout seul une fois la racine atteinte : manager_id IS NULL, donc la jointure ne renvoie plus rien.

Ce schéma est très pratique pour les fils d'Ariane, les commentaires imbriqués, les chemins de catégories, ou tout ce qui demande de « remonter jusqu'en haut ».

Conditions d'arrêt et boucles infinies

Le bug le plus classique avec une CTE récursive SQLite, c'est d'oublier la condition d'arrêt — ou d'en écrire une qui ne se déclenche jamais. Comparez :

-- Boucle infinie :
WITH RECURSIVE bad(n) AS (
    SELECT 1
    UNION ALL
    SELECT n + 1 FROM bad
)
SELECT n FROM bad;

Il n'y a aucune clause WHERE qui finisse par renvoyer zéro ligne. Du coup, SQLite va joyeusement compter jusqu'à l'infini.

Deux réflexes à prendre pour éviter la boucle infinie dans une CTE récursive :

Toujours mettre une clause WHERE dans la partie récursive pour borner la progression.
Ajouter un LIMIT sur le SELECT extérieur en guise de filet de sécurité pendant le développement — comme ça, même si vous vous trompes sur la condition d'arrêt, la requête finit par se terminer.

WITH RECURSIVE counter(n) AS (
    SELECT 1
    UNION ALL
    SELECT n + 1 FROM counter
)
SELECT n FROM counter LIMIT 5;

La CTE en elle-même n'a pas de borne, mais le LIMIT 5 coupe la requête externe assez tôt. SQLite est suffisamment malin pour ne pas continuer à récurser au-delà de ce que LIMIT réclame. Pratique pour explorer, mais ne remplace pas une vraie condition d'arrêt dans du code de production.

Cycles dans les graphes

Un arbre, par définition, ne contient pas de cycle. Un graphe quelconque, en revanche, peut en contenir — et une CTE récursive naïve va alors tourner à l'infini dès que les données bouclent. La parade : garder en mémoire le chemin déjà parcouru et refuser de repasser par un nœud déjà visité :

CREATE TABLE edges (a INTEGER, b INTEGER);
INSERT INTO edges VALUES (1, 2), (2, 3), (3, 1), (3, 4);

WITH RECURSIVE walk(node, path) AS (
    SELECT 1, ',1,'
    UNION ALL
    SELECT e.b, path || e.b || ','
    FROM edges e
    JOIN walk ON e.a = walk.node
    WHERE instr(path, ',' || e.b || ',') = 0
)
SELECT node, path FROM walk;

path est une chaîne de nœuds déjà visités, séparés par des virgules. Avant d'ajouter un nouveau nœud, la clause WHERE vérifie qu'il n'y figure pas déjà. Sans ce garde-fou, le cycle 1 → 2 → 3 → 1 tournerait indéfiniment dans une boucle infinie.

SQL ne propose pas de structure « ensemble des nœuds visités » prête à l'emploi — il faut la construire soi-même, en général sous forme de chaîne ou en faisant une jointure sur la CTE en cours de construction.

CTE récursive ou auto-jointure ?

Si vous n'avez besoin de descendre que d'un ou deux niveaux, une auto-jointure reste plus simple et plus rapide :

CREATE TABLE employees (
    id INTEGER PRIMARY KEY,
    name TEXT NOT NULL,
    manager_id INTEGER REFERENCES employees(id)
);

INSERT INTO employees VALUES
    (1, 'Ada',    NULL),
    (2, 'Boris',  1),
    (3, 'Carla',  1),
    (4, 'Diego',  2),
    (5, 'Elena',  2),
    (6, 'Farouk', 3);

SELECT e.name AS employé, m.name AS responsable
FROM employees e
LEFT JOIN employees m ON e.manager_id = m.id;

Ça règle la question « qui est le manager direct de chaque personne ». Mais si vous voulez « toutes les personnes qui remontent jusqu'à Ada, peu importe la profondeur » — quand on ne connaît pas la profondeur — seule une CTE récursive s'en sort proprement. Choisissez l'outil en fonction de la profondeur dont vous avez besoin :

Profondeur fixe et faible : une auto-jointure, voire deux ou trois.
Profondeur inconnue ou quelconque : WITH RECURSIVE.

Comment se la représenter

Une CTE récursive SQLite, c'est une boucle écrite de manière déclarative :

L'ancre (anchor) donne la valeur initiale de la boucle.
La requête récursive est le corps de la boucle : elle produit le prochain lot de lignes à partir des lignes courantes.
La condition d'arrêt est le test de sortie : quand elle ne renvoie plus aucune ligne, la boucle s'arrête.
UNION ALL accumule le tout dans le résultat final.

Une fois ce schéma en tête, la syntaxe ne paraît plus bizarre du tout. Vous êtes en train d'écrire une boucle for en SQL.

La suite : les index

Une CTE récursive parcourt beaucoup de lignes, et la jointure à l'intérieur de l'étape récursive est rejouée à chaque itération. Si la colonne de jointure n'est pas indexée, les performances s'écroulent très vite. Les index, c'est le prochain chapitre, et manager_id est typiquement le genre de colonne qui en tire un énorme bénéfice.

Questions fréquentes

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

Une CTE récursive est une requête WITH RECURSIVE qui construit son résultat en se référant à elle-même de façon répétée. Elle se compose de deux parties reliées par un UNION ALL : une requête d'ancrage qui produit les lignes de départ, et une requête récursive qui génère de nouvelles lignes à partir de l'étape précédente. SQLite réexécute la partie récursive jusqu'à ce qu'elle ne renvoie plus aucune nouvelle ligne.

Quand utiliser WITH RECURSIVE en SQLite ?