SQL search depth/breadth first

1. Geringe Abweichung: Inhalt der <sequence column>

Die Search-Klausel von With Recursive erzeugt eine Spalte, mit der das Ergebnis entsprechend einer Tiefensuche oder Breitensuche sortiert werden kann.

Die Search-Klausel folgt unmittelbar auf ein rekursives With-Element – sogar noch vor der Cycle-Klausel. Sie legt die primäre Reihenfolge mit den Schlüsselworten Depth First (Tiefe zuerst) oder Breadth First (Breite zuerst) fest. In der darauffolgenden, zwingend erforderlichen By-Klausel wird durch eine Liste von Ausdrücken die Reihenfolge pro Ebene festgelegt. Zuletzt weist die Set-Klausel der so erzeugten Sequenzspalte einen Namen zu.

WITH RECURSIVE
     categories (category_id, parent, name)
  AS ( SELECT *
         FROM product_categories
        WHERE parent IS NULL
    UNION ALL
       SELECT pc.*
         FROM categories AS parent
         JOIN product_categories pc
           ON pc.parent = parent.category_id
     )
SEARCH DEPTH FIRST BY name SET seq_col
SELECT category_id, name
  FROM categories
 ORDER BY seq_col

Beachte, dass die Search-Klausel nicht festlegt, in welche Reihenfolge die Zeilen aus der rekursiven Abfrage kommen.0Stattdessen erzeugt sie seine Spalten, die in einer Order By-Klausel verwendet werden kann.

Das obere Beispiel durchwandert eine Hierarchie, wie zum Beispiel die unten dargestellte, vom Wurzelknoten zu den Blattknoten. Die Order By-Klausel in der letzten Zeile nutzt die durch die Search-Klausel erzeugte Sequenzspalte seq_col um die entsprechende Reihenfolge tatsächlich herzustellen. Dabei ist seq_col wirklich nur ein Spaltenname. Man kann ihn auch in die Select-Klausel aufnehmen, um sich den Inhalt anzusehen – oder select * verwenden. Natürlich kann man in der Order By-Klausel auch andere Spalten verwenden oder Asc/Desc und Nulls First/Last-Angaben machen.

Egal ob man eine Tiefe-zuerst oder eine Breite-zuerst Reihenfolge wählt, die Zeilen aus dem Initialisierungszweig der Rekursion haben in der Sequenzspalte immer den kleinsten Wert. Das heißt, dass man sie bei einer aufsteigenden Reihenfolge wie im Beispiel oben zuerst erhält. Konkret ist das der Wurzelknoten: All Goodies.

Die nächste Zeile ist – wiederum in beiden „Zuerst“-Fällen – das erste Kind auf der zweiten Ebene. Das ist allerdings nicht Types, sondern Brands, da die Angabe by name die Reihenfolge in der Ebene festlegt.

Danach unterscheiden sich die Reihenfolge zwischen Depth First und Breadth First. Depth first, liefert zuerst die tieferen Knoten. Das sind Modern SQL und Use The Index, Luke, in dieser Reihenfolge. Erst danach folgt der Nachbarknoten Types und dessen Kinder.

Breadth First liefert den Nachbarknoten Types jedoch noch vor den Knoten der dritten Ebene. Erst nach allen Knoten der zweiten Ebene folgen jene der dritten – in der durch die By-Klausel festgelegte Reihenfolge. Konkret: Books, Modern SQL, Mugs & co, Stickers, Use The Index, Luke. Beachte, dass die Geschwister nicht beieinanderbleiben. Die Kinder von Brands und Types kommen aufgrund der By name-Angabe entsprechend Ihrem Namen durcheinander.

Nennenswerte Erweiterungen

Standard SQL erlaubt keine Asc/Desc oder Nulls First/Last-Angaben in der By-Klausel von Search.1

SEARCH DEPTH FIRST BY name DESC SET seq_col

Daher ist das Umdrehen der Pro-Ebene-Reihenfolge in Standard-SQL nicht möglich. Da das jedoch eine nachvollziehbare Anforderung ist, gibt es Systeme, die solche Angaben unterstützen.

Inhalt der Sequenzspalte

Der SQL-Standard definiert die Search-Klausel anhand einer syntaktischen Transformation, die die Sequenzspalte mit Zeilenwerten (Breadth First) oder einem Array aus Zeilenwerten (Depth First) befüllt. Sortiert man anhand dieser Werte, erhält man die festgelegte Reihenfolge.2 Daraus folgt aber, dass die von der Order By-Klausel gewohnten Optionen nicht zur Verfügung stehen, da sie nicht in den Zeilenwerten untergebracht werden können.3 Daher ist es vermutlich kein Zufall, dass ausgerechnet jene Systeme, die die Order By-Optionen auch in Search…By erlauben, in der Sequenzspalte nicht die vom Standard vorgesehenen Zeilenwerte liefern, sondern eine einfache Ordnungszahl.

Weiterführende Links

• cycle: Endlosschleifen in rekursiven Abfragen verhindern

  Wenn sowohl Search als auch Cycle verwendet wird, muss Search zuerst angegeben werden.

• Anleitung: With — komplexe Abfragen strukturieren

Normative Referenzen

Die Search-Klausel ist in ISO/IEC 9075-2:2023 §7.18 als Teil des optionalen Features T131, „Recursive query“ definiert.