×
CoC AGB Impressum Datenschutz Kontakt Sitemap

Common Table Expressions (CTEs) Teil 2: Rekursive CTEs

Im ersten Teil dieser Reihe haben wir gesehen, wie nicht-rekursive CTEs aufgebaut sind und wie man mit ihnen Queries lesbarer machen kann. In diesem Teil wollen wir uns anschauen wie CTEs, die auf sich selbst verweisen können (sogenannte rekursive CTEs), aufgebaut sind und welchen Nutzen sie, vor allem für hierarchische Daten, haben.

Zur Veranschaulichung soll das folgende Beispiel dienen: Ein simples Dateisystem mit Ordnern und Dateien wird in einer Datenbank nachgestellt.  Dafür gibt es zwei Tabellen (Ordner und Datei) mit folgenden Spalten:

Ordner:

  • id
  • parent_id
  • name

Datei:

  • id
  • ordner_id
  • name
  • groesse_in_kb

Unser Dateisystem hat eine Baumstruktur. Ordner können Unterordner (Many-to-one) und Dateien (Many-to-One) beinhalten. Jeder Ordner hat dabei die ID seines Vater-Ordners (parent_id) und jede Datei die ID des Ordners (ordner_id), in dem sie sich befindet, gesetzt. Ordner auf der höchsten Ebene haben NULL als parent_id gesetzt. So gesehen ist NULL die Wurzel des Ordnerbaums.

Das Praktische an dieser Struktur ist, dass die Ordnertiefe praktisch unbegrenzt ist, da jeder Ordner immer nur die ID seines Vater-Ordners wissen muss. Zum Erstellen oder Verschieben eines Ordners oder einer Datei muss man lediglich die ID des Vaters (um)-setzen und ist fertig.

Doch diese Struktur hat auch Nachteile, wie man am folgenden Beispiel gut sehen kann. Angenommen wir wollen die Anzahl aller Ordner oder Dateien unterhalb eines bestimmten Ordners herausfinden. Da aber jeder Ordner nur seinen Vater-Ordner kennt, ist es zwar einfach alle direkten Unterordner eines Ordners zu finden (SELECT * FROM Ordner WHERE parent_id = 123), jedoch nicht möglich mit einer simplen Query auch die indirekten Unterordner (oder Dateien) zu finden.

Im Folgenden sollen verschiedene Ansätze betrachtet werden und deren Vor- und Nachteile voneinander abgewogen werden.

Anzahl Ordner/Dateien als Spalte am Ordner vorhalten

Da die Anzahl von Ordnern und Dateien eine grundlegende Funktionalität ist, scheint es Sinn zu machen diese an jedem Ordner vorzuhalten. Jedoch ergeben sich dabei mehrere Probleme:

  • Zusätzlicher Speicherplatz
  • Beim Anlegen/Verschieben/Löschen müssen die Anzahl für alle Überordner bis zur obersten Ebene aktualisiert werden.
  • Wird an einer Stelle die Aktualisierung der Anzahl vergessen oder falsch berechnet, werden falsche Informationen angezeigt. So muss man auch bei jeder Veränderung oder beim Hinzufügen von neuen Features bedenken die Anzahl zu aktualisieren.

Außerdem: Was ist, wenn man nur die Anzahl der Dateien über 100kb haben möchte oder nur die Ordner, die mit “A” anfangen oder nur die Anzahl der Ordner auf der fünften Ebene? Da man diese Informationen schlecht alle in dedizierten Spalten vorhalten kann, wird ein Weg gebraucht, diese Informationen bei Bedarf zu sammeln.

Hierarchie manuell traversieren

Ein simpler Ansatz ist das traversieren des Dateisystem-Baumes, in dem man für einen bestimmten Startordner die Dateien zählt und dann die Hierarchie herabsteigt und für dessen Unterordner die Dateien zählt und für deren Unterordner, usw., bis man alle Ordner des Teilbaumes besucht hat:

  1. Zähle Dateien für Order und summiere Anzahl zu Gesamtanzahl auf: 
    SELECT COUNT(*) FROM Datei where ordner_id=
  1. Hole alle Unterordner von Ordner: 
    SELECT id FROM Ordner WHERE id=
  1. Für jeden Unterordner: Wiederhole 1– 3

