🥇PostgreSQL Antipatterns: “Infinity is not the limit!” jeb Mazliet par rekursiju

rekursija - ļoti spēcīgs un ērts mehānisms, ja ar saistītajiem datiem tiek veiktas tādas pašas “padziļinātas” darbības. Bet nekontrolēta atkārtošanās ir ļaunums, kas var novest pie jebkura no tiem bezgalīga izpilde process, vai (kas notiek biežāk) uz "apēdot" visu pieejamo atmiņu.

DBVS šajā ziņā strādā pēc tiem pašiem principiem - "Viņi teica, lai es raktu, tāpēc es raktu". Jūsu pieprasījums var ne tikai palēnināt blakus esošos procesus, pastāvīgi aizņemot procesora resursus, bet arī "nomest" visu datu bāzi, "apēdot" visu pieejamo atmiņu. aizsardzība pret bezgalīgu atkārtošanos - paša izstrādātāja atbildība.

Programmā PostgreSQL iespēja izmantot rekursīvus vaicājumus, izmantojot WITH RECURSIVE parādījās jau 8.4. versijas neatminamos laikos, taču joprojām varat regulāri saskarties ar potenciāli neaizsargātiem “neaizsardzības” pieprasījumiem. Kā atbrīvoties no šāda veida problēmām?

Nerakstiet rekursīvus vaicājumus

Un rakstiet nerekursīvos. Ar cieņu Jūsu K.O.

Faktiski PostgreSQL nodrošina diezgan daudz funkcionalitātes, ko varat izmantot nē pielietot rekursiju.

Izmantojiet principiāli atšķirīgu pieeju problēmai

Dažreiz jūs varat vienkārši paskatīties uz problēmu no “citas puses”. Rakstā minēju šādas situācijas piemēru "SQL HowTo: 1000 un viens apkopošanas veids" — skaitļu kopas reizināšana, neizmantojot pielāgotas apkopošanas funkcijas:

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;

Šo pieprasījumu var aizstāt ar matemātikas ekspertu opciju:

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

Cilpu vietā izmantojiet gener_series

Pieņemsim, ka mēs saskaramies ar uzdevumu ģenerēt visus iespējamos virknes prefiksus '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;

Vai esat pārliecināts, ka šeit ir nepieciešama rekursija?.. Ja izmantojat LATERAL и generate_series, tad jums pat nevajadzēs CTE:

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

Mainīt datu bāzes struktūru

Piemēram, jums ir foruma ziņojumu tabula ar savienojumiem no tā, kurš kam atbildēja, vai pavediens sociālais tīkls:

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

Tipisks pieprasījums lejupielādēt visus ziņojumus par vienu tēmu izskatās apmēram šādi:

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, tā kā mums vienmēr ir vajadzīga visa tēma no saknes ziņojuma, kāpēc gan mums to nedarīt pievienojiet tā ID katram ierakstam automātiski?

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

Tagad visu mūsu rekursīvo vaicājumu var samazināt līdz šim:

SELECT
  *
FROM
  message
WHERE
  theme_id = $1;

Izmantojiet lietotos "ierobežotājus"

Ja kāda iemesla dēļ nevaram mainīt datu bāzes struktūru, paskatīsimies, uz ko varam paļauties, lai pat kļūdas esamība datos neizraisītu bezgalīgu rekursiju.

Rekursijas dziļuma skaitītājs

Mēs vienkārši palielinām skaitītāju par vienu katrā rekursijas solī, līdz sasniedzam robežu, ko uzskatām par acīmredzami neatbilstošu:

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

Pro: Mēģinot izveidot cilpu, mēs joprojām nedarīsim vairāk par norādīto iterāciju ierobežojumu “dziļumā”.
mīnusi: Nav garantijas, ka mēs neapstrādāsim to pašu ierakstu vēlreiz - piemēram, 15 un 25 dziļumā, un pēc tam ik pēc +10. Un neviens neko nesolīja par “platumu”.

Formāli šāda rekursija nebūs bezgalīga, taču, ja katrā solī ierakstu skaits pieaug eksponenciāli, mēs visi labi zinām, ar ko tas beidzas...

Skatīt “Graudu problēma uz šaha galdiņa”

"Ceļa" sargs

Mēs pārmaiņus pievienojam visus objektu identifikatorus, kurus mēs sastapām rekursijas ceļā, masīvā, kas ir unikāls “ceļš” uz to:

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

Pro: Ja datos ir cikls, mēs noteikti neapstrādāsim vienu un to pašu ierakstu atkārtoti tajā pašā ceļā.
mīnusi: Bet tajā pašā laikā mēs varam burtiski apiet visus ierakstus, neatkārtojoties.

skatiet "Bruņinieka kustības problēma"

Ceļa garuma ierobežojums

Lai izvairītos no situācijas, kad notiek rekursijas “klejošana” nesaprotamā dziļumā, varam apvienot divas iepriekšējās metodes. Vai arī, ja nevēlamies atbalstīt nevajadzīgos laukus, papildiniet nosacījumu par rekursijas turpināšanu ar ceļa garuma aprēķinu:

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
)

Izvēlieties metodi pēc savas gaumes!

Avots: www.habr.com

PostgreSQL antipatterns: “Bezgalība nav ierobežojums!” jeb Mazliet par rekursiju