Einführung von rekursiven Common Table Expressions: Databricks SQL Turing-vollständig machen

Rekursive Common Table Expressions (CTEs) werden jetzt in Databricks unterstützt. Dies bietet eine native Möglichkeit, Schleifen und Traversierungen in SQL auszudrücken, was nützlich für die Arbeit mit hierarchischen und graphenstrukturierten Daten ist. Diese Funktionen entsprechen dem SQL-Standard und folgen bekannten Mustern, die in älteren Data Warehouses wie Teradata und Snowflake verwendet werden, was Migrationen von solchen Warehouses erheblich erleichtert. Databricks hat auch die Unterstützung für rekursive CTEs zu Apache Spark™ beigetragen, wodurch diese vollständig Open Source ist.

Databricks verwendet die Standard-ANSI-SQL-Syntax für rekursive CTEs, einschließlich des Schlüsselworts RECURSIVE.

Diese scheinbar kleine Funktion erweitert die Ausdrucksfähigkeit von SQL erheblich und macht sie theoretisch Turing-vollständig – das bedeutet, sie kann jede Berechnung durchführen, die ein Computer ausführen kann. Rekursive CTEs ermöglichen komponierbare Lösungen, die zuvor prozeduralen Code wie Python oder externe Tools erforderten.

Rekursive CTEs sind jetzt in der Public Preview DBSQL 2025.20 und Databricks Runtime 17.0 verfügbar (bald auch für Lakeflow Declarative Pipelines). In diesem Blogbeitrag untersuchen wir, wie rekursive CTEs funktionieren – und wie sie Ihnen helfen können, reale Probleme mit reinem SQL zu lösen.

Hauptmerkmale der Unterstützung für rekursive CTEs

Die Unterstützung für rekursive CTEs in Databricks umfasst:

• Durchlaufen von Baum- und Graphen-ähnlichen Strukturen, wie Organigrammen, Ordnern und Routing-Netzwerken
• Vollständig Open Source und in Apache Spark™ integriert
• Integrierte Schutzmechanismen gegen unendliche Rekursion (100 Schritte, 1 Mio. Zeilen)
• Anpassbare Schutzmechanismen mit MAX RECURSION LEVEL
• Unterstützung für kontrollierte unendliche Rekursion mit LIMIT

Rekursive CTEs funktionieren gut sowohl mit traditionellen Systemen, die hierarchische Daten in normalisierten Tabellen speichern, als auch mit Daten aus modernen Anwendungen, die flexible JSON/XML-Hierarchien generieren. Sehen Sie sich unten Beispiele für beides an, einschließlich RCTEs, die den Variant-Datentyp für JSON-Hierarchien nutzen.

Darüber hinaus vereinfacht die Unterstützung für rekursive CTEs Migrationen von älteren Datenbanksystemen. Teradata und Postgres sind zwei Beispiele für Systeme, deren Syntax identisch ist, während Systeme wie Oracle, die die CONNECT BY-Syntax verwenden, leicht konvertiert werden können.

Wie rekursive CTEs funktionieren

Rekursive CTEs sind Common Table Expressions, die mit dem Schlüsselwort RECURSIVE definiert werden. Sie bestehen aus zwei Teilen, die mit UNION ALL kombiniert werden:

1. Eine Basis-Subquery – diese wird einmal ausgeführt und startet die Rekursion
2. Eine rekursive Schritt-Subquery – diese bezieht sich auf die CTE selbst und wird wiederholt angewendet, um neue Zeilen zu erstellen.

Die Ausführung beginnt mit der Basis-Abfrage. Dann wird in jeder Iteration der rekursive Schritt ausgeführt, wobei die Ausgabe des vorherigen Schritts verwendet wird. Dies wird fortgesetzt, bis keine neuen Zeilen mehr produziert werden.

Um zu verhindern, dass unendliche Rekursion übermäßige Ressourcen verbraucht, erzwingt Databricks zwei Sicherheitsgrenzen: eine maximale Rekursionstiefe von 100 Schritten und eine Zeilengrenze von 1 Million. Wenn eine der Schwellenwerte überschritten wird, schlägt die Abfrage mit einem Fehler fehl.

