🥇PostgreSQL Antipatterns: sa e thellë është rruga e lepurit? le të ecim përmes hierarkisë

Në sistemet ERP komplekse shumë entitete kanë një natyrë hierarkike, kur objekte të ngjashëm renditen në një pemë marrëdhëniesh «prind - fëmijë» — kjo përfshin strukturën organizative të ndërmarrjes (të gjitha këto degët, departamentet dhe grupet e punës), katalogun e produkteve, fushat e punës, dhe gjeografinë e pikave të shitjes,…

Në të vërtetë, nuk ka asnjë fushë të automatizimit të biznesit, ku ndonjë hierarki nuk do të ekzistonte si rezultat. Por edhe nëse nuk punoni "për biznesin", gjithsesi mund të përballeni lehtësisht me lidhje hierarkike. Thjesht, madje edhe pemë gjenalogjike ose skema të katërkëndësh për dyqanet — janë struktura të ngjashme.

Ka shumë mënyra për të ruajtur një pemë të tillë në DBMS, por sot do të ndalemi vetëm në një variant:

CREATE TABLE hier(
  id
    integer
      PRIMARY KEY
, pid
    integer
      REFERENCES hier
, data
    json
);

CREATE INDEX ON hier(pid); -- mos harroni, që FK nuk nënkupton krijimin automatik të indeksit, ndryshe nga PK

Dhe derisa ju po shqyrtoni thellësinë e hierarkisë, ajo po pret me durim, sa të jenë [jo]efikas mënyrat tuaja "naive" për të punuar me një strukturë të tillë.

Le të shqyrtojmë detyrat tipike që shfaqen, realizimin e tyre në SQL dhe të përpiqemi t'i përmirësojmë performancën.

#1. Насколько глубока кроличья нора?

Le të pranojmë që kjo strukturë do të reflektojë nënshtrimin e departamenteve në strukturën organizative: departamentet, divizionet, sektorët, degët, grupet e punës,… — si të doni t'i quani.

Së pari, do të krijojmë 'pemën' tonë me 10K elemente

INSERT INTO hier
WITH RECURSIVE T AS (
  SELECT
    1::integer id
  , '{1}'::integer[] pids
UNION ALL
  SELECT
    id + 1
  , pids[1:(random() * array_length(pids, 1))::integer] || (id + 1)
  FROM
    T
  WHERE
    id < 10000
)
SELECT
  pids[array_length(pids, 1)] id
, pids[array_length(pids, 1) - 1] pid
FROM
  T;

Le të fillojmë me detyrën më të thjeshtë — të gjejmë të gjithë punonjësit që punojnë brenda një sektori të caktuar, ose në terma hierarkikë — të gjejmë të gjithë pasardhësit e një nyjeje. Dhe gjithashtu të marrim "thellësinë" e pasardhësit… Të gjitha këto mund të jetë e nevojshme, për shembull, për të ndërtuar një zgjedhje të ndërlikuar mbi listën e ID-ve të këtyre punonjësve.

Nuk do të kishte asnjë problem, nëse këta pasardhës ishin vetëm disa nivele dhe numri i tyre ishte brenda dhjetëshes, por nëse nivelet janë më shumë se 5, dhe pasardhësit kanë arritur në disa dhjetëra — mund të ketë probleme. Le të shohim se si shkruhen (dhe funksionojnë) variante tradicionale të kërkimit "poshtë pemës". Por së pari, le të përcaktojmë se cilat nga nyjet do të jenë më interesante për studimet tona.

Më të "thellat" nënpemët:

WITH RECURSIVE T AS (
  SELECT
    id
  , pid
  , ARRAY[id] path
  FROM
    hier
  WHERE
    pid IS NULL
UNION ALL
  SELECT
    hier.id
  , hier.pid
  , T.path || hier.id
  FROM
    T
  JOIN
    hier
      ON hier.pid = T.id
)
TABLE T ORDER BY array_length(path, 1) DESC;

 id  | pid  | path
---------------------------------------------
7624 | 7623 | {7615,7620,7621,7622,7623,7624}
4995 | 4994 | {4983,4985,4988,4993,4994,4995}
4991 | 4990 | {4983,4985,4988,4989,4990,4991}
...

Më të "të gjera" nënpemët:

...
SELECT
  path[1] id
, count(*)
FROM
  T
GROUP BY
  1
ORDER BY
  2 DESC;

id   | count
------------
5300 |   30
 450 |   28
1239 |   27
1573 |   25

Për këto kërkesa, ne përdorëm një tipik JOIN rekurziv:

Është e qartë, që në këtë model kërkese numri i iteracioneve do të përputhen me numrin e përgjithshëm të pasardhësve (dhe ata janë disa dhjetëra), dhe do të mbatë kjo mund të konsumojë burime të konsiderueshme, dhe si pasojë, kohë.

Le të verifikojmë në nënpemën më "të gjerë":

WITH RECURSIVE T AS (
  SELECT
    id
  FROM
    hier
  WHERE
    id = 5300
UNION ALL
  SELECT
    hier.id
  FROM
    T
  JOIN
    hier
      ON hier.pid = T.id
)
TABLE T;

