I komplekse ERP-systemer mange enheter har en hierarkisk naturnår homogene gjenstander står på linje tre av forfedre-etterkommer-forhold - dette er organisasjonsstrukturen til bedriften (alle disse grenene, avdelingene og arbeidsgruppene), og katalogen over varer og arbeidsområder, og geografien til salgsstedene,...
Faktisk er det ingen , hvor det ikke ville være noe hierarki som et resultat. Men selv om du ikke jobber "for bedriften", kan du fortsatt lett møte hierarkiske relasjoner. Det er banalt, til og med slektstreet eller plantegningen av lokaler i et kjøpesenter er den samme strukturen.
Det er mange måter å lagre et slikt tre i en DBMS, men i dag vil vi fokusere på bare ett alternativ:
CREATE TABLE hier(
id
integer
PRIMARY KEY
, pid
integer
REFERENCES hier
, data
json
);
CREATE INDEX ON hier(pid); -- не забываем, что FK не подразумевает автосоздание индекса, в отличие от PK
Og mens du ser ned i dypet av hierarkiet, venter den tålmodig på å se hvor [in]effektive dine "naive" måter å jobbe med en slik struktur på vil være.
La oss se på typiske problemer som oppstår, deres implementering i SQL, og prøve å forbedre ytelsen deres.
#1. Hvor dypt er kaninhullet?
La oss, for bestemthetens skyld, akseptere at denne strukturen vil reflektere underordningen av avdelinger i strukturen til organisasjonen: avdelinger, divisjoner, sektorer, grener, arbeidsgrupper... - hva du enn kaller dem.
Først, la oss generere vårt "tre" med 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;La oss starte med den enkleste oppgaven - å finne alle ansatte som jobber innenfor en bestemt sektor, eller i form av hierarki - finn alle barn til en node. Det ville også vært fint å få "dybden" til etterkommeren... Alt dette kan være nødvendig, for eksempel for å bygge en slags .
Alt ville være bra hvis det bare er et par nivåer av disse etterkommerne og antallet er innenfor et dusin, men hvis det er mer enn 5 nivåer, og det allerede er dusinvis av etterkommere, kan det være problemer. La oss se på hvordan tradisjonelle søkealternativer er skrevet (og fungerer). Men først, la oss bestemme hvilke noder som vil være mest interessante for vår forskning.
Mest "dyp" undertrær:
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ær:
...
SELECT
path[1] id
, count(*)
FROM
T
GROUP BY
1
ORDER BY
2 DESC;id | count
------------
5300 | 30
450 | 28
1239 | 27
1573 | 25
For disse spørsmålene brukte vi den typiske rekursiv JOIN:
Tydeligvis med denne forespørselsmodellen antall iterasjoner vil samsvare med det totale antallet etterkommere (og det er flere dusin av dem), og dette kan ta ganske betydelige ressurser, og som et resultat, tid.
La oss sjekke det "bredeste" undertreet:
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 fant vi alle de 30 postene. Men de brukte 60 % av den totale tiden på dette – fordi de også gjorde 30 søk i indeksen. Er det mulig å gjøre mindre?
Massekorrekturlesing etter indeks
Trenger vi å lage en egen indeksspørring for hver node? Det viser seg at nei - vi kan lese fra indeksen bruke flere taster samtidig i en samtale via = ANY(array).
Og i hver slik gruppe av identifikatorer kan vi ta alle ID-ene som ble funnet i forrige trinn ved "noder". Det vil si, ved hvert neste trinn vil vi søk etter alle etterkommere av et visst nivå samtidig.
Bare her er problemet, i rekursivt utvalg kan du ikke få tilgang til seg selv i en nestet spørring, men vi må på en eller annen måte bare velge det som ble funnet på forrige nivå... Det viser seg at det er umulig å lage en nestet spørring for hele utvalget, men for det spesifikke feltet er det mulig. Og dette feltet kan også være en matrise - som er det vi må bruke ANY.
Det høres litt sprøtt ut, 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 viktigste ikke engang vinne 1.5 ganger på tid, og at vi trakk fra færre buffere, siden vi kun har 5 kall til indeksen i stedet for 30!
En ekstra bonus er det faktum at etter den siste unnest, vil identifikatorene forbli sortert etter "nivåer".
Node tegn
Den neste vurderingen som vil bidra til å forbedre ytelsen er − «blader» kan ikke få barn, det vil si at for dem er det ikke nødvendig å se "ned" i det hele tatt. I utformingen av vår oppgave betyr dette at dersom vi fulgte avdelingskjeden og nådde en ansatt, så er det ikke nødvendig å se videre langs denne grenen.
La oss gå inn i tabellen vår ytterligere boolean-felt, som umiddelbart vil fortelle oss om denne spesielle oppføringen i treet vårt er en "node" - det vil si om den i det hele tatt kan ha etterkommere.
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 мс.Flott! Det viser seg at bare litt mer enn 30 % av alle treelementer har etterkommere.
La oss nå bruke en litt annen mekaniker - koblinger til den rekursive delen gjennom LATERAL, som lar oss umiddelbart få tilgang til feltene i den rekursive "tabellen", og bruke en aggregert funksjon med en filtreringsbetingelse basert på en node for å redusere settet med nøkler:
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 å redusere enda en indeksanrop og vunnet mer enn 2 ganger i volum korrekturlest.
#2. La oss gå tilbake til røttene
Denne algoritmen vil være nyttig hvis du trenger å samle poster for alle elementer "opp i treet", samtidig som du beholder informasjon om hvilket kildeark (og med hvilke indikatorer) som førte til at det ble inkludert i prøven - for eksempel for å generere en sammendragsrapport med aggregering til noder.
Det som følger skal kun tas som et proof-of-concept, siden forespørselen viser seg å være svært tungvint. Men hvis det dominerer databasen din, bør du tenke på å bruke lignende teknikker.
La oss starte med et par enkle utsagn:
- Samme post fra databasen Det er best å lese den bare én gang.
- Registreringer fra databasen Det er mer effektivt å lese i grupperenn alene.
La oss nå prøve å konstruere forespørselen vi trenger.
Trinn 1
Når vi initialiserer rekursjon (hvor ville vi vært uten det!) må vi selvsagt trekke fra postene til selve bladene basert på settet med initiale 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 virket rart for noen at "settet" er lagret som en streng og ikke en matrise, så er det en enkel forklaring på dette. Det er en innebygd aggregerende "liming"-funksjon for strenger string_agg, men ikke for arrays. Selv om hun .
Trinn 2
Nå ville vi få et sett med seksjons-IDer som må leses videre. Nesten alltid vil de dupliseres i forskjellige plater av originalsettet - så vi ville gruppere dem, samtidig som informasjon om kildebladene bevares.
Men her venter tre problemer oss:
- Den "subrekursive" delen av spørringen kan ikke inneholde aggregerte funksjoner med
GROUP BY. - En referanse til en rekursiv "tabell" kan ikke være i en nestet underspørring.
- En forespørsel i den rekursive delen kan ikke inneholde en CTE.
Heldigvis er alle disse problemene ganske enkle å omgå. La oss starte fra slutten.
CTE i rekursiv del
Her så no jobber:
WITH RECURSIVE tree AS (
...
UNION ALL
WITH T (...)
SELECT ...
)Og så fungerer det, parentesene utgjør forskjellen!
WITH RECURSIVE tree AS (
...
UNION ALL
(
WITH T (...)
SELECT ...
)
)Nestet søk mot en rekursiv "tabell"
Hmm... En rekursiv CTE kan ikke åpnes i en underspørring. Men det kan være inne i CTE! Og en nestet forespørsel kan allerede få tilgang til denne CTE!
GROUP BY innvendig rekursjon
Det er ubehagelig, men... Vi har en enkel måte å etterligne GROUP BY å bruke DISTINCT ON og vindusfunksjoner!
SELECT
(rec).pid id
, string_agg(chld::text, ',') chld
FROM
tree
WHERE
(rec).pid IS NOT NULL
GROUP BY 1 -- не работает!Og slik 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 NULLNå ser vi hvorfor den numeriske ID-en ble omgjort til tekst - slik at de kunne slås sammen atskilt med kommaer!
Trinn 3
Til finalen har vi ingenting igjen:
- vi leser "seksjons"-poster basert på et sett med grupperte IDer
- vi sammenligner de subtraherte delene med "settene" til de originale arkene
- "utvid" sett-strengen ved hjelp av
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