🥇PostgreSQL-Antiŝablonoj: "Senfineco ne estas la limo!", aŭ Iom pri rekursio

Rikurso - tre potenca kaj oportuna mekanismo se la samaj "profundaj" agoj estas faritaj sur rilataj datumoj. Sed nekontrolita rekurso estas malbono, kiu povas konduki al ambaŭ senfina ekzekuto procesi, aŭ (kio okazas pli ofte) al "manĝante" la tutan disponeblan memoron.

DBMS ĉi-rilate laboras laŭ la samaj principoj - "Ili diris al mi fosi, do mi fosas". Via peto povas ne nur malrapidigi najbarajn procezojn, konstante okupante procesorajn rimedojn, sed ankaŭ "faligi" la tutan datumbazon, "manĝante" la tutan disponeblan memoron. Tial protekto kontraŭ senfina rekurso - la respondeco de la programisto mem.

En PostgreSQL, la kapablo uzi rekursiajn demandojn per WITH RECURSIVE aperis en la nememorebla tempo de versio 8.4, sed vi ankoraŭ povas regule renkonti eble vundeblajn "sendefendajn" demandojn. Kiel forigi tian problemojn?

Ne skribu rekursivajn demandojn

Kaj skribu nerekursivajn. Sincere, Via K.O.

Fakte, PostgreSQL provizas sufiĉe da funkcioj, kiujn vi povas uzi ne apliki rikurson.

Uzu fundamente malsaman aliron al la problemo

Kelkfoje vi povas simple rigardi la problemon de la "malsama flanko". Mi donis ekzemplon de tia situacio en la artikolo "SQL HowTo: 1000 kaj unu maniero de agregado" — multipliko de aro de nombroj sen uzi kutimajn entuta funkciojn:

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 tiu peto povas esti anstataŭigita per opcio de matematikaj spertuloj:

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

Uzu generate_series anstataŭ bukloj

Ni diru, ke ni estas antaŭ la tasko generi ĉiujn eblajn prefiksojn por ĉeno '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;

Ĉu vi certas, ke vi bezonas rekursion ĉi tie?.. Se vi uzas LATERAL и generate_series, tiam vi eĉ ne bezonos CTE:

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

Ŝanĝi datumbazan strukturon

Ekzemple, vi havas tabelon de forumaj mesaĝoj kun ligoj de kiu respondis al kiu, aŭ fadenon enen socia reto:

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

Nu, tipa peto elŝuti ĉiujn mesaĝojn pri unu temo aspektas kiel ĉi tio:

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;

Sed ĉar ni ĉiam bezonas la tutan temon el la radika mesaĝo, kial do ni ne aldonu ĝian ID al ĉiu eniro aŭtomata?

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

Nun nia tuta rekursiva demando povas esti reduktita nur al tio:

SELECT
  *
FROM
  message
WHERE
  theme_id = $1;

Uzu aplikatajn "limigilojn"

Se ni ial ne kapablas ŝanĝi la strukturon de la datumbazo, ni vidu, pri kio ni povas fidi, por ke eĉ la ĉeesto de eraro en la datumoj ne konduku al senfina rekurso.

Rekursia profundo-kalkulilo

Ni simple pliigas la nombrilon je unu ĉe ĉiu rekursa paŝo ĝis ni atingas limon, kiun ni konsideras evidente neadekvata:

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

Avantaĝo: Kiam ni provas cirkuli, ni ankoraŭ faros ne pli ol la specifita limo de ripetoj "profunde".
trompoj: Ne estas garantio, ke ni ne prilaboros la saman rekordon denove - ekzemple, ĉe profundo de 15 kaj 25, kaj poste ĉiun +10. Kaj neniu promesis ion pri "larĝo".

Formale tia rekurso ne estos senfina, sed se je ĉiu paŝo la nombro da registroj eksponente pliiĝas, ni ĉiuj bone scias kiel ĝi finiĝas...

vidu "La problemo de grenoj sur ŝaktabulo"

Gardisto de la "vojo"

Ni alterne aldonas ĉiujn objektajn identigilojn, kiujn ni renkontis laŭ la rekursa vojo en tabelon, kiu estas unika "vojo" al ĝi:

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

Avantaĝo: Se estas ciklo en la datumoj, ni absolute ne prilaboros la saman rekordon ree ene de la sama vojo.
trompoj: Sed samtempe ni povas laŭvorte preteriri ĉiujn rekordojn sen ripeti nin.

vidu "La Movo Problemo de Kavaliro"

Voja Longa Limo

Por eviti la situacion de rekurso "vagado" je nekomprenebla profundo, ni povas kombini la du antaŭajn metodojn. Aŭ, se ni ne volas subteni nenecesajn kampojn, kompletigu la kondiĉon por daŭrigi la rikurson kun takso de la padlongo:

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
)

Elektu metodon laŭ via gusto!

fonto: www.habr.com

PostgreSQL-Antiŝablonoj: "Senfineco ne estas la limo!", aŭ Iom pri rekursio