🥇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: «Бясконцасць – не мяжа!», ці Трохі аб рэкурсіі