🥇PostgreSQL Antipatterns: Gaano kalalim ang butas ng kuneho? dumaan tayo sa hierarchy

Sa mga kumplikadong sistema ng ERP maraming entity ang may hierarchical na kalikasankapag ang mga homogenous na bagay ay pumila puno ng ugnayang ninuno-nag-anak - ito ang istraktura ng organisasyon ng negosyo (lahat ng mga sangay na ito, departamento at grupo ng trabaho), at ang katalogo ng mga kalakal, at mga lugar ng trabaho, at ang heograpiya ng mga punto ng pagbebenta,...

Sa totoo lang, wala naman mga lugar ng automation ng negosyo, kung saan walang anumang hierarchy bilang resulta. Ngunit kahit na hindi ka nagtatrabaho "para sa negosyo," madali ka pa ring makatagpo ng mga hierarchical na relasyon. It's trite, even your family tree or floor plan of premises in a shopping center is the same structure.

Mayroong maraming mga paraan upang mag-imbak ng tulad ng isang puno sa isang DBMS, ngunit ngayon kami ay tumutuon sa isang pagpipilian lamang:

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

CREATE INDEX ON hier(pid); -- не забываем, что FK не подразумевает автосоздание индекса, в отличие от PK

At habang tumitingin ka sa kailaliman ng hierarchy, matiyagang naghihintay na makita kung gaano [kabisado] ang iyong "walang muwang" na mga paraan ng pagtatrabaho sa gayong istraktura.

Tingnan natin ang mga karaniwang problema na lumitaw, ang kanilang pagpapatupad sa SQL, at subukang pagbutihin ang kanilang pagganap.

#1. Gaano kalalim ang butas ng kuneho?

Tanggapin natin, para sa katiyakan, na ang istrukturang ito ay magpapakita ng subordination ng mga kagawaran sa istruktura ng organisasyon: mga departamento, dibisyon, sektor, sangay, mga grupong nagtatrabaho... - anuman ang tawag mo sa kanila.

Una, buuin natin ang ating 'puno' ng 10K elemento

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;

Magsimula tayo sa pinakasimpleng gawain - paghahanap ng lahat ng empleyado na nagtatrabaho sa loob ng isang partikular na sektor, o sa mga tuntunin ng hierarchy - hanapin ang lahat ng mga anak ng isang node. Magiging maganda din na makuha ang "lalim" ng inapo... Ang lahat ng ito ay maaaring kinakailangan, halimbawa, upang bumuo ng ilang uri ng kumplikadong pagpili batay sa listahan ng mga ID ng mga empleyadong ito.

Magiging maayos ang lahat kung mayroon lamang isang pares ng mga antas ng mga inapo na ito at ang bilang ay nasa loob ng isang dosena, ngunit kung mayroong higit sa 5 mga antas, at mayroon nang dose-dosenang mga inapo, maaaring may mga problema. Tingnan natin kung paano isinusulat (at gumagana) ang tradisyonal na mga opsyon sa paghahanap sa down-the-tree. Ngunit una, tukuyin natin kung aling mga node ang magiging pinakakawili-wili para sa aming pananaliksik.

Ang pinaka "malalim" mga subtree:

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}
...

Ang pinaka "malawak" mga subtree:

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

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

Para sa mga query na ito ginamit namin ang karaniwang recursive SUMALI:

Malinaw, sa modelo ng kahilingang ito ang bilang ng mga pag-ulit ay tutugma sa kabuuang bilang ng mga inapo (at mayroong ilang dosenang mga ito), at ito ay maaaring tumagal ng lubos na makabuluhang mga mapagkukunan, at, bilang isang resulta, oras.

Tingnan natin ang "pinakamalawak" na subtree:

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;

[tingnan sa explain.tensor.ru]

Gaya ng inaasahan, nakita namin ang lahat ng 30 record. Ngunit gumugol sila ng 60% ng kabuuang oras dito - dahil gumawa din sila ng 30 paghahanap sa index. Posible bang gumawa ng mas kaunti?