Diese Art von Ansatz wird oft implizit bei der Verwendung von ORMs angewendet, wenn man dort mit den entsprechenden Entities arbeitet. Ausgehend von einem Startordner würde man dessen Dateien zählen und anschließend getUnterordner() aufrufen und so die Hierarchie abarbeiten.

Was bei kleinen Dateisystemen relativ schnell geht, kann bei größeren Dateisystem sehr viel Zeit in Anspruch nehmen, da im Endeffekt für jeden besuchten Ordner zwei Datenbankabfragen gemacht werden müssen (Zähle Dateien, hole Unterordner), was auch genereller als n+1-Problem bekannt ist (Bei ORM-Verwendung und n Ordner: 1-mal hole initialen Ordner, n-mal hole Unterordner).

Self-Joins

Eine andere Möglichkeit wäre so lange über die parent_id zu joinen, bis alle Unterordner gejoined wurden:

SELECT * FROM Ordner o
LEFT JOIN Ordner o1 ON o1.parent_id = o.id
LEFT JOIN Ordner o2 ON o2.parent_id = o1.id
LEFT JOIN Ordner o3 ON o3.parent_id = o2.id
LEFT JOIN Ordner o4 ON o4.parent_id = o3.id
LEFT JOIN Ordner o5 ON o5.parent_id = o4.id
…
WHERE o.id = 123

Ein Nachteil dieser Query ist, dass man im Extremfall so viele Joins haben muss, wie das Dateisystem maximal tief ist. Da wir per se aber keine Beschränkung der Tiefe haben, könnte dies zu riesigen Queries führen. Mal eben eine kleine Abfrage zu schreiben, wird dann unmöglich. Außerdem wurden hier lediglich die Ordner geholt. Als nächstes muss noch die Zählung der Dateien stattfinden. Selbst bei in der Tiefe begrenzten Hierarchien keine annehmbare Lösung.

Pfad für jedes Element

Eine weitere Möglichkeit ist das Speichern des eindeutigen Pfades von der Wurzel des Baumes bis hin zum jeweiligen Element. Auch hier gibt es mehrere Möglichkeiten, wie der Pfad gespeichert werden kann, z.B. als String/VarChar/etc. oder mit einer ID-Spalte pro Ebene.

Bei einer ID-Spalte pro Ebene hätte jedes Element einer ID für sich und für jedes direkte und indirekte Eltern-Element. Das würde bedeuten, dass bei einer maximalen Tiefe von 5 jeder Ordner 5 Spalten (z.B. p1, p2, p3, p4, p5). Jeder Ordner übernimmt dabei den Pfad seines Vaters. Pfadspalten unterhalb der Ebene eines Ordners werden mit 0 oder NULL belegt. Hier ein Beispiel von Pfaden (durch Punkt getrennt):

  • Ordner x auf höchster Ebene: 1.0.0.0.0
  • Ordner y auf höchster Ebene: 2.0.0.0.0
  • Ordner x_1 als Unterordner von x: 1.1.0.0.0
  • Ordner y_1 als Unterordner von y: 2.1.0.0.0
  • Ordner y_1_1 als Unterordner von y_1: 2.1.4.0.0

Wie man in diesem Beispiel sieht können Ordern x1 und y1 auf ihrer Ebene dieselbe Pfadnummer (1) haben, solange der gesamte Pfad eindeutig ist. Diese Art der Identifikation macht es sehr einfach auf alle direkten und indirekten Unterordner eines Ordners zuzugreifen. Wollten wir z.B. alle Ordner unterhalb des Ordners mit dem Pfad 1.2.0.0.0 haben wollen, könnten wir folgende Query benutzen

SELECT * FROM Ordner o WHERE o.k1 = 1 AND o.k2 = 2

Aber auch diese Lösung hat einige Nachteile:

  • Platzbedarf steigt mit der Tiefe der Hierarchie
  • Ebenentiefe begrenzt, da pro Ebene eine Tabellenspalte angelegt werden muss
  • Es sollte ein Index benutzt werden, der sämtliche Pfadspalten abdeckt. Der Platzbedarf und die Zeit für einen INSERT steigen dadurch mit der Tiefe.
  • Queries sind immer noch komplex (Gib alle Unterordner für drei ausgewählte Ordner zurück): 
    SELECT * FROM Ordner o
WHERE (o.k1 = 1 AND o.k2 = 2 and o.k3 = 5 and o.k4 =6)
OR (o.k1 = 1 AND o.k2 = 2 and o.k3 = 5 and o.k4 =7)
OR (o.k1 = 1 AND o.k2 = 2 and o.k3 = 5 and o.k4 =8)

