2025-05-23

USING KEY in rekursiven CTEs

Björn Bamberg, Torsten Grust

SQL-Abfragen aus Teilen zusammensetzen: CTEs

Wenn SQL-Abfragen komplexer werden, wird ihre Lesbarkeit, Modularität und Wiederverwendbarkeit zunehmend zur Herausforderung. Common Table Expressions (CTEs) wurden eingeführt, um diese Probleme zu lösen, indem Entwickler temporäre, benannte Ergebnismengen innerhalb einer Abfrage definieren können. Ähnlich wie Funktionen in der Programmierung erlauben CTEs, eine große Abfrage in logische Bausteine zu zerlegen – leichter zu verstehen, zu pflegen und zu debuggen.

CTEs sind besonders nützlich, um mehrstufige Transformationen zu strukturieren, die sonst tief verschachtelte Unterabfragen oder komplexe Joins erfordern würden. Indem sie Klarheit und Struktur von SQL-Code verbessern, sind CTEs zu einem wesentlichen Werkzeug im modernen Query-Schreiben geworden – sie ermöglichen die klare, deklarative Formulierung auch der anspruchsvollsten Logik.

Iterieren wie 1999: Rekursive CTEs

Um die Ausdruckskraft von SQL zu steigern, wurden rekursive CTEs im Standard SQL:1999 eingeführt. Sie erlauben einer Abfrage, auf die Ergebnisse vorheriger Iterationen innerhalb desselben Ausdrucks zu verweisen, sodass SQL komplexere Probleme wie Graph-Traversierung und andere iterative Berechnungen lösen kann.

Diese Fähigkeit schiebt SQL über das reine Datenabrufen hinaus und erlaubt die Formulierung komplexer, iterativer Logik direkt in SQL. Tatsächlich machen rekursive CTEs SQL Turing-vollständig, das heißt, es kann theoretisch jede Berechnung ausdrücken (bei ausreichend Zeit und Speicher).

Aber wie funktionieren rekursive CTEs in DuckDB?

Schauen wir uns ein einfaches Beispiel an, um den Mechanismus zu zerlegen. Angenommen, wir wollen die größte Zweierpotenz berechnen, die kleiner als 100 ist. Wir können eine rekursive CTE power nutzen, um Zweierpotenzen iterativ zu erzeugen, bis wir diese Grenze erreichen. Für jede Zeile (a, b, c) in power gilt a^b = c:

WITH RECURSIVE power(a, b, c) AS (
    SELECT 2, 0, 1       -- 2^0 = 1
        UNION
    SELECT a, b+1, a * c -- a^(b+1) = a * a^b
    FROM power           -- reads the working table (contains a single row)
    WHERE a * c < 100
)
FROM power;         -- reads the union table (contains all intermediate results)

Wir können eine rekursive CTE in zwei Teile teilen, getrennt durch das Schlüsselwort UNION. Der Teil oberhalb von UNION ist der nicht-rekursive Teil (SELECT 2, 0, 1 in unserem Beispiel), der Teil darunter der rekursive Teil.

Im rekursiven Teil verweist die CTE power auf sich selbst. Diese Selbstreferenz zeigt auf das, was wir Working Table nennen. Die Working Table hält immer die Zeilen, die in der unmittelbar vorhergehenden Iteration erzeugt wurden. Und nur die.

So funktioniert es Schritt für Schritt:

• Zuerst wird der nicht-rekursive Teil ausgeführt und erzeugt initiale Zeilen – in unserem Beispiel nur die Zeile (2, 0, 1). Diese Zeilen werden in der Working Table gespeichert.
• Dann wird der rekursive Teil mit den Zeilen aus der Working Table ausgeführt. Jede neue Zeile, die der rekursive Teil erzeugt, wird in der Intermediate Table gespeichert, die Ergebnisse der aktuellen Iteration hält.
• Ist die Intermediate Table leer, endet die Iteration.
• Andernfalls leeren wir die Working Table und ersetzen sie durch den Inhalt der Intermediate Table – Vorbereitung auf die nächste Iteration.
• Zusätzlich fügen wir den Inhalt der Intermediate Table der Union Table hinzu, die alle Zwischenergebnisse über die Iterationen sammelt.