Maramihang pag-proofread ayon sa index

Kailangan ba nating gumawa ng hiwalay na index query para sa bawat node? Lumalabas na hindi - mababasa natin mula sa index gamit ang ilang key nang sabay-sabay sa isang tawag sa tulong = ANY(array).

At sa bawat ganoong pangkat ng mga identifier maaari nating kunin ang lahat ng mga ID na natagpuan sa nakaraang hakbang sa pamamagitan ng "mga node". Ibig sabihin, sa bawat susunod na hakbang ay gagawin natin hanapin ang lahat ng mga inapo ng isang tiyak na antas nang sabay-sabay.

Kaya lang, eto ang problema, sa recursive selection, hindi mo ma-access ang sarili nito sa isang nested query, ngunit kailangan nating piliin lamang kung ano ang natagpuan sa nakaraang antas... Lumalabas na imposibleng gumawa ng nested query para sa buong seleksyon, ngunit posible para sa partikular na field nito. At ang field na ito ay maaari ding isang array - na kung ano ang kailangan nating gamitin ANY.

Ito ay medyo mabaliw, ngunit sa diagram ang lahat ay simple.

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$, '{}') <> '{}' -- условие выхода из цикла - пустой массив
)
SELECT
  unnest(id$) id
FROM
  T;

[tingnan sa explain.tensor.ru]

At dito ang pinakamahalagang bagay ay hindi kahit na manalo ng 1.5 beses sa oras, at nagbawas kami ng mas kaunting buffer, dahil mayroon lang kaming 5 tawag sa index sa halip na 30!

Ang isang karagdagang bonus ay ang katotohanan na pagkatapos ng huling unnest, ang mga identifier ay mananatiling nakaayos ayon sa "mga antas".

Node sign

Ang susunod na pagsasaalang-alang na makakatulong sa pagpapabuti ng pagganap ay − "dahon" ay hindi maaaring magkaroon ng mga anak, iyon ay, para sa kanila ay hindi na kailangang tumingin "pababa" sa lahat. Sa pagbabalangkas ng aming gawain, nangangahulugan ito na kung sinundan namin ang kadena ng mga departamento at naabot namin ang isang empleyado, kung gayon hindi na kailangang tumingin pa sa sangay na ito.

Pumasok na tayo sa table natin karagdagang boolean-field, na agad na magsasabi sa amin kung ang partikular na entry na ito sa aming puno ay isang "node" - iyon ay, kung maaari itong magkaroon ng mga inapo.

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
);
-- Запрос успешно выполнен: 3033 строк изменено за 42 мс.

Malaki! Lumalabas na mahigit 30% lamang ng lahat ng elemento ng puno ang may mga inapo.

Ngayon ay gumamit tayo ng bahagyang naiibang mekaniko - mga koneksyon sa recursive na bahagi sa pamamagitan ng LATERAL, na magbibigay-daan sa aming agarang ma-access ang mga field ng recursive na "talahanayan", at gumamit ng pinagsama-samang function na may kundisyon sa pag-filter batay sa isang node upang bawasan ang hanay ng mga key:

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;

[tingnan sa explain.tensor.ru]

Nagawa naming bawasan ang isa pang index call at nanalo ng higit sa 2 beses sa dami proofread.

#2. Balik tayo sa pinagmulan

Magiging kapaki-pakinabang ang algorithm na ito kung kailangan mong mangolekta ng mga tala para sa lahat ng elemento "up the tree", habang pinapanatili ang impormasyon tungkol sa kung aling source sheet (at kung anong mga indicator) ang naging dahilan upang maisama ito sa sample - halimbawa, upang makabuo ng isang buod na ulat na may pagsasama-sama sa mga node.

Ang mga sumusunod ay dapat kunin lamang bilang isang patunay-ng-konsepto, dahil ang kahilingan ay lumalabas na napakahirap. Ngunit kung nangingibabaw ito sa iyong database, dapat mong isipin ang paggamit ng mga katulad na pamamaraan.

