🥇PostgreSQL Antipatterns: “Beskonačnost nije granica!”, ili Malo o rekurziji

rekurzija - vrlo moćan i prikladan 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 događa) da "jede" svu dostupnu memoriju.

DBMS u tom pogledu rade na istim principima - "Rekli su mi da kopam, pa kopam". Vaš zahtjev ne samo da može usporiti susjedne procese, stalno zauzimajući resurse procesora, već i "ispustiti" cijelu bazu podataka, "jesti" 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 pamtivijeku verzije 8.4, ali još uvijek se redovito možete susresti s potencijalno ranjivim zahtjevima "bez obrane". 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 bitno drugačiji pristup problemu

Ponekad jednostavno možete pogledati problem s "druge strane". U članku sam naveo primjer takve situacije "SQL HowTo: 1000 i jedan način agregacije" — množenje skupa brojeva bez upotrebe 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 matematičkih stručnjaka:

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 ovdje treba rekurzija?.. Ako koristite LATERAL и generate_series, tada vam neće trebati ni CTE:

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

Promjena strukture baze podataka

Na primjer, imate tablicu poruka na forumu s vezama tko je kome odgovorio ili nit u društvena 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 jednoj temi 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 budući da uvijek trebamo cijelu temu iz korijenske poruke, zašto 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čivače"

Ako iz nekog razloga ne možemo promijeniti strukturu baze podataka, pogledajmo na što se možemo osloniti kako čak i postojanje pogreške u podacima ne bi dovelo do beskrajne rekurzije.

Brojač dubine rekurzije

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

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

Pro: Kada pokušamo napraviti petlju, i dalje nećemo učiniti više od navedenog ograničenja ponavljanja "u dubinu".
kontra: Nema jamstva da nećemo ponovno obraditi isti zapis – npr. na dubini od 15 i 25, pa svakih +10. A o "širini" nitko ništa nije obećao.

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

pogledajte “Problem zrnaca na šahovskoj ploči”

Č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 istog puta.
kontra: Ali u isto vrijeme, možemo doslovno zaobići sve rekorde bez ponavljanja.

vidi "Problem poteza skakača"

Ograničenje duljine puta

Kako bismo izbjegli situaciju da rekurzija “luta” na nesagledivoj dubini, možemo kombinirati dvije prethodne metode. Ili, ako ne želimo podržavati nepotrebna polja, dopunimo uvjet za nastavak rekurzije procjenom duljine puta:

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

PostgreSQL Antipatterns: “Beskonačnost nije granica!”, ili Malo o rekurziji