Hier die Einträge der drei beteiligten Tabellen in jeder Iteration der CTE:

Wenn die rekursive CTE fertig ist, hält die Union Table die gesamte Ergebnismenge, einschließlich aller Zwischenzeilen aus jeder Iteration:

┌───────┬───────┬───────┐
│   a   │   b   │   c   │ -- a^b = c
│ int32 │ int32 │ int32 │
├───────┼───────┼───────┤
│     2 │     0 │     1 │
│     2 │     1 │     2 │
│     2 │     2 │     4 │
│     2 │     3 │     8 │
│     2 │     4 │    16 │
│     2 │     5 │    32 │
│     2 │     6 │    64 │
└───────┴───────┴───────┘

Die Union Table liefert eine vollständige Historie der Potenzberechnung. Das kann zu unnötigem Overhead führen, besonders wenn wir nur die letzte Zeile brauchen – das Endergebnis der Rekursion. Jeden Zwischenwert zu speichern kann ineffizient sein, besonders wenn die Zwischenergebnisse nicht gebraucht werden oder bei großen Datensätzen (viele Zeilen oder breite Zeilen, z. B. mit Array-Spalten).

Rekursive CTEs leiden an Amnesie

Während die Union Table die erwähnte Historie hält, sobald die Berechnung fertig ist, leiden rekursive CTEs an einer Art „Amnesie“ während die Iteration läuft: Der rekursive Teil sieht immer nur die Zwischenergebnisse der unmittelbar vorhergehenden Iteration. Das kann einschränkend sein, und viele von uns haben gesehen, wie Query-Autoren diese Einschränkung umgehen, indem sie manuell Arrays (oder ähnliche Containerstrukturen) pflegen, die Informationen über vorherige Iterationen halten. Das kann teuer sein. Andererseits kann es, dem rekursiven Teil den Zugriff auf die Union Table mit all ihren angesammelten – potenziell umfangreichen – Zwischenergebnissen zu erlauben, leicht Performance-Probleme während der Iteration verursachen. Ein echtes Dilemma.

USING a KEY, um Amnesie zu heilen

Können wir uns leisten, dem rekursiven Teil Zugriff auf die Union Table zu geben? Ja, aber wir brauchen ein Mittel, ihre Größe zu kontrollieren. Die Union Table im Append-only-Modus zu betreiben ist daher ein No-Go. Stattdessen lassen wir den rekursiven Teil optional vorhandene Zeilen in der Union Table mit frischen Informationen überschreiben, die in der aktuellen Iteration berechnet wurden. Das kann die Größe der Union Table deutlich reduzieren (siehe unsere Experimente unten).

Ab Version 1.3 bietet DuckDB eine USING KEY-Variante rekursiver CTEs, die genau diese Idee umsetzt.

Wenn Sie mehr über die Ursprünge lesen möchten, schauen Sie sich CIDR 2023 an. Zur Implementierung siehe SIGMOD 2025.

Die Variante führt zwei wesentliche Unterschiede gegenüber traditionellen rekursiven CTEs ein:

1. Sie bietet Zugriff auf die Working Table (wie immer) sowie Zugriff auf die Union Table – die wir jetzt Recurring Table nennen.
2. Statt einfach neue Zeilen an die Recurring Table anzuhängen, funktioniert die Tabelle jetzt eher wie ein Wörterbuch (ähnlich einem Python-dict) und erlaubt schlüsselbasierte Updates.

Um dieses neue Feature zu nutzen, fügen Sie die Klausel USING KEY (...) zu Ihrer rekursiven CTE hinzu:

