🥇PostgreSQL Antipatterns: «Нескінченність - не межа!», або Трохи про рекурсію

рекурсія — дуже потужний і зручний механізм, якщо над пов'язаними даними робляться ті самі дії «вглиб». Але неконтрольована рекурсія — зло, яке може призводити чи до нескінченному виконанню процесу, або (що трапляється частіше) до «вижирання» всієї доступної пам'яті.

СУБД щодо цього працюють за тими самими принципами - "сказали копати, я і копаюВаш запит може не тільки загальмувати сусідні процеси, постійно займаючи ресурси процесора, а й «упустити» всю базу цілком, «з'ївши» всю доступну пам'ять. захист від нескінченної рекурсії - Обов'язок самого розробника.

У PostgreSQL можливість використовувати рекурсивні запити через WITH RECURSIVE з'явилася ще в незапам'ятні часи версії 8.4, але досі можна регулярно зустріти потенційно-вразливі «беззахисні» запити. Як позбавити себе проблем подібного роду?

Не писати рекурсивні запити

А писати нерекурсивно. З повагою, Ваш К.О.

Насправді, PostgreSQL надає досить велику кількість функціоналу, яким можна скористатися, щоб НЕ застосовувати рекурсію.

Використовувати принципово інший підхід до завдання

Іноді можна просто подивитись завдання «з іншого боку». Приклад такої ситуації я наводив у статті SQL HowTo: 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;

Використовувати generate_series замість циклів

Допустимо, перед нами стоїть завдання згенерувати всі можливі префікси для рядка '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, то навіть CTE не знадобляться:

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 -- предел
)

Pro: При спробі зациклювання ми однаково зробимо трохи більше зазначеного ліміту ітерацій «вглиб».
мінуси: Немає гарантії, що ми не обробимо повторно один і той самий запис - наприклад, на глибині 15 і 25, ну і далі буде кожні +10. Та й про «вшир» ніхто нічого не обіцяв.

Формально, така рекурсія не буде нескінченною, але якщо на кожному кроці кількість записів збільшується експонентом, ми всі добре знаємо, чим це закінчується.

див. «Завдання про зерна на шахівниці»

Зберігач «шляху»

Почергово дописуємо всі ідентифікатори об'єктів, що зустрілися нам шляхом рекурсії в масив, який є унікальним «шляхом» до нього:

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

Pro: За наявності циклу в даних ми абсолютно точно не будемо обробляти повторно один і той самий запис в рамках одного шляху.
мінуси: Але при цьому ми можемо обійти буквально всі записи, так і не повторившись.

див. «Завдання про перебіг коня»

Обмеження довжини колії

Щоб уникнути ситуації «блукання» рекурсії на незрозумілій глибині, ми можемо скомбінувати два попередні методи. Або, якщо не хочемо підтримувати зайві поля, доповнити умову продовження рекурсії оцінкою довжини шляху:

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
)

Вибирайте спосіб на власний смак!

Джерело: habr.com

PostgreSQL Antipatterns: «Нескінченність — не межа!», або трохи про рекурсію