PostgreSQL Antipatterns: “Neskončnost ni meja!” ali Nekaj ​​o rekurziji

Rekurzija - zelo zmogljiv in priročen mehanizem, če se enaka "poglobljena" dejanja izvajajo na povezanih podatkih. Toda nenadzorovana rekurzija je zlo, ki lahko privede do enega ali drugega neskončno izvajanje ali (kar se zgodi pogosteje) do "požre" ves razpoložljivi pomnilnik.

DBMS v zvezi s tem delujejo po enakih načelih - "Rekli so mi, naj kopam, zato kopam". Vaša zahteva lahko ne samo upočasni sosednje procese, nenehno zavzema procesorske vire, ampak tudi "spusti" celotno bazo podatkov in "poje" ves razpoložljivi pomnilnik. Zato zaščita pred neskončno rekurzijo - odgovornost razvijalca samega.

V PostgreSQL je možnost uporabe rekurzivnih poizvedb prek WITH RECURSIVE se je pojavil v nedavnih časih različice 8.4, vendar lahko še vedno redno naletite na potencialno ranljive "neobrambne" zahteve. Kako se znebiti tovrstnih težav?

Ne pišite rekurzivnih poizvedb

In napišite nerekurzivne. S spoštovanjem, vaš K.O.

Pravzaprav PostgreSQL ponuja kar veliko funkcij, ki jih lahko uporabite ne uporabite rekurzijo.

Uporabite bistveno drugačen pristop k problemu

Včasih lahko preprosto pogledate na problem z "druge strani". V članku sem navedel primer takšne situacije "SQL HowTo: 1000 in en način združevanja" — množenje niza števil brez uporabe agregatnih funkcij po meri:

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;

To zahtevo lahko nadomestite z možnostjo strokovnjakov za matematiko:

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

Uporabite generate_series namesto zank

Recimo, da se soočimo z nalogo generiranja vseh možnih predpon 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;

Ali ste prepričani, da tukaj potrebujete rekurzijo?.. Če uporabljate LATERAL и generate_series, potem sploh ne boste potrebovali CTE:

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

Spremenite strukturo baze podatkov

Na primer, imate tabelo forumskih sporočil s povezavami od tega, kdo je komu odgovoril, ali nit v njej socialno omrežje:

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

No, tipična zahteva za prenos vseh sporočil na eno temo izgleda nekako takole:

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;

A ker vedno potrebujemo celotno temo iz korenskega sporočila, zakaj je ne bi vsakemu vnosu dodajte svoj ID samodejno?

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

Zdaj lahko našo celotno rekurzivno poizvedbo skrčimo samo na to:

SELECT
  *
FROM
  message
WHERE
  theme_id = $1;

Uporabite uporabljene "omejevalnike"

Če iz nekega razloga ne moremo spremeniti strukture baze podatkov, poglejmo, na kaj se lahko zanesemo, da tudi prisotnost napake v podatkih ne vodi do neskončne rekurzije.

Rekurzijski števec globine

Števec preprosto povečamo za eno na vsakem koraku rekurzije, dokler ne dosežemo meje, ki se nam zdi očitno neustrezna:

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

Pro: Ko poskušamo narediti zanko, še vedno ne bomo naredili več kot je podana omejitev ponovitev "poglobljeno".
slabosti: Nobenega zagotovila ni, da istega zapisa ne bomo ponovno obdelali – na primer na globini 15 in 25, nato pa vsakih +10. In nihče ni nič obljubljal o "širini".

Formalno taka rekurzija ne bo neskončna, a če na vsakem koraku število zapisov narašča eksponentno, vsi dobro vemo, kako se konča ...

glej “Problem zrn na šahovnici”

Varuh "poti"

Izmenično dodajamo vse identifikatorje objektov, ki smo jih srečali vzdolž poti rekurzije, v matriko, ki je edinstvena "pot" do nje:

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

Pro: Če je v podatkih cikel, nikakor ne bomo večkrat obdelovali istega zapisa znotraj iste poti.
slabosti: A hkrati lahko vse rekorde dobesedno obidemo, ne da bi se ponavljali.

glej "Težava s potezo skakača"

Omejitev dolžine poti

Da bi se izognili situaciji, ko bi rekurzija "tavala" na nedojemljivi globini, lahko združimo prejšnji dve metodi. Ali pa, če ne želimo podpirati nepotrebnih polj, dopolnimo pogoj za nadaljevanje rekurzije z oceno dolžine poti:

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
)

Izberite metodo po svojem okusu!

Vir: www.habr.com