— ist ein sehr mächtiger und nützlicher Mechanismus, wenn an verknüpften Daten die gleichen Aktionen „nach unten“ durchgeführt werden. Aber unkontrollierte Rekursion ist böse, die entweder zu endloser Ausführung des Prozesses führen kann, oder (was häufiger vorkommt) zu „Auszehrung“ des gesamten verfügbaren Speichers.
Datenbanken arbeiten in dieser Hinsicht nach denselben Prinzipien — "Sie haben gesagt, ich soll graben, also grabe ich". Ihre Anfrage kann nicht nur benachbarte Prozesse verlangsamen, indem sie ständig Rechenressourcen beansprucht, sondern auch die gesamte Datenbank „zum Absturz bringen“, indem sie den gesamten verfügbaren Speicher „aufbraucht“. Daher ist der Schutz vor endloser Rekursion die Verantwortung des Entwicklers.
In PostgreSQL wurde die Möglichkeit, rekursive Anfragen über bereits in der fernen Vergangenheit der Version 8.4 eingeführt, aber bis heute können potenziell verwundbare „unverteidigte“ Anfragen regelmäßig beobachtet werden. Wie kann man sich von solchen Problemen befreien?
Schreiben Sie keine rekursiven Anfragen
Sondern schreiben Sie nicht-rekursive. Mit freundlichen Grüßen, Ihr K.O.
Tatsächlich bietet PostgreSQL eine Vielzahl von Funktionen, die genutzt werden können, um nicht Rekursion anzuwenden.
Einen grundlegend anderen Ansatz für die Aufgabe verwenden
Manchmal kann man die Aufgabe einfach „aus einer anderen Perspektive“ betrachten. Ein Beispiel für solche Situationen habe ich in dem Artikel — die Multiplikation einer Menge von Zahlen, ohne benutzerdefinierte Aggregatfunktionen zu verwenden:
WITH RECURSIVE src AS (
SELECT '{2,3,5,7,11,13,17,19}'::integer[] arr
)
, T(i, val) AS (
SELECT
1::bigint
, 1
UNION ALL
SELECT
i + 1
, val * arr[i]
FROM
T
, src
WHERE
i <= array_length(arr, 1)
)
SELECT
val
FROM
T
ORDER BY -- Auswahl des endgültigen Ergebnisses
i DESC
LIMIT 1;Eine solche Anfrage kann durch die Variante eines Mathematikexperten ersetzt werden:
WITH src AS (
SELECT unnest('{2,3,5,7,11,13,17,19}'::integer[]) prime
)
SELECT
exp(sum(ln(prime)))::integer val
FROM
src;Verwenden Sie generate_series anstelle von Schleifen
Angenommen, wir haben die Aufgabe, alle möglichen Präfixe für die Zeichenkette 'abcdefgh':
WITH RECURSIVE T AS (
SELECT 'abcdefgh' str
UNION ALL
SELECT
substr(str, 1, length(str) - 1)
FROM
T
WHERE
length(str) > 1
)
TABLE T; Brauchen wir hier wirklich Rekursion?.. Wenn man LATERAL und generate_series, dann sind sogar CTEs nicht nötig:
SELECT
substr(str, 1, ln) str
FROM
(VALUES('abcdefgh')) T(str)
, LATERAL(
SELECT generate_series(length(str), 1, -1) ln
) X;Die Struktur der DB ändern
Zum Beispiel haben Sie eine Tabelle mit Forum-Nachrichten, in der verknüpft ist, wer wem geantwortet hat oder Threads in :
CREATE TABLE message(
message_id
uuid
PRIMARY KEY
, reply_to
uuid
REFERENCES message
, body
text
);
CREATE INDEX ON message(reply_to); 
Ein typischer Abfrage zum Laden aller Nachrichten zu einem bestimmten Thema sieht ungefähr so aus:
WITH RECURSIVE T AS (
SELECT
*
FROM
message
WHERE
message_id = $1
UNION ALL
SELECT
m.*
FROM
T
JOIN
message m
ON m.reply_to = T.message_id
)
TABLE T;Da wir jedoch immer das gesamte Thema vom Wurzelbeitrag benötigen, warum sollten wir nicht seine ID in jeden Beitrag automatisch hinzufügen?
-- Wir fügen ein Feld mit der gemeinsamen Thema-ID und einen Index dafür hinzu
ALTER TABLE message
ADD COLUMN theme_id uuid;
CREATE INDEX ON message(theme_id);
-- Wir initialisieren die Thema-ID im Trigger bei der Einfügung
CREATE OR REPLACE FUNCTION ins() RETURNS TRIGGER AS $$
BEGIN
NEW.theme_id = CASE
WHEN NEW.reply_to IS NULL THEN NEW.message_id -- nehmen wir aus dem Startereignis
ELSE ( -- oder aus der Nachricht, auf die wir antworten
SELECT
theme_id
FROM
message
WHERE
message_id = NEW.reply_to
)
END;
RETURN NEW;
END;
$$ LANGUAGE plpgsql;
CREATE TRIGGER ins BEFORE INSERT
ON message
FOR EACH ROW
EXECUTE PROCEDURE ins(); 
Jetzt kann unsere gesamte rekursive Abfrage auf Folgendes verkürzt werden:
SELECT
*
FROM
message
WHERE
theme_id = $1;Anwendungsbezogene 'Begrenzer' verwenden
Wenn wir aus bestimmten Gründen die Struktur der Datenbank nicht ändern können, lassen Sie uns schauen, auf was wir uns stützen können, damit das Vorhandensein von Fehlern in den Daten nicht zu einer endlosen Rekursion führt.
Rekursions-'Tiefenzähler'
Wir erhöhen einfach den Zähler um eins bei jedem Schritt der Rekursion, bis wir das Limit erreichen, das wir als eindeutig unangemessen ansehen:
WITH RECURSIVE T AS (
SELECT
0 i
...
UNION ALL
SELECT
i + 1
...
WHERE
T.i < 64 -- Limit
) Pro: Bei einem Versuch, in eine Schleife zu geraten, werden wir dennoch nicht mehr als die angegebene Anzahl von Iterationen 'nach unten' durchführen.
Contra: Es gibt keine Garantie, dass wir denselben Beitrag nicht mehrmals verarbeiten — zum Beispiel auf der Tiefe 15 und 25, und dann wieder alle 10. Und niemand hat etwas über 'nach außen' versprochen.
Formal wird eine solche Rekursion nicht unendlich sein, aber wenn die Anzahl der Beiträge bei jedem Schritt exponentiell steigt, wissen wir alle, wie das endet…
Wächter des 'Weges'
Schrittweise tragen wir alle IDs der Objekte, die uns auf dem Weg der Rekursion begegnen, in ein Array ein, das 'Weg' zu ihm ist:
MIT REKURSION T AS (
WÄHLE
ARRAY[id] pfad
...
VEREINIGE ALLE
WÄHLE
pfad || id
...
WO
id ALL(T.pfad) -- stimmt mit keiner der
) Pro: Wenn ein Zyklus in den Daten vorhanden ist, werden wir definitiv nicht denselben Datensatz innerhalb eines Pfades erneut verarbeiten.
Contra: Aber gleichzeitig können wir praktisch alle Datensätze durchlaufen, ohne uns zu wiederholen.
Pfad-Längenbeschränkung
Um die Situation des "Umherirrens" der Rekursion in unerklärlicher Tiefe zu vermeiden, können wir die beiden vorherigen Methoden kombinieren. Oder, wenn wir keine zusätzlichen Felder unterstützen möchten, erweitern wir die Fortsetzungsbedingung der Rekursion um die Bewertung der Pfadlänge:
MIT REKURSION T AS (
WÄHLE
ARRAY[id] pfad
...
VEREINIGE ALLE
WÄHLE
pfad || id
...
WO
id ALL(T.pfad) UND
array_length(T.pfad, 1) < 10
) Wählen Sie die Methode nach Ihrem Geschmack!
Quelle: habr.com
