U složenim ERP sustavima mnogi entiteti imaju hijerarhijsku prirodukada se homogeni predmeti poredaju stablo odnosa preci-potomci - ovo je i organizacijska struktura poduzeća (sve te podružnice, odjela i radne grupe), i katalog robe, i područja rada, i geografija prodajnih mjesta,...
Zapravo, nema ga , gdje kao rezultat ne bi bilo nikakve hijerarhije. Ali čak i ako ne radite "za posao", još uvijek možete lako naići na hijerarhijske odnose. Otrcano je, čak je i vaše obiteljsko stablo ili tlocrt prostora u trgovačkom centru iste strukture.
Postoji mnogo načina za pohranjivanje takvog stabla u DBMS, ali danas ćemo se fokusirati samo na jednu opciju:
CREATE TABLE hier(
id
integer
PRIMARY KEY
, pid
integer
REFERENCES hier
, data
json
);
CREATE INDEX ON hier(pid); -- не забываем, что FK не подразумевает автосоздание индекса, в отличие от PK
I dok virite u dubinu hijerarhije, ona strpljivo čeka da vidi koliko će vaši “naivni” načini rada s takvom strukturom biti [ne]učinkoviti.
Pogledajmo tipične probleme koji se pojavljuju, njihovu implementaciju u SQL i pokušajmo poboljšati njihovu izvedbu.
#1. Koliko je duboka zečja rupa?
Prihvatimo, definitivno, da će ova struktura odražavati subordinaciju odjela u strukturi organizacije: odjela, odjela, sektora, ogranaka, radnih grupa... - kako god ih zvali.
Prvo, generirajmo naše 'stablo' od 10K elemenata
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;Počnimo s najjednostavnijim zadatkom - pronalaženjem svih zaposlenika koji rade unutar određenog sektora, ili u smislu hijerarhije - pronaći sve potomke čvora. Također bi bilo lijepo dobiti "dubinu" potomka ... Sve ovo može biti potrebno, na primjer, za izgradnju neke vrste .
Sve bi bilo u redu da postoji samo nekoliko razina tih potomaka i da je broj unutar desetak, ali ako ima više od 5 razina, a već postoje deseci potomaka, može doći do problema. Pogledajmo kako su napisane (i rade) tradicionalne opcije pretraživanja nizvodno. Ali prvo, odredimo koji će čvorovi biti najzanimljiviji za naše istraživanje.
Najviše "duboko" podstabla:
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}
...Najviše "širok" podstabla:
...
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 ove upite koristili smo tipične rekurzivni JOIN:
Očito, s ovim modelom zahtjeva broj ponavljanja bit će jednak ukupnom broju potomaka (a ima ih nekoliko desetaka), a to može oduzeti prilično značajna sredstva, a posljedično i vrijeme.
Provjerimo "najšire" podstablo:
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;
Očekivano, pronašli smo svih 30 zapisa. Ali na to su potrošili 60% ukupnog vremena – jer su također izvršili 30 pretraga u indeksu. Je li moguće učiniti manje?
Skupna lektura po indeksu
Moramo li napraviti zaseban indeksni upit za svaki čvor? Ispostavilo se da ne - čitamo iz indeksa koristeći nekoliko tipki odjednom u jednom pozivu uz pomoć = ANY(array).
I u svakoj takvoj grupi identifikatora možemo uzeti sve ID-ove pronađene u prethodnom koraku prema "čvorovima". Odnosno, na svakom sljedećem koraku ćemo traženje svih potomaka određene razine odjednom.
Samo, evo problema, u rekurzivnom odabiru, ne možete pristupiti samom sebi u ugniježđenom upitu, ali treba nekako odabrati samo ono što je pronađeno na prethodnoj razini... Ispada da je nemoguće napraviti ugniježđeni upit za cijeli odabir, ali za njegovo specifično polje je moguće. A ovo polje također može biti niz - što je ono što trebamo koristiti ANY.
Zvuči pomalo ludo, ali na dijagramu je sve jednostavno.
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;
I ovdje najvažnije nije čak pobijediti 1.5 puta u vremenu, i da smo oduzeli manje međuspremnika, budući da imamo samo 5 poziva na indeks umjesto 30!
Dodatni bonus je činjenica da će nakon konačnog unistiranja, identifikatori ostati poredani po "razinama".
Znak čvora
Sljedeće razmatranje koje će pomoći u poboljšanju performansi je − "lišće" ne može imati djece, odnosno za njih uopće nema potrebe gledati “dolje”. U formulaciji našeg zadatka to znači da ako smo pratili lanac odjela i došli do zaposlenika, onda nema potrebe tražiti dalje duž ove grane.
Uđimo u naš stol dodatni boolean-polje, što će nam odmah reći da li je ovaj određeni unos u našem stablu “čvor” - odnosno može li uopće imati potomke.
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 мс.Sjajno! Ispostavilo se da samo nešto više od 30% svih elemenata stabla ima potomke.
Sada upotrijebimo nešto drugačiju mehaniku - veze s rekurzivnim dijelom putem LATERAL, što će nam omogućiti trenutni pristup poljima rekurzivne "tablice" i korištenje agregatne funkcije s uvjetom filtriranja na temelju čvora za smanjenje skupa ključeva:
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;
Uspjeli smo smanjiti još jedan indeksni poziv i osvojio više od 2 puta u obimu lektoriran.
#2. Vratimo se korijenima
Ovaj algoritam bit će koristan ako trebate prikupiti zapise za sve elemente "gore na stablu", dok zadržavate informacije o tome koji je izvorni list (i s kojim pokazateljima) uzrokovao njegovo uključivanje u uzorak - na primjer, za generiranje sažetog izvješća s agregacijom u čvorove.
Ono što slijedi treba uzeti isključivo kao dokaz koncepta, budući da se zahtjev pokazao vrlo glomaznim. Ali ako dominira vašom bazom podataka, trebali biste razmisliti o korištenju sličnih tehnika.
Počnimo s nekoliko jednostavnih izjava:
- Isti zapis iz baze podataka Najbolje ga je pročitati samo jednom.
- Zapisi iz baze podataka Učinkovitije je čitati u serijamanego sama.
Sada pokušajmo konstruirati zahtjev koji nam je potreban.
Korak 1
Očito, kada inicijaliziramo rekurziju (gdje bismo bez nje!) morat ćemo oduzeti zapise samih listova na temelju skupa početnih identifikatora:
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
...
Ako se nekome činilo čudnim da je "set" pohranjen kao niz, a ne niz, onda za to postoji jednostavno objašnjenje. Postoji ugrađena funkcija agregiranja "lijepljenja" za nizove string_agg, ali ne i za nizove. Iako ona .
Korak 2
Sada bismo dobili skup ID-ova sekcija koje će trebati dalje čitati. Gotovo uvijek će biti duplicirani u različitim zapisima izvornog skupa - tako bismo i mi grupirati ih, uz očuvanje informacija o izvornim listovima.
Ali ovdje nas čekaju tri nevolje:
- "Subrekurzivni" dio upita ne može sadržavati agregatne funkcije s
GROUP BY. - Referenca na rekurzivnu "tablicu" ne može biti u ugniježđenom podupitu.
- Zahtjev u rekurzivnom dijelu ne može sadržavati CTE.
Srećom, sve ove probleme je prilično lako riješiti. Krenimo od kraja.
CTE u rekurzivnom dijelu
Ovdje tako ne radi:
WITH RECURSIVE tree AS (
...
UNION ALL
WITH T (...)
SELECT ...
)I tako to funkcionira, zagrade čine razliku!
WITH RECURSIVE tree AS (
...
UNION ALL
(
WITH T (...)
SELECT ...
)
)Ugniježđeni upit prema rekurzivnoj "tablici"
Hmm... Rekurzivnom CTE-u nije moguće pristupiti u podupitu. Ali moglo bi biti unutar CTE-a! A ugniježđeni zahtjev već može pristupiti ovom CTE-u!
GROUP BY unutar rekurzije
Neugodno je, ali... Imamo jednostavan način da emuliramo GROUP BY pomoću DISTINCT ON i funkcije prozora!
SELECT
(rec).pid id
, string_agg(chld::text, ',') chld
FROM
tree
WHERE
(rec).pid IS NOT NULL
GROUP BY 1 -- не работает!I evo kako to funkcionira!
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 NULLSada vidimo zašto je numerički ID pretvoren u tekst - kako bi se mogli spojiti razdvojeni zarezima!
Korak 3
Za finale nam ne preostaje ništa:
- čitamo zapise “sekcije” na temelju skupa grupiranih ID-ova
- uspoređujemo oduzete dijelove s "setovima" izvornih listova
- "proširite" set-string pomoću
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;
Izvor: www.habr.com