Lernen Sie die Leistungsfähigkeit von rekursiven SQL-Abfragen kennen

In der Regel sind die SQL-Abfragen, die wir in einer Datenbank ausführen, recht einfach. Das hängt natürlich von Ihrer Rolle ab. Analysten in Data Warehouses rufen ganz andere Arten von Informationen ab und verwenden (sehr oft) viel kompliziertere Abfragen als Softwareingenieure, die CRUD-Anwendungen erstellen.

Manchmal ist es jedoch einfacher oder eleganter, eine etwas anspruchsvollere Abfrage auszuführen, ohne dass eine weitere Datenverarbeitung im Code erforderlich ist. Eine Möglichkeit, dies zu erreichen, ist eine SQL-Funktion namens rekursive Abfragen.

Nehmen wir ein Beispiel aus der Praxis. Nehmen wir an, wir haben eine Datenbank mit einer Liste von Knoten und einer Liste von Verbindungen zwischen ihnen (Sie können sich diese als Städte und Straßen vorstellen). Unsere Aufgabe ist es, den kürzesten Weg von Knoten 1 zu Knoten 6 zu finden.

Nun, eigentlich ist es nichts anderes als Graphentraversal. Der erste Gedanke, den ein durchschnittlicher Softwareentwickler haben könnte, wäre, alle Zeilen aus beiden Tabellen zu holen und einen DFS- (Depth-First Search) oder BFS-Algorithmus (Breadth-First Search) in seiner bevorzugten Programmiersprache zu implementieren. Das ist keine schlechte Idee (wenn man gerne programmiert 😉 ), aber man kann es mit einer einzigen SQL-Abfrage machen!

WITH-Klausel - Gemeinsame Tabellenausdrücke zur Rettung!

Hinweis: Alle Beispiele wurden für PostgreSQL 9.3 geschrieben; es sollte jedoch nicht schwer sein, sie mit einem anderen RDBMS nutzbar zu machen.

Wenn Ihr RDBMS PostgreSQL, IBM DB2, MS SQL Server, Oracle (nur ab 11g Release 2) oder MySQL (nur ab Release 8.0.1) ist, können Sie WITH-Abfragen verwenden, die als Common Table Expressions (CTEs) bekannt sind. Im Allgemeinen ermöglichen sie es Ihnen, komplizierte Abfragen in eine Reihe von einfacheren Abfragen aufzuteilen, wodurch eine Abfrage leichter zu lesen ist. Die Struktur einer WITH-Klausel ist wie folgt:

WITH [cte_name] AS (
	[cte_term])
SELECT ... FROM [cte_name];

Wir möchten zum Beispiel höchstens 3 Knoten erhalten, deren Gesamtlänge der ausgehenden Verbindungen mindestens 100 beträgt und mindestens eine einzelne ausgehende Verbindung eine Länge von mehr als 50 hat. Sie müssen das folgende Beispiel nicht vollständig verstehen, schauen Sie sich einfach die Abfragestruktur an. Anstatt eine Abfrage wie diese zu schreiben:

SELECT * FROM node 
WHERE id IN (
    SELECT distinct node_from_id 
    FROM link
    WHERE length > 50 
      AND node_from_id IN (
        SELECT node_from_id
        FROM link 
        GROUP BY node_from_id 
        HAVING SUM(length) >= 100 
        ORDER BY SUM(length) DESC
        LIMIT 3));

können wir sie wie folgt schreiben:

WITH
longest_outgoing_links AS (
    SELECT node_from_id
    FROM link 
    GROUP BY node_from_id 
    HAVING SUM(length) >= 100 
    ORDER BY SUM(length) DESC
    LIMIT 3),
nodes_from_longest_outgoing_links AS (
    SELECT distinct node_from_id 
    FROM link
    WHERE length > 50 
      AND node_from_id IN 
         (SELECT * FROM longest_outgoing_links)
)
SELECT * FROM node 
WHERE id IN (SELECT * FROM nodes_from_longest_outgoing_links);

Die Abfragen werden separat definiert, was das Verständnis bei der Implementierung komplizierterer Beispiele erheblich erleichtert.

Ein wichtiger Punkt: CTEs können auch eine rekursive Struktur haben:

WITH RECURSIVE [cte_name] (column, ...) AS (
    [non-recursive_term]
    UNION ALL
    [recursive_term])
SELECT ... FROM [cte_name];

Wie funktioniert das?