Wenn Sie sicher sind, dass Ihre Rekursion mehr als 100 Schritte benötigt, um alle Ergebnisse zu produzieren, können Sie die maximale Stufe überschreiben, indem Sie den MAX RECURSION LEVEL-Hinweis verwenden:

 Weitere Details finden Sie in der Dokumentation zu CTEs.

„Bei bp Supply Trading and Shipping – Market Risk ist das Verständnis der Berichterstattung über die Portfoliohierarchie über Geschäftsbereiche hinweg entscheidend für die Effizienz unseres Geschäftsbetriebs. Durch den Ersatz unseres Altsystems durch rekursive CTEs in Databricks SQL haben wir einen Schritt zur Vorbereitung hierarchischer Daten von ca. 6 Minuten auf ca. 30 Sekunden reduziert, was einer Verbesserung um das 12-fache entspricht.“ — Dharmik Prajapati, bp Staff Software Engineer

Beispiele für die Lösung iterativer Aufgaben mit rekursiven CTEs

Navigieren in Baum- und Hierarchiedaten: Ermitteln benötigter Materialien mit einer Stückliste

In der Fertigungsindustrie benötigt jedes hergestellte Teil eine Reihe von Komponenten zum Bau. Jede Komponente kann in eine kleinere Reihe von Einzelteilen zerlegt werden. Die Gesamtheit aller Teile wird als Stückliste (Bill of Materials, BOM) bezeichnet. 

Eine Stückliste bildet oft eine baumartige Struktur – oder allgemeiner einen gerichteten azyklischen Graphen (DAG). In diesem Beispiel betrachten wir die Teile eines Fahrrads, die wir vereinfachen, indem wir von einer Baumstruktur ausgehen, bei der jede Komponente in genau einem übergeordneten Teil verwendet wird. 

Angenommen, wir möchten berechnen, wie viele Rohmaterialien für den Bau eines Fahrrads benötigt werden. Betrachten Sie die folgende Stückliste:

Jede Zeile beschreibt eine Komponente, das übergeordnete Teil, zu dem sie gehört, und wie viele Komponenten zur Montage einer Einheit des übergeordneten Teils benötigt werden.

Der rekursive CTE beginnt mit einem Ziel: dem Bau eines Fahrrads. Das ist der Basisfall. In jedem rekursiven Schritt zerlegen wir Komponenten in ihre Unterkomponenten. Zum Beispiel besteht ein Fahrrad aus einem Rahmen, einem Antriebsstrang und zwei Rädern. Jedes Rad wiederum besteht aus einem Reifen und 32 Speichen. Die rekursive Struktur wird deutlich, wenn wir Teile in kleinere Stücke zerlegen.

Sobald wir die Hierarchie vollständig erweitert haben, filtern wir Zwischenkomponenten (Elternteile) heraus, um nur die Rohmaterialien für die Montage zu erhalten.

Diese Abfrage berechnet die Gesamtmenge jedes Basismaterials, das zum Bau eines Fahrrads benötigt wird:

Pfadfindung basierend auf der Graphentraversierung: Finden aller Flugrouten von einer Stadt

Betrachten wir ein Problem anhand einer Graphen-Datenstruktur. Ein Graph besteht aus einer Menge von Knoten, die durch Kanten verbunden sind. Er wird verwendet, um Beziehungen oder Verbindungen zwischen Paaren von Elementen darzustellen. Das Lösen eines Graphenproblems erforderte früher Python, komplizierte Skriptlogik oder eine externe Bibliothek. Jetzt machen rekursive Abfragen es einfach. 

Ein typisches Problem mit Graphenstrukturen ist der Flugverkehr: Welche Flughäfen kann ich mit einer Reihe von Flügen erreichen? Angenommen, wir haben die folgenden Flüge, die an einem Tag stattfinden:

Jeder Flug ist mit den IATA-Codes seines Abflug- und Zielflughafens sowie den Abflug- und Ankunftszeiten angegeben.

