U složenim ERP sistemima mnogi entiteti imaju hijerarhijsku prirodukada se homogeni objekti poredaju stablo odnosa predaka i potomaka - ovo je organizaciona struktura preduzeća (sve ove grane, odjeljenja i radne grupe), i katalog robe, i područja rada, i geografija prodajnih mjesta,...
U stvari, ne postoji , gdje kao rezultat ne bi bilo nikakve hijerarhije. Ali čak i ako ne radite „za posao“, i dalje možete lako naići na hijerarhijske odnose. Otrcano je, čak je i vaše porodično stablo ili tlocrt prostorija u tržnom centru ista struktura.
Postoji mnogo načina da se takvo stablo pohrani u DBMS, ali danas ćemo se fokusirati na samo jednu opciju:
CREATE TABLE hier(
id
integer
PRIMARY KEY
, pid
integer
REFERENCES hier
, data
json
);
CREATE INDEX ON hier(pid); -- не забываем, что FK не подразумевает автосоздание индекса, в отличие от PK
I dok vi zavirujete u dubinu hijerarhije, ona strpljivo čeka da vidi koliko će vaši „naivni“ načini rada sa takvom strukturom biti [ne]djelotvorni.
Pogledajmo tipične probleme koji se javljaju, njihovu implementaciju u SQL-u i pokušajmo poboljšati njihove performanse.
#1. Koliko je duboka zečja rupa?
Definitivno prihvatimo da će ova struktura odražavati subordinaciju odjela u strukturi organizacije: odjeljenja, odjeljenja, sektori, filijale, radne grupe... - kako god ih nazvali.
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 zaposlenih koji rade u okviru određenog sektora, ili u smislu hijerarhije - pronaći svu djecu č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 nivoa ovih potomaka i da je broj unutar desetak, ali ako ima više od 5 nivoa, a već ima desetine potomaka, može doći do problema. Pogledajmo kako se pišu (i rade) tradicionalne opcije pretraživanja na nižem stablu. Ali prvo, hajde da 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 "široko" 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čno rekurzivni JOIN:
Očigledno, sa ovim modelom zahtjeva broj iteracija će odgovarati ukupnom broju potomaka (a ima ih nekoliko desetina), a to može oduzeti prilično značajna sredstva, a kao rezultat 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 ovo su potrošili 60% ukupnog vremena - jer su izvršili i 30 pretraživanja u indeksu. Da li je moguće učiniti manje?
Skupna lektura po indeksu
Da li trebamo napraviti poseban indeksni upit za svaki čvor? Ispada da ne - možemo čitati iz indeksa koristeći nekoliko tastera 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 po „čvorovima“. Odnosno, na svakom sledećem koraku ćemo tražiti sve potomke određenog nivoa odjednom.
Samo, evo problema, u rekurzivnom odabiru, ne možete sebi pristupiti u ugniježđenom upitu, ali moramo nekako odabrati samo ono što je pronađeno na prethodnom nivou... Ispada da je nemoguće napraviti ugniježđeni upit za cijelu selekciju, ali je za njeno specifično polje moguće. A ovo polje može biti i 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žnija stvar nije ravnomjerna pobijediti 1.5 puta na vrijeme, i da smo oduzeli manje bafera, pošto imamo samo 5 poziva indeksu umjesto 30!
Dodatni bonus je činjenica da će nakon konačnog unnest-a, identifikatori ostati poredani po “nivoima”.
Znak čvora
Sljedeće razmatranje koje će pomoći u poboljšanju performansi je − "lišće" ne može imati djecu, odnosno za njih uopšte nema potrebe da gledaju „dole“. U formulaciji našeg zadatka, to znači da ako smo pratili lanac odjela i došli do zaposlenika, onda nema potrebe dalje tražiti ovu granu.
Uđimo u našu tabelu dodatno 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 мс.Odlično! Ispostavilo se da samo nešto više od 30% svih elemenata stabla ima potomke.
Sada koristimo malo drugačiju mehaniku - veze sa rekurzivnim dijelom kroz LATERAL, što će nam omogućiti da odmah pristupimo poljima rekurzivne „tablice“ i koristimo agregatnu funkciju sa uslovom filtriranja na osnovu čvora da smanjimo skup 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 poziv indeksa i osvojio više od 2 puta po obimu lektorisanje.
#2. Vratimo se korijenima
Ovaj algoritam će biti koristan ako trebate prikupiti zapise za sve elemente „gore po stablu“, uz zadržavanje informacija o tome koji izvorni list (i s kojim indikatorima) je doveo do toga da bude uključen u uzorak - na primjer, za generiranje sažetog izvještaja sa agregacijom u čvorove.
Ono što slijedi treba uzeti samo kao dokaz koncepta, jer se zahtjev ispostavlja vrlo glomazan. 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 je da ga pročitate samo jednom.
- Zapisi iz baze podataka Efikasnije je čitati u serijamanego sama.
Pokušajmo sada konstruirati zahtjev koji nam je potreban.
korak 1
Očigledno, prilikom inicijalizacije rekurzije (gdje bismo bili bez nje!) morat ćemo oduzeti zapise samih listova na osnovu 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 je nekome izgledalo čudno da je "set" pohranjen kao string, a ne niz, onda za to postoji jednostavno objašnjenje. Postoji ugrađena agregirajuća funkcija “lijepljenja” za nizove string_agg, ali ne i za nizove. Iako ona .
korak 2
Sada bismo dobili skup ID-ova odjeljka koje će trebati dalje čitati. Gotovo uvijek će biti duplirane u različitim zapisima originalnog skupa - tako bismo i mi grupisati ih, uz očuvanje informacija o izvornim listovima.
Ali ovdje nas čekaju tri nevolje:
- "Subrekurzivni" dio upita ne može sadržavati agregatne funkcije sa
GROUP BY. - Referenca na rekurzivnu "tabelu" ne može biti u ugniježđenom potupitu.
- Zahtjev u rekurzivnom dijelu ne može sadržavati CTE.
Srećom, sve ove probleme je prilično lako zaobići. Počnimo od kraja.
CTE u rekurzivnom dijelu
Evo tako ne radi:
WITH RECURSIVE tree AS (
...
UNION ALL
WITH T (...)
SELECT ...
)I tako funkcionira, zagrade čine razliku!
WITH RECURSIVE tree AS (
...
UNION ALL
(
WITH T (...)
SELECT ...
)
)Ugniježđeni upit prema rekurzivnoj "tablici"
Hmm... Rekurzivnom CTE-u se ne može pristupiti u potupitu. Ali može biti unutar CTE! A ugniježđeni zahtjev već može pristupiti ovom CTE-u!
GROUP BY unutarnja rekurzija
Neprijatno je, ali... Imamo jednostavan način da oponašamo GROUP BY koristeći 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 ovako 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 brojčani ID pretvoren u tekst - tako da se mogu spojiti zajedno razdvojeni zarezima!
korak 3
Za finale nam ne preostaje ništa:
- čitamo zapise "sekcije" na osnovu skupa grupisanih ID-ova
- upoređujemo oduzete dijelove sa “skupovima” originalnih listova
- “proširi” set-string koristeći
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