Rekursive CTEs fuer hierarchische Daten

1. Warum normale Abfragen an Hierarchien scheitern

Hierarchische Daten wie Kategoriebaeume, Organigramme oder Stuecklisten haben eine Eigenschaft, die eine gewoehnliche SQL-Abfrage nicht abbilden kann: eine unbekannte Verschachtelungstiefe. Eine Tabelle mit einer parent_id-Spalte laesst sich mit einem einzelnen JOIN nur eine Ebene tief verknuepfen. Fuer eine zweite Ebene braucht man einen zweiten JOIN, fuer eine dritte einen dritten, und so weiter, bis die Baumtiefe im schlimmsten Fall die Anzahl der noetigen Joins uebersteigt und die Abfrage nicht mehr generisch ist.

Genau hier setzt eine rekursive CTE an. Sie ist die einzige Standard-SQL-Konstruktion, die eine Abfrage wiederholt auf ihr eigenes Zwischenergebnis anwenden kann, bis keine neuen Zeilen mehr hinzukommen. Damit wird eine Baumtraversierung mit beliebiger Tiefe in einem einzigen Statement moeglich, ohne Anwendungscode, der die Ebenen einzeln nachlaedt, und ohne eine fest kodierte maximale Tiefe.

Eine rekursive CTE unterscheidet sich von einer gewoehnlichen CTE durch das Schluesselwort RECURSIVE und durch die Tatsache, dass sie sich selbst in ihrer eigenen Definition referenziert. Diese Selbstreferenz ist in Standard-SQL ausschliesslich in diesem Kontext erlaubt, was WITH RECURSIVE zu einem klar abgegrenzten, aber maechtigen Werkzeug macht, sobald Baumstrukturen im relationalen Modell abgebildet werden muessen.

2. Die Syntax von WITH RECURSIVE

Eine rekursive CTE besteht aus zwei durch UNION oder UNION ALL verbundenen Teilen: der Ankeranfrage, auch Basisfall genannt, und dem rekursiven Teil. Die Ankeranfrage liefert die Startzeilen, typischerweise die Wurzelknoten eines Baums ohne Elternelement. Der rekursive Teil referenziert die rekursive CTE selbst und wird so lange wiederholt ausgefuehrt, bis er keine neuen Zeilen mehr liefert. Jede Iteration nutzt dabei nur die Zeilen, die in der vorherigen Iteration neu hinzugekommen sind, nicht das gesamte bisherige Ergebnis.

PostgreSQL und MySQL 8 erfordern das Schluesselwort RECURSIVE direkt nach WITH, auch wenn nur eine der mehreren CTEs in der Klausel tatsaechlich rekursiv ist. SQL Server benoetigt dieses Schluesselwort nicht, dort reicht die reine Selbstreferenz im rekursiven Teil. Oracle nutzt ab Version 11g Release 2 ebenfalls die WITH RECURSIVE-Syntax, kennt aber alternativ die aeltere, Oracle-spezifische CONNECT BY-Syntax fuer denselben Zweck.

-- Recursive CTE skeleton: anchor UNION ALL recursive part
WITH RECURSIVE category_tree AS (
    -- Anchor: root categories with no parent
    SELECT category_id, name, parent_id, 1 AS level
    FROM categories
    WHERE parent_id IS NULL

    UNION ALL

    -- Recursive part: join child rows to the previous iteration
    SELECT c.category_id, c.name, c.parent_id, ct.level + 1
    FROM categories c
    JOIN category_tree ct ON c.parent_id = ct.category_id
)
SELECT category_id, name, level
FROM category_tree
ORDER BY level, name;

3. Praxisbeispiel: Kategoriebaum von oben nach unten

Der klassische Anwendungsfall fuer eine rekursive CTE ist das Abwaertsdurchlaufen eines Kategoriebaums: Ausgehend von einer Wurzelkategorie sollen alle Unterkategorien beliebiger Tiefe gefunden werden, etwa um alle Produkte einer Hauptkategorie inklusive aller Unterkategorien anzuzeigen. Die Ankeranfrage startet bei der gewuenschten Kategorie, der rekursive Teil findet in jeder Iteration die direkten Kinder der zuletzt gefundenen Knoten.

