🥇PostgreSQL Antipatterns: "Infinity is not the limit!", tai vähän rekursiosta

rekursio - erittäin tehokas ja kätevä mekanismi, jos samat "syvälliset" toimenpiteet suoritetaan liittyville tiedoille. Mutta hallitsematon rekursio on paha, joka voi johtaa kumpaan tahansa loputon toteutus prosessia tai (mitä tapahtuu useammin) varten "syö" kaiken käytettävissä olevan muistin.

DBMS toimii tässä suhteessa samoilla periaatteilla - "He käskivät minun kaivaa, joten minä kaivanPyyntösi ei voi vain hidastaa viereisiä prosesseja, jotka vievät jatkuvasti prosessoriresursseja, vaan myös "pudottaa" koko tietokannan, "syömällä" kaiken käytettävissä olevan muistin. suojaa loputonta rekursiota vastaan - kehittäjän itsensä vastuulla.

PostgreSQL:ssä mahdollisuus käyttää rekursiivisia kyselyitä kautta WITH RECURSIVE ilmestyi ikimuistoisena versiona 8.4, mutta voit silti kohdata säännöllisesti mahdollisesti haavoittuvia "puolustumattomia" pyyntöjä. Kuinka päästä eroon tällaisista ongelmista?

Älä kirjoita rekursiivisia kyselyitä

Ja kirjoita ei-rekursiivisia. Ystävällisin terveisin K.O.

Itse asiassa PostgreSQL tarjoaa melko paljon toimintoja, joita voit käyttää ei käytä rekursiota.

Käytä täysin erilaista lähestymistapaa ongelmaan

Joskus voi vain katsoa ongelmaa "eri puolelta". Annoin artikkelissa esimerkin tällaisesta tilanteesta "SQL HowTo: 1000 ja yksi tapa yhdistää" — lukujoukon kertominen ilman mukautettuja aggregaattifunktioita:

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;

Tämä pyyntö voidaan korvata matematiikan asiantuntijoiden vaihtoehdolla:

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

Käytä gener_sarjaa silmukoiden sijaan

Oletetaan, että joudumme luomaan kaikki mahdolliset etuliitteet merkkijonolle '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;

Oletko varma, että tarvitset tässä rekursiota?.. Jos käytät LATERAL и generate_series, silloin et edes tarvitse CTE:tä:

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

Muuta tietokannan rakennetta

Sinulla on esimerkiksi taulukko foorumin viesteistä, joissa on yhteyksiä kenelle vastanneista tai viestiketjusta sosiaalinen verkosto:

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

No, tyypillinen pyyntö ladata kaikki viestit samasta aiheesta näyttää suunnilleen tältä:

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;

Mutta koska tarvitsemme aina koko aiheen juuriviestistä, niin miksi emme lisää sen tunnus jokaiseen merkintään Automaattinen?

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

Nyt koko rekursiivinen kyselymme voidaan tiivistää tähän:

SELECT
  *
FROM
  message
WHERE
  theme_id = $1;

Käytä käytettyjä "rajoittimia"

Jos tietokannan rakennetta ei jostain syystä pysty muuttamaan, katsotaan mihin voimme luottaa, jotta edes virheen olemassaolo tiedoissa ei johda loputtomaan rekursioon.

Rekursion syvyyslaskuri

Kasvatamme laskuria yhdellä jokaisessa rekursiovaiheessa, kunnes saavutamme rajan, jota pidämme ilmeisen riittämättömänä:

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

Pro: Kun yritämme tehdä silmukan, emme silti tee enempää kuin määritetyn iteraatiorajan "syvyys".
haittoja: Ei ole mitään takeita siitä, ettemme käsittele samaa tietuetta uudelleen - esimerkiksi 15 ja 25 syvyydessä ja sen jälkeen +10 välein. Eikä kukaan luvannut mitään "leveydestä".

Muodollisesti tällainen rekursio ei ole ääretön, mutta jos tietueiden määrä kasvaa joka vaiheessa eksponentiaalisesti, tiedämme kaikki hyvin, miten se päättyy...

katso "Jyvien ongelma shakkilaudalla"

"polun" vartija

Lisäämme vuorotellen kaikki rekursiopolulla kohtaamamme objektitunnisteet taulukkoon, joka on ainutlaatuinen "polku" siihen:

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

Pro: Jos tiedoissa on sykli, emme ehdottomasti käsittele samaa tietuetta toistuvasti samalla polulla.
haittoja: Mutta samaan aikaan voimme kirjaimellisesti ohittaa kaikki tietueet toistamatta itseämme.

katso "Knight's Move Problem"

Polun pituusrajoitus

Välttääksemme tilanteen, jossa rekursio "vaeltelee" käsittämättömällä syvyydellä, voimme yhdistää kaksi edellistä menetelmää. Tai jos emme halua tukea tarpeettomia kenttiä, täydennä rekursion jatkamisen ehtoa arviolla polun pituudesta:

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
)

Valitse menetelmä makusi mukaan!

Lähde: will.com

PostgreSQL-antipatterns: "Infinity ei ole raja!", tai vähän rekursiosta