V kompleksnih sistemih ERP številne entitete imajo hierarhično naravoko se homogeni predmeti postavijo v vrsto drevo odnosov prednik-potomec - to je organizacijska struktura podjetja (vse te podružnice, oddelki in delovne skupine) in katalog blaga ter področja dela in geografija prodajnih mest, ...
Pravzaprav ga ni , kjer posledično ne bi bilo hierarhije. Toda tudi če ne delate "za posel", lahko še vedno zlahka naletite na hierarhična razmerja. To je banalno, tudi vaše družinsko drevo ali tloris prostorov v nakupovalnem središču je enake strukture.
Obstaja veliko načinov za shranjevanje takšnega drevesa v DBMS, vendar se bomo danes osredotočili le na eno možnost:
CREATE TABLE hier(
id
integer
PRIMARY KEY
, pid
integer
REFERENCES hier
, data
json
);
CREATE INDEX ON hier(pid); -- не забываем, что FK не подразумевает автосоздание индекса, в отличие от PK
In medtem ko vi zrete v globino hierarhije, ta potrpežljivo čaka, kako [ne]učinkoviti bodo vaši »naivni« načini dela s tako strukturo.
Oglejmo si tipične težave, ki se pojavljajo, njihovo implementacijo v SQL in poskusimo izboljšati njihovo delovanje.
#1. Kako globoka je zajčja luknja?
Sprejmimo za določeno, da bo ta struktura odražala podrejenost oddelkov v strukturi organizacije: oddelkov, divizij, sektorjev, podružnic, delovnih skupin ... - kakor koli jih imenujete.
Najprej ustvarimo naše "drevo" 10K elementov
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čnimo z najpreprostejšo nalogo – iskanjem vseh zaposlenih, ki delajo v določenem sektorju ali v smislu hierarhije – najti vse otroke vozlišča. Prav tako bi bilo lepo pridobiti "globino" potomca ... Vse to bo morda potrebno, na primer, za izgradnjo neke vrste .
Vse bi bilo v redu, če je le nekaj ravni teh potomcev in je število znotraj ducata, če pa je več kot 5 stopenj in je že na desetine potomcev, lahko pride do težav. Poglejmo, kako so napisane (in delujejo) tradicionalne možnosti iskanja navzdol po drevesu. Najprej pa ugotovimo, katera vozlišča bodo najbolj zanimiva za naše raziskave.
Največ "globoko" poddrevesa:
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}
...Največ "širok" poddrevesa:
...
SELECT
path[1] id
, count(*)
FROM
T
GROUP BY
1
ORDER BY
2 DESC;id | count
------------
5300 | 30
450 | 28
1239 | 27
1573 | 25
Za te poizvedbe smo uporabili tipično rekurzivni JOIN:
Očitno s tem modelom zahteve število ponovitev se bo ujemalo s skupnim številom potomcev (in teh je več deset), kar lahko zahteva precejšnja sredstva in posledično čas.
Preverimo "najširše" poddrevo:
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;
Po pričakovanjih smo našli vseh 30 zapisov. A za to so porabili 60 % celotnega časa – ker so opravili tudi 30 iskanj v indeksu. Je mogoče narediti manj?
Množično lektoriranje po indeksu
Ali moramo narediti ločeno indeksno poizvedbo za vsako vozlišče? Izkazalo se je, da ne - lahko beremo iz kazala uporabo več tipk hkrati v enem klicu s pomočjo = ANY(array).
In v vsaki takšni skupini identifikatorjev lahko vzamemo vse ID-je, ki jih najdemo v prejšnjem koraku po "vozliščih". Se pravi, pri vsakem naslednjem koraku bomo iskanje vseh potomcev določene stopnje hkrati.
Samo tukaj je problem, pri rekurzivnem izboru ne morete dostopati do njega v ugnezdeni poizvedbi, vendar moramo nekako izbrati samo tisto, kar je bilo najdeno na prejšnji ravni ... Izkazalo se je, da je nemogoče narediti ugnezdeno poizvedbo za celotno izbiro, za njeno specifično polje pa je to mogoče. In to polje je lahko tudi niz - kar moramo uporabiti ANY.
Sliši se malce noro, a v diagramu je vse preprosto.
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;
In tukaj najpomembnejše ni celo zmagati 1.5-krat v časuin da smo odšteli manj medpomnilnikov, saj imamo samo 5 klicev indeksa namesto 30!
Dodaten bonus je dejstvo, da bodo identifikatorji po končnem razgnezdenju ostali razvrščeni po "nivojih".
Znak vozlišča
Naslednji dejavnik, ki bo pomagal izboljšati učinkovitost, je − "listi" ne morejo imeti otrok, to pomeni, da jim sploh ni treba gledati »dol«. V formulaciji naše naloge to pomeni, da če smo sledili verigi oddelkov in prišli do zaposlenega, potem ni treba iskati naprej po tej veji.
Vstopimo v našo mizo dodatno boolean-polje, ki nam bo takoj povedal, ali je ta določen vnos v našem drevesu "vozlišče" - torej ali ima sploh lahko potomce.
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 мс.Super! Izkazalo se je, da ima le nekaj več kot 30% vseh drevesnih elementov potomce.
Zdaj pa uporabimo nekoliko drugačno mehaniko - povezave z rekurzivnim delom skozi LATERAL, ki nam bo omogočil takojšen dostop do polj rekurzivne »tabele« in uporabo agregatne funkcije s pogojem filtriranja, ki temelji na vozlišču, da zmanjšamo nabor ključev:
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;
Uspelo nam je zmanjšati še en indeksni klic in zmagal več kot 2-krat v količini lektoriran.
#2. Vrnimo se h koreninam
Ta algoritem bo uporaben, če boste morali zbrati zapise za vse elemente "navzgor po drevesu", hkrati pa obdržati informacije o tem, kateri izvorni list (in s kakšnimi indikatorji) je povzročil vključitev v vzorec - na primer za ustvarjanje povzetka poročila z združevanjem v vozlišča.
Kar sledi, je treba jemati izključno kot dokaz koncepta, saj se je zahteva izkazala za zelo okorno. Če pa prevladuje v vaši bazi podatkov, razmislite o uporabi podobnih tehnik.
Začnimo z nekaj preprostimi izjavami:
- Isti zapis iz baze podatkov Najbolje ga je prebrati samo enkrat.
- Zapisi iz baze Bolj učinkovito je brati v serijahkot sam.
Zdaj pa poskusimo sestaviti zahtevo, ki jo potrebujemo.
Korak 1
Očitno bomo morali pri inicializaciji rekurzije (kje bi bili brez nje!) odšteti zapise samih listov na podlagi niza začetnih identifikatorjev:
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
...
Če se je komu zdelo nenavadno, da je "nabor" shranjen kot niz in ne matrika, potem za to obstaja preprosta razlaga. Obstaja vgrajena funkcija združevanja "lepljenje" za nize string_agg, vendar ne za polja. Čeprav ona .
Korak 2
Zdaj bi dobili nabor ID-jev odsekov, ki jih bo treba nadalje prebrati. Skoraj vedno bodo podvojeni v različnih zapisih izvirnega kompleta - tako bi tudi mi jih združite, pri čemer se ohranijo informacije o izvornih listih.
Toda tukaj nas čakajo tri težave:
- "Subrekurzivni" del poizvedbe ne more vsebovati agregatnih funkcij z
GROUP BY. - Sklic na rekurzivno "tabelo" ne more biti v ugnezdeni podpoizvedbi.
- Zahteva v rekurzivnem delu ne more vsebovati CTE.
Na srečo je vsem tem težavam precej enostavno zaobiti. Začnimo od konca.
CTE v rekurzivnem delu
Tukaj tako ne dela:
WITH RECURSIVE tree AS (
...
UNION ALL
WITH T (...)
SELECT ...
)In tako deluje, oklepaji naredijo razliko!
WITH RECURSIVE tree AS (
...
UNION ALL
(
WITH T (...)
SELECT ...
)
)Ugnezdena poizvedba proti rekurzivni "tabeli"
Hmm ... Do rekurzivnega CTE ni mogoče dostopati v podpoizvedbi. Lahko pa je znotraj CTE! In ugnezdena zahteva že lahko dostopa do tega CTE!
GROUP BY znotraj rekurzije
Neprijetno je, toda ... Imamo preprost način za posnemanje GROUP BY z uporabo DISTINCT ON in okenske funkcije!
SELECT
(rec).pid id
, string_agg(chld::text, ',') chld
FROM
tree
WHERE
(rec).pid IS NOT NULL
GROUP BY 1 -- не работает!In tako to deluje!
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 NULLZdaj vidimo, zakaj je bil številčni ID spremenjen v besedilo – da bi ju lahko združili in ločevali z vejicami!
Korak 3
Za finale nam ne preostane nič:
- beremo zapise »sekcije« na podlagi niza združenih ID-jev
- odštete odseke primerjamo z »nizi« originalnih listov
- »razširite« nastavljeni niz z uporabo
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;
Vir: www.habr.com