WITH RECURSIVE power(a, b, c) USING KEY (a)
    -- key: a, payload: b, c
AS (
    ...
);

Mit USING KEY wird das Schema der rekursiven CTE in Schlüsselspalten und Payload-Spalten geteilt. Die Schlüsselspalten werden mit der Klausel USING KEY (⟨column names⟩){:.language-sql .highlight} angegeben, die restlichen Spalten werden als Payload behandelt.

Diese Aufteilung beeinflusst, wie sich die Recurring Table verhält. Statt stur neue Zeilen in jeder Iteration anzuhängen, wirkt sie eher wie ein Wörterbuch: Wenn der rekursive Teil eine Zeile zurückgibt, die noch nicht gesehen wurde, wird sie wie üblich zur Recurring Table hinzugefügt. Teilt eine Zeile aber einen Schlüssel mit einem vorhandenen Eintrag in der Recurring Table, wird der Payload aktualisiert – die vorherigen Werte für diesen Schlüssel in der Recurring Table werden ersetzt.

Wenn in einer einzelnen Iteration mehrere Zeilen mit demselben Schlüssel erzeugt werden, wird nur die letzte behalten. Deshalb möchten Sie im rekursiven Teil vielleicht die Klausel ORDER BY nutzen, um zu steuern, welche Zeile behalten wird.

Dieser Ansatz erlaubt rekursiven Abfragen, Zustand effizienter zu halten und zu aktualisieren, besonders für Algorithmen, bei denen der neueste (oder „beste“) Wert für einen gegebenen Schlüssel entscheidend ist.

Alte Zwischenergebnisse überschreiben

Nehmen wir unser rekursives Beispiel von oben wieder auf. Jetzt berechnen wir die Potenzen der Basen 2 und 3, solange sie kleiner als 100 sind:

WITH RECURSIVE power(a, b, c) USING KEY (a) AS (
    FROM (VALUES (2, 0, 1), (3, 0, 1))   -- 2^0 = 1, 3^0 = 1
        UNION
    SELECT a, b+1, a * c                 -- a^(b+1) = a * a^b
    FROM power                           -- reads the working table (contains two rows)
    WHERE a * c < 100
)
FROM power;                              -- reads the recurring table (contains two rows)

Wir beginnen mit zwei Zeilen im nicht-rekursiven Teil: eine mit Schlüssel (Basis) 2 und eine mit Schlüssel 3. Im rekursiven Teil multiplizieren wir die Zwischenpotenz mit der Basis. Das erzeugt zwei Zeilen, wieder mit den Schlüsseln 2 und 3.

Anders als bei traditionellen rekursiven CTEs hängen wir diese zwei neuen Zeilen nicht an die Recurring Table an. Stattdessen aktualisieren wir die vorhandenen Zeilen mit den Schlüsseln 2 und 3 in der Recurring Table und überschreiben ihre Payload-Werte. So behalten wir während der gesamten Berechnung nur zwei Zeilen, jede mit dem aktuellen Potenzwert für ihren Schlüssel (oder ihre Basis) in Spalte a.

Wie wir sehen, bleibt die Größe der Recurring Table konstant. Irrelevante Berechnungshistorie wird überschrieben, was zu reduziertem Speicherverbrauch führt. Die finale Recurring Table liest sich so:

┌───────┬───────┬───────┐
│   a   │   b   │   c   │ -- a^b = c
│ int32 │ int32 │ int32 │
├───────┼───────┼───────┤
│     2 │     6 │    64 │
│     3 │     4 │    81 │
└───────┴───────┴───────┘

Dieses Verhalten ist besonders nützlich bei Algorithmen, bei denen uns der neueste, beste oder kleinste Wert für einen gegebenen Schlüssel interessiert. Die maximale Zahl der Zeilen in der Recurring Table ist jetzt durch die Zahl eindeutiger Schlüssel begrenzt. Da die Zahl der verwendeten eindeutigen Schlüssel unter Kontrolle des rekursiven Teils liegt, kann das ein mächtiger Vorteil bei umfangreichen Datensätzen sein.