In der Praxis wird dieses Ergebnis meist direkt mit der Produkttabelle verknuepft: Die rekursive CTE liefert die Menge aller relevanten Kategorie-IDs, und ein anschliessender JOIN oder ein WHERE category_id IN (SELECT category_id FROM category_tree) filtert die Produkte. Diese Kombination ersetzt eine Anwendungslogik, die sonst rekursiv Kategorien nachladen und die IDs client-seitig sammeln muesste.

-- Find all products under "Electronics", including every subcategory
WITH RECURSIVE subtree AS (
    SELECT category_id, name, parent_id
    FROM categories
    WHERE name = 'Electronics'

    UNION ALL

    SELECT c.category_id, c.name, c.parent_id
    FROM categories c
    JOIN subtree st ON c.parent_id = st.category_id
)
SELECT p.product_id, p.product_name, s.name AS category_name
FROM products p
JOIN subtree s ON s.category_id = p.category_id
ORDER BY s.name, p.product_name;

4. Praxisbeispiel: Organigramm von unten nach oben

Nicht jede Baumtraversierung geht abwaerts. Ein typisches Gegenbeispiel ist die Frage nach der gesamten Fuehrungskette eines Mitarbeiters in einem Organigramm: ausgehend von einem konkreten Mitarbeiter sollen alle Vorgesetzten bis zur Unternehmensspitze gefunden werden. Hier startet die Ankeranfrage beim Mitarbeiter selbst, und der rekursive Teil folgt der manager_id-Spalte aufwaerts, statt wie beim Kategoriebaum abwaerts ueber parent_id zu Kindern zu gelangen.

Diese Richtung ist symmetrisch zur ersten: Statt c.parent_id = ct.category_id im JOIN steht hier e.employee_id = eh.manager_id, die Beziehung wird also umgekehrt. Eine rekursive CTE kennt keine feste Richtung, sie folgt schlicht der im rekursiven Teil definierten Join-Bedingung, egal ob diese abwaerts zu Kindern oder aufwaerts zu Eltern fuehrt.

-- Walk up the management chain from a given employee to the CEO
WITH RECURSIVE reporting_chain AS (
    SELECT employee_id, full_name, manager_id, 0 AS steps_up
    FROM employees
    WHERE employee_id = 4711

    UNION ALL

    SELECT e.employee_id, e.full_name, e.manager_id, rc.steps_up + 1
    FROM employees e
    JOIN reporting_chain rc ON e.employee_id = rc.manager_id
)
SELECT employee_id, full_name, steps_up
FROM reporting_chain
ORDER BY steps_up;

5. Tiefe, Pfad und Sortierung innerhalb des Baums

Neben den reinen Zeilen liefert eine rekursive CTE haeufig auch Metadaten ueber die Position im Baum. Ein Tiefenzaehler, der in der Ankeranfrage mit einem festen Startwert initialisiert und im rekursiven Teil bei jeder Iteration um eins erhoeht wird, macht sichtbar, wie weit ein Knoten von der Wurzel entfernt ist. Diese Tiefe eignet sich fuer Einrueckungen in einer Baumdarstellung oder als Filter, um die Traversierung auf eine maximale Anzahl Ebenen zu begrenzen.

Fuer eine korrekte visuelle Sortierung, bei der Kindknoten direkt unter ihrem Elternknoten erscheinen sollen, reicht eine einfache Sortierung nach Tiefe nicht aus. Der gaengige Ansatz ist ein Pfad-Array oder ein Pfad-String, der bei jeder Iteration um die aktuelle ID erweitert wird, etwa mit PostgreSQLs Array-Typ oder mit String-Konkatenation. Eine anschliessende ORDER BY path sortiert den gesamten Baum in korrekter, hierarchischer Reihenfolge, mit allen Nachkommen direkt unter ihrem jeweiligen Vorfahren.