Das ist ganz einfach. Im ersten Schritt wird ein nicht rekursiver Term ausgewertet. Anschließend wird für jede Ergebniszeile der vorherigen Auswertung ein rekursiver Term ausgewertet, dessen Ergebnisse an die vorherigen angehängt werden. Der rekursive Term hat Zugriff auf die Ergebnisse des zuvor ausgewerteten Terms.

Ein einfaches Beispiel #1

Schauen wir uns ein einfaches Beispiel an - die Multiplikation mit 2:

WITH RECURSIVE x2 (result) AS ( 
    SELECT 1 
    UNION ALL 
    SELECT result*2 FROM x2) 
SELECT * FROM x2 LIMIT 10; 

 result 
-------- 
      1 
      2 
      4 
      8 
     16 
     32 
     64 
    128 
    256 
    512 
(10 rows)

Im ersten Schritt ist die einzige Ergebniszeile "1". Dann gibt es UNION ALL mit einem rekursiven Term. 1 wird mit 2 multipliziert, was zu einer Ergebniszeile - "2" - führt. Im Moment gibt es zwei Ergebniszeilen: 1, 2. Die letzte Termauswertung ergab jedoch nur eine Zeile - "2" - und diese wird an den nächsten Rekursionsschritt weitergegeben. 2 wird mit 2 multipliziert, was "4" ergibt, und so weiter... In diesem Beispiel wäre die Rekursion unendlich, wenn wir nicht die LIMIT Klausel angeben würden.

Ein einfaches Beispiel #2

Machen wir ein weiteres schnelles (typisch akademisches) Beispiel - die Fibonacci-Folge. Sie ist wie folgt definiert:

Eine solche Funktion kann in SQL mit der WITH-Klausel definiert werden:

WITH RECURSIVE fib(f1, f2) AS ( 
    SELECT 0, 1 
    UNION ALL 
    SELECT f2, (f1+f2) FROM fib ) 
SELECT f1 FROM fib LIMIT 10;

 f1 
---- 
  0 
  1 
  1 
  2 
  3 
  5 
  8 
 13 
 21 
 34 
(10 Zeilen)

Ich hoffe, das Konzept ist jetzt klar.

Graph Traversal

Kehren wir zurück zu unserem Beispiel mit einem Graphen-Traversal. Wir wollen den kürzesten Weg zwischen zwei Knoten finden. So sieht die DB-Struktur aus:

Um unser SQL besser lesbar zu machen, definieren wir eine einfache Ansicht node_links_view, die node mit link und wieder mit node verbindet:

CREATE VIEW node_links_view AS 
SELECT 
    n1.id AS node_id, 
    n1.name AS node_name, 
    n2.id AS destination_node_id, 
    n2.name AS ziel_knoten_name, 
    l.length AS link_length 
FROM 
    Knoten n1 
    JOIN link l ON (n1.id = l.node_from_id) 
    JOIN node n2 ON (l.node_to_id = n2.id);

Nun sieht unsere Modellstruktur wie folgt aus:

Was brauchen wir als Ergebnis der Abfrage? Wir wollen einen genauen Pfad zwischen den Knoten und seine gesamte Länge. Um Zyklen im Graphen auszuschließen, benötigen wir außerdem ein Kennzeichen, das angibt, ob der letzte Knoten bereits besucht wurde. Der erste Teil der CTE-Definition sieht also wie folgt aus:

WITH RECURSIVE search_path (path_ids, length, is_visited) AS 

Im ersten Schritt müssen wir alle Links vom Anfangsknoten holen:

   
SELECT . 
    ARRAY[node_id, destination_node_id], -- path_ids
    link_length, -- Länge
    node_id = destination_node_id -- is_visited
FROM 
    node_links_view;

Das ist unser nicht-rekursiver Begriff.

Nun gehen wir rekursiv vor, beginnend mit dem zuletzt besuchten Knoten, der das letzte Element in einem Array ist:

    SELECT 
        path_ids || d.destination_node_id, -- path_ids
        f.length + d.link_length, -- length
        d.destination_node_id = ANY(f.path_ids) -- is_visited
    FROM 
        node_links_view d, 
        such_pfad f 
    WHERE 
        f.path_ids[array_length(path_ids, 1)] = d.node_id 
        AND NOT f.is_visited;

Wie funktioniert das? Sehen Sie sich die Klauseln FROM und WHERE an. Die Abfrage holt die nächsten Zeilen aus node_link_view die am letzten Knoten der vorherigen Auswertung beginnen, der nicht mit einem Zyklus endete. Sie gibt ein Array zurück, das um den Zielknoten des Links, eine Summe der Längen und ein Flag, das bestimmt, ob dieser Knoten zuvor besucht wurde, erweitert wird. Dieser rekursive Teil der Abfrage wird so lange ausgeführt, wie es Links zu nicht besuchten Knoten gibt.