Ein Schlüsselwechsel

Falls Sie doch an der Historie der Berechnung interessiert sind und bereit sind, den Speicherplatz zu investieren, reicht ein Wechsel des Schlüssels. Mit

WITH RECURSIVE power(a, b, c)
    USING KEY (a, b)
AS (  -- formerly: USING KEY (a)
    ...
)
FROM power
ORDER BY a, b;

wird der Iterationszähler (oder Exponent) in Spalte b ebenfalls als Teil des Schlüssels betrachtet. Die Recurring Table verfolgt dann eindeutige (a, b)- Kombinationen (also Basis, Exponent), und wir können nachvollziehen, was während der Iteration passiert ist:

┌───────┬───────┬───────┐
│   a   │   b   │   c   │
│ int32 │ int32 │ int32 │
├───────┼───────┼───────┤
│     2 │     0 │     1 │
│     2 │     1 │     2 │
│     2 │     2 │     4 │
│     2 │     3 │     8 │
│     2 │     4 │    16 │
│     2 │     5 │    32 │
│     2 │     6 │    64 │
│     3 │     0 │     1 │
│     3 │     1 │     3 │
│     3 │     2 │     9 │
│     3 │     3 │    27 │
│     3 │     4 │    81 │
└───────┴───────┴───────┘

Relevante Historie zugreifen

Ein weiterer großer Unterschied zu Vanilla-rekursiven CTEs: Jetzt, da die Größe der Recurring Table unter Kontrolle ist, können wir uns leisten, sie direkt im rekursiven Teil der CTE zu referenzieren. Das erlaubt uns, jedes Zwischenergebnis zuzugreifen, das noch nicht überschrieben wurde – unabhängig davon, welche Iteration diese Ergebnisse berechnet hat. Keine Amnesie mehr! Um auf die Recurring Table zuzugreifen, stellen Sie dem CTE-Namen einfach den Pseudo-Schema-Namen recurring voran:

WITH RECURSIVE t(...) USING KEY (...) AS (
    ...
    FROM recurring.t  -- reads the recurring table while we iterate
)
...;

USING KEY kann Performance-Vorteile freischalten

Um die Unterschiede zwischen Vanilla- und schlüsselbasierten CTEs weiter hervorzuheben, schauen wir uns ein komplexeres Beispiel mit einem Graph-Datensatz an – einem Social-Network-Graphen.

Die Graphen stammen aus dem LDBC Social Network Benchmark (SNB), der einen Generator für synthetische Social-Network-Daten bereitstellt. Um die Graphen für die Nutzung mit der WITH RECURSIVE-Abfrage handhabbarer zu machen, haben wir sie weiter nach Personennamen gefiltert und so ihre Dichte reduziert.

In diesem Datensatz stehen Knoten für Personen, Kanten für Beziehungen zwischen ihnen. Die Tabellen, mit denen wir arbeiten, sind Person(id), die alle existierenden IDs im Netzwerk enthält, und knows(person1id, person2id), in der jede Zeile ein Paar von Personen hält, die sich kennen.

Wenn Sie das selbst ausprobieren möchten, hängen Sie zuerst die Datenbank an jede DuckDB-Sitzung.

ATTACH 'https://blobs.duckdb.org/data/using-key-graph.duckdb';
USE 'using-key-graph';

