🥇PostgreSQL антипаттерндері: «Шексіздік - бұл шек емес!» немесе рекурсия туралы аздап

Рекурсия - егер ұқсас деректерде бірдей «терең» әрекеттер орындалса, өте күшті және ыңғайлы механизм. Бірақ бақыланбайтын рекурсия - бұл екеуіне де әкелуі мүмкін зұлымдық шексіз орындау процесс, немесе (бұл жиі орын алады). барлық қолжетімді жадты «жеу»..

Осыған байланысты ДҚБЖ дәл сол принциптер бойынша жұмыс істейді - «Олар маған қазба деді, мен қазып беремін". Сіздің сұранысыңыз үнемі процессор ресурстарын алып жатқан көршілес процестерді баяулатып қана қоймайды, сонымен қатар барлық дерекқорды "түсіреді", барлық қолжетімді жадты "жейді". Сондықтан. шексіз рекурсиядан қорғау - әзірлеушінің өз жауапкершілігі.

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;

Бірақ біз әрқашан түбірлік хабарламадан бүкіл тақырыпты қажет ететіндіктен, неге бізге қажет емес әр жазбаға оның идентификаторын қосыңыз автоматты?

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

PostgreSQL антипаттерндері: «Шексіздік - бұл шек емес!» немесе рекурсия туралы аздап