I komplekse ERP-systemer mange enheder har en hierarkisk karakternår homogene genstande står på linje træ af forfader-efterkommer forhold - dette er virksomhedens organisatoriske struktur (alle disse filialer, afdelinger og arbejdsgrupper) og kataloget over varer og arbejdsområder og salgsstedernes geografi,...
Faktisk er der ingen , hvor der ikke ville være noget hierarki som følge heraf. Men selvom du ikke arbejder "for virksomheden", kan du stadig nemt støde på hierarkiske relationer. Det er banalt, selv dit stamtræ eller plantegning af lokaler i et indkøbscenter er den samme struktur.
Der er mange måder at gemme et sådant træ i et DBMS, men i dag vil vi kun fokusere på én mulighed:
CREATE TABLE hier(
id
integer
PRIMARY KEY
, pid
integer
REFERENCES hier
, data
json
);
CREATE INDEX ON hier(pid); -- не забываем, что FK не подразумевает автосоздание индекса, в отличие от PK
Og mens du kigger ned i dybden af hierarkiet, venter det tålmodigt på at se, hvor [in]effektive dine "naive" måder at arbejde med sådan en struktur vil være.
Lad os se på typiske problemer, der opstår, deres implementering i SQL, og forsøge at forbedre deres ydeevne.
#1. Hvor dybt er kaninhullet?
Lad os for en bestemthed acceptere, at denne struktur vil afspejle afdelingernes underordning i organisationens struktur: afdelinger, divisioner, sektorer, grene, arbejdsgrupper... - hvad end du kalder dem.
Lad os først generere vores 'træ' af 10K elementer
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;Lad os starte med den enkleste opgave - at finde alle medarbejdere, der arbejder inden for en bestemt sektor, eller i form af hierarki - find alle børn af en node. Det ville også være rart at få “dybden” af efterkommeren... Alt dette kan være nødvendigt, for eksempel for at bygge en form for .
Alt ville være fint, hvis der kun er et par niveauer af disse efterkommere, og antallet er inden for et dusin, men hvis der er mere end 5 niveauer, og der allerede er snesevis af efterkommere, kan der være problemer. Lad os se på, hvordan traditionelle søgemuligheder er skrevet (og fungerer). Men lad os først bestemme, hvilke noder der vil være de mest interessante for vores forskning.
Mest "dyb" undertræer:
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}
...Mest "bred" undertræer:
...
SELECT
path[1] id
, count(*)
FROM
T
GROUP BY
1
ORDER BY
2 DESC;id | count
------------
5300 | 30
450 | 28
1239 | 27
1573 | 25
Til disse forespørgsler brugte vi den typiske rekursiv JOIN:
Selvfølgelig med denne anmodningsmodel antallet af iterationer vil være det samme som det samlede antal efterkommere (og der er flere dusin af dem), og det kan tage ret betydelige ressourcer og som følge heraf tid.
Lad os se på det "bredeste" undertræ:
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;
Som forventet fandt vi alle 30 poster. Men de brugte 60 % af den samlede tid på dette – fordi de også lavede 30 søgninger i indekset. Er det muligt at gøre mindre?
Massekorrektur efter indeks
Skal vi lave en separat indeksforespørgsel for hver node? Det viser sig, at nej - det kan vi læse af indekset bruge flere taster på én gang i et opkald via = ANY(array).
Og i hver sådan gruppe af identifikatorer kan vi tage alle de ID'er, der blev fundet i det foregående trin, ved "knudepunkter". Det vil sige, at vi ved hvert næste skridt vil søg efter alle efterkommere af et bestemt niveau på én gang.
Bare her er problemet, i rekursivt valg kan du ikke få adgang til sig selv i en indlejret forespørgsel, men vi skal på en eller anden måde kun vælge det, der blev fundet på det forrige niveau... Det viser sig, at det er umuligt at lave en indlejret forespørgsel for hele markeringen, men for dets specifikke felt er det muligt. Og dette felt kan også være et array - hvilket er det, vi skal bruge ANY.
Det lyder lidt skørt, men i diagrammet er alt enkelt.
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;
Og her er det vigtigste ikke engang vinde 1.5 gange i tid, og at vi fratrak færre buffere, da vi kun har 5 kald til indekset i stedet for 30!
En ekstra bonus er det faktum, at efter den endelige unnest vil identifikatorerne forblive sorteret efter "niveauer".
Node tegn
Den næste overvejelse, der vil hjælpe med at forbedre ydeevnen, er - "blade" kan ikke få børn, det vil sige, for dem er der slet ikke behov for at kigge "ned". I formuleringen af vores opgave betyder det, at hvis vi fulgte kæden af afdelinger og nåede frem til en medarbejder, så er der ingen grund til at kigge videre i denne gren.
Lad os gå ind i vores tabel ekstra boolean-Mark, som med det samme vil fortælle os, om netop denne indgang i vores træ er en "node" - altså om den overhovedet kan have efterkommere.
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 мс.Store! Det viser sig, at kun lidt mere end 30 % af alle træelementer har efterkommere.
Lad os nu bruge en lidt anden mekaniker - forbindelser til den rekursive del igennem LATERAL, som giver os mulighed for straks at få adgang til felterne i den rekursive "tabel" og bruge en aggregeret funktion med en filtreringsbetingelse baseret på en node for at reducere nøglesættet:
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;
Vi var i stand til at reducere endnu et indekskald og vundet mere end 2 gange i volumen korrekturlæst.
#2. Lad os gå tilbage til rødderne
Denne algoritme vil være nyttig, hvis du har brug for at indsamle optegnelser for alle elementer "op i træet", samtidig med at du bevarer information om, hvilket kildeark (og med hvilke indikatorer), der forårsagede, at det blev inkluderet i prøven - for eksempel for at generere en sammenfattende rapport med aggregering til noder.
Det følgende skal udelukkende opfattes som et proof-of-concept, da anmodningen viser sig at være meget besværlig. Men hvis det dominerer din database, bør du overveje at bruge lignende teknikker.
Lad os starte med et par enkle udsagn:
- Den samme post fra databasen Det er bedst at læse den én gang.
- Optegnelser fra databasen Det er mere effektivt at læse i batchesend alene.
Lad os nu prøve at konstruere den anmodning, vi har brug for.
Trin 1
Når vi initialiserer rekursion (hvor ville vi være uden det!), bliver vi naturligvis nødt til at trække registreringerne af selve bladene fra, baseret på sættet af indledende identifikatorer:
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
...
Hvis det virkede mærkeligt for nogen, at "sættet" er gemt som en streng og ikke et array, så er der en simpel forklaring på dette. Der er en indbygget aggregerende "limning" funktion for strenge string_agg, men ikke for arrays. Selvom hun .
Trin 2
Nu ville vi få et sæt sektions-id'er, som skal læses videre. Næsten altid vil de blive duplikeret i forskellige optegnelser af det originale sæt - så det ville vi gruppere dem, samtidig med at oplysninger om kildebladene bevares.
Men her venter os tre problemer:
- Den "subrekursive" del af forespørgslen kan ikke indeholde aggregerede funktioner med
GROUP BY. - En reference til en rekursiv "tabel" kan ikke være i en indlejret underforespørgsel.
- En anmodning i den rekursive del kan ikke indeholde en CTE.
Heldigvis er alle disse problemer ret nemme at løse. Lad os starte fra slutningen.
CTE i rekursiv del
Her så nej arbejder:
WITH RECURSIVE tree AS (
...
UNION ALL
WITH T (...)
SELECT ...
)Og så virker det, parenteserne gør forskellen!
WITH RECURSIVE tree AS (
...
UNION ALL
(
WITH T (...)
SELECT ...
)
)Indlejret forespørgsel mod en rekursiv "tabel"
Hmm... En rekursiv CTE kan ikke tilgås i en underforespørgsel. Men det kunne være inde i CTE! Og en indlejret anmodning kan allerede få adgang til denne CTE!
GROUP BY indvendig rekursion
Det er ubehageligt, men... Vi har en enkel måde at efterligne GROUP BY at bruge DISTINCT ON og vinduesfunktioner!
SELECT
(rec).pid id
, string_agg(chld::text, ',') chld
FROM
tree
WHERE
(rec).pid IS NOT NULL
GROUP BY 1 -- не работает!Og sådan fungerer det!
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 NULLNu kan vi se, hvorfor det numeriske ID blev omdannet til tekst - så de kunne slås sammen adskilt af kommaer!
Trin 3
Til finalen har vi intet tilbage:
- vi læser "sektions"-poster baseret på et sæt grupperede ID'er
- vi sammenligner de fratrukne sektioner med "sættene" af de originale ark
- "udvid" sæt-strengen vha
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;
Kilde: www.habr.com