PostgreSQL Antipatterns: „Igavik ei ole piir!”, ehk natuke rekursioonist

Rekursioon — väga võimas ja mugav mehhanism, kui seotud andmete kallal teostatakse samu toiminguid „süvitsi”. Kuid kontrollimata rekursioon on kuritegu, mis võib viia kas lõputu täitmiseni protsessi või (mis juhtub sagedamini) „mälu ammendumiseni”.

Andmebaasid töötavad selles osas samade printsiipide järgi — "kui öeldi kaevama, kaevan mina". Teie päring ei pruugi mitte ainult pidurdada naaberkeskkondi, pidevalt ressursse kasutades, vaid võib ka „kukutada” kogu andmebaasi, „söödes” kogu saadaoleva mälu. Seetõttu igavese rekursiooni kaitse on arendaja kohustus.

PostgreSQL-is on rekursiivsete päringute võimalus kasutades WITH RECURSIVE ilmnenud juba ammu versioonis 8.4, kuid siiani võib regulaarselt kohata potentsiaalselt haavatavaid „alasti” päringuid. Kuidas end sellistest probleemidest vabaks saada?

Ärge kirjutage rekursiivseid päringuid

Vaid kirjutage mitte-rekursiivseid. Lugupidamisega, Teie K.O.

Tegelikult pakub PostgreSQL piisavalt suurt funktsionaalsust, millega saab kasutada ei rekursiooni.

Kasutage täiesti erinevat lähenemist probleemile

Mõnikord võib lihtsalt vaadata ülesannet „teise nurga alt”. Näiteks tõin sellise olukorra välja artiklis „SQL HowTo: 1000 ja üks viis agregeerimiseks” — numberkogumi korrutamine ilma kasutaja defineeritud agregeerimisfunktsioone rakendamata:

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 -- tulemuse selektsioon
  i DESC
LIMIT 1;

Sellise päringu võib asendada matemaatika tundjate 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 generate_series-i tsüklite asemel

Eeldame, et meil on ülesanne genereerida kõik võimalikult eelnevad strings sõne '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 rekursioon on tõesti vajalik?.. Kui kasutada LATERAL ja generate_seriesit, siis isegi CTE ei ole vajalik:

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

Muuda andmebaasi struktuuri

Näiteks, teil on foorumi postituste tabel, kus on seosed, kes kellele vastas või teema sotsiaalmeedias:

LOOD TABLE message(
  message_id
    uuid
      PEAMI KEEPA
, reply_to
    uuid
      VIIDAT message
, body
    text
);
LOODA INDICES message(reply_to);

Tüüpiline päring, mis laadib kõik sõnumid ühe teema kohta, näeb välja umbes nii:

WITH RECURSIVE T AS (
  VALI
    *
  FROM
    message
  WHERE
    message_id = $1
UNION ALL
  VALI
    m.*
  FROM
    T
  JOIN
    message m
      ON m.reply_to = T.message_id
)
TABLE T;

Kuna meil on alati vaja kogu teemat juursõnumist, siis miks mitte lisada selle identifikaator igasse kirjesse automaatselt?

-- lisame teema ühise identifikaatori välja ja indeksi sellele
ALTER TABLE message
  ADD COLUMN theme_id uuid;
CREATE INDEX ON message(theme_id);

-- initsialiseerime teema identifikaatori trikkides sisestamisel
CREATE OR REPLACE FUNCTION ins() RETURNS TRIGGER AS $$
BEGIN
  NEW.theme_id = CASE
    WHEN NEW.reply_to IS NULL THEN NEW.message_id -- võtame algse sündmuse seest
    ELSE ( -- või message, millele vastame
      VALI
        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 rekursiivpäringu vähendada lihtsalt selliseks:

SELECT
  *
FROM
  message
WHERE
  theme_id = $1;

Kasutage rakenduslikke "piirajaid"

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

Rekursiooni "sügavuse" loendur

Lihtsalt suurendame loendurit ühe võrra igal rekursiooni sammul kuni hetkeni, mil jõuame piirini, mida peame ilmselgelt ebasobivaks:

WITH RECURSIVE T AS (
  VALI
    0 i
  ...
UNION ALL
  VALI
    i + 1
  ...
  WHERE
    T.i < 64 -- piir
)

Pro: Tsüklite katsetamisel ei tee me ikkagi rohkem kui määratud iteratsioonide piiri "sügavusse".
Contra: Pole garantiid, et me ei töötle uuesti sama kirjet — näiteks sügavuses 15 ja 25, ning edasi iga +10 kohta. Ja keegi ei ole lubanud midagi "laiuses".

Formaalsete tingimuste kohaselt ei ole selline rekursioon lõpmatu, kuid kui iga sammu korral arvude hulk suureneb eksponentsiaalselt, siis teame kõik, kuidas see lõpeb...

vt "Küsimus terade kohta malelaual"

Teekonna "hoidja"

Kirjutame järjestikku kõik kohtunud identifikaatorid rekursiooni teel massiivi, mis on ainulaadne "tee" selle juurde:

WITH RECURSIVE T AS (
  VALI
    ARRAY[id] tee
  ...
UNION ALL
  VALI
    tee || id
  ...
  WHERE
    id  ALL(T.tee) -- ei vasta ühele neist
)

Pro: Andmete tsüklite puhul ei töötle me kunagi sama kirje uuesti ühe ja sama tee jooksul.
Contra: Kuid me saame kõiki kirjeid läbida, ilma et me korduksime.

vt "Ratsaniku liikumise probleem"

Teepikkuse piirang

Kuna vältida olukorda, kus rekurss sukeldub segase sügavuseni, saame kombineerida kaks eelmise meetodit. Kui me ei soovi toetada liigseid välju, saame lisada rekurssimise jätkamise tingimusse teepikkuse hindamise:

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
)

Valige sobiv meetod vastavalt oma maitsele!

Allikas: habr.com