PostgreSQL Antipatterns: „Безкрайността не е границата!“ или Малко за рекурсията

рекурсия - много мощен и удобен механизъм, ако същите „задълбочени“ действия се извършват върху свързани данни. Но неконтролираната рекурсия е зло, което може да доведе до двете безкрайно изпълнение процес, или (което се случва по-често) на "изяждане" на цялата налична памет.

СУБД в това отношение работят на същите принципи - "Казаха ми да копая, затова копая". Вашата заявка може не само да забави съседните процеси, постоянно заемайки ресурси на процесора, но и да „изпусне" цялата база данни, „изяждайки“ цялата налична памет. Следователно защита срещу безкрайна рекурсия - отговорност на самия разработчик.

В PostgreSQL възможността за използване на рекурсивни заявки чрез WITH RECURSIVE се появи в незапомнените времена на версия 8.4, но все още можете редовно да срещате потенциално уязвими „беззащитни“ заявки. Как да се отървете от проблеми от този род?

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

И напишете нерекурсивни. С уважение, Вашият K.O.

Всъщност 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
)

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

Източник: www.habr.com