PostgreSQL Antipatterns: «Përjetësia nuk është fundi!», ose Pak për rekursivitetin

Rekurzioni — një mekanizëm shumë të fuqishëm dhe të përshtatshëm, nëse kryhen të njëjtat veprime "në thellësi" mbi të dhënat e lidhura. Por rekurzioni i pakontrolluar është një të keqe, e cila mund të çojë ose në ekzekutimin e pafund të procesit, ose (çka ndodh më shpesh) në "shkarkimin" e të gjithë memories së disponueshme.

DBMS në këtë aspekt veprojnë sipas të njëjtave parime — "tha të gërmojë, dhe unë po gërmoj". Kërkesa juaj mund të ngadalësojë jo vetëm proceset përreth, duke zënë vazhdimisht burimet e procesorit, por gjithashtu të "bjerë" tërë bazën, duke "ngënë" të gjithë memorien e disponueshme. Prandaj mbrojtja nga rekurzioni i pafund është përgjegjësi e zhvilluesit vetë.

Në PostgreSQL, mundësia për të përdorur kërkesa rekurzive përmes WITH RECURSIVE ka qenë e pranishme që nga koha e lashtë e versionit 8.4, por ende mund të hasni rregullisht kërkesa "të pambrojtura" me potencial për t'u sulmuar. Si të shlyeni veten nga probleme të tilla?

Të mos shkruani kërkesa rekurzive

Por të shkruani ato që nuk janë rekurzive. Me respekt, K.O.

Në fakt, PostgreSQL ofron një sasi mjaft të madhe funksionaliteti, të cilin mund ta shfrytëzoni për të nuk aplikuar rekurzion.

Të përdorësh një qasje thelbësisht të ndryshme për problemin

Ndonjëherë mund të shohësh problemin "nga një këndvështrim tjetër". Një shembull i tillë unë e kam sjellë në artikullin "SQL HowTo: 1000 dhe një mënyrë për agregimin" — shumëzimi i një grumbulli numrash pa përdorur funksione agregates të përdoruesve:

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 -- përzgjedhja e rezultatit përfundimtar
  i DESC
LIMIT 1;

Ky kërkesë mund të zëvendësohet me një variant nga ekspertët e matematikës:

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

Përdor generate_series në vend të cikleve

Supozoni se na pret një problem për të gjeneruar të gjitha prefixet e mundshme për një 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;

A e duam me të vërtetë rekursivitetin këtu?.. Nëse përdorim LATERAL dhe generate_series, atëherë as CTE nuk do të nevojiten:

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

Ndrysho strukturën e DB

Për shembull, ju keni një tabelë mesazhesh në forum me lidhjet kush-iu përgjigj ose temën në rrjetet sociale:

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

Dhe një kërkesë tipike për të ngarkuar të gjitha mesazhet në një temë duket pak a shumë kështu:

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;

Por pasi që gjithmonë na nevojitet e gjithë tema nga mesazhi rrënjësor, pse të mos shtojmë identifikuesin e tij në secilën hyrje automatikisht?

-- le të shtojmë një fushë me identifikuesin e përgjithshëm të temës dhe një indeks mbi të
ALTER TABLE message
  ADD COLUMN theme_id uuid;
CREATE INDEX ON message(theme_id);

-- inicializojmë identifikuesin e temës në triggerin gjatë futjes
CREATE OR REPLACE FUNCTION ins() RETURNS TRIGGER AS $$
BEGIN
  NEW.theme_id = CASE
    WHEN NEW.reply_to IS NULL THEN NEW.message_id -- marrim nga ngjarja fillestare
    ELSE ( -- ose nga mesazhi, për të cilin përgjigjemi
      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();

Tani e gjithë kërkesa jonë rekursive mund të përfundojë vetëm kështu:

SELECT
  *
FROM
  message
WHERE
  theme_id = $1;

Të përdorim "ndryshues" aplikativë

Nëse nuk përmbyllim strukturën e bazës për arsye të caktuara, le të shohim se çfarë mund të përdorim që prania e një gabimi në të dhëna të mos çojë në ekzekutimin e pafund të rekursit.

Numëruesi i „thellësisë” së rekursit

Thjesht e rritim numëruesin me njësi në çdo hap të rekursit deri në momentin e arritjes së kufirit që ne e konsiderojmë të papranueshëm:

WITH RECURSIVE T AS (
  SELECT
    0 i
  ...
UNION ALL
  SELECT
    i + 1
  ...
  WHERE
    T.i < 64 -- kufiri
)

Pro: Në përpjekjen për të bërë cikli, ne gjithsesi do të bëjmë jo më shumë se limitin e përcaktuar të iteracioneve "në thellësi."
Contra: Nuk ka garanci që ne nuk do të përpunojmë sërish një të dhënë — për shembull, në thellësinë 15 dhe 25, dhe më pas çdo +10. E ashtuquajtur “në gjerësi” nuk premton asgjë.

Formalisht, një rekurs i tillë nuk do të jetë pafund, por nëse numri i të dhënave rritet eksponencialisht në secilin hap, të gjithë e dimë se si përfundon kjo...

shih „Problemi i kokrrave mbi tabelën e shahut”

Ruajtësi i "rrugës"

Radhitshëm shkruajmë të gjitha identifikatorët e objekteve që hasim gjatë rrugës së rekursit në një varg, i cili është "rruga" unike deri te ajo:

ME RECURSIVE T AS (
  SELECT
    ARRAY[id] path
  ...
UNION ALL
  SELECT
    path || id
  ...
  WHERE
    id  ALL(T.path) -- nuk përputhet me asnjë nga
)

Pro: Nëse ka një cikël në të dhëna, ne përfundimisht nuk do të procesojmë të njëjtën shënim përsëri brenda një rruge.
Contra: Megjithatë, ne mund të kalojmë, në të vërtetë, të gjitha shënime, pa u përsëritur.

shih «Problemi i lëvizjes së kalit»

Kufizimi i gjatë të rrugës

Për të shmangur situatën e «pastrimit» të rekursisë në thellësi të paqartë, ne mund të kombinojmë dy metodat e mëparshme. Ose, nëse nuk duam të mbajmë fusha të tepërta, të shtojmë kushtin e vazhdimit të rekursisë me vlerësimin e gjatë të rrugës:

ME RECURSIVE T AS (
  SELECT
    ARRAY[id] path
  ...
UNION ALL
  SELECT
    path || id
  ...
  WHERE
    id  ALL(T.path) DHE
    array_length(T.path, 1) < 10
)

Zgjidhni metodën sipas dëshirës tuaj!

Burimi: habr.com