Komplekssetes ERP-süsteemides on paljusid üksusi iseloomustanud hierarhiline loomus, kus sarnased objektid on paigutatud suhete puusse "algataja - järeltulija" — see on nii ettevõtte organisatsiooniline struktuur (kõik need filiaalid, osakonnad ja töögrupid), tootekataloog, tööalad kui ka müügikohtade geograafia,…
Tegelikult pole ühtegi , kus mingit hierarhiat poleks. Kuid isegi kui te ei tööta „äri“ nimel, võite ikkagi kergesti kokku puutuda hierarhiliste suhetega. Lihtsalt, isegi teie genealoogia või kaubanduskeskuse korrusekava on sama struktuur.
Hierarhia salvestamiseks on palju viise, kuid täna peatume ainult ühel variandil:
CREATE TABLE hier(
id
integer
PRIMARY KEY
, pid
integer
REFERENCES hier
, data
json
);
CREATE INDEX ON hier(pid); -- ärge unustage, et FK ei tähenda indeksi automaatset loomist, erinevalt PK-st
Ja seni, kuni vaatate hierarhia sügavusi, ootab see rahulikult, kui efektiivsed on teie "naiivsed" lähenemised sellise struktuuriga töötamiseks.
Vaatame tavapäraseid tekkinud ülesandeid, nende rakendamist SQL-is ja proovime nende tulemuslikkust parandada.
#1. Насколько глубока кроличья нора?
Võtame selguse huvides, et see struktuur peegeldab meie organisatsiooni osakondade alluvust: osakonnad, divisjonid, sektorid, filiaalid, töögrupid,… — kuidas iganes neid nimetada.
Alustame oma 'puu' genereerimist 10K elemendiga
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;Alustame kõige lihtsama ülesandega - leida kõik töötajad, kes töötavad konkreetse sektori sees, või hierarhia terminiliselt - leida kõik sõlme järeltulijad. Samuti oleks hea saada järeltulija "sügavus"… Kõik see võib olla vajalik näiteks mingi .
Kõik oleks muidu hästi, kui neid järeltulijaid oleks seal vaid paar taset ja koguseliselt kümne ringis, kuid kui tasemeid on rohkem kui 5 ja järeltulijaid juba kümnete kaupa — võivad tekkida probleemid. Vaatame, kuidas kirjutatakse (ja töötavad) traditsioonilised variandid 'puu allapoole' otsimiseks. Kuid kõigepealt määratlegeme, millised sõlmed on meie uuringute jaoks kõige huvitavamad.
Kõige sügavamad alampuud:
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}
...Kõige laiad alampuud:
...
SELECT
path[1] id
, count(*)
FROM
T
GROUP BY
1
ORDER BY
2 DESC;id | count
------------
5300 | 30
450 | 28
1239 | 27
1573 | 25
Nende päringute jaoks kasutasime tüüpilist rekursiivset JOIN:
Ilmselt vastab sellise päringu mudel iteratsioonide arv kogu järeltulijate arvule (ja neid on mitukümmend), ja see võib võtta üsna märkimisväärseid ressursse ning seega aega.
Kontrollime kõige 'laiema' alampuu peal:
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; 
Nagu arvata võisime, leidsime kõik 30 kirjet. Kuid selleks kulus 60% kogu ajast — sest tegime sellega ka 30 otsingut indeksi järgi. Kas vähem ei saa?
Massiline lugemine indeksi kaudu
Kas iga sõlme jaoks on meil vaja teha eraldi päring indeksile? Tundub, et ei — saame indeksist lugeda koos mitme võtmega ühe taotlemisega kasutades = ANY(array).
Ja igasse sellesse identifikaatorite gruppi saame võtta kõik eelmisel sammul leitud ID-d 'sõlmedes'. See tähendab, et igal järgmistel sammudel otsime me otseselt kõiki teatud taseme järeltulijaid.
Kuid, siin on probleem, rekursiivses valikus ei saa me viidata endale sisemises päringus, aga me peame kuidagi valima just selle, mis eelmisel tasemel leiti... Selgub, et ei ole võimalik teha sisemist päringut kogu valikule — kuid selle konkreetsele väljadele — on võimalik. Ja see väli võib olla ka massiiv — mis ongi vajalik meie kasutamiseks. ALL.
Kõlab pisut veidralt, kuid skeemil on kõik lihtne.
REKURSIOONIGA T NAGU (
VALI
ARRAY[id] id$
KUST
id = 5300
UNION ALL
VALI
ARRAY(
VALI
id
KUST
pid = ANY(T.id$)
) id$
KUST
T
KUS
coalesce(id$, '{}') <> '{}' -- tsükli väljumise tingimus - tühi massiiv
)
VALI
unnest(id$) id
KUST
T; 
Siin on kõige olulisem isegi mitte 1,5 korda ajavõit, vaid see, et me lugesime vähem bufrite, sest indeksile pöördumisi on meil ainult 5, mitte 30!
Lisaboonuseks on see, et pärast lõplikku unnest jäävad identifikaatorid tasemete kaupa järjestatud.
Sõlme tunnus
Järgmine mõte, mis aitab parandada jõudlust — lehtedel ei saa olla lapsi, see tähendab, et nende jaoks ei ole mõtet otsida "alla". Meie ülesande püstituses tähendab see, et kui me käisime osakondade ahelas ja jõudsime töötajani, siis pole mõtet enam selles oksas otsida.
Vaatame, kas suudame meie tabelisse lisada boolean-veergu, mis ütleb meile kohe, kas see konkreetne kirje meie puus on "sõlm" — st kas sellel võivad üldse olla järeltulijad.
ALTER TABLE hier
LISAGE VEERG branch boolean;
UUENDAGE
hier T
SEADISTAGE
branch = TRUE
KUST
EXISITS(
VALI
NULL
KUST
hier
KUST
pid = T.id
PIIRANG 1
);
-- Päring täideti edukalt: 3033 rida muudetud 42 ms jooksul.Suurepärane! Selgub, et meil on vaid veidi üle 30% kõikidest puu elementidest, kellel on järeltulijad.
Nüüd rakendame veidi teistsuguse mehhanismi — liitmise rekursiivse osa kaudu LATERAL, mille abil saame kohe pöörduda rekursiivse "tabeli" väljade juurde, ja kasutame ühendamise tingimuse alusel sõlme tunnust aggregaatfunktsiooni jaoks, et vähendada võtmete hulka:
REKURSIOONIGA T NAGU (
VALI
array_agg(id) id$
, array_agg(id) FILTREERI(KUST branch) ns$
KUST
id = 5300
UNION ALL
VALI
X.*
KUST
T
LIITU LATERAL (
VALI
array_agg(id) id$
, array_agg(id) FILTREERI(KUST branch) ns$
KUST
pid = ANY(T.ns$)
) X
KUS coalesce(T.ns$, '{}') <> '{}'
)
VALI
unnest(id$) id
KUST
T; 
Me suutsime veel ühe indeksi pöördumise vähendada ja võitsime rohkem kui 2 korda mahtudes loetavast.
#2. Вернемся к корням
See algoritm on kasulik, kui peate koguma kirjeid kõigi elementide „üles puu”, säilitades samal ajal teabe selle kohta, milline algne leht (ja milliste näitajatega) tõi selle valikusse — näiteks kokkuvõttearuande koostamiseks sõlmedel aggregatsiooniga.
Edasi tuleks võtta kui ainult tõestuseks kontseptsioonist, kuna päring muutub väga raskeks. Kuid kui see domineerib teie andmekogus, tasub kaaluda sarnaste meetodite rakendamist.
Alustame paari lihtsa väitega:
- Sama kirje andmebaasist on parem lugeda ainult üks kord.
- Andmed andmebaasist on efektiivsem lugeda 'kimbu' kaupa, kui ükshaaval.
Nüüd proovime konstrueerida vajalikku päringut.
Samm 1
Selgelt on, et rekursiooni alguses (kuhu muidu!) peame lugema lehtede kirjeid vastavalt algsetele identifikaatoritele:
WITH RECURSIVE tree AS (
SELECT
rec -- see on terviklik kirje tabelis
, id::text chld -- see on "kogum" kergitavatest lehtedest
FROM
hier rec
WHERE
id = ANY('{1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192}'::integer[])
UNION ALL
... Kui kellelegi tundub veider, et "kogum" on salvestatud stringina, mitte massiivina, siis sellele on lihtne selgitus. Stringide puhul on olemas sisseehitatud agrgeeriv "ühendav" funktsioon string_agg, aga massiivide jaoks ei ole. Kuigi selle rakendamine ei ole raske .
Samm 2
need rühma panema , säilitades samas teavet allika lehtede kohta.Kuid siin ootavad meid ees kolm ebameeldivust:
"Alamrekursiivne" osa päringust ei tohi sisaldada agregaatfunktsioone
- Kutsumine rekursiivsesse "tabelisse" ei tohi olla sisestatud alam-päringus.
on olemas, vaate määratlemine peab sisaldama. - Päring rekursiivses osas ei tohi sisaldada CTE-d.
- Õnneks on need probleemid suhteliselt lihtsad ületada. Alustame lõpust.
CTE rekursiivses osas
töötab:
Nii ei WITH RECURSIVE tree AS ( ... UNION ALL WITH T (...) SELECT ... )
Ja nii — töötab, sulud lahendavad!WITH RECURSIVE tree AS ( ... UNION ALL ( WITH T (...) SELECT ... ) )
Sisenev päring rekursiivsesse "tabelisse"Hm... Kutsumine rekursiivsele CTE-le ei tohi olla sisestatud päringus. Kuid see võib olla CTE sees! Ja sisendpäring võib juba seda CTE-t kutsuda!
GROUP BY rekursiooni sees
Ebameeldiv, kuid... Meil on lihtne viis, kuidas simuleerida GROUP BY koos
DISTINCT ON ja akna funktsioonidega! SELECT (rec).pid id , string_agg(chld::text, ',') chld FROM tree WHERE (rec).pid IS NOT NULL GROUP BY 1 -- ei tööta!
Aga nii — töötab!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
VALI 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üüd näeme, miks numbriline ID muutus tekstiks — et neid saaks komadega kokku kleepida!
Samm 3
Finaali jaoks on meil alles vaid vähe:
- me kontrollime «jaotuste» kirjeid rühmitatud ID-de seast
- me seome loetud jaotused algsete lehtede «kogudega»
- me «avame» komplekti stringi abil
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; 
Allikas: habr.com