Magsimula tayo sa ilang simpleng pahayag:

Ang parehong talaan mula sa database Pinakamabuting basahin ito nang isang beses lamang.
Mga tala mula sa database Ito ay mas mahusay na basahin sa mga batchkaysa mag-isa.

Ngayon subukan nating buuin ang kahilingan na kailangan natin.

Hakbang 1

Malinaw, kapag sinisimulan ang recursion (nasaan tayo kung wala ito!) kakailanganin nating ibawas ang mga rekord ng mga dahon mismo batay sa hanay ng mga paunang identifier:

WITH RECURSIVE 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
  ...

Kung tila kakaiba sa isang tao na ang "set" ay naka-imbak bilang isang string at hindi isang array, pagkatapos ay mayroong isang simpleng paliwanag para dito. Mayroong built-in na aggregating "gluing" function para sa mga string string_agg, ngunit hindi para sa mga array. Bagama't siya madaling ipatupad sa iyong sarili.

Hakbang 2

Ngayon ay makakakuha tayo ng isang set ng mga section ID na kailangang basahin pa. Halos palaging madodoble sila sa iba't ibang mga talaan ng orihinal na hanay - kaya gagawin namin pangkatin sila, habang pinapanatili ang impormasyon tungkol sa pinagmulang dahon.

Ngunit narito ang tatlong problemang naghihintay sa atin:

Ang "subrecursive" na bahagi ng query ay hindi maaaring maglaman ng mga pinagsama-samang function na may GROUP BY.
Ang isang reference sa isang recursive na "talahanayan" ay hindi maaaring nasa isang nested subquery.
Ang isang kahilingan sa recursive na bahagi ay hindi maaaring maglaman ng CTE.

Sa kabutihang palad, ang lahat ng mga problemang ito ay medyo madaling lutasin. Magsimula tayo sa dulo.

CTE sa recursive na bahagi

Narito ito hindi gumagana:

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

At kaya ito gumagana, ang mga panaklong ay gumagawa ng pagkakaiba!

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

Nested query laban sa isang recursive na "table"

Hmm... Hindi ma-access ang recursive CTE sa isang subquery. Ngunit maaaring nasa loob ito ng CTE! At ang isang nested na kahilingan ay maaari nang ma-access ang CTE na ito!

GROUP BY inside recursion

Ito ay hindi kasiya-siya, ngunit... Mayroon kaming isang simpleng paraan upang tularan ang GROUP BY gamit DISTINCT ON at mga function ng window!

SELECT
  (rec).pid id
, string_agg(chld::text, ',') chld
FROM
  tree
WHERE
  (rec).pid IS NOT NULL
GROUP BY 1 -- не работает!

At ito ay kung paano ito gumagana!

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

Ngayon ay nakita na natin kung bakit ginawang text ang numeric ID - upang pagsamahin ang mga ito na pinaghihiwalay ng mga kuwit!

Hakbang 3

Para sa final wala na tayong natitira:

binabasa namin ang mga talaan ng "seksyon" batay sa isang hanay ng mga nakagrupong ID
inihahambing namin ang mga ibinawas na seksyon sa mga "set" ng orihinal na mga sheet
"palawakin" ang set-string gamit unnest(string_to_array(chld, ',')::integer[])

WITH RECURSIVE 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;

[tingnan sa explain.tensor.ru]

Pinagmulan: www.habr.com

Mga PostgreSQL Antipattern: Gaano kalalim ang butas ng kuneho? dumaan tayo sa hierarchy

#1. Gaano kalalim ang butas ng kuneho?

Maramihang pag-proofread ayon sa index

Node sign

#2. Balik tayo sa pinagmulan

Hakbang 1

Hakbang 2

CTE sa recursive na bahagi

Nested query laban sa isang recursive na "table"

GROUP BY inside recursion

Hakbang 3

Magdagdag ng komento Kanselahin ang sumagot