🥇PostgreSQL Antipatterns: "L'infinitu ùn hè micca u limitu!", o Un pocu di ricursione

Ricursione - un mecanismu assai putente è còmuda se e stesse azzioni "in profonda" sò realizate nantu à e dati rilativi. Ma a ricursione incontrollata hè un male chì pò purtà à l'una o l'altra esecuzione infinita prucessu, o (chì succede più spessu) à "manghjendu" tutta a memoria dispunibile.

DBMS in questu sensu travaglia nantu à i stessi principii - "M'anu dettu di scavà, cusì aghju scavatu". A vostra dumanda ùn pò micca solu rallentà i prucessi vicini, pigghiannu constantemente risorse di u processatore, ma ancu "drop" tutta a basa di dati, "manghjendu" tutta a memoria dispunibule. prutezzione contra a recurssioni infinita - a rispunsabilità di u sviluppatore stessu.

In PostgreSQL, a capacità di utilizà e dumande recursive via WITH RECURSIVE apparsu in i tempi immemorabili di a versione 8.4, ma pudete sempre incontru regularmente richieste "senza difesa" potenzialmente vulnerabili. Cumu caccià i prublemi di stu tipu?

Ùn scrive micca e dumande recursive

È scrivite micca ricursivi. Sinceramente, u vostru K.O.

In fatti, PostgreSQL furnisce assai funziunalità chì pudete aduprà ùn applicà a ricursione.

Aduprate un approcciu fundamentale differente à u prublema

Calchì volta vi pò solu fighjulà u prublema da u "parte differente". Aghju datu un esempiu di una tale situazione in l'articulu "SQL HowTo: 1000 è un modu di aggregazione" - multiplicazione di un inseme di numeri senza aduprà funzioni aggregate persunalizate:

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;

Questa dumanda pò esse rimpiazzata cù una opzione da esperti di matematica:

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

Aduprate generate_series invece di loops

Diciamu chì simu di fronte à u compitu di generà tutti i prefissi pussibuli per una stringa '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;

Sò sicuru d'avè bisognu di ricursione quì ? .. Sè aduprate LATERAL и generate_series, allora ùn avete mancu bisognu di CTE:

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

Cambia a struttura di a basa di dati

Per esempiu, avete una tavola di messagi di foru cù cunnessione da quale hà rispostu à quale, o un filu in rete suciale:

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

Ebbè, una dumanda tipica per scaricà tutti i missaghji nantu à un tema s'assumiglia à questu:

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;

Ma postu chì avemu sempre bisognu di tuttu u tema da u messagiu radicali, perchè ùn avemu micca aghjunghje u so ID à ogni entrata autumàticu?

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

Avà a nostra intera dumanda recursiva pò esse ridutta solu à questu:

SELECT
  *
FROM
  message
WHERE
  theme_id = $1;

Aduprate "limitatori" applicati

Se ùn pudemu micca cambià a struttura di a basa di dati per qualchì ragiuni, vedemu ciò chì pudemu cunfidassi in modu chì ancu a presenza di un errore in i dati ùn porta micca à una recursione infinita.

Contatore di prufundità di ricursione

Aumentemu simpricimenti u cuntatore da unu à ogni passu di recursione finu à ghjunghje à un limitu chì cunsideremu ovviamente inadegwate:

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

Pro: Quandu pruvemu à loop, ùn faremu micca più di u limitu specificatu di iterazioni "in prufundità".
Cons: Ùn ci hè micca guarantisci chì ùn avemu micca processatu u stessu record novu - per esempiu, à una prufundità di 15 è 25, è dopu ogni +10. È nimu hà prumessu nunda di "larghezza".

Formalmente, una tale recursione ùn serà micca infinita, ma s'ellu à ogni passu u numeru di registri aumenta in modu esponenziale, tutti sapemu bè cumu finisce...

vede "U prublema di i grani nantu à una scacchiera"

Guardian di u "caminu"

Aghjunghjemu alternativamente tutti l'identificatori di l'ughjettu chì avemu scontru longu u percorsu di ricursione in un array, chì hè un "path" unicu à questu:

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

Pro: Se ci hè un ciculu in i dati, ùn avemu micca assolutamente processatu u listessu record ripetutamente in u stessu percorsu.
Cons: Ma à u stessu tempu, pudemu literalmente bypassà tutti i registri senza ripetiri.

vede "Problemu di Move di Cavaliere"

Limite di a lunghezza di a strada

Per evitari a situazione di ricursione "vandering" à una prufundità incomprensibile, pudemu cumminà i dui metudi previ. O, se ùn vulemu sustene campi innecessarii, cumplementà a cundizione per cuntinuà a ricursione cù una stima di a longa di a strada:

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
)

Sceglite un metudu à u vostru gustu!

Source: www.habr.com

PostgreSQL Antipatterns: "L'infinitu ùn hè micca u limitu!", o Un pocu di ricursione