Sudėtingose ERP sistemose daugelis subjektų turi hierarchinį pobūdįkai vienarūšiai objektai išsirikiuoja protėvių ir palikuonių santykių medis - tai yra įmonės organizacinė struktūra (visi šie filialai, skyriai ir darbo grupės), prekių katalogas ir darbo sritys, prekybos vietų geografija,...
Tiesą sakant, nėra nė vieno , kur dėl to nebūtų jokios hierarchijos. Bet net jei nedirbate „verslui“, vis tiek galite lengvai susidurti su hierarchiniais santykiais. Tai banalu, net jūsų šeimos medis ar patalpų planas prekybos centre yra vienodos struktūros.
Yra daug būdų, kaip saugoti tokį medį DBVS, tačiau šiandien mes sutelksime dėmesį tik į vieną variantą:
CREATE TABLE hier(
id
integer
PRIMARY KEY
, pid
integer
REFERENCES hier
, data
json
);
CREATE INDEX ON hier(pid); -- не забываем, что FK не подразумевает автосоздание индекса, в отличие от PK
Ir kol jūs žiūrite į hierarchijos gelmes, kantriai laukiate, kiek [ne]veiksmingi bus jūsų „naivūs“ darbo su tokia struktūra būdai.
Pažvelkime į tipines kylančias problemas, jų įgyvendinimą SQL ir pabandykime pagerinti jų veikimą.
#1. Kokio gylio yra triušio duobė?
Sutikime, kad ši struktūra atspindės padalinių pavaldumą organizacijos struktūroje: skyriai, padaliniai, sektoriai, filialai, darbo grupės... - kaip juos pavadinsi.
Pirmiausia sukurkime 10 XNUMX elementų „medį“.
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;Pradėkime nuo paprasčiausios užduoties – surasti visus darbuotojus, kurie dirba konkrečiame sektoriuje arba hierarchijos požiūriu. rasti visus mazgo vaikus. Taip pat būtų malonu gauti palikuonio „gylį“... Viso to gali prireikti, pavyzdžiui, norint pastatyti kokį nors .
Viskas būtų gerai, jei šių palikuonių yra tik pora lygių ir skaičius yra keliolikos ribose, bet jei yra daugiau nei 5 lygiai, o palikuonių jau yra dešimtys, gali kilti problemų. Pažiūrėkime, kaip rašomos (ir veikia) tradicinės paieškos parinktys. Tačiau pirmiausia išsiaiškinkime, kurie mazgai bus įdomiausi mūsų tyrimams.
Labiausiai "giliai" pomedžiai:
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}
...Labiausiai "platus" pomedžiai:
...
SELECT
path[1] id
, count(*)
FROM
T
GROUP BY
1
ORDER BY
2 DESC;id | count
------------
5300 | 30
450 | 28
1239 | 27
1573 | 25
Šioms užklausoms naudojome tipines rekursyvus JOIN:
Akivaizdu, kad su šiuo prašymo modeliu iteracijų skaičius atitiks bendrą palikuonių skaičių (o jų yra kelios dešimtys), ir tai gali pareikalauti gana didelių išteklių, o dėl to ir laiko.
Pažiūrėkime į „plačiausią“ pomedį:
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;
Kaip ir tikėtasi, radome visus 30 įrašų. Tačiau jie tam skyrė 60% viso laiko, nes jie taip pat atliko 30 paieškų indekse. Ar įmanoma padaryti mažiau?
Masinis korektūra pagal rodyklę
Ar kiekvienam mazgui reikia atlikti atskirą indekso užklausą? Pasirodo, kad ne – galime perskaityti iš rodyklės naudojant kelis klavišus vienu skambučio metu per = ANY(array).
Ir kiekvienoje tokioje identifikatorių grupėje galime paimti visus ankstesniame žingsnyje rastus ID pagal „mazgus“. Tai reiškia, kad tai padarysime kiekviename kitame žingsnyje iš karto ieškoti visų tam tikro lygio palikuonių.
Tik štai problema, rekursyvaus pasirinkimo metu negalite pasiekti savęs įdėtoje užklausoje, bet reikia kažkaip atrinkti tik tai, kas buvo rasta ankstesniame lygyje... Pasirodo, kad neįmanoma padaryti įdėtos užklausos visam pasirinkimui, bet jo konkrečiam laukui galima. Ir šis laukas taip pat gali būti masyvas – būtent tai ir turime naudoti ANY.
Tai skamba šiek tiek beprotiškai, bet diagramoje viskas paprasta.
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;
O čia svarbiausia ne net laimėti 1.5 karto per laiką, ir kad atėmėme mažiau buferių, nes turime tik 5 iškvietimus į indeksą, o ne 30!
Papildoma premija yra tai, kad po galutinio iškrovimo identifikatoriai liks išdėstyti pagal „lygius“.
Mazgo ženklas
Kitas veiksnys, padėsiantis pagerinti našumą, yra − „lapai“ negali turėti vaikų, tai yra, jiems visai nereikia žiūrėti „žemyn“. Formuluojant mūsų užduotį, tai reiškia, kad jei sekėme skyrių grandinę ir pasiekėme darbuotoją, tada nereikia ieškoti toliau šioje šakoje.
Įeikime į savo stalą papildomas boolean- laukas, kuri iš karto mums pasakys, ar šis konkretus įrašas mūsų medyje yra „mazgas“, tai yra, ar jis apskritai gali turėti palikuonių.
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 мс.Puiku! Pasirodo, tik šiek tiek daugiau nei 30% visų medžio elementų turi palikuonių.
Dabar naudokime šiek tiek kitokią mechaniką – jungtis su rekursine dalimi per LATERAL, kuri leis mums iš karto pasiekti rekursinės „lentelės“ laukus ir naudoti agregavimo funkciją su filtravimo sąlyga, pagrįsta mazgu, kad sumažintume raktų rinkinį:
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;
Mums pavyko sumažinti dar vieną indekso skambutį ir tūriu laimėjo daugiau nei 2 kartus korektūros.
#2. Grįžkime prie šaknų
Šis algoritmas bus naudingas, jei reikės rinkti visų elementų įrašus „aukštyn medyje“, išsaugant informaciją apie tai, kuris šaltinio lapas (ir su kokiais rodikliais) įtraukė jį į pavyzdį, pavyzdžiui, norint sugeneruoti suvestinę ataskaitą. su agregavimu į mazgus.
Tai, kas išdėstyta toliau, turėtų būti laikoma tik koncepcijos įrodymu, nes prašymas yra labai sudėtingas. Bet jei ji dominuoja jūsų duomenų bazėje, turėtumėte pagalvoti apie panašių metodų naudojimą.
Pradėkime nuo kelių paprastų teiginių:
- Tas pats įrašas iš duomenų bazės Geriausia jį perskaityti tik vieną kartą.
- Įrašai iš duomenų bazės Veiksmingiau skaityti partijomisnei vienas.
Dabar pabandykime sukonstruoti reikalingą užklausą.
Žingsnis 1
Akivaizdu, kad inicijuodami rekursiją (kur mes būtume be jos!) pagal pradinių identifikatorių rinkinį turėsime atimti pačių lapų įrašus:
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
...
Jei kam nors atrodė keista, kad „rinkinys“ saugomas kaip eilutė, o ne masyvas, tai yra paprastas paaiškinimas. Yra įmontuota stygų agregavimo „klijavimo“ funkcija string_agg, bet ne masyvams. Nors ji .
Žingsnis 2
Dabar gautume skyrių ID rinkinį, kurį reikės skaityti toliau. Beveik visada jie bus dubliuojami skirtinguose originalaus rinkinio įrašuose – taip ir mes sugrupuoti juos, išsaugant informaciją apie šaltinio lapus.
Bet čia mūsų laukia trys bėdos:
- „Subrekursyvinėje“ užklausos dalyje negali būti suvestinių funkcijų su
GROUP BY. - Nuorodos į rekursyvią „lentelę“ negali būti įdėtoje antrinėje užklausoje.
- Užklausoje rekursinėje dalyje negali būti CTE.
Laimei, visas šias problemas gana lengva išspręsti. Pradėkime nuo pabaigos.
CTE rekursinėje dalyje
Čia taip ne dirba:
WITH RECURSIVE tree AS (
...
UNION ALL
WITH T (...)
SELECT ...
)Ir tai veikia, skliausteliuose yra skirtumas!
WITH RECURSIVE tree AS (
...
UNION ALL
(
WITH T (...)
SELECT ...
)
)Įdėta užklausa prieš rekursyvią "lentelę"
Hmm... Rekursyvaus CTE negalima pasiekti per antrinę užklausą. Bet tai gali būti CTE viduje! Ir įdėta užklausa jau gali pasiekti šį CTE!
GROUP BY vidinė rekursija
Nemalonu, bet... Turime paprastą būdą mėgdžioti GROUP BY naudojant DISTINCT ON ir langų funkcijos!
SELECT
(rec).pid id
, string_agg(chld::text, ',') chld
FROM
tree
WHERE
(rec).pid IS NOT NULL
GROUP BY 1 -- не работает!Ir štai kaip tai veikia!
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 NULLDabar matome, kodėl skaitmeninis ID buvo paverstas tekstu – kad juos būtų galima sujungti, atskiriant kableliais!
Žingsnis 3
Finalui mums nieko neliko:
- skaitome "skyrių" įrašus pagal sugrupuotų ID rinkinį
- atimtus skyrius lyginame su pirminių lapų „rinkiniais“.
- „Išplėskite“ rinkinio eilutę naudodami
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;
Šaltinis: www.habr.com