V komplexných ERP systémoch mnohé entity majú hierarchickú povahukeď sa homogénne predmety zoradia strom vzťahov predok-potomok - ide o organizačnú štruktúru podniku (všetky tieto odvetvia, oddelenia a pracovné skupiny), katalóg tovaru a oblasti práce a geografiu predajných miest,...
V skutočnosti žiadna neexistuje , kde by v dôsledku toho neexistovala žiadna hierarchia. Ale aj keď nepracujete „pre firmu“, stále sa môžete ľahko stretnúť s hierarchickými vzťahmi. Je to banálne, dokonca aj váš rodokmeň alebo pôdorys priestorov v nákupnom centre má rovnakú štruktúru.
Existuje mnoho spôsobov, ako uložiť takýto strom v DBMS, ale dnes sa zameriame len na jednu možnosť:
CREATE TABLE hier(
id
integer
PRIMARY KEY
, pid
integer
REFERENCES hier
, data
json
);
CREATE INDEX ON hier(pid); -- не забываем, что FK не подразумевает автосоздание индекса, в отличие от PK
A zatiaľ čo vy nazeráte do hlbín hierarchie, ona trpezlivo čaká, ako [ne]efektívne budú vaše „naivné“ spôsoby práce s takouto štruktúrou.
Pozrime sa na typické problémy, ktoré vznikajú, ich implementáciu v SQL a pokúsme sa zlepšiť ich výkon.
#1. Aká hlboká je králičia nora?
Pripusťme pre istotu, že táto štruktúra bude odrážať podriadenosť oddelení v štruktúre organizácie: oddelenia, divízie, sektory, pobočky, pracovné skupiny... - akokoľvek ich nazvete.
Najprv vygenerujme náš „strom“ 10 XNUMX prvkov
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;Začnime najjednoduchšou úlohou - nájsť všetkých zamestnancov, ktorí pracujú v konkrétnom sektore alebo z hľadiska hierarchie - nájsť všetky deti uzla. Tiež by bolo fajn dostať „hĺbku“ potomka... To všetko môže byť potrebné napríklad na vybudovanie nejakého .
Všetko by bolo v poriadku, ak existuje iba niekoľko úrovní týchto potomkov a počet je v rámci tucta, ale ak existuje viac ako 5 úrovní a už existujú desiatky potomkov, môžu nastať problémy. Pozrime sa na to, ako sú napísané (a fungujú) tradičné možnosti vyhľadávania podľa nižšieho stromu. Najprv však určme, ktoré uzly budú pre náš výskum najzaujímavejšie.
Najviac "hlboký" podstromy:
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}
...Najviac "široký" podstromy:
...
SELECT
path[1] id
, count(*)
FROM
T
GROUP BY
1
ORDER BY
2 DESC;id | count
------------
5300 | 30
450 | 28
1239 | 27
1573 | 25
Pre tieto otázky sme použili typické rekurzívne JOIN:
Samozrejme, s týmto modelom požiadavky počet iterácií sa bude zhodovať s celkovým počtom potomkov (a je ich niekoľko desiatok), čo si môže vyžadovať značné prostriedky a v dôsledku toho aj čas.
Pozrime sa na „najširší“ podstrom:
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;
Podľa očakávania sme našli všetkých 30 záznamov. Ale venovali tomu 60 % celkového času – pretože v indexe vykonali aj 30 vyhľadávaní. Je možné urobiť menej?
Hromadná korektúra podľa indexu
Musíme vytvoriť samostatný indexový dotaz pre každý uzol? Ukazuje sa, že nie - môžeme čítať z indexu pomocou niekoľkých tlačidiel naraz v rámci jedného hovoru skrz = ANY(array).
A v každej takejto skupine identifikátorov môžeme zobrať všetky ID nájdené v predchádzajúcom kroku podľa „uzlov“. To znamená, že pri každom ďalšom kroku budeme hľadať všetkých potomkov určitej úrovne naraz.
Len tu je problém, v rekurzívnom výbere nemôžete pristupovať k sebe samému vo vnorenom dotaze, ale musíme nejakým spôsobom vybrať len to, čo sa našlo na predchádzajúcej úrovni... Ukazuje sa, že nie je možné urobiť vnorený dotaz pre celý výber, ale pre jeho konkrétne pole je to možné. A toto pole môže byť tiež pole - čo musíme použiť ANY.
Znie to trochu bláznivo, ale v diagrame je všetko jednoduché.
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;
A tu najdôležitejšia vec nie je rovnomerná vyhrať 1.5 krát v časea že sme odpočítali menej vyrovnávacích pamätí, pretože máme len 5 volaní indexu namiesto 30!
Dodatočným bonusom je skutočnosť, že po konečnom rozpojení zostanú identifikátory zoradené podľa „úrovní“.
Znak uzla
Ďalšou úvahou, ktorá pomôže zlepšiť výkon, je − "listy" nemôžu mať deti, to znamená, že pre nich vôbec nie je potrebné pozerať sa „dole“. Vo formulácii našej úlohy to znamená, že ak by sme sledovali reťazec oddelení a dostali sme sa k zamestnancovi, nie je potrebné hľadať ďalej po tomto odvetví.
Vstúpme do nášho stola dodatočné boolean-lúka, čo nám hneď povie, či je tento konkrétny záznam v našom strome “uzol” – teda či vôbec môže mať potomkov.
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 мс.Skvelé! Ukazuje sa, že len o niečo viac ako 30 % všetkých prvkov stromu má potomkov.
Teraz použijeme trochu inú mechaniku - spojenie s rekurzívnou časťou cez LATERAL, čo nám umožní okamžite pristupovať k poliam rekurzívnej „tabuľky“ a použiť agregovanú funkciu s filtračnou podmienkou založenou na uzle na zníženie sady kľúčov:
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;
Podarilo sa nám znížiť ďalšie volanie indexu a vyhral viac ako 2 krát v objeme korektúry.
#2. Vráťme sa ku koreňom
Tento algoritmus bude užitočný, ak potrebujete zhromaždiť záznamy pre všetky prvky „v strome“ a zároveň zachovať informácie o tom, ktorý zdrojový hárok (a s akými indikátormi) spôsobil jeho zaradenie do vzorky – napríklad na vytvorenie súhrnnej správy. s agregáciou do uzlov.
To, čo nasleduje, by sa malo brať výlučne ako dôkaz koncepcie, pretože požiadavka sa ukazuje ako veľmi ťažkopádna. Ak však dominuje vo vašej databáze, mali by ste premýšľať o použití podobných techník.
Začnime niekoľkými jednoduchými tvrdeniami:
- Rovnaký záznam z databázy Najlepšie je prečítať si to raz.
- Záznamy z databázy Je efektívnejšie čítať v dávkachnež sám.
Teraz sa pokúsme zostaviť požiadavku, ktorú potrebujeme.
Krok 1
Je zrejmé, že pri inicializácii rekurzie (kde by sme bez nej boli!) budeme musieť odpočítať záznamy samotných listov na základe sady počiatočných identifikátorov:
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
...
Ak sa niekomu zdalo divné, že „množina“ je uložená ako reťazec a nie ako pole, potom existuje jednoduché vysvetlenie. Pre struny je zabudovaná agregačná funkcia „lepenia“. string_agg, ale nie pre polia. Hoci ona .
Krok 2
Teraz by sme dostali sadu ID sekcií, ktoré bude potrebné čítať ďalej. Takmer vždy budú duplikované v rôznych záznamoch pôvodného súboru - tak by sme to urobili zoskupiť ich, pričom sa zachovajú informácie o zdrojových listoch.
Ale tu nás čakajú tri problémy:
- "Subrekurzívna" časť dotazu nemôže obsahovať agregačné funkcie s
GROUP BY. - Odkaz na rekurzívnu „tabuľku“ nemôže byť vo vnorenom poddotaze.
- Požiadavka v rekurzívnej časti nemôže obsahovať CTE.
Našťastie sa všetky tieto problémy dajú celkom ľahko obísť. Začnime od konca.
CTE v rekurzívnej časti
Páči sa ti to nie pracuje:
WITH RECURSIVE tree AS (
...
UNION ALL
WITH T (...)
SELECT ...
)A tak to funguje, zátvorky robia rozdiel!
WITH RECURSIVE tree AS (
...
UNION ALL
(
WITH T (...)
SELECT ...
)
)Vnorený dotaz proti rekurzívnej "tabuľke"
Hmm... K rekurzívnemu CTE nie je možné pristupovať v poddotaze. Ale mohlo by to byť vnútri CTE! A vnorená požiadavka už môže pristupovať k tomuto CTE!
GROUP BY vnútorná rekurzia
Je to nepríjemné, ale... Máme jednoduchý spôsob, ako napodobniť GROUP BY pomocou DISTINCT ON a funkcie okien!
SELECT
(rec).pid id
, string_agg(chld::text, ',') chld
FROM
tree
WHERE
(rec).pid IS NOT NULL
GROUP BY 1 -- не работает!A takto to funguje!
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 NULLTeraz vidíme, prečo sa číselné ID zmenilo na text - aby sa dali spojiť oddelené čiarkami!
Krok 3
Na finále nám nezostáva nič:
- čítame záznamy „sekcií“ na základe súboru zoskupených ID
- porovnávame odčítané časti so „súbormi“ pôvodných listov
- „rozbaľte“ reťazec nastavenia pomocou
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;
Zdroj: hab.com