Angenommen, eine Person kommt um 8 Uhr morgens am Flughafen BEG an und möchte alle möglichen Reiserouten für diesen Tag finden.

Dies ist natürlich ein iteratives Problem. Jedes Mal, wenn wir eine neue Stadt entdecken, die wir erreichen können, finden wir alle Flüge, die von dort abfliegen nach unserer Ankunftszeit. Aus diesem Grund verfolgen wir im rekursiven CTE die Ankunftszeit an jedem Flughafen.  

Dies erzeugt die Menge aller erreichbaren Flughäfen zusammen mit der benötigten Anzahl und Menge der Flüge.

Diese Abfrage kann Benutzern helfen, alle erreichbaren Ziele unter Berücksichtigung von Zeitplänen zu erkunden und unterstützt Anwendungen wie Reiseplanung, Paket-Routing oder Transportlogistik.

Im vorherigen Beispiel haben wir Spaltennamen in der WITH RECURSIVE ... AS (...) Klausel definiert. Hier definieren wir sie stattdessen in der Ankerabfrage. Beide Ansätze sind bei rekursiven CTEs auf Databricks gültig.

Durchsuchen von semi-strukturierten und unstrukturierten Daten: Finden aller Mitarbeiter in einer JSON-Datei

Traditionelle Systeme speichern hierarchische Daten oft in starren, normalisierten Tabellen. Inzwischen generieren moderne Anwendungen häufig flexible JSON/XML-Hierarchien. Die Kombination von Databricks aus rekursiven CTEs mit dem VARIANT-Typ ermöglicht es Ihnen, diese Datenmuster nahtlos zu migrieren, sodass Sie sowohl traditionelle normalisierte Daten als auch flexible JSON/XML-Strukturen in einem einzigen System abfragen können.

In diesem Beispiel erhalten wir eine (relativ kleine) Unternehmenshierarchie. Aber anstatt einer vollständig strukturierten Tabelle erhalten wir sie in Form von JSON:

Angenommen, wir möchten eine Liste aller Mitarbeiter und ihrer Titel in einer Tabelle. Die Felder der Personen im Unternehmen folgen nicht demselben Schema: Einige haben direkte Untergebene, andere nicht; einige haben ihren Standort, andere nicht! Mit dem VARIANT Datentyp in Databricks können alle benötigten Gemeinsamkeiten innerhalb eines rekursiven CTE verwendet werden, um die verschachtelte Struktur des JSON vollständig zu durchlaufen, während ihre Unterschiede ignoriert werden können.

Der Basisfall der Rekursion ist die vollständigen JSON-Daten des Stammmmitarbeiters, die eine Liste seiner Untergebenen enthalten. In jedem rekursiven Schritt verarbeitet die Abfrage die Daten jedes Untergebenen und wiederholt den Vorgang, bis sie einen Mitarbeiter ohne Untergebene erreicht.

Hier ist die rekursive Abfrage für dieses Beispiel:

Obwohl hier alle CTEs unter einem WITH RECURSIVE Block stehen, wird nur derjenige mit tatsächlicher Rekursion als rekursiv behandelt. Databricks erkennt intelligent, welche eine Rekursion benötigen – auch wenn Sie sie alle markieren!

Die Ausgabe der Abfrage:

Erste Schritte

Beginnen Sie mit rekursiven CTEs, indem Sie die Databricks Dokumentation lesen. 

Der beste Data Warehouse ist ein Lakehouse. Um mehr über Databricks SQL zu erfahren, besuchen Sie unsere Website oder lesen Sie die Dokumentation. Sie können auch die Produkttour für Databricks SQL ansehen. Wenn Sie Ihr bestehendes Warehouse in ein hochleistungsfähiges, serverloses Data Warehouse mit großartiger Benutzererfahrung und niedrigeren Gesamtkosten migrieren möchten, dann ist Databricks SQL die Lösung – probieren Sie es kostenlos aus.

(Dieser Blogbeitrag wurde mit KI-gestützten Tools übersetzt.) Originalbeitrag