🥇PostgreSQL Antipatterns: „A végtelenség nem a határ!”, vagy egy kicsit a rekurzióról

rekurzió - nagyon hatékony és kényelmes mechanizmus, ha ugyanazokat a „mélyreható” műveleteket hajtják végre a kapcsolódó adatokon. De az ellenőrizetlen rekurzió olyan rossz, amely bármelyikhez vezethet végtelen végrehajtás folyamat, vagy (ami gyakrabban fordul elő). "elfogyasztja" az összes rendelkezésre álló memóriát.

A DBMS ebben a tekintetben ugyanazon az elveken dolgozik - "Azt mondták, hogy ássak, hát ástamAz Ön kérése nemcsak lelassíthatja a szomszédos folyamatokat, folyamatosan lefoglalva a processzor erőforrásait, hanem „ledobhatja” a teljes adatbázist, „felveszi” az összes rendelkezésre álló memóriát. védelem a végtelen rekurzió ellen - magának a fejlesztőnek a felelőssége.

A PostgreSQL-ben rekurzív lekérdezések használatának lehetősége a következőn keresztül WITH RECURSIVE a 8.4-es verzió időtlen időkben jelent meg, de továbbra is rendszeresen találkozhat potenciálisan sebezhető „védtelen” lekérdezésekkel. Hogyan szabadulhatsz meg az ilyen jellegű problémáktól?

Ne írjon rekurzív lekérdezéseket

És írj nem rekurzívakat. Üdvözlettel: K.O.

Valójában a PostgreSQL elég sok olyan funkciót kínál, amelyeket használhat nincs alkalmazza a rekurziót.

Használjon alapvetően más megközelítést a problémához

Néha egyszerűen „más oldalról” nézheti a problémát. Példát adtam egy ilyen helyzetre a cikkben "SQL HowTo: 1000 és az összesítés egyik módja" — egy számkészlet szorzása egyéni összesítő függvények használata nélkül:

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;

Ez a kérés helyettesíthető egy matematikai szakértői opcióval:

WITH src AS (
  SELECT unnest('{2,3,5,7,11,13,17,19}'::integer[]) prime
)
SELECT
  exp(sum(ln(prime)))::integer val
FROM
  src;

Használja a gener_series-t ciklusok helyett

Tegyük fel, hogy azzal a feladattal állunk szemben, hogy egy karakterlánchoz minden lehetséges előtagot generáljunk '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;

Biztos, hogy itt rekurzióra van szükséged?.. Ha használod LATERAL и generate_series, akkor még CTE-re sem lesz szüksége:

SELECT
  substr(str, 1, ln) str
FROM
  (VALUES('abcdefgh')) T(str)
, LATERAL(
    SELECT generate_series(length(str), 1, -1) ln
  ) X;

Az adatbázis szerkezetének módosítása

Például van egy fórumüzenettáblázata a kapcsolataival, hogy ki kinek válaszolt, vagy egy szál közösségi háló:

CREATE TABLE message(
  message_id
    uuid
      PRIMARY KEY
, reply_to
    uuid
      REFERENCES message
, body
    text
);
CREATE INDEX ON message(reply_to);

Nos, egy tipikus kérés az összes üzenet letöltésére egy témában valahogy így néz ki:

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;

De mivel mindig szükségünk van a teljes témára a gyökérüzenettől kezdve, akkor miért ne minden bejegyzéshez adja hozzá az azonosítóját automatikus?

-- добавим поле с общим идентификатором темы и индекс на него
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();

Most a teljes rekurzív lekérdezésünk csak erre redukálható:

SELECT
  *
FROM
  message
WHERE
  theme_id = $1;

Alkalmazott "korlátozók" használata

Ha valamilyen oknál fogva nem tudjuk megváltoztatni az adatbázis szerkezetét, nézzük meg, mire támaszkodhatunk, hogy még az adatokban lévő hiba jelenléte se vezessen végtelen rekurzióhoz.

Rekurziós mélységszámláló

Egyszerűen növeljük a számlálót eggyel minden rekurziós lépésnél, amíg el nem érjük azt a határt, amelyet nyilvánvalóan nem megfelelőnek tartunk:

WITH RECURSIVE T AS (
  SELECT
    0 i
  ...
UNION ALL
  SELECT
    i + 1
  ...
  WHERE
    T.i < 64 -- предел
)

Pro: Amikor megpróbálunk hurkolni, továbbra sem fogunk többet tenni, mint az iterációk meghatározott határértéke „mélységben”.
hátránya: Nincs garancia arra, hogy nem dolgozzuk fel újra ugyanazt a rekordot – például 15 és 25 fokos mélységben, majd minden +10-nél. A „szélességről” pedig senki nem ígért semmit.

Formálisan egy ilyen rekurzió nem lesz végtelen, de ha minden lépésnél exponenciálisan növekszik a rekordok száma, akkor mindannyian jól tudjuk, hogyan végződik...

lásd „A szemek problémája a sakktáblán”

Az "ösvény" őre

Felváltva hozzáadjuk a rekurziós útvonalon talált objektumazonosítókat egy tömbhöz, amely egy egyedi „útvonal” hozzá:

WITH RECURSIVE T AS (
  SELECT
    ARRAY[id] path
  ...
UNION ALL
  SELECT
    path || id
  ...
  WHERE
    id <> ALL(T.path) -- не совпадает ни с одним из
)

Pro: Ha van egy ciklus az adatokban, akkor egyáltalán nem dolgozzuk fel ugyanazt a rekordot ugyanazon az útvonalon belül.
hátránya: De ugyanakkor szó szerint megkerülhetjük az összes rekordot anélkül, hogy megismételnénk magunkat.

lásd "Knight's Move Problem"

Úthossz-korlát

Az érthetetlen mélységben való rekurziós „vándorlás” szituációjának elkerülésére kombinálhatjuk a két előző módszert. Vagy ha nem akarjuk támogatni a szükségtelen mezőket, a rekurzió folytatásának feltételét egészítsük ki az útvonal hosszának becsült értékével:

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
)

Válassz az ízlésednek megfelelő módszert!

Forrás: will.com

PostgreSQL Antipatterns: „A végtelenség nem a határ!”, vagy egy kicsit a rekurzióról