🥇PostgreSQL-i antimustrid: "Lõpmatus pole piir!" ehk Natuke rekursioonist

rekursioon - väga võimas ja mugav mehhanism, kui samad toimingud tehakse seotud andmetega "sügavalt". Kuid kontrollimatu rekursioon on kurjus, mis võib viia mõlemani lõputu hukkamine protsessi või (mis juhtub sagedamini) selleks tarbib kogu vaba mälu.

DBMS töötab selles osas samadel põhimõtetel - "nad ütlesid, et kaeva, ma kaevan". Teie taotlus ei saa mitte ainult aeglustada naaberprotsesse, võttes pidevalt protsessori ressursse, vaid ka "kukkuda" kogu andmebaasi tervikuna, "söödes" ära kogu olemasoleva mälu. lõpmatu rekursioonikaitse vastutab arendaja.

PostgreSQL-is on võimalus kasutada rekursiivseid päringuid WITH RECURSIVE ilmus iidsetel aegadel versioonis 8.4, kuid võite siiski regulaarselt vastata potentsiaalselt haavatavatele kaitsetutele päringutele. Kuidas end sellistest probleemidest säästa?

Ärge kirjutage rekursiivseid päringuid

Ja kirjutage mitterekursiivselt. Lugupidamisega Teie K.O.

Tegelikult pakub PostgreSQL üsna palju funktsioone, mida saate kasutada ei rakendada rekursiooni.

Kasutage probleemile põhimõtteliselt teistsugust lähenemist

Mõnikord võite probleemile lihtsalt "teisest küljest" vaadata. Toon artiklis sellise olukorra näite "SQL HowTo: 1000 ja üks viis koondamiseks" - arvude komplekti korrutamine ilma kohandatud koondfunktsioone kasutamata:

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;

Sellise taotluse saab asendada matemaatikaekspertide variandiga:

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

Kasutage tsüklite asemel gener_series

Oletame, et seisame silmitsi ülesandega genereerida stringile kõik võimalikud prefiksid '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;

Kas sa tõesti vajad siin rekursiooni? .. Kui kasutad LATERAL и generate_series, siis pole isegi CTE-sid vaja:

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

Muutke andmebaasi struktuuri

Näiteks on teil foorumipostituste tabel linkidega, kes kellele vastas, või lõime sotsiaalvõrgustik:

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

Tüüpiline taotlus kõigi ühe teema kirjade allalaadimiseks näeb välja umbes selline:

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;

Aga kuna me vajame alati kogu teemat juursõnumist, siis miks mitte lisage igale kirjele selle ID automaatne?

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

Nüüd saab kogu meie rekursiivse päringu taandada järgmiseks:

SELECT
  *
FROM
  message
WHERE
  theme_id = $1;

Kasutage rakendatud "piirajaid"

Kui me ei saa mingil põhjusel andmebaasi struktuuri muuta, siis vaatame, millele saame tugineda, et isegi vea olemasolu andmetes ei tooks kaasa lõputut rekursiooni.

Rekursiooni "sügavuse" loendur

Me lihtsalt suurendame loendurit rekursiooni igal sammul ühe võrra, kuni saavutame piiri, mida peame ilmselgelt ebapiisavaks:

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

Pro: Kui proovite silmust teha, ei tee me siiski rohkem kui "sügavalt" määratud iteratsioonide limiit.
miinuseid: Pole mingit garantiid, et me sama kirjet uuesti ei töötle – näiteks 15 ja 25 sügavusel ning seejärel iga +10 järel. Ja "laiuse" kohta ei lubanud keegi midagi.

Formaalselt ei ole selline rekursioon lõpmatu, kuid kui kirjete arv suureneb igal sammul eksponentsiaalselt, teame kõik hästi, kuidas see lõpeb ...

vaata "Terade probleem malelaual"

Tee valvur

Lisame omakorda kõik objekti identifikaatorid, mida me rekursiooniteel kohtasime, massiivi, mis on selle ainulaadne "tee":

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

Pro: Kui andmetes on tsükkel, siis me absoluutselt ei töötle sama kirjet sama tee jooksul korduvalt.
miinuseid: Kuid samal ajal saame sõna otseses mõttes mööda minna kõigist rekorditest ilma end kordamata.

vaata "Rüütli liikumise probleem"

Tee pikkuse piirang

Vältimaks arusaamatul sügavusel "rändava" rekursiooni olukorda, võime ühendada kaks eelmist meetodit. Või kui me ei soovi täiendavaid välju toetada, täiendage rekursiooni jätkamise tingimust tee pikkuse hinnanguga:

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
)

Vali endale meelepärane viis!

Allikas: www.habr.com

PostgreSQL-i antimustrid: "Lõpmatus pole piir!" või Natuke rekursioonist