🥇PostgreSQL Antipatterns: “Nekonečno není limit!”, aneb Něco málo o rekurzi

Rekurze - velmi výkonný a pohodlný mechanismus, pokud se stejné „hloubkové“ akce provádějí na souvisejících datech. Ale nekontrolovaná rekurze je zlo, které může vést k obojímu nekonečné provádění procesu, nebo (což se stává častěji). „sežere“ veškerou dostupnou paměť.

DBMS v tomto ohledu fungují na stejných principech - "Řekli mi, abych kopal, tak kopám". Váš požadavek může nejen zpomalit sousední procesy, neustále zabírat zdroje procesoru, ale také "zahodit" celou databázi a "sníst" veškerou dostupnou paměť. ochrana před nekonečnou rekurzí - odpovědnost samotného vývojáře.

V PostgreSQL možnost používat rekurzivní dotazy přes WITH RECURSIVE se objevil v nepaměti verze 8.4, ale stále se můžete pravidelně setkávat s potenciálně zranitelnými „bezbrannými“ požadavky. Jak se zbavit problémů tohoto druhu?

Nepište rekurzivní dotazy

A psát nerekurzivní. S pozdravem Vaše K.O.

Ve skutečnosti PostgreSQL poskytuje poměrně mnoho funkcí, které můžete použít ne aplikovat rekurzi.

Použijte zásadně odlišný přístup k problému

Někdy se stačí podívat na problém z „jiné strany“. V článku jsem uvedl příklad takové situace "SQL HowTo: 1000 a jeden způsob agregace" — násobení sady čísel bez použití vlastních agregačních funkcí:

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;

Tento požadavek lze nahradit možností od odborníků 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;

Místo smyček použijte generovat_series

Řekněme, že stojíme před úkolem vygenerovat všechny možné předpony pro řetězec '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;

Jste si jisti, že zde potřebujete rekurzi?... Pokud používáte LATERAL и generate_series, pak nebudete potřebovat ani CTE:

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

Změna struktury databáze

Máte například tabulku zpráv na fóru se spojeními od toho, kdo komu odpověděl, nebo vlákno, ve kterém se nachází sociální síť:

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

Typický požadavek na stažení všech zpráv na jedno téma vypadá 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 protože vždy potřebujeme celé téma z kořenové zprávy, tak proč ne ke každému záznamu přidejte jeho ID 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();

Nyní lze celý náš rekurzivní dotaz zredukovat pouze na toto:

SELECT
  *
FROM
  message
WHERE
  theme_id = $1;

Použijte aplikované "omezovače"

Pokud z nějakého důvodu nemůžeme změnit strukturu databáze, pojďme se podívat, na co se můžeme spolehnout, aby ani přítomnost chyby v datech nevedla k nekonečné rekurzi.

Čítač hloubky rekurze

Jednoduše zvýšíme počítadlo o jednu v každém kroku rekurze, dokud nedosáhneme limitu, který považujeme za zjevně nedostatečný:

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

Od: Když se pokusíme o smyčku, stále neuděláme více než stanovený limit iterací „do hloubky“.
nevýhody: Není zaručeno, že stejný záznam nezpracujeme znovu – např. v hloubce 15 a 25 a poté každých +10. A nikdo nic nesliboval o „šířce“.

Formálně taková rekurze nebude nekonečná, ale pokud na každém kroku exponenciálně narůstá počet záznamů, všichni dobře víme, jak to skončí...

viz „Problém zrn na šachovnici“

Strážce "cesty"

Střídavě přidáváme všechny identifikátory objektů, se kterými jsme se setkali na cestě rekurze, do pole, což je jedinečná „cesta“ k němu:

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

Od: Pokud je v datech cyklus, absolutně nezpracujeme stejný záznam opakovaně v rámci stejné cesty.
nevýhody: Ale zároveň můžeme všechny záznamy doslova obejít, aniž bychom se opakovali.

viz "Problém s pohybem rytířů"

Limit délky cesty

Abychom se vyhnuli situaci „bloudící“ rekurze v nepochopitelné hloubce, můžeme obě předchozí metody zkombinovat. Nebo, pokud nechceme podporovat zbytečná pole, doplňte podmínku pokračování rekurze o odhad délky 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 metodu podle svého vkusu!

Zdroj: www.habr.com

PostgreSQL Antipatterns: „Nekonečno není limit!“ nebo Něco málo o rekurzi