Keerulistes ERP-süsteemides paljudel üksustel on hierarhiline iseloomkui homogeensed objektid reastuvad esivanemate ja järeltulijate suhete puu - see on ettevõtte organisatsiooniline struktuur (kõik need filiaalid, osakonnad ja töörühmad) ja kaupade kataloog ja töövaldkonnad ning müügikohtade geograafia,...
Tegelikult pole ühtegi , kus selle tulemusena ei tekiks hierarhiat. Kuid isegi kui te ei tööta "ettevõtte heaks", võite siiski kergesti kokku puutuda hierarhiliste suhetega. See on tühine, isegi teie sugupuu või kaubanduskeskuse ruumide plaan on sama struktuuriga.
Sellise puu salvestamiseks DBMS-is on palju võimalusi, kuid täna keskendume ainult ühele võimalusele:
CREATE TABLE hier(
id
integer
PRIMARY KEY
, pid
integer
REFERENCES hier
, data
json
);
CREATE INDEX ON hier(pid); -- не забываем, что FK не подразумевает автосоздание индекса, в отличие от PK
Ja samal ajal kui vaatate hierarhia sügavustesse, ootab see kannatlikult, et näha, kui tõhusad on teie "naiivsed" viisid sellise struktuuriga töötamiseks.
Vaatame tüüpilisi tekkivaid probleeme, nende rakendamist SQL-is ja proovime parandada nende jõudlust.
#1. Kui sügav on jänese auk?
Kindluse mõttes nõustugem sellega, et see struktuur peegeldab osakondade alluvust organisatsiooni struktuuris: osakonnad, allüksused, sektorid, filiaalid, töörühmad... - kuidas te neid nimetate.
Esiteks genereerime oma 10 XNUMX elemendist koosneva "puu".
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 lihtsamast ülesandest – leida kõik töötajad, kes töötavad konkreetses sektoris või hierarhiliselt – leida kõik sõlme lapsed. Tore oleks ka järeltulija “sügavus” kätte saada... Seda kõike võib vaja minna näiteks mingisuguse .
Kõik oleks hästi, kui neid järeltulijaid on ainult paar taset ja arv jääb tosina piiresse, aga kui tasemeid on rohkem kui 5 ja järeltulijaid on juba kümneid, võib probleeme tekkida. Vaatame, kuidas on kirjutatud (ja toimivad) traditsioonilised puu otsast otsimise valikud. Kuid kõigepealt teeme kindlaks, millised sõlmed on meie uurimistöö jaoks kõige huvitavamad.
Kõige rohkem "sügav" 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 rohkem "lai" 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 rekursiivne JOIN:
Ilmselgelt selle taotluse mudeliga iteratsioonide arv ühtib järeltulijate koguarvuga (ja neid on mitukümmend) ja see võib võtta üsna märkimisväärseid ressursse ja sellest tulenevalt aega.
Kontrollime "kõige laiemat" alampuud:
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;
Ootuspäraselt leidsime kõik 30 kirjet. Kuid nad kulutasid sellele 60% kogu ajast – kuna nad tegid ka 30 otsingut indeksist. Kas on võimalik vähem teha?
Hulgikorrektuur indeksi järgi
Kas peame tegema iga sõlme jaoks eraldi indeksipäringu? Selgub, et ei – saame indeksist välja lugeda mitme klahvi korraga kasutamine ühe kõne ajal abiga = ANY(array).
Ja igas sellises identifikaatorite rühmas saame võtta kõik eelmises etapis leitud ID-d “sõlmede” kaupa. See tähendab, et igal järgmisel etapil me seda teeme otsida kõiki teatud taseme järeltulijaid korraga.
Ainult, see on halb õnn, rekursiivse valiku korral ei saa te pesastatud päringus endale juurde pääseda, aga peame kuidagi selekteerima ainult eelmisel tasemel leitu... Selgub, et kogu valiku kohta pesastatud päringut teha ei saa, aga selle konkreetse välja jaoks on see võimalik. Ja see väli võib olla ka massiiv – seda me peame kasutama ANY.
See kõlab pisut hullumeelselt, kuid diagrammil on kõik lihtne.
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;
Ja siin pole kõige tähtsam isegi mitte võita 1.5 korda aja jooksul, ja et me lahutasime vähem puhvreid, kuna meil on 5 asemel ainult 30 indeksi kõnet!
Lisaboonuseks on asjaolu, et pärast lõplikku pesitsemist jäävad identifikaatorid “tasemete” järgi järjestatuks.
Sõlme märk
Järgmine kaalutlus, mis aitab jõudlust parandada, on − "lehed" ei saa lapsi saada, see tähendab, et nende jaoks pole vaja üldse "alla" vaadata. Meie ülesande sõnastuses tähendab see seda, et kui järgisime osakondade ahelat ja jõudsime töötajani, siis pole vaja seda haru mööda kaugemale vaadata.
Siseneme oma tabelisse lisaks boolean- väli, mis annab meile kohe teada, kas see konkreetne kirje meie puus on "sõlm" ehk kas sellel võib üldse olla järglasi.
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 мс.Suurepärane! Selgub, et ainult veidi rohkem kui 30% kõigist puuelementidest on järglased.
Nüüd kasutame veidi teistsugust mehaanikat – ühendused rekursiivse osaga läbi LATERAL, mis võimaldab meil kohe juurde pääseda rekursiivse "tabeli" väljadele ja kasutada võtmete hulga vähendamiseks sõlmel põhinevat filtreerimistingimusega koondfunktsiooni:
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;
Suutsime veel ühe indeksikõne vähendada ja võitis mahult rohkem kui 2 korda korrektuur.
#2. Lähme tagasi juurte juurde
See algoritm on kasulik, kui peate koguma kõigi elementide kirjeid "puust ülespoole", säilitades samal ajal teabe selle kohta, milline lähteleht (ja milliste näitajatega) põhjustas selle valimisse kaasamise - näiteks kokkuvõtliku aruande loomiseks. sõlmedeks liitmisega.
Järgnevat tuleks võtta üksnes kui kontseptsiooni tõestust, kuna taotlus osutub väga tülikaks. Kuid kui see domineerib teie andmebaasis, peaksite mõtlema sarnaste tehnikate kasutamisele.
Alustame paari lihtsa väitega:
- Sama kirje andmebaasist Parem on seda ainult üks kord lugeda.
- Kirjed andmebaasist Tõhusam on lugeda partiidenakui üksi.
Nüüd proovime koostada vajaliku taotluse.
Samm 1
Ilmselt peame rekursiooni lähtestamisel (kus me oleksime ilma selleta!) algidentifikaatorite komplekti alusel lahutama lehtede endi kirjed:
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
...
Kui kellelegi tundus kummaline, et “komplekt” on salvestatud stringina, mitte massiivina, siis on sellele lihtne seletus. Stringide jaoks on sisseehitatud liimimisfunktsioon string_agg, kuid mitte massiivide jaoks. Kuigi ta .
Samm 2
Nüüd saame jaotise ID-de komplekti, mida tuleb edasi lugeda. Peaaegu alati dubleeritakse neid originaalkomplekti erinevates kirjetes – nii teeksime ka meie rühmitada neid, säilitades samal ajal teabe lähtelehtede kohta.
Kuid siin ootavad meid kolm häda:
- Päringu "alamrekursiivne" osa ei tohi sisaldada koondfunktsioone
GROUP BY. - Viide rekursiivsele "tabelile" ei saa olla pesastatud alampäringus.
- Rekursiivses osas olev päring ei tohi sisaldada CTE-d.
Õnneks on kõiki neid probleeme üsna lihtne lahendada. Alustame lõpust.
CTE rekursiivses osas
Siin nii ei töötab:
WITH RECURSIVE tree AS (
...
UNION ALL
WITH T (...)
SELECT ...
)Ja nii see töötab, sulgudes on vahe!
WITH RECURSIVE tree AS (
...
UNION ALL
(
WITH T (...)
SELECT ...
)
)Pesastatud päring rekursiivse "tabeli" vastu
Hmm... Rekursiivsele CTE-le ei pääse alampäringus juurde. Kuid see võib olla CTE sees! Ja pesastatud päring pääseb juba sellele CTE-le juurde!
GROUP BY siserekursioon
See on ebameeldiv, aga... Meil on lihtne viis GROUP BY jäljendamiseks DISTINCT ON ja aknafunktsioonid!
SELECT
(rec).pid id
, string_agg(chld::text, ',') chld
FROM
tree
WHERE
(rec).pid IS NOT NULL
GROUP BY 1 -- не работает!Ja nii see toimib!
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üüd näeme, miks numbriline ID muudeti tekstiks – et neid saaks komadega eraldades omavahel ühendada!
Samm 3
Finaaliks ei jää meil midagi üle:
- loeme jaotise kirjeid rühmitatud ID-de komplekti alusel
- võrdleme lahutatud sektsioone algsete lehtede “komplektidega”.
- "laiendage" set-stringi kasutades
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: www.habr.com