PostgreSQL ანტიპატერნები: "უსასრულობა არ არის ზღვარი!" ან ცოტა რამ რეკურსიის შესახებ

რეკურსია - ძალიან ძლიერი და მოსახერხებელი მექანიზმი, თუ იგივე „სიღრმისეული“ მოქმედებები შესრულდება დაკავშირებულ მონაცემებზე. მაგრამ უკონტროლო რეკურსი არის ბოროტება, რომელიც შეიძლება გამოიწვიოს ორივე გაუთავებელი აღსრულება პროცესი, ან (რაც უფრო ხშირად ხდება). ყველა ხელმისაწვდომი მეხსიერების "ჭამა"..

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;

გამოიყენეთ 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;

მაგრამ რადგან ჩვენ ყოველთვის გვჭირდება მთელი თემა საწყისი გზავნილიდან, მაშინ რატომ არ გვჭირდება დაამატეთ მისი 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: მაგრამ ამავე დროს, ჩვენ შეგვიძლია სიტყვასიტყვით ავუაროთ ყველა ჩანაწერს საკუთარი თავის გამეორების გარეშე.

იხილეთ "რაინდის მოძრაობის პრობლემა"

ბილიკის სიგრძის ლიმიტი

გაუგებარ სიღრმეზე რეკურსიული „ხეტიალის“ სიტუაციის თავიდან ასაცილებლად, შეგვიძლია გავაერთიანოთ წინა ორი მეთოდი. ან, თუ არ გვინდა არასაჭირო ველების მხარდაჭერა, შეავსეთ რეკურსიის გაგრძელების პირობა ბილიკის სიგრძის შეფასებით:

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