- ein sehr leistungsfähiger und praktischer Mechanismus, wenn dieselben „tiefgreifenden“ Aktionen für verwandte Daten ausgeführt werden. Aber unkontrollierte Rekursion ist ein Übel, das zu beidem führen kann endlose Hinrichtung Prozess, oder (was häufiger vorkommt) zu „frisst“ den gesamten verfügbaren Speicher.
DBMS arbeiten in dieser Hinsicht nach den gleichen Prinzipien – „Sie sagten mir, ich solle graben, also grabe ich". Ihre Anfrage kann nicht nur benachbarte Prozesse verlangsamen und ständig Prozessorressourcen beanspruchen, sondern auch die gesamte Datenbank „löschen“ und den gesamten verfügbaren Speicher „fressen“. Deshalb Schutz vor unendlicher Rekursion - die Verantwortung liegt beim Entwickler selbst.
In PostgreSQL besteht die Möglichkeit, rekursive Abfragen über zu verwenden tauchte schon seit der Gründung von Version 8.4 auf, dennoch kann es immer noch regelmäßig zu potenziell anfälligen „wehrlosen“ Anfragen kommen. Wie kann man sich von solchen Problemen befreien?
Schreiben Sie keine rekursiven Abfragen
Und schreibe nicht rekursive. Mit freundlichen Grüßen Ihr K.O.
Tatsächlich bietet PostgreSQL eine ganze Reihe von Funktionen, die Sie nutzen können nicht Rekursion anwenden.
Gehen Sie das Problem grundsätzlich anders an
Manchmal kann man das Problem einfach von der „anderen Seite“ betrachten. Ich habe in dem Artikel ein Beispiel für eine solche Situation gegeben – Multiplikation einer Zahlenmenge ohne Verwendung benutzerdefinierter Aggregatfunktionen:
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 -- отбор финального результата
i DESC
LIMIT 1;Diese Anfrage kann durch eine Option von 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
Nehmen wir an, wir stehen vor der Aufgabe, alle möglichen Präfixe für einen String zu generieren '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;
Sind Sie sicher, dass Sie hier eine Rekursion benötigen? Wenn Sie verwenden LATERAL и generate_series, dann brauchen Sie nicht einmal CTE:
SELECT
substr(str, 1, ln) str
FROM
(VALUES('abcdefgh')) T(str)
, LATERAL(
SELECT generate_series(length(str), 1, -1) ln
) X;Datenbankstruktur ändern
Beispielsweise verfügen Sie über eine Tabelle mit Forennachrichten mit Verbindungen darüber, wer wem geantwortet hat, oder über einen Thread darin :
CREATE TABLE message(
message_id
uuid
PRIMARY KEY
, reply_to
uuid
REFERENCES message
, body
text
);
CREATE INDEX ON message(reply_to);
Nun, eine typische Anfrage zum Herunterladen aller Nachrichten zu einem Thema sieht in etwa 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;Aber da wir immer das gesamte Thema aus der Stammnachricht benötigen, warum tun wir es dann nicht? Fügen Sie jedem Eintrag seine ID hinzu automatisch?
-- добавим поле с общим идентификатором темы и индекс на него
ALTER TABLE message
ADD COLUMN theme_id uuid;
CREATE INDEX ON message(theme_id);
-- инициализируем идентификатор темы в триггере при вставке
CREATE OR REPLACE FUNCTION ins() RETURNS TRIGGER AS $$
BEGIN
NEW.theme_id = CASE
WHEN NEW.reply_to IS NULL THEN NEW.message_id -- берем из стартового события
ELSE ( -- или из сообщения, на которое отвечаем
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 reduziert werden:
SELECT
*
FROM
message
WHERE
theme_id = $1;Verwenden Sie angewandte „Begrenzer“
Wenn wir aus irgendeinem Grund nicht in der Lage sind, die Struktur der Datenbank zu ändern, sehen wir uns an, worauf wir uns verlassen können, damit selbst das Vorhandensein eines Fehlers in den Daten nicht zu einer endlosen Rekursion führt.
Rekursionstiefenzähler
Wir erhöhen einfach den Zähler bei jedem Rekursionsschritt um eins, bis wir eine Grenze erreichen, die wir für offensichtlich unzureichend halten:
WITH RECURSIVE T AS (
SELECT
0 i
...
UNION ALL
SELECT
i + 1
...
WHERE
T.i < 64 -- предел
)
Vorteile: Wenn wir versuchen, eine Schleife durchzuführen, werden wir immer noch nicht mehr als die angegebene Grenze an Iterationen „in der Tiefe“ ausführen.
Nachteile: Es gibt keine Garantie dafür, dass wir denselben Datensatz nicht noch einmal verarbeiten – zum Beispiel bei einer Tiefe von 15 und 25 und dann alle +10. Und niemand hat etwas über „Breite“ versprochen.
Formal wird eine solche Rekursion nicht unendlich sein, aber wenn bei jedem Schritt die Anzahl der Datensätze exponentiell zunimmt, wissen wir alle genau, wie sie endet ...
Hüter des „Weges“
Wir fügen abwechselnd alle Objektbezeichner, die wir entlang des Rekursionspfads gefunden haben, in ein Array ein, das einen eindeutigen „Pfad“ dorthin darstellt:
WITH RECURSIVE T AS (
SELECT
ARRAY[id] path
...
UNION ALL
SELECT
path || id
...
WHERE
id <> ALL(T.path) -- не совпадает ни с одним из
)
Vorteile: Wenn es einen Zyklus in den Daten gibt, werden wir auf keinen Fall denselben Datensatz wiederholt innerhalb desselben Pfads verarbeiten.
Nachteile: Aber gleichzeitig können wir buchstäblich alle Datensätze umgehen, ohne uns zu wiederholen.
Pfadlängenbegrenzung
Um zu vermeiden, dass die Rekursion in einer unverständlichen Tiefe „wandert“, können wir die beiden vorherigen Methoden kombinieren. Oder, wenn wir keine unnötigen Felder unterstützen möchten, ergänzen Sie die Bedingung für die Fortsetzung der Rekursion durch eine Schätzung der Pfadlänge:
WITH RECURSIVE T AS (
SELECT
ARRAY[id] path
...
UNION ALL
SELECT
path || id
...
WHERE
id <> ALL(T.path) AND
array_length(T.path, 1) < 10
)
Wählen Sie eine Methode nach Ihrem Geschmack!
Source: habr.com