🥇PostgreSQL Antimönster: "Infinity is not the limit!", eller Lite om rekursion

Rekursion - en mycket kraftfull och bekväm mekanism om samma "djupgående" åtgärder utförs på relaterade data. Men okontrollerad rekursion är ett ont som kan leda till antingen oändlig avrättning process, eller (vilket händer oftare) till "äter" allt tillgängligt minne.

DBMS i detta avseende arbetar på samma principer - "De sa åt mig att gräva, så jag gräver". Din begäran kan inte bara sakta ner närliggande processer, ständigt ta upp processorresurser, utan också "släppa" hela databasen och "äta upp" allt tillgängligt minne. Därför skydd mot oändlig rekursion - byggherrens eget ansvar.

I PostgreSQL, möjligheten att använda rekursiva frågor via WITH RECURSIVE dök upp i urminnes tider av version 8.4, men du kan fortfarande regelbundet stöta på potentiellt sårbara "försvarslösa" förfrågningar. Hur kan man bli av med problem av det här slaget?

Skriv inte rekursiva frågor

Och skriv icke-rekursiva sådana. Med vänliga hälsningar, din K.O.

Faktum är att PostgreSQL ger ganska mycket funktionalitet som du kan använda till ingen tillämpa rekursion.

Använd ett fundamentalt annorlunda förhållningssätt till problemet

Ibland kan man bara titta på problemet från en "annorlunda sida". Jag gav ett exempel på en sådan situation i artikeln "SQL HowTo: 1000 och ett sätt att aggregera" — multiplikation av en uppsättning tal utan att använda anpassade aggregatfunktioner:

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;

Denna begäran kan ersättas med ett alternativ från matematikexperter:

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

Använd generera_serier istället för loopar

Låt oss säga att vi står inför uppgiften att generera alla möjliga prefix för en sträng '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;

Är du säker på att du behöver rekursion här?.. Om du använder LATERAL и generate_series, då behöver du inte ens CTE:

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

Ändra databasstruktur

Du har till exempel en tabell med forummeddelanden med kopplingar från vem som svarat vem, eller en tråd in socialt nätverk:

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

Tja, en typisk begäran om att ladda ner alla meddelanden om ett ämne ser ut ungefär så här:

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 eftersom vi alltid behöver hela ämnet från rotmeddelandet, varför gör vi inte det lägg till dess ID till varje 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 hela vår rekursiva fråga reduceras till just detta:

SELECT
  *
FROM
  message
WHERE
  theme_id = $1;

Använd tillämpade "begränsare"

Om vi inte kan ändra strukturen på databasen av någon anledning, låt oss se vad vi kan lita på så att även förekomsten av ett fel i data inte leder till oändlig rekursion.

Rekursionsdjupräknare

Vi ökar helt enkelt räknaren med en vid varje rekursionssteg tills vi når en gräns som vi anser uppenbart otillräcklig:

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

Pro: När vi försöker loopa kommer vi fortfarande inte att göra mer än den angivna gränsen för iterationer "i djupet".
nackdelar: Det finns ingen garanti för att vi inte kommer att behandla samma post igen - till exempel på ett djup av 15 och 25, och sedan varje +10. Och ingen lovade något om "bredd".

Formellt kommer en sådan rekursion inte att vara oändlig, men om antalet poster vid varje steg ökar exponentiellt vet vi alla väl hur det slutar...

se "Problemet med korn på ett schackbräde"

Väktare av "vägen"

Vi lägger växelvis till alla objektidentifierare vi stötte på längs rekursionsvägen till en array, som är en unik "sökväg" till den:

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

Pro: Om det finns en cykel i datan kommer vi absolut inte att behandla samma post upprepade gånger inom samma väg.
nackdelar: Men samtidigt kan vi bokstavligen gå förbi alla rekord utan att upprepa oss.

se "Knight's Move Problem"

Banlängdsgräns

För att undvika att rekursionen "vandrar" på ett obegripligt djup kan vi kombinera de två föregående metoderna. Eller, om vi inte vill stödja onödiga fält, komplettera villkoret för att fortsätta rekursionen med en uppskattning av väglängden:

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älj en metod efter din smak!

Källa: will.com

PostgreSQL Antimönster: "Infinity is not the limit!", eller Lite om rekursion