Ausführbare SQLite-Docs: Rekursive CTEs

Q: Was ist eine rekursive CTE in SQLite?

Eine rekursive CTE ist eine WITH RECURSIVE-Abfrage, die ihr Ergebnis Schritt für Schritt aufbaut, indem sie sich selbst referenziert. Sie besteht aus zwei Teilen, die mit UNION ALL verknüpft werden: dem Anker, der die Startzeilen liefert, und dem rekursiven Teil, der aus den Zeilen des vorherigen Schritts neue Zeilen erzeugt. SQLite wiederholt den rekursiven Teil so lange, bis keine neuen Zeilen mehr hinzukommen.

Q: Wann sollte ich WITH RECURSIVE in SQLite einsetzen?

Immer dann, wenn du einen Baum oder Graphen durchlaufen willst — also Mitarbeiter und Vorgesetzte, Kategorien und Unterkategorien, verschachtelte Kommentare — oder eine Sequenz brauchst, etwa alle Daten in einem Zeitraum oder die Zahlen von 1 bis 100. Klassische Joins reichen für ein, zwei Ebenen; eine rekursive CTE kommt mit beliebiger Tiefe klar, ohne dass du sie vorher kennen musst.

Q: Wie vermeide ich Endlosschleifen in einer rekursiven CTE?

Sorg dafür, dass der rekursive Teil ein klares Abbruchkriterium hat — eine WHERE-Bedingung, die irgendwann keine Zeilen mehr liefert, oder einen Zähler mit Obergrenze. Bei Graphen mit Zyklen merkst du dir den bisherigen Pfad in einer Spalte und schließt bereits besuchte Knoten aus. Als Sicherheitsnetz hilft ein LIMIT in der äußeren Abfrage, damit eine entgleiste Rekursion nicht den Speicher sprengt.

Rekursion in SQL klingt seltsam – bis man sie einmal in Aktion sieht

Die meisten Abfragen geben Zeilen aus Daten zurück, die bereits existieren. Eine rekursive CTE in SQLite funktioniert anders: Sie erzeugt Zeilen, indem sie ihre eigene Ausgabe Schritt für Schritt wieder als Eingabe verwendet – so lange, bis nichts Neues mehr hinzukommt. Genau so läuft man durch einen Baum unbekannter Tiefe oder erzeugt die Zahlen von 1 bis 100, ganz ohne eine Zahlentabelle.

Der Aufbau ist immer derselbe:

WITH RECURSIVE name(columns) AS (
    -- Anker: die Startzeilen
    SELECT ...
    UNION ALL
    -- rekursiv: Zeilen, die aus dem vorherigen Schritt abgeleitet werden
    SELECT ... FROM name WHERE ...
)
SELECT * FROM name;

Anker oben, UNION ALL, rekursive Abfrage darunter. SQLite führt den Anker genau einmal aus und wiederholt dann den rekursiven Teil — jede Runde mit den Zeilen aus dem vorherigen Durchgang — so lange, bis keine neuen Zeilen mehr dazukommen. Dann ist Schluss.

Mit SQLite eine Zahlenreihe von 1 bis 10 erzeugen

Das einfachste Beispiel für eine rekursive CTE in SQLite ist eine Zahlenreihe. Ganz ohne Tabelle:

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

Schritt für Schritt durchgespielt:

Der Anker liefert eine Zeile: n = 1.
Der rekursive Teil nimmt diese Zeile, berechnet n + 1 = 2, und weil 2 < 10 zutrifft, bleibt die Zeile erhalten.
Im nächsten Durchgang wird aus n = 2 dann n = 3. Und so weiter.
Sobald n den Wert 10 erreicht, ist 10 < 10 nicht mehr wahr, der rekursive Teil liefert keine Zeilen mehr, und SQLite hört auf.

Das WHERE n < 10 ist hier die Abbruchbedingung. Ohne sie läuft die Abfrage in eine Endlosschleife.

Datumsreihe in SQLite generieren

Gleiches Prinzip, in echten Auswertungen oft Gold wert — etwa wenn du jeden Tag eines Zeitraums auffüllen willst, auch die Tage, an denen schlicht nichts passiert ist:

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;

Üblicherweise machst du dann ein LEFT JOIN auf eine Events-Tabelle, damit Tage ohne Events korrekt mit Null gezählt werden. Ein simples GROUP BY date lässt leere Tage komplett unter den Tisch fallen – mit der Datumsreihe bekommst du dagegen für jeden Tag eine Zeile, egal ob etwas passiert ist oder nicht.

Hierarchische Abfrage: Eltern-Kind-Baum durchlaufen

Der Klassiker schlechthin. Hier eine Mitarbeitertabelle, in der jede Zeile auf ihren Vorgesetzten verweist:

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 tree
FROM org;

Der Ankerteil wählt die Wurzel (also die Person ohne Manager). Im rekursiven Schritt verbinden wir die employees-Tabelle wieder mit der CTE und finden jeden, dessen manager_id zu einer id passt, die bereits in der CTE steckt. Mit jeder Iteration gehen wir eine Ebene tiefer. depth ist einfach ein Zähler, den wir einbauen, um die Ausgabe einzurücken.

Das funktioniert für Bäume jeder Tiefe. Egal ob zwei oder zehn Ebenen — die Abfrage bleibt gleich.

Alle Vorfahren einer bestimmten Zeile finden