Wählt man die Speicherung des Pfades als String/VarChar/etc (z.B. „1.3.4.8“) hat man den Vorteil, dass die Ebenentiefe nicht mehr durch die Anzahl der ID-Spalten wie im vorherigen Beispiel begrenzt ist, sondern nur ggf. durch die maximale Länge des Feldes in der Datenbank. Auch würden die länglichen WHERE-Klauseln aus dem vorherigen Beispiel wegfallen, stattdessen könnte man z.B. „WHERE path LIKE ‘1.2.5.6.%‘ schreiben. Durch das Setzen eines Indexes wären die Abfragen relativ schnell. Allerdings hat diese Methode auch Nachteile. So muss/kann man hier nicht einfach durch das Setzen eines Foreign Keys verhindern, dass der Vater gelöscht wird. Auch bei WHERE-Klauseln mit einer Wildcard am Anfang des Pfades (z.B. ‘%2.3.4‘) kann ein auf das Feld gesetzter Index je nach Datenbank nicht oder nur eingeschränkt verwendet werden.

Beide Ansätze haben außerdem den Nachteil, dass man zum Verschieben eines Teilbaumes alle Elemente des Teilbaumes aktualisieren muss.

Rekursive CTEs

Eine Alternative sind die rekursiven CTEs, die sich von normalen CTEs darin unterscheiden, dass sie auf sich selbst verweisen können. Mit diesen rekursiven CTEs sind Operationen möglich, die mit relationaler Algebra, also der theoretischen Grundlage für relationale Datenbanken, nicht möglich sind.

Ein Beispiel ist das Bestimmen der transitiven Hülle einer Relation in einem Graphen oder einem Baum mit beliebiger maximaler Tiefe mit einer einzigen Abfrage. Dies bedeutet, dass man z.B. in einer Graphen- oder Baumstruktur alle direkt und indirekt erreichbaren Knoten von einem Ausgangsknoten zurückgeliefert bekommen kann, unabhängig von der Tiefe des Baumes. Diese Funktionalität kann in unserem Beispiel für viele Fragestellungen interessant sein, z.B. zur Ermittlung aller direkten und indirekten Unterordner eines bestimmten Ordners.

Die Struktur und Funktionsweise von CTEs lässt sich einführend an einem simplen Beispiel erklären:

WITH levelCTE(lvl) AS
( 
  SELECT 1 -- Ankerelement
  UNION ALL 
  SELECT levelCTE.lvl + 1 FROM levelCTE -- Rekursives Element
  WHERE levelCTE.lvl < 5 -- Abbruchbedingung 
)
SELECT * from levelCTE -- Ergebnis

Das Ausführen dieser CTE bringt das folgende Ergebnis (hier in einer Zeile zusammengefasst): 1, 2, 3, 4, 5.
Generell besteht eine rekursive CTE aus Ankerelementen, rekursiven Elementen, einer Abbruchbedingung und dem Ergebnis:

  • Ankerelement(e): Diese initialen Abfragen geben Reihen (T0) zurück, die die Ausgangsbasis für die Rekursion bilden.
  • Rekursive Elemente(e): Diese Abfrage(n) bekommen Reihen (Ti) als Input (aufgerufen per levelCTE), verarbeiten diese Reihen weiter und geben die aus der Verarbeitung resultierenden Reihen (Ti+1) als Output zurück. Der Output wird anschließend wiederum als Input für die rekursiven Elemente verwendet. Der initiale Input ist der Input T0 der Ankerelemente.
  • Abbruchbedingung (implizit): Die Rekursion wird beendet sobald die rekursiven Elemente keine Reihen mehr zurückliefern.
  • Ergebnis: Das Ergebnis ist die Vereinigung (UNION ALL) aller Outputs von T0 bis Tn

Dadurch, dass die Ergebnisse der Ankerelemente und der rekursiven Elemente als Input für die rekursiven Elemente genommen werden, müssen die Spaltenanzahl und die jeweiligen Spaltentypen in den Ankerelementen und den rekursiven Elementen übereinstimmen. Zusätzlich, aber je nach Datenbanksystem optional, kann man hinter dem Namen der CTE die Spaltennahmen angeben (WITH levelCTE(lvl) AS…).

