Mga PostgreSQL Antipattern: "Ang Infinity ay hindi ang limitasyon!", o Medyo tungkol sa recursion

Recursion - isang napakalakas at maginhawang mekanismo kung ang parehong "malalim" na mga aksyon ay isinasagawa sa nauugnay na data. Ngunit ang hindi makontrol na recursion ay isang kasamaan na maaaring humantong sa alinman walang katapusang pagpapatupad proseso, o (na nangyayari nang mas madalas) sa "pagkain" lahat ng magagamit na memorya.

Ang DBMS sa bagay na ito ay gumagana sa parehong mga prinsipyo - "Sinabi nila sa akin na maghukay, kaya hinukay ko". Hindi lamang maaaring pabagalin ng iyong kahilingan ang mga kalapit na proseso, patuloy na kumukuha ng mga mapagkukunan ng processor, ngunit "i-drop" din ang buong database, "kinakain" ang lahat ng magagamit na memorya. proteksyon laban sa walang katapusang recursion - ang responsibilidad ng developer mismo.

Sa PostgreSQL, ang kakayahang gumamit ng mga recursive na query sa pamamagitan ng WITH RECURSIVE ay lumitaw noong unang panahon ng bersyon 8.4, ngunit maaari mo pa ring regular na makatagpo ng mga potensyal na mahina na "walang pagtatanggol" na mga kahilingan. Paano mapupuksa ang iyong sarili sa ganitong uri ng mga problema?

Huwag magsulat ng mga recursive na query

At sumulat ng mga hindi recursive. Taos-puso, ang iyong K.O.

Sa katunayan, ang PostgreSQL ay nagbibigay ng napakaraming functionality na magagamit mo hindi ilapat ang recursion.

Gumamit ng isang panimula na naiibang diskarte sa problema

Minsan maaari mong tingnan ang problema mula sa "iba't ibang panig". Nagbigay ako ng isang halimbawa ng ganoong sitwasyon sa artikulo "SQL HowTo: 1000 at isang paraan ng pagsasama-sama" — pagpaparami ng isang hanay ng mga numero nang hindi gumagamit ng mga custom na pinagsama-samang function:

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;

Maaaring palitan ang kahilingang ito ng opsyon mula sa mga eksperto sa matematika:

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

Gumamit ng generate_series sa halip na mga loop

Sabihin nating nahaharap tayo sa gawain ng pagbuo ng lahat ng posibleng prefix para sa isang string '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;

Sigurado ka bang kailangan mo ng recursion dito?.. Kung gagamitin mo LATERAL и generate_series, pagkatapos ay hindi mo na kakailanganin ang CTE:

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

Baguhin ang istraktura ng database

Halimbawa, mayroon kang talahanayan ng mga mensahe sa forum na may mga koneksyon mula sa kung kanino tumugon, o isang thread sa loob social network:

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

Well, ang isang karaniwang kahilingan na i-download ang lahat ng mga mensahe sa isang paksa ay mukhang ganito:

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;

Ngunit dahil lagi nating kailangan ang buong paksa mula sa ugat na mensahe, kung gayon bakit hindi natin idagdag ang ID nito sa bawat entry awtomatiko?

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

Ngayon ang aming buong recursive query ay maaaring bawasan sa ito lamang:

SELECT
  *
FROM
  message
WHERE
  theme_id = $1;

Gumamit ng inilapat na "mga limitasyon"

Kung hindi natin mababago ang istraktura ng database sa ilang kadahilanan, tingnan natin kung ano ang maaasahan natin upang kahit na ang pagkakaroon ng isang error sa data ay hindi humantong sa walang katapusang recursion.

Recursion depth counter

Dinadagdagan lang namin ng isa ang counter sa bawat hakbang ng recursion hanggang sa maabot namin ang limitasyon na itinuturing naming malinaw na hindi sapat:

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

Pro: Kapag sinubukan naming mag-loop, gagawa pa rin kami ng hindi hihigit sa tinukoy na limitasyon ng mga pag-ulit "sa lalim".
cons: Walang garantiya na hindi namin muling ipoproseso ang parehong record - halimbawa, sa lalim na 15 at 25, at pagkatapos ay tuwing +10. At walang nangako ng anuman tungkol sa "lawak".

Sa pormal na paraan, ang gayong recursion ay hindi magiging walang hanggan, ngunit kung sa bawat hakbang ang bilang ng mga talaan ay tumaas nang husto, alam nating lahat kung paano ito nagtatapos...

tingnan ang "Ang problema ng mga butil sa isang chessboard"

Tagapangalaga ng "landas"

Halili naming idinaragdag ang lahat ng object identifier na nakatagpo namin kasama ang recursion path sa isang array, na isang natatanging "path" dito:

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

Pro: Kung mayroong isang cycle sa data, talagang hindi namin ipoproseso ang parehong record nang paulit-ulit sa loob ng parehong landas.
cons: Ngunit sa parehong oras, maaari nating literal na i-bypass ang lahat ng mga talaan nang hindi inuulit ang ating sarili.

tingnan ang "Knight's Move Problem"

Limitasyon sa Haba ng Landas

Upang maiwasan ang sitwasyon ng recursion na "paglaboy-laboy" sa isang hindi maintindihan na lalim, maaari nating pagsamahin ang dalawang naunang pamamaraan. O, kung ayaw naming suportahan ang mga hindi kinakailangang field, dagdagan ang kundisyon para sa pagpapatuloy ng recursion na may pagtatantya ng haba ng path:

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
)

Pumili ng paraan sa iyong panlasa!

Pinagmulan: www.habr.com