Drehen wir die Richtung um. Statt von der Wurzel nach unten zu laufen, gehen wir von einem bestimmten Mitarbeiter nach oben und ermitteln so dessen komplette Manager-Kette:

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;

Der Anker ist der Mitarbeiter, bei dem wir starten. Jeder rekursive Schritt springt eine Ebene höher zum Vorgesetzten. SQLite hört auf, sobald die Wurzel erreicht ist — also manager_id IS NULL, denn dann findet der Join nichts mehr.

Dieses Muster brauchst du häufig: für Breadcrumbs, verschachtelte Kommentare, Kategoriepfade — überall dort, wo du dich „nach oben durchhangeln" musst.

Abbruchbedingungen und Endlosschleifen

Der häufigste Fehler bei einer rekursiven CTE in SQLite: Die Abbruchbedingung fehlt oder greift einfach nie. Schauen wir uns das im Vergleich an:

-- Läuft endlos:
WITH RECURSIVE bad(n) AS (
    SELECT 1
    UNION ALL
    SELECT n + 1 FROM bad
)
SELECT n FROM bad;

Es gibt keine WHERE-Klausel, die irgendwann null Zeilen zurückgibt. SQLite zählt also munter bis ins Unendliche – willkommen in der Endlosschleife.

Zwei Gewohnheiten, die dich davor schützen:

Im rekursiven Teil immer eine WHERE-Klausel einbauen, die das Wachstum begrenzt.
Während der Entwicklung zur Sicherheit ein LIMIT ans äußere SELECT hängen – falls deine Abbruchbedingung doch nicht greift, bricht die Abfrage trotzdem ab.

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

Die CTE selbst hat keine Abbruchbedingung, aber LIMIT 5 beendet die äußere Abfrage frühzeitig. SQLite ist clever genug, um nicht weiter zu rekursieren, als LIMIT es verlangt. Praktisch zum Ausprobieren – aber im Produktivcode kein Ersatz für eine echte Abbruchbedingung.

Zyklen in Graphen

Bäume sind zyklenfrei. Allgemeine Graphen dagegen können Zyklen enthalten – und eine naive rekursive CTE läuft dann in eine sqlite Endlosschleife Rekursion. Die Lösung: Den bisher zurückgelegten Pfad mitführen und bereits besuchte Knoten überspringen:

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 ist ein durch Kommas getrennter String mit allen bereits besuchten Knoten. Bevor ein neuer Knoten angehängt wird, prüft die WHERE-Klausel, ob er nicht schon enthalten ist. Ohne diese Absicherung würde der Zyklus 1 → 2 → 3 → 1 zur Endlosschleife – und genau so vermeidest du in SQLite eine Endlosschleife bei der Rekursion.

Ein eingebautes "Visited Set" gibt es in SQL nicht – du baust es dir selbst, meistens als String oder über einen Join gegen die bisherige CTE.

Rekursive CTE vs. Self Join

Wenn du nur ein oder zwei Ebenen tief gehen musst, ist ein Self Join einfacher und schneller:

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 mitarbeiter, m.name AS vorgesetzter
FROM employees e
LEFT JOIN employees m ON e.manager_id = m.id;

Damit lässt sich beantworten, wer der direkte Vorgesetzte einer Person ist. Sobald du aber wissen willst, "wer alles unter Ada hängt – egal wie tief", weißt du die Tiefe nicht im Voraus. Und dann führt an einer rekursiven CTE kein Weg vorbei. Wähle das Werkzeug passend zur Tiefe:

Feste, geringe Tiefe: Self Join, eventuell zwei oder drei davon.
Unbekannte oder beliebige Tiefe: WITH RECURSIVE.

Das mentale Modell

Eine rekursive CTE in SQLite ist im Grunde eine Schleife – nur deklarativ formuliert:

Der Anker ist der Startwert der Schleife.
Die rekursive Abfrage ist der Schleifenrumpf – sie erzeugt aus den aktuellen Zeilen die nächste Runde.
Die Abbruchbedingung ist der Ausstieg – sobald keine Zeilen mehr zurückkommen, ist Schluss.
UNION ALL sammelt alles im finalen Ergebnis ein.

Wenn du dieses Bild einmal im Kopf hast, fühlt sich die Syntax nicht mehr fremd an. Du schreibst quasi eine for-Schleife in SQL.

Wie geht's weiter: Indizes

Rekursive CTEs laufen über viele Zeilen, und der Join im rekursiven Schritt wird in jeder Iteration neu ausgeführt. Ist die Join-Spalte nicht indiziert, bricht die Performance rapide ein. Im nächsten Kapitel geht es deshalb um Indizes – und manager_id ist genau so eine Spalte, die davon massiv profitiert.

Häufig gestellte Fragen

Was ist eine rekursive CTE in SQLite?

Eine rekursive CTE ist eine WITH RECURSIVE-Abfrage, die ihr Ergebnis Schritt für Schritt aufbaut, indem sie sich selbst referenziert. Sie besteht aus zwei Teilen, die mit UNION ALL verknüpft werden: dem Anker, der die Startzeilen liefert, und dem rekursiven Teil, der aus den Zeilen des vorherigen Schritts neue Zeilen erzeugt. SQLite wiederholt den rekursiven Teil so lange, bis keine neuen Zeilen mehr hinzukommen.

Wann sollte ich WITH RECURSIVE in SQLite einsetzen?