-- Track depth and a sortable materialized path through the tree
WITH RECURSIVE category_tree AS (
    SELECT category_id, name, parent_id,
           1 AS depth,
           ARRAY[category_id] AS path,
           name::text AS path_label
    FROM categories
    WHERE parent_id IS NULL

    UNION ALL

    SELECT c.category_id, c.name, c.parent_id,
           ct.depth + 1,
           ct.path || c.category_id,
           ct.path_label || ' / ' || c.name
    FROM categories c
    JOIN category_tree ct ON c.parent_id = ct.category_id
)
SELECT REPEAT('  ', depth - 1) || name AS indented_name, path_label
FROM category_tree
ORDER BY path;

6. Terminierungsbedingungen richtig setzen

Eine rekursive CTE terminiert automatisch dann, wenn der rekursive Teil in einer Iteration keine neuen Zeilen mehr liefert, weil kein Datensatz mehr existiert, der die Join-Bedingung erfuellt. Das ist bei einem Baum ohne Zyklen der Normalfall: Irgendwann sind alle Blattknoten erreicht, es gibt keine weiteren Kinder mehr, und die Rekursion stoppt von selbst. Diese implizite Terminierung reicht fuer die meisten Baumstrukturen mit korrekten Fremdschluessel-Constraints vollstaendig aus.

Zusaetzlich kann eine explizite Bedingung im rekursiven Teil die Rekursion vorzeitig begrenzen, etwa WHERE ct.depth < 10, um bei unerwartet tiefen oder fehlerhaften Daten eine harte Obergrenze zu setzen. SQL Server bietet mit der Abfrageoption MAXRECURSION eine serverseitige Sicherheitsgrenze, die eine rekursive CTE nach einer festgelegten Anzahl Iterationen mit einem Fehler abbricht, standardmaessig nach 100 Ebenen, was insbesondere in Produktionsumgebungen ein sinnvolles Sicherheitsnetz gegen fehlerhafte Daten darstellt.

7. Zyklen erkennen und Endlosschleifen vermeiden

Die groesste Gefahr bei einer rekursive CTE ist ein Zyklus in den Daten: Wenn Knoten A auf Knoten B verweist und Knoten B durch einen Datenfehler wieder auf Knoten A zurueckverweist, terminiert die implizite Bedingung nie, weil in jeder Iteration weiterhin neue Kombinationen gefunden werden. Ohne Schutzmassnahme laeuft die Datenbank in eine Endlosschleife, bis Arbeitsspeicher oder eine harte Iterationsgrenze das Statement abbricht.

PostgreSQL 14 hat mit CYCLE eine native Zyklenerkennung eingefuehrt, die automatisch prueft, ob ein Knoten bereits im aktuellen Pfad vorkommt, und die Rekursion an dieser Stelle stoppt, ohne das gesamte Statement fehlschlagen zu lassen. In aelteren Versionen und anderen Datenbanken implementiert man dieselbe Pruefung manuell ueber ein Pfad-Array und eine WHERE NOT c.category_id = ANY(ct.path)-Bedingung im rekursiven Teil, die verhindert, dass ein bereits besuchter Knoten erneut in die Rekursion aufgenommen wird.

-- PostgreSQL 14+: native cycle detection
WITH RECURSIVE category_tree AS (
    SELECT category_id, parent_id, name
    FROM categories
    WHERE parent_id IS NULL

    UNION ALL

    SELECT c.category_id, c.parent_id, c.name
    FROM categories c
    JOIN category_tree ct ON c.parent_id = ct.category_id
) CYCLE category_id SET is_cycle USING path
SELECT category_id, name, is_cycle
FROM category_tree;

