🥇PostgreSQL Antipatterns: "Enfini se pa limit la!", oswa Yon ti kras sou rekursion

Rekursion - yon mekanis trè pwisan ak pratik si menm aksyon "an pwofondè" yo fèt sou done ki gen rapò. Men, retou san kontwòl se yon mal ki ka mennen nan swa ekzekisyon kontinuèl pwosesis, oswa (ki rive pi souvan) nan "manje" tout memwa ki disponib.

DBMS nan sans sa a travay sou menm prensip yo - "Yo di m fouye, se konsa mwen fouye". Demann ou a ka pa sèlman ralanti pwosesis vwazen yo, toujou ap pran resous processeur, men tou, "depoze" baz done a tout antye, "manje" tout memwa ki disponib. Se poutèt sa. pwoteksyon kont repetisyon enfini - responsablite pwomotè a tèt li.

Nan PostgreSQL, kapasite pou sèvi ak rekèt rekursif atravè WITH RECURSIVE parèt nan tan imemoryal nan vèsyon 8.4, men ou ka toujou rankontre regilyèman potansyèlman vilnerab "san defans" demann. Ki jan yo debarase tèt ou de pwoblèm nan kalite sa a?

Pa ekri demann rekursif

Epi ekri sa ki pa rekursif. Sensèman, K.O.

An reyalite, PostgreSQL bay anpil fonksyonalite ke ou ka itilize pa gen okenn aplike recursion.

Sèvi ak yon apwòch fondamantalman diferan nan pwoblèm nan

Pafwa ou ka jis gade nan pwoblèm nan soti nan "bò a diferan". Mwen bay yon egzanp yon sitiyasyon konsa nan atik la "SQL HowTo: 1000 ak yon sèl fason pou agrégation" — miltiplikasyon yon seri nimewo san yo pa itilize fonksyon total koutim:

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;

Ou ka ranplase demann sa a ak yon opsyon ekspè nan matematik:

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

Sèvi ak generate_series olye de boucles

Ann di nou ap fè fas ak travay la nan jenere tout prefiks posib pou yon fisèl '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;

Èske ou sèten ou bezwen rekursion isit la? .. Si ou itilize LATERAL и generate_series, Lè sa a, ou p ap menm bezwen CTE:

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

Chanje estrikti baz done

Pou egzanp, ou gen yon tablo nan mesaj fowòm ak koneksyon ki soti nan ki moun ki reponn a ki moun, oswa yon fil nan rezo sosyal:

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

Oke, yon demann tipik pou telechaje tout mesaj sou yon sijè sanble yon bagay tankou sa 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;

Men, depi nou toujou bezwen sijè a tout antye soti nan mesaj la rasin, Lè sa a, poukisa nou pa fè sa ajoute ID li nan chak antre otomatik?

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

Koulye a, tout rechèch rekursif nou an ka redwi a jis sa a:

SELECT
  *
FROM
  message
WHERE
  theme_id = $1;

Sèvi ak "limitateur" aplike

Si nou pa kapab chanje estrikti baz done a pou kèk rezon, ann wè sou kisa nou ka konte pou menm prezans yon erè nan done yo pa mennen nan repetisyon kontinuèl.

Kontwa pwofondè Recursion

Nou senpleman ogmante kontwa a pa youn nan chak etap rekouvèr jiskaske nou rive nan yon limit ke nou konsidere evidamman ensifizan:

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

Pro: Lè nou eseye bouk, nou pral toujou fè pa plis pase limit la espesifye nan iterasyon "an pwofondè".
Kont: Pa gen okenn garanti ke nou pa pral trete menm dosye a ankò - pou egzanp, nan yon pwofondè de 15 ak 25, ak Lè sa a, chak +10. E pesonn pa te pwomèt anyen sou "lajè".

Fòmèlman, tankou yon retou pa pral enfini, men si nan chak etap kantite dosye ogmante eksponansyèlman, nou tout konnen byen ki jan li fini ...

gade "Pwoblèm grenn yo sou yon echikye"

Gadyen "chemen an"

Nou altènativman ajoute tout idantifyan objè yo nou te rankontre sou chemen an recursion nan yon etalaj, ki se yon "chemen" inik nan li:

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

Pro: Si gen yon sik nan done yo, nou absoliman pa pral trete menm dosye a repete nan menm chemen an.
Kont: Men, an menm tan an, nou ka literalman kontoune tout dosye yo san yo pa repete tèt nou.

gade "pwoblèm mouvman Knight an"

Limit longè chemen

Pou evite sitiyasyon an nan recursion "egare" nan yon pwofondè enkonpreyansib, nou ka konbine de metòd anvan yo. Oswa, si nou pa vle sipòte jaden ki pa nesesè yo, konplete kondisyon an pou kontinye rekursion a ak yon estimasyon nan longè chemen an:

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
)

Chwazi yon metòd nan gou ou!

Sous: www.habr.com

PostgreSQL Antipatterns: "Enfini se pa limit la!", oswa Yon ti kras sou repetisyon