🥇ПостгреСКЛ Антиобрасци: „Бесконачност није граница!“, или Мало о рекурзији

Рекурзија - веома моћан и згодан механизам ако се исте „дубинске“ радње изводе на сродним подацима. Али неконтролисана рекурзија је зло које може довести до једног и другог бескрајно извршење процес, или (што се чешће дешава) да „једе“ сву расположиву меморију.

ДБМС у том погледу раде на истим принципима - "Рекли су ми да копам, па ја копам". Ваш захтев може не само да успори суседне процесе, непрестано заузимајући процесорске ресурсе, већ и да "испусти" целу базу података, "једе" сву доступну меморију. Стога заштита од бесконачне рекурзије - одговорност самог програмера.

У ПостгреСКЛ-у, могућност коришћења рекурзивних упита преко WITH RECURSIVE појавио се у давна времена верзије 8.4, али и даље можете редовно да се сусрећете са потенцијално рањивим „безбрањеним“ захтевима. Како се ослободити проблема ове врсте?

Немојте писати рекурзивне упите

И напишите нерекурзивне. С поштовањем, Ваш К.О.

У ствари, ПостгреСКЛ пружа доста функционалности које можете користити не применити рекурзију.

Користите фундаментално другачији приступ проблему

Понекад можете само сагледати проблем са „друге стране“. У чланку сам навео пример такве ситуације „СКЛ ХовТо: 1000 и један начин агрегације“ — множење скупа бројева без коришћења прилагођених агрегатних функција:

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;

Овај захтев се може заменити опцијом стручњака за математику:

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

Користите генерате_сериес уместо петљи

Рецимо да смо суочени са задатком генерисања свих могућих префикса за стринг '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;

Да ли сте сигурни да вам је овде потребна рекурзија?.. Ако користите LATERAL и generate_series, онда вам неће ни требати ЦТЕ:

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

Промените структуру базе података

На пример, имате табелу порука на форуму са везама ко је коме одговорио или нит друштвена мрежа:

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

Па, типичан захтев за преузимање свих порука на једну тему изгледа отприлике овако:

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;

Али пошто нам је увек потребна цела тема из основне поруке, зашто онда не бисмо додајте свој ИД сваком уносу аутоматски?

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

Сада се цео наш рекурзивни упит може свести само на ово:

SELECT
  *
FROM
  message
WHERE
  theme_id = $1;

Користите примењене „ограничаваче“

Ако из неког разлога нисмо у могућности да променимо структуру базе података, хајде да видимо на шта се можемо ослонити да чак и присуство грешке у подацима не доведе до бесконачне рекурзије.

Бројач дубине рекурзије

Једноставно повећавамо бројач за један на сваком кораку рекурзије док не достигнемо границу коју сматрамо очигледно неадекватном:

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

про: Када покушамо да направимо петљу, и даље нећемо радити више од наведеног ограничења итерација „у дубину“.
Цонс: Нема гаранције да нећемо поново обрадити исти запис – на пример, на дубини од 15 и 25, а затим сваких +10. А о „ширини“ нико ништа није обећавао.

Формално, таква рекурзија неће бити бесконачна, али ако се на сваком кораку број записа експоненцијално повећава, сви добро знамо како се завршава...

види „Проблем зрна на шаховској табли”

Чувар "пута"

Наизменично додајемо све идентификаторе објеката на које смо наишли дуж путање рекурзије у низ, што је јединствена „пута“ до њега:

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

про: Ако постоји циклус у подацима, апсолутно нећемо више пута обрађивати исти запис унутар исте путање.
Цонс: Али у исто време, буквално можемо да заобиђемо све рекорде, а да се не понављамо.

види "Проблем витезова потеза"

Ограничење дужине путање

Да бисмо избегли ситуацију да рекурзија „лута“ на несхватљивој дубини, можемо комбиновати две претходне методе. Или, ако не желимо да подржимо непотребна поља, допунимо услов за наставак рекурзије проценом дужине путање:

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
)

Изаберите метод по свом укусу!

Извор: ввв.хабр.цом

ПостгреСКЛ антиобрасци: „Бесконачност није граница!“, или Мало о рекурзији