-- Portable manual cycle guard using a path array
WITH RECURSIVE category_tree AS (
    SELECT category_id, parent_id, name, ARRAY[category_id] AS visited
    FROM categories
    WHERE parent_id IS NULL

    UNION ALL

    SELECT c.category_id, c.parent_id, c.name, ct.visited || c.category_id
    FROM categories c
    JOIN category_tree ct ON c.parent_id = ct.category_id
    WHERE NOT c.category_id = ANY(ct.visited)
)
SELECT category_id, name FROM category_tree;

8. Performance bei grossen Hierarchien

Bei grossen Hierarchien mit mehreren zehntausend Knoten haengt die Performance einer rekursive CTE massgeblich von einem Index auf der Fremdschluessel-Spalte ab, ueber die die Rekursion joint, in der Regel parent_id. Ohne diesen Index degeneriert jede Iteration zu einem vollstaendigen Tabellenscan, was bei tiefen Baeumen zu quadratischer statt linearer Laufzeit fuehrt. Ein einfacher Index auf parent_id reduziert das haeufig auf akzeptable Laufzeiten selbst bei sehr grossen Tabellen.

Bei extrem grossen oder sehr tiefen Hierarchien, die haeufig gelesen, aber selten geaendert werden, ist eine rekursive CTE nicht immer die schnellste Loesung. Alternativen wie ein Nested-Set-Modell oder eine materialisierte Pfadspalte, die bei jeder Aenderung aktualisiert wird, verschieben die Kosten von der Leseoperation auf die Schreiboperation und koennen bei read-heavy Workloads spuerbar schneller sein als eine rekursive Traversierung bei jeder Anfrage.

9. Typische Fehler bei rekursiven CTEs

Der haeufigste Fehler ist das Fehlen einer Terminierungsbedingung bei zyklischen oder potenziell fehlerhaften Daten, was direkt in eine Endlosschleife fuehrt. Der zweite haeufige Fehler ist die Verwendung von UNION statt UNION ALL im Uebergang zwischen Ankeranfrage und rekursivem Teil: UNION dedupliziert bei jeder Iteration die gesamte bisherige Ergebnismenge, was die Performance bei grossen Baeumen drastisch verschlechtert, waehrend UNION ALL ohne Deduplizierung auskommt und in praktisch allen Faellen die richtige Wahl ist, solange keine Zyklen vorliegen.

Ein dritter Fehler ist der Versuch, im rekursiven Teil eine Aggregatfunktion wie SUM oder COUNT ueber die gesamte rekursive CTE zu verwenden. Aggregatfunktionen sind im rekursiven Teil in Standard-SQL nicht erlaubt, weil das Ergebnis zum Zeitpunkt der Iteration noch nicht vollstaendig ist. Wer eine Summe ueber den gesamten Baum braucht, aggregiert nach Abschluss der Rekursion in einer separaten, auf die rekursive CTE aufbauenden Abfrage.

10. Zusammenfassung

Eine rekursive CTE ist das Standard-SQL-Werkzeug fuer Baumstrukturen beliebiger Tiefe. Sie besteht aus einer Ankeranfrage, die die Startknoten liefert, und einem rekursiven Teil, der sich selbst referenziert und in jeder Iteration nur die neu hinzugekommenen Zeilen verarbeitet. Ob ein Kategoriebaum abwaerts oder eine Fuehrungskette aufwaerts durchlaufen wird, entscheidet allein die Richtung der Join-Bedingung im rekursiven Teil.

Terminierung geschieht in der Regel implizit, sobald keine neuen Zeilen mehr gefunden werden, sollte bei potenziell zyklischen Daten aber immer durch ein Pfad-Array oder native Zyklenerkennung wie CYCLE in PostgreSQL 14 abgesichert werden. UNION ALL statt UNION ist die richtige Wahl fuer Performance, ein Index auf der Fremdschluessel-Spalte ist bei grossen Hierarchien Pflicht. Fuer extrem grosse, selten geaenderte Baeume lohnt sich der Blick auf Alternativen wie Nested Sets oder materialisierte Pfade.

11. FAQ: Rekursive CTEs