🥇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;

Циклдердин ордуна generator_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 -- предел
)

Pro: Биз цикл жасоого аракет кылганда, биз дагы эле "тереңдикте" кайталоонун белгиленген чегинен ашпайбыз.
Cons: Ошол эле жазууну кайра иштетпейбиз деген кепилдик жок - мисалы, 15 жана 25 тереңдикте, анан ар бир +10. Ал эми "кеңдик" жөнүндө эч ким эч нерсе убада кылган эмес.

Формалдуу түрдө мындай рекурсия чексиз болбойт, бирок ар бир кадам сайын жазуулардын саны экспоненциалдуу түрдө көбөйө берсе, анын кандай бүтөрүн баарыбыз жакшы билебиз...

караңыз "Шахмат тактасындагы дан маселеси"

"Жолдун" сакчысы

Рекурсия жолунда кезиккен бардык объекттин идентификаторлорун кезектешип массивге кошобуз, бул ага уникалдуу "жол":

WITH RECURSIVE T AS (
  SELECT
    ARRAY[id] path
  ...
UNION ALL
  SELECT
    path || id
  ...
  WHERE
    id <> ALL(T.path) -- не совпадает ни с одним из
)

Pro: Эгерде маалыматтарда цикл болсо, биз бир эле жолдун ичинде бир эле жазууну кайра-кайра иштетпейбиз.
Cons: Бирок, ошол эле учурда, биз өзүбүздү кайталабастан түзмө-түз бардык жазууларды айланып өтүүгө болот.

кара "Rыцардын жылыш көйгөйүн"

Жолдун узундугунун чеги

Түшүнүксүз тереңдикте рекурсиянын "тентип кетүү" абалынан качуу үчүн биз мурунку эки ыкманы айкалыштыра алабыз. Же болбосо, керексиз талааларды колдогубуз келбесе, рекурсияны улантуу шартын жолдун узундугун баалоо менен толуктаңыз:

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
)

Сиздин табитиңизге ылайык ыкманы тандаңыз!

Source: www.habr.com

PostgreSQL Antipatterns: "Чексиздик - чек эмес!", же бир аз рекурсия жөнүндө