Unser Ziel ist, den kürzesten Pfad zwischen allen Personenpaaren im sozialen Netzwerk zu berechnen. Da das ein Problem mit inhärent quadratischer Komplexität ist, müssen wir Laufzeit und Speicherbedarf genau im Auge behalten. Für jedes Paar beginnen wir damit, eine Zeile hinzuzufügen, die eine Person als Start- Knoten und die andere als Zielknoten hat. Dann erkunden wir iterativ alle Personen, die der Startknoten kennt, und setzen die Traversierung fort, bis die Zielperson erreicht ist. Pfade durch das Netzwerk werden durch via-Knoten kodiert: Um das Ziel vom Startknoten zu erreichen, gehen Sie zuerst zum via-Knoten (einem unmittelbaren Nachbarn des Startknotens) – einmal dort, nutzen Sie den via-Eintrag dieses Knotens, um die Traversierung fortzusetzen.

Eine rekursive CTE, die diesen Ansatz umsetzt, liest sich so:

WITH RECURSIVE paths(here, current, via, len, there, completed, found) AS (
  SELECT n1.id AS here, n1.id AS current, NULL::BIGINT AS via,
         0 AS len, n2.id AS there, false AS completed, false AS found
    FROM Person AS n1 JOIN Person AS n2 ON (n2.id <> n1.id)
    UNION ALL
  SELECT paths.here,
         person2id AS current,
         coalesce(paths.via, knows.person2id) AS via,
         paths.len+1 AS len,
         paths.there,
         bool_or(knows.person2id = paths.there)
                 OVER (PARTITION BY paths.here, paths.there
                       ROWS BETWEEN UNBOUNDED PRECEDING
                                AND UNBOUNDED FOLLOWING) AS completed,
         knows.person2id = paths.there AS found
      FROM paths
      JOIN knows ON (paths.current = knows.person1id AND NOT paths.completed)
 )
 SELECT here, there, via, len
 FROM paths WHERE found
 ORDER BY len, here, there;

Die Working Table der rekursiven CTE paths hat sieben Spalten:

• here bezeichnet die Person, bei der die Traversierung startet,
• there bezeichnet die Zielperson, die wir erreichen wollen,
• via zeigt den unmittelbaren Nachbarn des Startknotens des aktuellen Pfads,
• len ist die Länge des aktuellen Pfads, die bei jedem Schritt der Traversierung um eins erhöht wird.

Die übrigen drei Spalten steuern die Traversierungslogik und optimieren die Berechnung.

• current bezeichnet den Knoten, der gerade während der Traversierung erkundet wird,
• found zeigt, ob der aktuelle Pfad die Zielperson erfolgreich erreicht hat,
• completed verfolgt, ob irgendein Pfad mit demselben here und there das Ziel bereits erreicht hat. Das verhindert weitere Traversierung für dieses Paar, sobald ein kürzester Pfad gefunden wurde, und vermeidet so die Erkundung längerer Pfade.

Wenn wir in einem großen Graphen mit vielen Kanten suchen, kann die Union Table in einer Vanilla-rekursiven CTE groß werden und potenziell Speichergrenzen überschreiten. Das verursacht nicht nur deutliche Performance-Probleme, sondern kann in Extremfällen sogar zu Query-Abstürzen führen.

Die neuen schlüsselbasierten CTEs können dieses Problem vermeiden, indem sie ändern, wie der Zustand der Suche gehalten wird. Das ermöglicht eine Reihe neuer Algorithmen, die effizient in SQL ausgedrückt werden können, einschließlich Algorithmen zum Finden kürzester Pfade in großen Graphen.

Ein solcher Algorithmus ist Distance Vector Routing (DVR), eine Methode zur Berechnung kürzester Pfade in einem Netzwerk auf Basis knotenlokaler Routing-Tabellen, die anzeigen, wohin als Nächstes „gesprungen“ werden soll.

• In DVR hält jeder Knoten eine Routing-Tabelle, die die Länge der Pfade aufzeichnet, die andere Knoten erreichen.
• Wir nutzen die Recurring Table, um diese Routing-Tabellen für alle Knoten im Netzwerk zu speichern: eine Zeile (here, there, via, len) zeigt an, dass der erste Hop auf dem Pfad von Knoten here zu Knoten there der Knoten via ist. Die Länge des gesamten Pfads ist len.
• Wenn ein kürzerer Pfad zu einem Zielknoten gefunden wird, wird der entsprechende Routing-Tabellen-Eintrag aktualisiert.
• In der letzten Iteration gefundene Routing-Updates werden über die Working Table an Nachbarknoten verteilt.