[shiko në explain.tensor.ru]

Siç e kishim parashikuar, gjetëm të gjitha 30 rekordet. Por për të arritur këtë, shpenzuam 60% të gjithë kohës — sepse realizuam gjithashtu dhe 30 kërkesa sipas indekseve. Por a është e mundur që të bëhet më mirë?

Leximi masiv sipas indeksit

A na nevojitet për secilën nyje të bëjmë kërkesë të veçantë ndaj indeksit? Në fakt, jo — ne mund të lexojmë nga indeksi menjëherë për disa çelësa me një kërkesë me anë të = ANY(array).

Dhe në çdo grup të tillë identifikuesish, ne mund të marrim të gjithë ID-të e gjetura në hapat e mëparshëm "për nyjet". Pra, në çdo hap të mëtejshëm, do të kërkojmë të gjithë pasardhësit e caktuar në nivelin e caktuar.

Por, ja problemet; në zgjedhjen rekurzive nuk mund të referohemi vetvetes në një kërkesë të brendshme, dhe ne na nevojitet ndonjë mënyrë për të selektuar vetëm atë që është gjetur në nivelin e mëparshëm… Me sa duket, nuk është e mundur të bëjmë një kërkesë të brendshme në të gjithë zgjedhjen — por ndaj një fushe të saj — është e mundur. Dhe kjo fushë mund të jetë dhe një varg — që është pikërisht ajo që na nevojitet për përdorimin ANY.

Dëgjohet disi e çuditshme, por në skemë — gjithçka është e thjeshtë.

WITH RECURSIVE T AS (
  SELECT
    ARRAY[id] id$
  FROM
    hier
  WHERE
    id = 5300
UNION ALL
  SELECT
    ARRAY(
      SELECT
        id
      FROM
        hier
      WHERE
        pid = ANY(T.id$)
    ) id$
  FROM
    T
  WHERE
    coalesce(id$, '{}')  '{}' -- kushti për t'u dalë nga cikli - vargu i zbrazët
)
SELECT
  unnest(id$) id
FROM
  T;

[shiko në explain.tensor.ru]

Dhe këtu më e rëndësishmja është madje jo fitimi prej 1.5 herë në kohë, por që ne lexuam më pak buffers, pasi kërkesat ndaj indeksit ishim gjithsej 5 në vend të 30!

Një bonus shtesë është fakti se pas unnest-it përfundimtar identifikuesit do të mbeten të renditur sipas "nivelit".

Shenja e nyjës

Konsiderata e ardhshme që do të ndihmojë në përmirësimin e performancës është se "gjethet" nuk mund të kenë fëmijë, pra për ta nuk nevojitet të kërkohet "poshtë". Në kontekstin e detyrës sonë, kjo do të thotë se nëse kemi kaluar nëpër zinxhirin e departamenteve dhe kemi arritur në një punonjës, atëherë nuk ka nevojë të kërkojmë më tej në këtë degë.

Le të shtojmë në tabelën tonë shtesë boolean-fushën, e cila do të na tregojë menjëherë nëse ky regjistrim specifik në strukturën tonë është "nyjë" – domethënë, a mund të ketë fëmijë në të vërtetë.

ALTER TABLE hier
  ADD COLUMN branch boolean;

UPDATE
  hier T
SET
  branch = TRUE
WHERE
  EXISTS(
    SELECT
      NULL
    FROM
      hier
    WHERE
      pid = T.id
    LIMIT 1
);
-- Kërkesa u përfundua me sukses: 3033 rreshta u ndryshuan në 42 ms.

Fantastike! Duket se vetëm pak mbi 30% e të gjithë elementeve të strukturës kanë fëmijë.

Tani le të aplikojmë një mekanizëm tjetër – lidhje me pjesën rekursive përmes LATERAL, e cila do të na lejojë të adresojmë drejtpërdrejt fushat e "tabelës" rekursive, ndërsa funksionin agregat me kushtin e filtrimit sipas shenjës së nyjës e përdorim për të zvogëluar setin e çelësave:

WITH RECURSIVE T AS (
  SELECT
    array_agg(id) id$
  , array_agg(id) FILTER(WHERE branch) ns$
  FROM
    hier
  WHERE
    id = 5300
UNION ALL
  SELECT
    X.*
  FROM
    T
  JOIN LATERAL (
    SELECT
      array_agg(id) id$
    , array_agg(id) FILTER(WHERE branch) ns$
    FROM
      hier
    WHERE
      pid = ANY(T.ns$)
  ) X
    ON coalesce(T.ns$, '{}')  '{}'
)
SELECT
  unnest(id$) id
FROM
  T;

[shiko në explain.tensor.ru]

Kemi arritur të shkurtosh një tjetër kërkesë për indeks dhe fituam më shumë se 2 herë në vëllim të lexueshëm.

#2. Вернемся к корням

Ky algoritëm do të jetë i dobishëm nëse ju nevojitet të mbledhni regjistrime për të gjithë elementët "lart në strukturë", duke ruajtur informacionin se cilat gjethe origjinale (dhe me cilat indikatorë) e kanë shkaktuar përfshirjen në përzgjedhje – për shembull, për formimin e një raporti përmbledhës me agregim në nyje.

