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

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

DBMS во овој поглед работат на истите принципи - "Ми рекоа да копам, па јас копамВашето барање не само што може да ги забави соседните процеси, постојано да ги зафаќа ресурсите на процесорот, туку и да ја „испушти“ целата база на податоци, „јадејќи ја“ целата достапна меморија. Затоа заштита од бесконечна рекурзија - одговорност на самиот развивач.

Во 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;

Користете gener_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;

Но, бидејќи секогаш ни е потребна целата тема од основната порака, тогаш зошто да не ни треба додадете го неговиот ID на секој запис автоматски?

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

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

Извор: www.habr.com