So, hier ist eine vollständige SQL-Abfrage, die alle Pfade vom Knoten mit id=1 zum Knoten mit id=6 abruft:

WITH RECURSIVE search_path (path_ids, length, is_visited) AS 
( 
    SELECT 
        ARRAY[node_id, destination_node_id], 
        link_length, 
        knoten_id = ziel_knoten_id 
    FROM 
        node_links_view 

    UNION ALL 
    SELECT 
        path_ids || d.destination_node_id, 
        f.length + d.link_length, 
        d.ziel_knoten_id = ANY(f.pfad_ids) 
    FROM 
        node_links_view d, 
        such_pfad f 
    WHERE 
    f.pfad_ids[array_length(pfad_ids, 1)] = d.node_id 
    AND NOT f.is_visited 
) 
SELECT * FROM such_pfad 
WHERE pfad_ids[1] = 1 
AND pfad_ids[array_length(pfad_ids, 1)] = 6 
ORDER BY length;

Als Ergebnis erhalten wir alle Pfade von Knoten 1 bis Knoten 6, geordnet nach der gesamten Pfadlänge:

 path_ids | length | is_visited 
---------------+--------+------------ 
 {1,3,2,5,6}   | 140 | f 
 {1,2,5,6}     | 150 | f 
 {1,3,4,5,6}   | 150 | f 
 {1,3,4,6}     | 190 | f 
 {1,2,3,4,5,6} | 200 | f 
 {1,2,3,4,6}   | 240 | f 
(6 Zeilen) 

Der kürzeste Weg ist der erste, also können wir eine LIMIT-Klausel hinzufügen, um nur ein Ergebnis zu erhalten.

Erinnern Sie sich, dass wir die externe Ansicht - node_links_view - erstellt haben, um die SQL einfacher zu lesen? Wir können dasselbe mit einer CTE tun:

WITH RECURSIVE search_path (path_ids, length, is_visited) AS 
( 
    SELECT 
        ARRAY[node_id, destination_node_id], 
        link_length, 
        knoten_id = ziel_knoten_id 
    FROM node_links_select

    UNION ALL 
    SELECT 
        path_ids || d.destination_node_id, 
        f.length + d.link_length, 
        d.ziel_knoten_id = ANY(f.pfad_ids) 
    FROM node_links_select d, 
        such_pfad f 
    WHERE 
        f.path_ids[array_length(path_ids, 1)] = d.node_id 
        AND NOT f.is_visited 
), 

node_links_select AS ( 
    SELECT 
        n1.id AS node_id, 
        n1.name AS node_name, 
        n2.id AS destination_node_id, 
        n2.name AS ziel_knoten_name, 
        l.length AS link_length 
    FROM 
        Knoten n1 
        JOIN link l ON (n1.id = l.node_from_id) 
        JOIN Knoten n2 ON (l.node_to_id = n2.id) 
)

SELECT * FROM such_pfad 
WHERE pfad_ids[1] = 1 
AND pfad_ids[array_length(pfad_ids, 1)] = 6 
ORDER BY length;

Hinweis: Dieses Beispiel ist in keiner Weise optimiert! Es soll Ihnen nur zeigen, wie Sie rekursive CTEs verwenden können.

Oracle (vor 11g Release 2) - Hierarchische Abfragen

Bis zu Oracle 11g Release 2 unterstützten Oracle-Datenbanken keine rekursiven WITH-Abfragen. In Oracle SQL werden diese Arten von Abfragen hierarchische Abfragen genannt und sie haben eine völlig andere Syntax, aber die Idee ist die gleiche. Mehr über hierarchische Abfragen können Sie in der Oracle-Dokumentation nachlesen.

MySQL - 33 Monate Schweigen...

Schlechte Nachrichten für MySQL-Benutzer. Es unterstützt die WITH-Klausel nicht, obwohl es viele Anfragen nach einer solchen Funktion gab. Wahrscheinlich war die erste diese, die seit 33 Monaten ignoriert wurde und seit Januar 2006 nicht mehr gelöst wurde...

Aktualisierung: Rekursive WITH-Abfragen sind in MySQL seit der Version 8.0.1, die im April 2017 veröffentlicht wurde, verfügbar.

Ich hoffe, die Idee der rekursiven Abfragen ist Ihnen nun klar. Viel Spaß beim rekursiven Genießen von rekursiven Abfragen!