🥇PostgreSQL Антипатерни: «Безкрайността не е предел!», или Малко за рекурсия

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

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

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

А питайте нерекурсивни. С уважение, Вашият К.О.

Всъщност, 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;:

Наистина ли е необходима рекурсия тук?.. Ако се възползвате от

generate_series LATERAL и , дори CTE не са необходими:SELECT substr(str, 1, ln) str FROM (VALUES('abcdefgh')) T(str) , LATERAL( SELECT generate_series(length(str), 1, -1) ln ) X;

Променете структурата на БД

Например, имате таблица с форуми с връзки кой-кого е отговорил или тема в

Например, имате таблица с форуми с връзки, кой на кого е отговорил или теме в социалната мрежа:

СЪЗДАЙ ТАБЛИЦА message(
  message_id
    uuid
      ПРАВЕН ПРИ КЛЮЧ
, reply_to
    uuid
      ОНАЗНАЧАВА message
, body
    текст
);
СЪЗДАЙ ИНДЕКС ВЪРХУ message(reply_to);

Типичният запрос за зареждане на всички съобщения по една тема изглежда по следния начин:

С СВОБОДНО ЗАБРАНЕНА T КАТО (
  ИЗБЕРИ
    *
  ОТ
    message
  КЪДЕ
    message_id = $1
СЪЮЗ ВСИЧКО
  ИЗБЕРИ
    m.*
  ОТ
    T
  СЪЕДИНЯВАМ
    message m
      ОН m.reply_to = T.message_id
)
ТАБЛИЦА T;

Но тъй като винаги ни е нужна цялата тема от коренното съобщение, защо да не добавим неговия идентификатор във всяка запис автоматично?

-- добавим поле с общ идентификатор на темата и индекс върху него
ALTER TABLE message
  ДОДАЙ КОЛОНА theme_id uuid;
СЪЗДАЙ ИНДЕКС ВЪРХУ message(theme_id);

-- инициализиране на идентификатора на темата при тригер при вмъкване
СЪЗДАЙ ИЛИ ЗАМЕНИ ФУНКЦИЯ ins() ВРЪЩА TRIGGER КАТО $$
ЗАПОЧВА...
  НОВ.theme_id = СЛУЧАЙ
    КОГАТО НОВ.reply_to Е NULL ТОГАВА НОВ.message_id -- взимаме от стартовото събитие
    ИЛИ ( -- или от съобщението, на което отговаряме
      ИЗБЕРИ
        theme_id
      ОТ
        message
      КЪДЕ
        message_id = НОВ.reply_to
    )
  КРАЙ;
  ВРЪЩА НОВ;
КРАЙ;
$$ ЕЗИК plpgsql;

СЪЗДАЙ ТРИГЕР ins ПРЕДИ ВМЪКВАНЕ
  ВЪРХУ message
    ЗА ВСИЧКИ РЕДОВЕ
      ИЗПРАВИ ПРОЦЕДУРАТА ins();

Сега нашият рекурсивен запрос може да бъде сведен до следното:

ИЗБЕРИ
  *
ОТ
  message
КЪДЕ
  theme_id = $1;

Използвайте приложни "ограничители"

Ако не можем да променим структурата на базата по някакви причини, нека видим какво можем да опрем, за да избегнем безкрайното изпълнение на рекурсията дори при наличие на грешки в данните.

Брояч на "дълбочината" на рекурсията

Просто увеличаваме брояча с единица на всяка стъпка на рекурсията до момента на достигане на предел, който смятаме за недопустим:

С СВОБОДНО ЗАБРАНЕНА T КАТО (
  ИЗБЕРИ
    0 i
  ...
СЪЮЗ ВСИЧКО
  ИЗБЕРИ
    i + 1
  ...
  КЪДЕ
    T.i < 64 -- предел
)

Професионалист: При опит за зацикляне, все пак ще направим не повече от зададения лимит итерации "навътре".
Недостатък: Няма гаранция, че няма да обработим повторно едно и също запис — например, на дълбочина 15 и 25, а след това пред всеки +10. И освен това никой не е обещал нищо за "нашир".

Формално, такава рекурсия няма да бъде безкрайна, но ако на всяка стъпка количеството на записите се увеличава експоненциално, всички знаем какво следва…

вж. "Задача за зърната на шахматната дъска"

Съхранител на "пътя"

Последователно добавяме всички срещнати по време на рекурсията идентификатори на обекти в масив, който е уникален "път" до него:

С СВОБОДНО ЗАБРАНЕНА T КАТО (
  ИЗБЕРИ
    ARRAY[id] path
  ...
СЪЮЗ ВСИЧКО
  ИЗБЕРИ
    path || id
  ...
  КЪДЕ
    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
)

Изберете начина, който ви харесва!

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