Um zu prüfen, ob ein neu eingehendes Routing-Update einen derzeit bekannten Pfad verbessert, führen wir einen Lookup in der Recurring Table aus. Ist die neue Länge kleiner als die des bekannten Pfads, aktualisieren wir den Eintrag und propagieren das Update an unsere unmittelbaren Nachbarn. Dieser Mechanismus erlaubt effizientes Path-Finding selbst in sehr großen Graphen – siehe unten, wie DVR den obigen Ansatz auf Basis einer Vanilla-rekursiven CTE übertrifft.

WITH RECURSIVE dvr(here, there, via, len) USING KEY (here, there) AS (
  -- initialize routing tables for all nodes, only the routes to
  -- immediate neighbors are known at this time
  SELECT n.person1id AS here, n.person2id AS there, n.person2id AS via, 1::DOUBLE AS len
  FROM   knows AS n
    UNION
  (SELECT n.person1id AS here, dvr.there, dvr.here AS via, 1 + dvr.len AS len
    FROM dvr -- working table - routing updates shared by neighbors
    JOIN knows AS n ON
        (n.person2id =  dvr.here AND    -- send update only to immediate neighbors
        n.person1id <> dvr.there)       -- no need to store a route to myself
    LEFT JOIN recurring.dvr AS rec ON   -- recurring table (current routing tables)
        (rec.here = n.person1id AND rec.there = dvr.there) -- identify affected routing table entry
    WHERE 1 + dvr.len < coalesce(rec.len, 'Infinity'::DOUBLE) --  does the routing update improve the entry in the routing table?
    ORDER BY len -- shortest path first
  )
)
FROM dvr
ORDER BY len, here, there;

Je größer die Social-Network-Graphen (A bis G), desto ausgeprägter ist die Performance- Lücke zwischen Vanilla-rekursiven CTEs (REC) und der neuen USING KEY-Variante (KEY). Die Tabelle unten berichtet die Zahl der in jeder Iteration verarbeiteten Zeilen:

Schon beim kleinsten Graphen, Graph A, ist der Unterschied deutlich: Die REC-CTE erzeugt rund 350.000 Zeilen, während KEY nur 744 Zeilen erzeugt. Mit wachsender Graphgröße wird die Lücke noch auffälliger. In Graph C, mit 424 Knoten und 1.446 Kanten, verarbeitet der REC-Ansatz fast 1 Milliarde Zeilen, während die KEY-Methode weniger als 20.000 Zeilen handhabt. Obwohl das nicht der größte Graph in unserem Benchmark ist, nähert sich der REC-Ansatz bereits Out-of-Memory-Bedingungen (OOM, ❌).

Dieser substanzielle Unterschied im Speicherverbrauch ist nur ein Teil der Geschichte. Die Performance des REC-Ansatzes verschlechtert sich ebenfalls schnell. Während beide CTEs auf kleinen Graphen ähnlich performen, wird REC mit wachsendem Graphen deutlich langsamer – und stürzt schließlich ab –, während KEY weiter glatt skaliert:

Und das ist das Schöne an den neuen USING KEY-CTEs. Sie ermöglichen eine effizientere Formulierung komplexer iterativer Algorithmen, indem sie schlüsselbasierte Kontrolle über die Größe der Zwischenergebnisse geben, die von Iteration zu Iteration weitergegeben werden – der Speicherdruck sinkt, die Laufzeit- Performance kann deutlich steigen. Wenn Sie mit rekursiven CTEs in DuckDB arbeiten, nutzen Sie unbedingt diese mächtige Ergänzung – sie kann einen signifikanten Unterschied in Ihren Abfragen machen.