🥇PostgreSQL Antipatterns: “Nekonečno nie je limit!”, alebo Trochu o rekurzii

rekurzia - veľmi výkonný a pohodlný mechanizmus, ak sa rovnaké „hĺbkové“ akcie vykonávajú na súvisiacich údajoch. Ale nekontrolovaná rekurzia je zlo, ktoré môže viesť k jednému z nich nekonečná exekúcia procesu, alebo (čo sa stáva častejšie). „požierajúc“ všetku dostupnú pamäť.

DBMS v tomto ohľade pracuje na rovnakých princípoch - "Povedali mi, aby som kopal, tak som kopalVaša požiadavka môže nielen spomaliť susedné procesy, neustále zaberať zdroje procesora, ale aj „zahodiť“ celú databázu a „zožrať“ všetku dostupnú pamäť. ochrana pred nekonečnou rekurziou - zodpovednosť samotného developera.

V PostgreSQL možnosť používať rekurzívne dotazy cez WITH RECURSIVE sa objavil v nepamäti verzie 8.4, ale stále sa môžete pravidelne stretávať s potenciálne zraniteľnými „bezbrannými“ požiadavkami. Ako sa zbaviť problémov tohto druhu?

Nepíšte rekurzívne dotazy

A píšte nerekurzívne. S pozdravom Vaša K.O.

V skutočnosti PostgreSQL poskytuje pomerne veľa funkcií, ktoré môžete použiť nie aplikovať rekurziu.

Použite zásadne odlišný prístup k problému

Niekedy sa stačí pozrieť na problém z „inej strany“. V článku som uviedol príklad takejto situácie "SQL HowTo: 1000 a jeden spôsob agregácie" — násobenie množiny čísel bez použitia vlastných agregačných funkcií:

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úto požiadavku možno nahradiť možnosťou od odborníkov na matematiku:

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

Namiesto slučiek použite create_series

Povedzme, že stojíme pred úlohou vygenerovať všetky možné predpony pre reťazec '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;

Si si istý, že tu potrebuješ rekurziu?... Ak použiješ LATERAL и generate_series, potom nebudete potrebovať ani CTE:

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

Zmena štruktúry databázy

Napríklad máte tabuľku správ vo fóre s prepojeniami od toho, kto komu odpovedal, alebo vláknom sociálna sieť:

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

Typická požiadavka na stiahnutie všetkých správ na jednu tému vyzerá asi takto:

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;

Ale keďže vždy potrebujeme celú tému z koreňovej správy, tak prečo nie pridajte jeho ID ku každému záznamu automatické?

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

Teraz je možné celý náš rekurzívny dotaz zredukovať len na toto:

SELECT
  *
FROM
  message
WHERE
  theme_id = $1;

Použite aplikované "obmedzovače"

Ak z nejakého dôvodu nedokážeme zmeniť štruktúru databázy, pozrime sa, na čo sa môžeme spoľahnúť, aby ani prítomnosť chyby v dátach neviedla k nekonečnej rekurzii.

Počítadlo hĺbky rekurzie

Jednoducho zvyšujeme počítadlo o jeden v každom kroku rekurzie, kým nedosiahneme limit, ktorý považujeme za zjavne nedostatočný:

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

Od: Keď sa pokúsime zacykliť, stále neurobíme viac, ako je špecifikovaný limit iterácií „do hĺbky“.
nevýhody: Nie je zaručené, že ten istý záznam nespracujeme znova – napríklad v hĺbke 15 a 25 a potom každých +10. A nikto nič nesľúbil o „šírke“.

Formálne takáto rekurzia nebude nekonečná, ale ak sa na každom kroku počet záznamov exponenciálne zvyšuje, všetci dobre vieme, ako to skončí...

pozri „Problém zŕn na šachovnici“

Strážca "cesty"

Všetky identifikátory objektov, s ktorými sme sa stretli na rekurznej ceste, striedavo pridávame do poľa, čo je jedinečná „cesta“ k nemu:

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

Od: Ak je v dátach cyklus, absolútne nespracujeme ten istý záznam opakovane v rámci tej istej cesty.
nevýhody: Ale zároveň môžeme doslova obísť všetky záznamy bez toho, aby sme sa opakovali.

pozri "Problém s pohybom rytiera"

Limit dĺžky cesty

Aby sme sa vyhli situácii „blúdenia“ rekurzie v nepochopiteľnej hĺbke, môžeme obe predchádzajúce metódy skombinovať. Alebo, ak nechceme podporovať nepotrebné polia, doplňte podmienku pokračovania rekurzie o odhad dĺžky cesty:

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
)

Vyberte si spôsob podľa svojho vkusu!

Zdroj: hab.com

PostgreSQL Antipatterns: "Nekonečno nie je limit!" alebo Trochu o rekurzii