🥇PostgreSQL Antimønstre: "Uendelighed er ikke grænsen!", eller Lidt om rekursion

Rekursion - en meget kraftfuld og bekvem mekanisme, hvis de samme "dybdegående" handlinger udføres på relaterede data. Men ukontrolleret rekursion er et onde, der kan føre til enten uendelig henrettelse proces, eller (hvilket sker oftere) til "spiser" al tilgængelig hukommelse.

DBMS arbejder i denne henseende efter de samme principper - "De bad mig grave, så jeg graver". Din anmodning kan ikke kun bremse tilstødende processer, konstant optage processorressourcer, men også "droppe" hele databasen og "spise" al tilgængelig hukommelse. Derfor beskyttelse mod uendelig rekursion - bygherrens eget ansvar.

I PostgreSQL, muligheden for at bruge rekursive forespørgsler via WITH RECURSIVE dukkede op i umindelige tider af version 8.4, men du kan stadig jævnligt støde på potentielt sårbare "forsvarsløse" forespørgsler. Hvordan slipper man for problemer af denne art?

Skriv ikke rekursive forespørgsler

Og skriv ikke-rekursive. Med venlig hilsen din K.O.

Faktisk giver PostgreSQL en hel del funktionalitet, som du kan bruge til nej anvende rekursion.

Brug en fundamentalt anderledes tilgang til problemet

Nogle gange kan man bare se på problemet fra den "anden side". Jeg gav et eksempel på en sådan situation i artiklen "SQL HowTo: 1000 og én måde at aggregere på" — multiplikation af et sæt tal uden at bruge tilpassede aggregerede funktioner:

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;

Denne anmodning kan erstattes med en mulighed fra matematikeksperter:

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

Brug gener_series i stedet for loops

Lad os sige, at vi står over for opgaven med at generere alle mulige præfikser for en streng '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;

Er du sikker på, at du har brug for rekursion her?.. Hvis du bruger LATERAL и generate_series, så behøver du ikke engang CTE:

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

Skift databasestruktur

For eksempel har du en tabel med forummeddelelser med forbindelser fra hvem der har svaret til hvem, eller en tråd ind Socialt netværk:

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

Nå, en typisk anmodning om at downloade alle beskeder om et emne ser sådan ud:

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;

Men da vi altid har brug for hele emnet fra rodbeskeden, hvorfor gør vi så ikke tilføje sit ID til hver post automatisk?

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

Nu kan hele vores rekursive forespørgsel reduceres til netop dette:

SELECT
  *
FROM
  message
WHERE
  theme_id = $1;

Brug anvendte "begrænsere"

Hvis vi af en eller anden grund ikke er i stand til at ændre strukturen af databasen, så lad os se, hvad vi kan stole på, så selv tilstedeværelsen af en fejl i dataene ikke fører til endeløs rekursion.

Rekursionsdybdetæller

Vi øger simpelthen tælleren med én ved hvert rekursionstrin, indtil vi når en grænse, som vi anser for åbenlyst utilstrækkelig:

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

Pro: Når vi forsøger at loope, vil vi stadig ikke gøre mere end den specificerede grænse for iterationer "i dybden".
ulemper: Der er ingen garanti for, at vi ikke behandler den samme post igen - for eksempel i en dybde på 15 og 25, og derefter hver +10. Og ingen lovede noget om "bredde".

Formelt vil en sådan rekursion ikke være uendelig, men hvis antallet af poster for hvert trin stiger eksponentielt, ved vi alle godt, hvordan det ender...

se "Problemet med korn på et skakbræt"

Vogter af "stien"

Vi tilføjer skiftevis alle de objektidentifikatorer, vi stødte på langs rekursionsstien, til en matrix, som er en unik "sti" til den:

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

Pro: Hvis der er en cyklus i dataene, vil vi absolut ikke behandle den samme post gentagne gange inden for den samme vej.
ulemper: Men samtidig kan vi bogstaveligt talt omgå alle rekorderne uden at gentage os selv.

se "Knight's Move Problem"

Stilængdegrænse

For at undgå situationen med rekursion "vandrende" i en uforståelig dybde, kan vi kombinere de to foregående metoder. Eller, hvis vi ikke ønsker at understøtte unødvendige felter, supplere betingelsen for at fortsætte rekursionen med et estimat af stiens længde:

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
)

Vælg en metode efter din smag!

Kilde: www.habr.com

PostgreSQL Antimønstre: “Uendelighed er ikke grænsen!”, eller lidt om rekursion