Gehen wir einmal das oben genannte Beispiel durch:

Ankerelement: SELECT 1 | Output: 1

Rekursives Element:

  • Input T0: 1 | Output T1: 2 | levelCTE.lvl (=1) + 1 = 2 | levelCTE.lvl (1) < 5: ok
  • Input T1: 2 | Output T2: 3 | levelCTE.lvl (=2) + 1 = 3 | levelCTE.lvl (2) < 5: ok
  • Input T2: 3 | Output T3: 4 | levelCTE.lvl (=3) + 1 = 4 | levelCTE.lvl (3) < 5: ok
  • Input T3: 4 | Output T4: 5 | levelCTE.lvl (=4) + 1 = 5 | levelCTE.lvl (4) < 5: ok
  • Input T4: 5 | Output T5: – |levelCTE.lvl (=5) + 1 = 6  | levelCTE.lvl (5) < 5: nicht ok

Anwendung auf das Beispiel

Dieses Beispiel scheint auf den ersten Blick vielleicht wenig nützlich, aber erinnern wir uns an unser Ordner/Dateien-Beispiel zurück. Angenommen man möchte die Summe aller Ordner wissen, die sich auf der dritten Ebene befinden oder die Summe der Dateien bis zu drei Ebenen tiefer, dann wäre so ein simpler Zähler zur Beschränkung der Rekursionstiefe auf einmal nützlich.

Im Folgenden ein paar Beispiel-Queries für die oben erwähnten Anwendungsfälle:

Anzahl Ordner unterhalb eines bestimmten Ordners

WITH ordnerCTE(ordner_id) AS
(
  SELECT o.id
    FROM Ordner o
    WHERE o.parent_id = 1
  UNION ALL
  SELECT o.id
    FROM Ordner o
    INNER JOIN ordnerCTE cte ON o.parent_id = cte.ordner_id
)
SELECT COUNT(*) FROM ordnerCTE

Anzahl Dateien unterhalb eines bestimmten Ordners

WITH ordnerCTE(ordner_id) AS
(
  SELECT o.id
    FROM Ordner o
    WHERE o.parent_id = 1
  UNION ALL
  SELECT o.id
    FROM Ordner o
    INNER JOIN ordnerCTE cte ON o.parent_id = cte.ordner_id
)
SELECT COUNT(*) FROM ordnerCTE cte
INNER JOIN Datei d ON d.ordner_id = cte.ordner_id

Anzahl Ordner auf bestimmter Ebene (hier: Ebene 4).

Hier kommt unser Zähler (ebene) zum Einsatz:

WITH ordnerCTE(ordner_id, ebene) AS
(
  SELECT o.id, 1 as ebene
    FROM Ordner o
    WHERE o.parent_id IS NULL
  UNION ALL
  SELECT o.id, cte.ebene + 1
    FROM Ordner o
    INNER JOIN ordnerCTE cte ON o.parent_id = cte.ordner_id
)
SELECT COUNT(*) FROM ordnerCTE cte
WHERE cte.ebene = 4

Anzahl Ordner gruppiert nach Ebene

WITH ordnerCTE(ordner_id, ebene) AS
(
  SELECT o.id, 1 as ebene
    FROM Ordner o
    WHERE o.parent_id IS NULL
  UNION ALL
    SELECT o.id, cte.ebene + 1
    FROM Ordner o
    INNER JOIN ordnerCTE cte ON o.parent_id = cte.ordner_id
)
SELECT cte.ebene, COUNT(*) as anzahl_ordner
FROM ordnerCTE cte
GROUP BY cte.ebene

3 größten Dateien pro Ebene

Dieses Beispiel ist etwas komplexer, da man nicht einfach die drei größten Dateien haben möchte, was relativ einfach mit SELECT TOP 3… zu bewerkstelligen wäre, sondern die jeweils größten Dateien pro Ebene.

WITH ordnerMitEbene(ordner_id, ebene) AS
(
  SELECT o.id, 1 as ebene
    FROM Ordner o
    WHERE o.parent_id IS NULL
  UNION ALL
  SELECT o.id, cte.ebene + 1
    FROM Ordner o
    INNER JOIN ordnerMitEbene cte ON o.parent_id = cte.ordner_id
), dateiGroesseProEbene AS
(
  SELECT
    d.id as datei_id,
    d.ordner_id,
    d.groesse_kb,
    cte.ebene,
    ROW_NUMBER() OVER (PARTITION BY cte.ebene ORDER BY d.groesse_kb DESC) as rowNr
  FROM ordnerMitEbene cte
  INNER JOIN Datei d ON d.ordner_id = cte.ordner_id
)
SELECT cte.ebene, cte.datei_id, cte.groesse_kb, cte.ordner_id FROM dateiGroesseProEbene cte
WHERE cte.rowNr <= 3
ORDER BY ebene, rowNr

