🥇PostgreSQL Antipatterns: "Хязгааргүй байдал бол хязгаар биш!", эсвэл Рекурсын талаар бага зэрэг

Рекурсив - холбогдох өгөгдөл дээр ижил "гүнзгий" үйлдлүүд хийгдсэн тохиолдолд маш хүчирхэг, тохиромжтой механизм. Гэхдээ хяналтгүй рекурс нь аль алинд нь хүргэж болзошгүй муу юм эцэс төгсгөлгүй гүйцэтгэл үйл явц, эсвэл (илүү олон тохиолддог) -д боломжтой бүх санах ойг "идэх".

Энэ талаар DBMS ижил зарчмаар ажилладаг - "Тэд намайг ухна гэж хэлсэн болохоор би ухаж байна". Таны хүсэлт процессорын нөөцийг байнга эзэлдэг хөрш зэргэлдээх процессуудыг удаашруулаад зогсохгүй мэдээллийн санг бүхэлд нь "унагаж", байгаа бүх санах ойг "идэж" чадна. Тиймээс. хязгааргүй рекурсийн эсрэг хамгаалалт - хөгжүүлэгч өөрөө хариуцна.

PostgreSQL-д дамжуулан рекурсив асуулга ашиглах чадвар WITH RECURSIVE 8.4 хувилбарын эрт дээр үед гарч ирсэн боловч та эмзэг "хамгаалалтгүй" хүсэлтүүдтэй байнга тулгардаг. Энэ төрлийн асуудлаас хэрхэн ангижрах вэ?

Рекурсив асуулга бүү бич

Мөн рекурсив бусыг бичээрэй. Хүндэтгэсэн, Таны K.O.

Үнэн хэрэгтээ 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;

Гогцооны оронд Generation_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: Бид давталт хийх гэж оролдохдоо "гүнзгий" давталтын заасан хязгаараас илүүг хийхгүй.
Байг: Бид ижил бичлэгийг дахин боловсруулахгүй гэсэн баталгаа байхгүй - жишээлбэл, 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 Antipatterns: "Хязгааргүй бол хязгаар биш!", эсвэл Рекурсын талаар бага зэрэг