Antipatterns PostgreSQL: „Infinitul nu este limita!” sau Un pic despre recursivitate

Recursiune - un mecanism foarte puternic și convenabil dacă aceleași acțiuni „de profunzime” sunt efectuate asupra datelor aferente. Dar recursiunea necontrolată este un rău care poate duce la oricare execuție nesfârșită proces, sau (ceea ce se întâmplă mai des) să „mâncând” toată memoria disponibilă.

DBMS în acest sens funcționează pe aceleași principii - "Mi-au spus să sap, așa că am săpat„. Solicitarea dumneavoastră nu poate doar să încetinească procesele învecinate, ocupând constant resursele procesorului, ci și să „aruncă” întreaga bază de date, „mâncând” toată memoria disponibilă. Prin urmare protecție împotriva recursiunii infinite - responsabilitatea dezvoltatorului însuși.

În PostgreSQL, abilitatea de a utiliza interogări recursive prin WITH RECURSIVE a apărut în vremurile imemoriale ale versiunii 8.4, dar încă puteți întâlni în mod regulat solicitări „fără apărare” potențial vulnerabile. Cum să scapi de astfel de probleme?

Nu scrieți interogări recursive

Și scrieți altele nerecursive. Cu stimă, K.O.

De fapt, PostgreSQL oferă o mulțime de funcționalități pe care le puteți folosi nu aplica recursiunea.

Utilizați o abordare fundamental diferită a problemei

Uneori puteți privi problema doar din „parte diferită”. Am dat un exemplu de astfel de situație în articol „SQL HowTo: 1000 și un mod de agregare” — multiplicarea unui set de numere fără a utiliza funcții de agregare personalizate:

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;

Această solicitare poate fi înlocuită cu o opțiune din partea experților în matematică:

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

Utilizați generate_series în loc de bucle

Să presupunem că ne confruntăm cu sarcina de a genera toate prefixele posibile pentru un șir '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;

Sunteți sigur că aveți nevoie de recursivitate aici?.. Dacă utilizați LATERAL и generate_series, atunci nici măcar nu veți avea nevoie de CTE:

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

Modificați structura bazei de date

De exemplu, aveți un tabel cu mesaje de forum cu conexiuni de la cine a răspuns cui sau un fir de discuție rețea socială:

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

Ei bine, o solicitare tipică de a descărca toate mesajele pe un subiect arată cam așa:

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;

Dar din moment ce avem întotdeauna nevoie de întregul subiect din mesajul rădăcină, atunci de ce nu avem adăugați ID-ul său la fiecare intrare automat?

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

Acum, întreaga noastră interogare recursivă poate fi redusă doar la aceasta:

SELECT
  *
FROM
  message
WHERE
  theme_id = $1;

Utilizați „limitatori” aplicați

Dacă nu putem schimba structura bazei de date dintr-un motiv oarecare, să vedem pe ce ne putem baza, astfel încât chiar și prezența unei erori în date să nu conducă la recursivitate fără sfârșit.

Contor de adâncime a recursiunii

Pur și simplu creștem contorul cu unul la fiecare pas de recursivitate până ajungem la o limită pe care o considerăm evident inadecvată:

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

Pro: Când încercăm să facem buclă, nu vom face în continuare mai mult decât limita specificată de iterații „în profunzime”.
Contra: Nu există nicio garanție că nu vom procesa din nou aceeași înregistrare - de exemplu, la o adâncime de 15 și 25 și apoi la fiecare +10. Și nimeni nu a promis nimic despre „lățime”.

Formal, o astfel de recursivitate nu va fi infinită, dar dacă la fiecare pas numărul înregistrărilor crește exponențial, știm cu toții bine cum se termină...

vezi „Problema cerealelor pe tabla de șah”

Gardianul „căii”

Adăugăm alternativ toți identificatorii de obiect pe care i-am întâlnit de-a lungul căii recursive într-o matrice, care este o „cale” unică către acesta:

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

Pro: Dacă există un ciclu în date, nu vom procesa în mod repetat aceeași înregistrare în aceeași cale.
Contra: Dar, în același timp, putem ocoli literalmente toate înregistrările fără să ne repetăm.

vezi „Problema mișcării lui Knight”

Limită de lungime a căii

Pentru a evita situația de „rătăcire” recursiunii la o adâncime de neînțeles, putem combina cele două metode anterioare. Sau, dacă nu dorim să acceptăm câmpuri inutile, completați condiția pentru continuarea recursiunii cu o estimare a lungimii căii:

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
)

Alege o metodă pe gustul tău!

Sursa: www.habr.com