Ergebnis:

ebene datei_id groesse_kb ordner_id
1 4 230 1
2 5 934 3
2 3 732 5
2 1 324 3

 

Für diese Art von Abfragen eignen sich sogenannte Fensterfunktionen in Verbindung mit einer CTE. Während GROUP BY die Anzahl der Reihen meistens verringert, bleibt bei Fensterfunktionen die Anzahl der Reihen gleich. Durch eine Fensterfunktion werden die Reihen in verschiedene Partitionen (oder auch Fenster) aufgeteilt und für jede Reihe einer Partition wird ein Wert berechnet. Dies wird für jede Partition separat gemacht.

Ein Beispiel dafür ist die oben angeführte Funktion ROW_NUMBER(). Diese Funktion vergibt für jede Reihe eine Zahl beginnend mit 1 und dann aufsteigend, startet aber für jede Partition wieder bei 1.

Eine Fensterfunktion wird mit Hilfe der OVER-Klausel definiert. Durch PARTITION BY wird bestimmt, wie die Reihen aufgeteilt werden sollen. Dabei beschreiben die Schlüsselwörter der Fensterfunktion oben eigentlich schon ziemlich genau was gemacht werden soll:

Berechne die Reihenzahl (ROW_NUMBER()) für die Reihen jeder Partition (OVER), partitioniert durch die Ebene (PARTITION BY cte.ebene) und sortiert nach der absteigenden Größe der Datei (ORDER BY d.groesse_kb DESC).

Dass diese Fensterfunktion in eine CTE (dateiCTE) ausgelagert wird, hat den Grund, dass man, wie vorher im Artikel schon beschrieben wurde, in der WHERE-Klausel aufgrund der Evaluationsreihenfolge von SQL noch nicht auf Aliase (hier rowNr) zugreifen kann und daher die Begrenzung auf die TOP 3 Resultate (WHERE rowNr <= 3) nicht in demselben Statement, in dem auch die Fensterfunktion verwendet wird, angeben kann.

Die Alternative wäre auch hier ein Inline-View, welcher das Ganze aber unübersichtlicher machen würde. Durch die Verwendung der CTEs entspricht die Vorgehenslogik auch der Ausführungsreihenfolge und so kann man die Query von oben nach unten durchgehen:

  1. ordnerMitEbeneCTE: Hole rekursiv alle Ordner und füge jedem Ordner seine jeweilige Ebene hinzu.
  2. dateiGroesseProEbeneCTE: Hole die Dateien für jeden Ordner, teile sie nach Ebene auf und sortiere sie der Größe nach
  3. Für jede Ebene, zeige die größten drei Dateien an

CTEs als Allheilmittel?

Im Gegensatz zum ersten Teil, wo es für ein Problem mehrere Lösungen gab, die sich nur in ihrer Lesbarkeit und ggf. nur marginal in ihrer Performanz unterschieden haben, gab es in diesem Teil mit rekursiven CTEs eine Funktionalität, die sich mit anderen Queries nicht oder nur eingeschränkt nachbilden lässt und welche oft auch weniger elegant und weniger lesbar sind.

Jedoch gibt es meist verschiedene Ansätze zum Aufbau der Tabellen und Spalten, so dass sich ggf. für einen anderen Ansatz auch andere Queries eignen. Daher ist es auch wichtig den passenden Aufbau in Abhängigkeit der Anforderungen zu wählen. Wird z.B. eher viel gelesen, eingefügt oder aktualisiert, werden auf unser Beispiel bezogen viele Ordner und Dateien herumgeschoben, sollen viele Auswertungen auf der Ordnerstruktur gemacht werden, etc…

Aber gerade für Baum- und Graphenstrukturen sind CTEs oftmals eine elegante und performante Lösung die von nahezu allen relationalen Datenbanksystemen unterstützt wird.

 

Von Robert Vollmann | 24.06.2020
Robert Vollmann

Softwareentwicklung

Themen