Postgresql-rekursiver Self-Join

Dies ist eine klassische Verwendung eines einfachen rekursiven allgemeinen Tabellenausdrucks (WITH RECURSIVE ), verfügbar in PostgreSQL 8.4 und höher.

Hier demonstriert:http://sqlfiddle.com/#!12/78e15/9

Gegeben sind die Beispieldaten als SQL:

CREATE TABLE Table1
    ("ID1" text, "ID2" text)
;

INSERT INTO Table1
    ("ID1", "ID2")
VALUES
    ('vc1', 'vc2'),
    ('vc2', 'vc3'),
    ('vc3', 'vc4'),
    ('vc4', 'rc7')
;

Sie könnten schreiben:

WITH RECURSIVE chain(from_id, to_id) AS (
  SELECT NULL, 'vc2'
  UNION
  SELECT c.to_id, t."ID2"
  FROM chain c
  LEFT OUTER JOIN Table1 t ON (t."ID1" = to_id)
  WHERE c.to_id IS NOT NULL
)
SELECT from_id FROM chain WHERE to_id IS NULL;

Was dies tut, ist die Kette iterativ zu durchlaufen und jede Zeile zur chain hinzuzufügen Tabelle als Von- und Bis-Zeiger. Wenn es auf eine Zeile stößt, für die die „to“-Referenz nicht existiert, fügt es eine Null-„to“-Referenz für diese Zeile hinzu. Die nächste Iteration wird feststellen, dass die „to“-Referenz null ist und Nullzeilen erzeugen, wodurch die Iteration beendet wird.

Die äußere Abfrage nimmt dann Zeilen auf, die als das Ende der Kette bestimmt wurden, weil sie eine nicht vorhandene to_id haben.

Es erfordert ein wenig Mühe, sich mit rekursiven CTEs vertraut zu machen. Die wichtigsten Dinge, die Sie verstehen müssen, sind:

• Sie beginnen mit der Ausgabe einer initialen Abfrage, die sie immer wieder mit der Ausgabe des „rekursiven Teils“ (der Abfrage nach dem UNION) vereinen oder UNION ALL ) bis der rekursive Teil keine Zeilen hinzufügt. Das stoppt die Iteration.

• Sie sind nicht wirklich rekursiv, eher iterativ, obwohl sie für die Art von Dingen gut sind, für die Sie Rekursion verwenden könnten.

Sie bauen also im Grunde eine Tabelle in einer Schleife auf. Sie können Zeilen nicht löschen oder ändern, sondern nur neue hinzufügen. Daher benötigen Sie im Allgemeinen eine äußere Abfrage, die die Ergebnisse filtert, um die gewünschten Ergebniszeilen zu erhalten. Sie fügen häufig zusätzliche Spalten mit Zwischendaten hinzu, die Sie verwenden, um den Status der Iteration zu verfolgen, Stoppbedingungen zu steuern usw.

Es kann helfen, sich das ungefilterte Ergebnis anzusehen. Wenn ich die abschließende zusammenfassende Abfrage durch eine einfache SELECT * FROM chain ersetze Ich kann die generierte Tabelle sehen:

 from_id | to_id 
---------+-------
         | vc2
 vc2     | vc3
 vc3     | vc4
 vc4     | rc7
 rc7     | 
(5 rows)

Die erste Zeile ist die manuell hinzugefügte Startpunktzeile, in der Sie angeben, was Sie nachschlagen möchten - in diesem Fall war das vc2 . Jede nachfolgende Zeile wurde von UNION hinzugefügt ed rekursiver Begriff, der einen LEFT OUTER JOIN ausführt auf dem vorherigen Ergebnis und gibt einen neuen Satz von Zeilen zurück, die die vorherige to_id paaren (jetzt in der from_id Spalte) zur nächsten to_id . Wenn der LEFT OUTER JOIN stimmt dann nicht mit to_id überein wird null sein, was dazu führt, dass der nächste Aufruf jetzt Zeilen zurückgibt und die Iteration beendet.

Weil diese Abfrage nicht versucht, nur das letzte hinzuzufügen Zeile jedes Mal, es wiederholt tatsächlich ein ziemliches Stück Arbeit bei jeder Iteration. Um dies zu vermeiden, müssten Sie einen Ansatz ähnlich dem von Gordon verwenden, aber zusätzlich nach dem vorherigen Tiefenfeld filtern, wenn Sie die Eingabetabelle scannen, sodass Sie nur die neueste Zeile verknüpft haben. In der Praxis ist dies normalerweise nicht erforderlich, kann jedoch bei sehr großen Datensätzen oder wenn Sie keine geeigneten Indizes erstellen können, ein Problem darstellen.

Weitere Informationen finden Sie in der PostgreSQL-Dokumentation zu CTEs.