Të tjerat duhet të perceptohen ekskluzivisht si një provë e konceptit, sepse kërkesa bëhet shumë e ngarkuar. Por nëse dominon në bazën tuaj – duhet të mendoni për aplikimin e metodave të ngjashme.

Le të fillojmë me disa shpallje të thjeshta:

Një regjistrim të vetëm nga baza është më mirë të lexosh vetëm një herë.
Regjistrimet nga baza lexohen më efektivisht "në grupe", sesa një nga një.

Tani le të përpiqemi të konstruktojmë kërkesën që na nevojitet.

Hapi 1

E qartë, që në inicializimin e rekursisë (çfarëdo pa të!) do të na duhen të lexojmë regjistrimet e vetë gjetheve sipas setit të identifikuesve fillestarë:

WITH RECURSIVE tree AS (
  SELECT
    rec -- kjo është regjistrimi i plotë i tabelës
  , id::text chld -- kjo është "seti" i gjetheve origjinale që e sollën këtu
  FROM
    hier rec
  WHERE
    id = ANY('{1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192}'::integer[])
UNION ALL
  ...

Nëse ndokush e ka menduar të çuditshme që "seti" ruhet si string, e jo si array, ka një shpjegim të thjeshtë për këtë. Për string-et ekziston një funksion agregues "bashkues" i ndërtuar brenda string_agg, dhe për array-në – nuk ka. Megjithëse mund të implementohet lehtësisht vetë.

Hapi 2

Tani na duhet të marrim setin e ID-ve të seksioneve që do të duhet të lexojmë më tej. Ato do të duhen të dublohen në regjistrimet e ndryshme nga seti fillestar – pra, na nevojitet të grumbullojmë ato, duke ruajtur informacionin për gjethet-burim.

Por këtu na presin tre probleme të pakëndshme:

"Pjesa nën-rekursive" e kërkesës nuk mund të përmbajë funksione agregate GROUP BY.
Aplikimi ndaj "tabelës" rekursive nuk mund të jetë në një nënkërkesë të ndodhur.
Kërkesa në pjesën rekursive nuk mund të përmbajë CTE.

Fatmirësisht, të gjitha këto probleme janë relativisht të lehta për t'u kapërcyer. Le të fillojmë nga fundi.

CTE në pjesën rekursive

Kështu nuk punon:

WITH RECURSIVE tree AS (
  ...
UNION ALL
  WITH T (...)
  SELECT ...
)

Dhe kështu – funksionon, kllapa zgjidh!

WITH RECURSIVE tree AS (
  ...
UNION ALL
  (
    WITH T (...)
    SELECT ...
  )
)

Nënkërkesa ndaj "tabelës" rekursive

Hë… Aplikimi ndaj CTE-së rekursive nuk mund të jetë në një nënkërkesë. Por mund të jetë brenda CTE-së! Dhe nënkërkesa mund të lidhet me këtë CTE!

GROUP BY brenda rekursisë

E pakëndshme, por… Ne kemi një mënyrë të thjeshtë për të simuluar GROUP BY përmes DISTINCT ON dhe funksioneve dritare!

SELECT
  (rec).pid id
, string_agg(chld::text, ',') chld
FROM
  tree
WHERE
  (rec).pid IS NOT NULL
GROUP BY 1 -- nuk funksionon!

Por kështu – funksionon!

SELECT DISTINCT ON((rec).pid)
  (rec).pid id
, string_agg(chld::text, ',') OVER(PARTITION BY (rec).pid) chld
FROM
  tree
WHERE
  (rec).pid IS NOT NULL

Tani e shohim pse ID numerik u shndërrua në tekst – që të mund të bashkohen përmes presjes!

Hapi 3

Për finale na mbetet vetëm pak:

lexojmë regjistrimet "seksioneve" sipas setit të ID-ve të grumbulluara
po ashtu shoqërojmë seksionet e lexuara me "setet" e gjetheve origjinale
"shpjegojmë" rreshtin-set përmes unnest(string_to_array(chld, ',')::integer[])

ME RECURSIV tree AS (
  SELECT
    rec
  , id::text chld
  FROM
    hier rec
  WHERE
    id = ANY('{1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192}'::integer[])
UNION ALL
  (
    WITH prnt AS (
      SELECT DISTINCT ON((rec).pid)
        (rec).pid id
      , string_agg(chld::text, ',') OVER(PARTITION BY (rec).pid) chld
      FROM
        tree
      WHERE
        (rec).pid IS NOT NULL
    )
    , nodes AS (
      SELECT
        rec
      FROM
        hier rec
      WHERE
        id = ANY(ARRAY(
          SELECT
            id
          FROM
            prnt
        ))
    )
    SELECT
      nodes.rec
    , prnt.chld
    FROM
      prnt
    JOIN
      nodes
        ON (nodes.rec).id = prnt.id
  )
)
SELECT
  unnest(string_to_array(chld, ',')::integer[]) leaf
, (rec).* 
FROM
  tree;

[shiko në explain.tensor.ru]

Burimi: habr.com