ProHoster > Blog > Ma'muriyat > PostgreSQL antipatternlari: “Cheksizlik chegara emas!” Yoki bir oz rekursiya haqida

PostgreSQL antipatternlari: “Cheksizlik chegara emas!” Yoki bir oz rekursiya haqida

rekursiya - tegishli ma'lumotlarda bir xil "chuqur" harakatlar amalga oshirilsa, juda kuchli va qulay mexanizm. Ammo nazoratsiz rekursiya har biriga olib kelishi mumkin bo'lgan yovuzlikdir cheksiz ijro jarayon yoki (bu tez-tez sodir bo'ladi) uchun barcha mavjud xotirani "eyish".

PostgreSQL antipatternlari: “Cheksizlik chegara emas!” Yoki bir oz rekursiya haqida
Bu borada DBMS xuddi shu tamoyillar asosida ishlaydi - "Ular menga qazishni aytishdi, men qazaman". Sizning so'rovingiz nafaqat qo'shni jarayonlarni sekinlashtirishi, doimiy ravishda protsessor resurslarini egallashi, balki butun ma'lumotlar bazasini "tashlab qo'yishi", barcha mavjud xotirani "eyishi" mumkin. Shuning uchun. cheksiz rekursiyadan himoya qilish - ishlab chiquvchining o'zi javobgarligi.

PostgreSQL-da, orqali rekursiv so'rovlardan foydalanish imkoniyati WITH RECURSIVE 8.4 versiyasida paydo bo'lgan, ammo siz hali ham potentsial zaif "himoyasiz" so'rovlarga duch kelishingiz mumkin. Bunday muammolardan qanday qutulish kerak?

Rekursiv so'rovlarni yozmang

Va rekursiv bo'lmaganlarni yozing. Hurmat bilan, Sizning K.O.

Aslida, PostgreSQL siz foydalanishingiz mumkin bo'lgan juda ko'p funksiyalarni taqdim etadi yo'q rekursiyani qo'llash.

Muammoga tubdan boshqacha yondashuvdan foydalaning

Ba'zan muammoga "boshqa tomondan" qarashingiz mumkin. Men maqolada bunday vaziyatga misol keltirdim "SQL HowTo: 1000 va birlashtirishning bir usuli" - maxsus agregat funktsiyalaridan foydalanmasdan raqamlar to'plamini ko'paytirish:

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;

Ushbu so'rov matematika bo'yicha mutaxassislarning varianti bilan almashtirilishi mumkin:

WITH src AS (
  SELECT unnest('{2,3,5,7,11,13,17,19}'::integer[]) prime
)
SELECT
  exp(sum(ln(prime)))::integer val
FROM
  src;

Looplar o'rnigagener_series dan foydalaning

Aytaylik, biz satr uchun barcha mumkin bo'lgan prefikslarni yaratish vazifasiga duch keldik '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;

Bu yerda rekursiya kerakligiga ishonchingiz komilmi?.. Agar foydalansangiz LATERAL и generate_series, keyin sizga CTE kerak bo'lmaydi:

SELECT
  substr(str, 1, ln) str
FROM
  (VALUES('abcdefgh')) T(str)
, LATERAL(
    SELECT generate_series(length(str), 1, -1) ln
  ) X;

Ma'lumotlar bazasi tuzilishini o'zgartirish

Masalan, sizda kimga javob berganligi yoki mavzudagi aloqalari bo'lgan forum xabarlari jadvali mavjud ijtimoiy tarmoq:

CREATE TABLE message(
  message_id
    uuid
      PRIMARY KEY
, reply_to
    uuid
      REFERENCES message
, body
    text
);
CREATE INDEX ON message(reply_to);

PostgreSQL antipatternlari: “Cheksizlik chegara emas!” Yoki bir oz rekursiya haqida
Bitta mavzudagi barcha xabarlarni yuklab olish uchun odatiy so'rov quyidagicha ko'rinadi:

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;

Ammo biz har doim asosiy xabardan butun mavzuga muhtojmiz, nega kerak emas har bir yozuvga uning identifikatorini qo'shing avtomatikmi?

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

PostgreSQL antipatternlari: “Cheksizlik chegara emas!” Yoki bir oz rekursiya haqida
Endi bizning butun rekursiv so'rovimiz shu qadar qisqartirilishi mumkin:

SELECT
  *
FROM
  message
WHERE
  theme_id = $1;

Amaldagi "cheklovchilar" dan foydalaning

Agar biron sababga ko'ra ma'lumotlar bazasi strukturasini o'zgartira olmasak, keling, ma'lumotlardagi xatoning mavjudligi ham cheksiz rekursiyaga olib kelmasligi uchun nimaga ishonishimiz mumkinligini ko'rib chiqaylik.

Rekursiya chuqurligi hisoblagichi

Biz yetarli emas deb hisoblagan chegaraga yetgunimizcha, har bir rekursiya bosqichida hisoblagichni bittaga oshiramiz:

WITH RECURSIVE T AS (
  SELECT
    0 i
  ...
UNION ALL
  SELECT
    i + 1
  ...
  WHERE
    T.i < 64 -- предел
)

Pro: Biz halqa qilishga harakat qilsak, biz hali ham "chuqurlikda" takrorlashning belgilangan chegarasidan ko'proq narsani qilmaymiz.
Kamchiliklari: Xuddi shu yozuvni qayta ishlamasligimizga kafolat yo'q - masalan, 15 va 25 chuqurlikda, keyin esa har +10. Va hech kim "kenglik" haqida hech narsa va'da qilmadi.

Rasmiy ravishda bunday rekursiya cheksiz bo'lmaydi, lekin agar har bir qadamda yozuvlar soni eksponent ravishda ko'paysa, uning qanday tugashini hammamiz yaxshi bilamiz...

PostgreSQL antipatternlari: “Cheksizlik chegara emas!” Yoki bir oz rekursiya haqida"Shaxmat taxtasidagi don muammosi" ga qarang.

"Yo'l" ning qo'riqchisi

Biz navbatma-navbat rekursiya yo'li bo'ylab uchragan barcha ob'ekt identifikatorlarini massivga qo'shamiz, bu unga o'ziga xos "yo'l":

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

Pro: Agar ma'lumotlarda tsikl mavjud bo'lsa, biz mutlaqo bir xil yozuvni bir xil yo'lda qayta-qayta qayta ishlamaymiz.
Kamchiliklari: Ammo shu bilan birga, biz o'zimizni takrorlamasdan, barcha yozuvlarni tom ma'noda chetlab o'tishimiz mumkin.

PostgreSQL antipatternlari: “Cheksizlik chegara emas!” Yoki bir oz rekursiya haqida"Ritsarning harakat muammosi" ga qarang

Yo'l uzunligi chegarasi

Tushunarsiz chuqurlikda rekursiyaning "aylanib yurishi" holatini oldini olish uchun biz oldingi ikkita usulni birlashtira olamiz. Yoki, agar biz keraksiz maydonlarni qo'llab-quvvatlashni istamasak, rekursiyani davom ettirish shartini yo'l uzunligini baholash bilan to'ldiring:

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
)

Sizning didingizga mos usulni tanlang!

Manba: www.habr.com

a Izoh qo'shish