🥇PostgreSQL antipatterns: „Begalybė nėra riba!“ arba Šiek tiek apie rekursiją

Rekursija - labai galingas ir patogus mechanizmas, jei su susijusiais duomenimis atliekami tie patys „išsamūs“ veiksmai. Tačiau nekontroliuojama pasikartojimas yra blogis, kuris gali sukelti bet kurį iš jų begalinis vykdymas procesą arba (kas nutinka dažniau) į „suvalgo“ visą turimą atmintį.

DBVS šiuo atžvilgiu dirba tais pačiais principais - "Jie man liepė kasti, todėl ir kasiauJūsų užklausa gali ne tik sulėtinti gretimus procesus, nuolat užimti procesoriaus resursus, bet ir „nuleisti“ visą duomenų bazę, „suvalgydama“ visą turimą atmintį. apsauga nuo begalinės rekursijos – paties kūrėjo atsakomybė.

„PostgreSQL“ galimybė naudoti rekursines užklausas per WITH RECURSIVE pasirodė neatmenamus 8.4 versijos laikus, tačiau vis tiek galite reguliariai susidurti su galimai pažeidžiamomis „be gynybos“ užklausomis. Kaip atsikratyti tokio pobūdžio problemų?

Nerašykite rekursinių užklausų

Ir rašykite nerekursyvius. Pagarbiai Jūsų K.O.

Tiesą sakant, PostgreSQL suteikia gana daug funkcijų, kurias galite naudoti ne taikyti rekursiją.

Naudokite iš esmės kitokį požiūrį į problemą

Kartais galite tiesiog pažvelgti į problemą iš „kitos pusės“. Straipsnyje pateikiau tokios situacijos pavyzdį „SQL HowTo: 1000 ir vienas agregavimo būdas“ — skaičių aibės dauginimas nenaudojant pasirinktinių suvestinių funkcijų:

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;

Šią užklausą galima pakeisti matematikos ekspertų parinktimi:

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

Vietoj kilpų naudokite gener_series

Tarkime, kad susiduriame su užduotimi sugeneruoti visus įmanomus eilutės priešdėlius '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;

Ar tikrai čia reikia rekursijos?.. Jei naudojate LATERAL и generate_series, tada jums net nereikės CTE:

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

Keisti duomenų bazės struktūrą

Pavyzdžiui, turite forumo pranešimų lentelę su ryšiais, kas kam atsakė, arba giją Socialinis tinklas:

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

Na, tipiškas prašymas atsisiųsti visus pranešimus viena tema atrodo maždaug taip:

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;

Bet kadangi mums visada reikia visos temos nuo pagrindinės žinutės, kodėl gi ne prie kiekvieno įrašo pridėkite savo ID automatinis?

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

Dabar visa mūsų rekursinė užklausa gali būti sumažinta iki šios:

SELECT
  *
FROM
  message
WHERE
  theme_id = $1;

Naudokite taikomus "ribojimus"

Jei dėl kokių nors priežasčių negalime pakeisti duomenų bazės struktūros, pažiūrėkime, kuo galime pasikliauti, kad net ir duomenų klaidos buvimas nesukeltų begalinės rekursijos.

Rekursijos gylio skaitiklis

Tiesiog kiekviename rekursijos žingsnyje skaitiklį padidiname vienu, kol pasiekiame ribą, kurią laikome akivaizdžiai netinkama:

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

Pro ": Kai bandysime sudaryti kilpą, vis tiek nedarysime daugiau nei nurodyta iteracijų riba „gylyje“.
trūkumai: Nėra garantijos, kad to paties įrašo neapdorosime dar kartą – pavyzdžiui, 15 ir 25 gylyje, o vėliau kas +10. Ir niekas nieko nežadėjo apie „plotį“.

Formaliai tokia rekursija nebus begalinė, bet jei kiekviename žingsnyje įrašų skaičius didėja eksponentiškai, visi puikiai žinome, kuo tai baigiasi...

žiūrėkite „Grūdelių problema šachmatų lentoje“

„Kelio“ sargas

Visus objekto identifikatorius, su kuriais susidūrėme rekursijos kelyje, pakaitomis pridedame į masyvą, kuris yra unikalus jo „kelias“:

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

Pro ": Jei duomenyse yra ciklas, mes tikrai neapdorosime to paties įrašo pakartotinai tame pačiame kelyje.
trūkumai: Tačiau tuo pat metu galime tiesiogine prasme apeiti visus įrašus nesikartodami.

žiūrėkite "Riterio judėjimo problema"

Kelio ilgio riba

Kad išvengtume rekursijos „klaidžiojimo“ nesuprantamame gylyje, galime sujungti du ankstesnius metodus. Arba, jei nenorime palaikyti nereikalingų laukų, rekursijos tęsimo sąlygą papildykite kelio ilgio įvertinimu:

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
)

Pasirinkite būdą pagal savo skonį!

Šaltinis: www.habr.com

PostgreSQL antipatterns: „Begalybė nėra riba!“ arba Šiek tiek apie rekursiją