În sistemele ERP complexe multe entităţi au o natură ierarhicăcând obiecte omogene se aliniază în arborele relațiilor strămoș-descendent - aceasta este structura organizatorică a întreprinderii (toate aceste ramuri, departamente și grupuri de lucru), catalogul de mărfuri și domeniile de lucru și geografia punctelor de vânzare,...
De fapt, nu există niciunul , unde nu ar exista nicio ierarhie ca urmare. Dar chiar dacă nu lucrați „pentru afacere”, puteți întâlni cu ușurință relații ierarhice. Este banal, chiar și arborele dvs. genealogic sau planul spațiilor dintr-un centru comercial are aceeași structură.
Există multe modalități de a stoca un astfel de arbore într-un SGBD, dar astăzi ne vom concentra pe o singură opțiune:
CREATE TABLE hier(
id
integer
PRIMARY KEY
, pid
integer
REFERENCES hier
, data
json
);
CREATE INDEX ON hier(pid); -- не забываем, что FK не подразумевает автосоздание индекса, в отличие от PK
Și în timp ce te uiți în profunzimile ierarhiei, așteaptă cu răbdare să vezi cât de [in]eficiente vor fi modurile tale „naive” de a lucra cu o astfel de structură.
Să ne uităm la problemele tipice care apar, la implementarea lor în SQL și să încercăm să le îmbunătățim performanța.
#1. Cât de adâncă este gaura iepurelui?
Să acceptăm, pentru certitudine, că această structură va reflecta subordonarea departamentelor în structura organizației: departamente, divizii, sectoare, sucursale, grupuri de lucru... - cum le-ați numi.
Mai întâi, să generăm „arborele” nostru de 10 de elemente
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;Să începem cu cea mai simplă sarcină - găsirea tuturor angajaților care lucrează într-un anumit sector sau în termeni de ierarhie - găsiți toți copiii unui nod. De asemenea, ar fi bine să obțineți „adâncimea” descendentului... Toate acestea pot fi necesare, de exemplu, pentru a construi un fel de .
Totul ar fi în regulă dacă există doar câteva nivele ale acestor descendenți și numărul este în decurs de o duzină, dar dacă există mai mult de 5 niveluri și există deja zeci de descendenți, pot apărea probleme. Să ne uităm la modul în care sunt scrise (și funcționează) opțiunile tradiționale de căutare în jos. Dar mai întâi, să stabilim care noduri vor fi cele mai interesante pentru cercetarea noastră.
Cel mai mult "adanc" subarbori:
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}
...Cel mai mult "lat" subarbori:
...
SELECT
path[1] id
, count(*)
FROM
T
GROUP BY
1
ORDER BY
2 DESC;id | count
------------
5300 | 30
450 | 28
1239 | 27
1573 | 25
Pentru aceste interogări am folosit tipicul JOIN recursiv:
Evident, cu acest model de cerere numărul de iterații se va potrivi cu numărul total de descendenți (și există câteva zeci de ele), iar acest lucru poate necesita resurse destul de semnificative și, ca urmare, timp.
Să verificăm subarborele „cel mai larg”:
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;
După cum era de așteptat, am găsit toate cele 30 de înregistrări. Dar au petrecut 60% din timpul total pe asta - pentru că au făcut și 30 de căutări în index. Este posibil să faci mai puțin?
Corectare în bloc prin index
Trebuie să facem o interogare separată de index pentru fiecare nod? Se pare că nu - putem citi din index folosind mai multe taste simultan într-un apel via = ANY(array).
Și în fiecare astfel de grup de identificatori putem lua toate ID-urile găsite în pasul anterior prin „noduri”. Adică, la fiecare pas următor vom face caută toți descendenții de un anumit nivel deodată.
Numai că aici e problema, în selecția recursivă, nu vă puteți accesa singur într-o interogare imbricată, dar trebuie să selectăm cumva doar ceea ce a fost găsit la nivelul anterior... Se dovedește că este imposibil să facem o interogare imbricată pentru întreaga selecție, dar pentru câmpul său specific este posibil. Și acest câmp poate fi, de asemenea, o matrice - care este ceea ce trebuie să folosim ANY.
Sună puțin nebunesc, dar în diagramă totul este simplu.
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 aici cel mai important lucru nu este nici măcar câștigă de 1.5 ori la timp, și că am scăzut mai puține buffere, deoarece avem doar 5 apeluri la index în loc de 30!
Un bonus suplimentar este faptul că după dezintegrarea finală, identificatorii vor rămâne ordonați pe „niveluri”.
Semnul nodului
Următorul considerent care va ajuta la îmbunătățirea performanței este − „frunzele” nu pot avea copii, adică pentru ei nu este deloc nevoie să privească „în jos”. În formularea sarcinii noastre, aceasta înseamnă că dacă am urmat lanțul de departamente și am ajuns la un angajat, atunci nu este nevoie să privim mai departe de-a lungul acestei ramuri.
Să intrăm în masa noastră adiţional boolean-camp, care ne va spune imediat dacă această intrare specială din arborele nostru este un „nod” - adică dacă poate avea descendenți.
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 мс.Grozav! Se pare că doar puțin mai mult de 30% din toate elementele arborelui au descendenți.
Acum să folosim o mecanică ușor diferită - conexiuni la partea recursivă prin LATERAL, care ne va permite să accesăm imediat câmpurile „tabelului” recursiv și să folosim o funcție de agregare cu o condiție de filtrare bazată pe un nod pentru a reduce setul de chei:
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;
Am putut reduce încă un apel de index și câștigat de mai mult de 2 ori în volum corectat.
#2. Să ne întoarcem la rădăcini
Acest algoritm va fi util dacă trebuie să colectați înregistrări pentru toate elementele „în sus”, păstrând în același timp informații despre ce foaie sursă (și cu ce indicatori) a determinat să fie inclusă în eșantion - de exemplu, pentru a genera un raport rezumat cu agregare în noduri.
Ceea ce urmează ar trebui luat doar ca o dovadă de concept, deoarece cererea se dovedește a fi foarte greoaie. Dar dacă îți domină baza de date, ar trebui să te gândești să folosești tehnici similare.
Să începem cu câteva afirmații simple:
- Aceeași înregistrare din baza de date Cel mai bine este să o citești o singură dată.
- Înregistrări din baza de date Este mai eficient să citiți în loturidecât singur.
Acum să încercăm să construim cererea de care avem nevoie.
Pasul 1
Evident, la inițializarea recursiunii (unde am fi fără ea!) va trebui să scădem înregistrările frunzelor însele pe baza setului de identificatori inițiali:
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
...
Dacă cuiva i s-a părut ciudat că „setul” este stocat ca șir și nu ca matrice, atunci există o explicație simplă pentru aceasta. Există o funcție de „lipire” de agregare încorporată pentru șiruri string_agg, dar nu pentru matrice. Deși ea .
Pasul 2
Acum vom obține un set de ID-uri de secțiune care vor trebui citite în continuare. Aproape întotdeauna vor fi duplicate în diferite înregistrări ale setului original - așa am face noi grupează-le, păstrând în același timp informațiile despre frunzele sursă.
Dar aici ne așteaptă trei necazuri:
- Partea „subrecursivă” a interogării nu poate conține funcții agregate cu
GROUP BY. - O referință la un „tabel” recursiv nu poate fi într-o subinterogare imbricată.
- O cerere din partea recursivă nu poate conține un CTE.
Din fericire, toate aceste probleme sunt destul de ușor de rezolvat. Să începem de la sfârșit.
CTE în partea recursivă
Aici nu lucru:
WITH RECURSIVE tree AS (
...
UNION ALL
WITH T (...)
SELECT ...
)Și așa funcționează, parantezele fac diferența!
WITH RECURSIVE tree AS (
...
UNION ALL
(
WITH T (...)
SELECT ...
)
)Interogare imbricată împotriva unui „tabel” recursiv
Hmm... Un CTE recursiv nu poate fi accesat într-o subinterogare. Dar ar putea fi în interiorul CTE! Și o solicitare imbricată poate accesa deja acest CTE!
GROUP BY în interiorul recursiunii
Este neplăcut, dar... Avem o modalitate simplă de a emula folosind GROUP BY DISTINCT ON și funcții ferestre!
SELECT
(rec).pid id
, string_agg(chld::text, ',') chld
FROM
tree
WHERE
(rec).pid IS NOT NULL
GROUP BY 1 -- не работает!Și așa funcționează!
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 NULLAcum vedem de ce ID-ul numeric a fost transformat în text - astfel încât acestea să poată fi unite separate prin virgule!
Pasul 3
Pentru finală nu mai avem nimic:
- citim înregistrări „secțiuni” bazate pe un set de ID-uri grupate
- comparăm secțiunile scăzute cu „seturile” foilor originale
- „extinde” șirul set folosind
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;
Sursa: www.habr.com