PostgreSQL antiobrasci: „Beskonačnost nije granica!“, ili Malo o rekurziji

Rekurzija - vrlo moćan i zgodan mehanizam ako se iste „dubinske“ radnje izvode na povezanim podacima. Ali nekontrolirana rekurzija je zlo koje može dovesti do bilo kojeg beskrajno izvršenje proces, ili (što se češće dešava) da "jede" svu raspoloživu memoriju.

DBMS u tom smislu radi na istim principima - "Rekli su mi da kopam, pa ja kopam". Vaš zahtjev može ne samo usporiti susjedne procese, konstantno zauzimajući procesorske resurse, već i "ispustiti" cijelu bazu podataka, "jedeći" svu dostupnu memoriju. Stoga zaštita od beskonačne rekurzije - odgovornost samog programera.

U PostgreSQL-u, mogućnost korištenja rekurzivnih upita putem WITH RECURSIVE pojavio u davna vremena verzije 8.4, ali i dalje se redovno možete susresti sa potencijalno ranjivim "bezobraćenim" zahtjevima. Kako se riješiti problema ove vrste?

Nemojte pisati rekurzivne upite

I napišite nerekurzivne. S poštovanjem, Vaš K.O.

U stvari, PostgreSQL pruža dosta funkcionalnosti koje možete koristiti ne primijeniti rekurziju.

Koristite fundamentalno drugačiji pristup problemu

Ponekad možete samo sagledati problem sa “druge strane”. U članku sam naveo primjer takve situacije "SQL HowTo: 1000 i jedan način agregacije" — množenje skupa brojeva bez korištenja prilagođenih agregatnih funkcija:

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;

Ovaj zahtjev se može zamijeniti opcijom stručnjaka za matematiku:

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

Koristite generate_series umjesto petlji

Recimo da smo suočeni sa zadatkom generiranja svih mogućih prefiksa za niz '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;

Jeste li sigurni da vam je potrebna rekurzija ovdje?.. Ako koristite LATERAL и generate_series, onda vam CTE neće ni trebati:

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

Promijenite strukturu baze podataka

Na primjer, imate tabelu poruka na forumu s vezama ko je kome odgovorio ili nit u njoj socijalna mreža:

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

Pa, tipičan zahtjev za preuzimanje svih poruka na jednu temu izgleda otprilike ovako:

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;

Ali pošto nam je uvijek potrebna cijela tema iz osnovne poruke, zašto onda ne bismo dodajte svoj ID svakom unosu automatski?

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

Sada se cijeli naš rekurzivni upit može svesti samo na ovo:

SELECT
  *
FROM
  message
WHERE
  theme_id = $1;

Koristite primijenjene "ograničavače"

Ako iz nekog razloga nismo u mogućnosti promijeniti strukturu baze podataka, da vidimo na što se možemo osloniti da čak i prisustvo greške u podacima ne dovede do beskonačne rekurzije.

Brojač dubine rekurzije

Jednostavno povećavamo brojač za jedan na svakom koraku rekurzije dok ne dostignemo granicu koju smatramo očigledno neadekvatnom:

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

Pro: Kada pokušamo da napravimo petlju, i dalje nećemo raditi više od navedenog ograničenja iteracija “u dubinu”.
Cons: Nema garancije da nećemo ponovo obraditi isti zapis - na primjer, na dubini od 15 i 25, a zatim svakih +10. I niko ništa nije obećavao o "širini".

Formalno, takva rekurzija neće biti beskonačna, ali ako se na svakom koraku broj zapisa eksponencijalno povećava, svi dobro znamo kako se završava...

vidi “Problem zrna na šahovskoj tabli”

Čuvar "puta"

Naizmjenično dodajemo sve identifikatore objekata na koje smo naišli duž putanje rekurzije u niz, koji je jedinstveni "put" do njega:

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

Pro: Ako postoji ciklus u podacima, apsolutno nećemo više puta obrađivati ​​isti zapis unutar iste putanje.
Cons: Ali u isto vrijeme, bukvalno možemo zaobići sve rekorde bez ponavljanja.

pogledajte "Problem vitezova poteza"

Ograničenje dužine putanje

Da bismo izbjegli situaciju da rekurzija „luta“ na neshvatljivoj dubini, možemo kombinirati dvije prethodne metode. Ili, ako ne želimo podržati nepotrebna polja, dopunimo uvjet za nastavak rekurzije procjenom dužine putanje:

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
)

Odaberite metodu po svom ukusu!

izvor: www.habr.com