Í flóknum ERP kerfum margar einingar hafa stigveldis eðliþegar einsleitir hlutir raðast inn tré tengsla forfeðra og afkomenda - þetta er skipulag fyrirtækisins (öll þessi útibú, deildir og vinnuhópar), og vörulisti, og starfssvið, og landafræði sölustaða,...
Í raun er enginn
Það eru margar leiðir til að geyma slíkt tré í DBMS, en í dag munum við einblína á aðeins einn valkost:
CREATE TABLE hier(
id
integer
PRIMARY KEY
, pid
integer
REFERENCES hier
, data
json
);
CREATE INDEX ON hier(pid); -- не забываем, что FK не подразумевает автосоздание индекса, в отличие от PK
Og á meðan þú ert að skyggnast inn í djúp stigveldisins, bíður það þolinmóður eftir því að sjá hversu [ó]árangursríkar „barnlausar“ leiðir þínar til að vinna með slíka uppbyggingu verða.
Skoðum dæmigerð vandamál sem koma upp, útfærslu þeirra í SQL, og reynum að bæta árangur þeirra.
#1. Hversu djúpt er kanínuholið?
Við skulum, svo sannarlega, viðurkenna að þessi uppbygging mun endurspegla undirskipun deilda í skipulagi stofnunarinnar: deilda, sviða, sviða, greina, vinnuhópa... - hvað sem þú kallar þær.
Fyrst skulum við búa til „tré“ okkar af 10K þáttum
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;
Byrjum á einfaldasta verkefninu - að finna alla starfsmenn sem starfa innan ákveðins geira, eða hvað varðar stigveldi - finna öll börn hnúts. Það væri líka gaman að fá “dýpt” afkomandans... Allt þetta gæti verið nauðsynlegt, til dæmis til að byggja einhvers konar
Allt væri í lagi ef það eru aðeins nokkur stig af þessum afkomendum og fjöldinn er innan við tugi, en ef það eru fleiri en 5 stig, og það eru nú þegar heilmikið af afkomendum, gætu verið vandamál. Við skulum skoða hvernig hefðbundnir leitarvalkostir eru skrifaðir (og virka). En fyrst skulum við ákvarða hvaða hnútar verða áhugaverðastir fyrir rannsóknir okkar.
Flestir "djúpt" undirtré:
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}
...
Flestir "breitt" undirtré:
...
SELECT
path[1] id
, count(*)
FROM
T
GROUP BY
1
ORDER BY
2 DESC;
id | count
------------
5300 | 30
450 | 28
1239 | 27
1573 | 25
Fyrir þessar fyrirspurnir notuðum við dæmigerða endurkvæmt JOIN:
Vitanlega, með þessu beiðni líkani fjöldi endurtekningar mun passa við heildarfjölda afkomenda (og það eru nokkrir tugir af þeim) og þetta getur tekið töluvert fjármagn og þar af leiðandi tíma.
Við skulum athuga „breiðasta“ undirtréð:
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;
Eins og við var að búast fundum við allar 30 plöturnar. En þeir eyddu 60% af heildartímanum í þetta - vegna þess að þeir gerðu líka 30 leitir í vísitölunni. Er hægt að gera minna?
Magnprófarkalestur eftir vísitölu
Þurfum við að gera sérstaka vísitölufyrirspurn fyrir hvern hnút? Það kemur í ljós að nei - við getum lesið úr vísitölunni nota nokkra takka í einu í einu símtali með hjálpinni = ANY(array)
.
Og í hverjum slíkum auðkennahópi getum við tekið öll auðkennin sem finnast í fyrra skrefi með „hnútum“. Það er, í hverju næsta skrefi munum við leitaðu að öllum afkomendum á ákveðnu stigi í einu.
Aðeins, hér er vandamálið, í endurkvæmu vali geturðu ekki fengið aðgang að sjálfu sér í hreiðri fyrirspurn, en við þurfum einhvern veginn að velja aðeins það sem fannst á fyrra stigi... Það kemur í ljós að það er ómögulegt að gera hreiðraða fyrirspurn fyrir allt valið, en fyrir sérstakan reit þess er það mögulegt. Og þetta svið getur líka verið fylki - sem er það sem við þurfum að nota ANY
.
Það hljómar svolítið klikkað, en á skýringarmyndinni er allt einfalt.
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 hér er það mikilvægasta ekki einu sinni vinna 1.5 sinnum í tíma, og að við drógum frá færri biðminni, þar sem við höfum aðeins 5 köll í vísitöluna í stað 30!
Viðbótarbónus er sú staðreynd að eftir síðasta óþægindi verða auðkennin áfram raðað eftir „stigum“.
Hnútamerki
Næsta íhugun sem mun hjálpa til við að bæta árangur er - "lauf" geta ekki eignast börn, það er, fyrir þá er engin þörf á að horfa "niður" yfirleitt. Við mótun verkefnis okkar þýðir þetta að ef við fylgjumst með keðju deilda og náðum til starfsmanns, þá er óþarfi að leita lengra eftir þessari grein.
Við skulum ganga inn í töfluna okkar til viðbótar boolean
-völlur, sem mun strax segja okkur hvort þessi tiltekna færsla í trénu okkar sé „hnútur“ - það er að segja hvort hún geti yfirhöfuð átt afkomendur.
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 мс.
Frábært! Það kemur í ljós að aðeins meira en 30% allra trjáþátta eiga afkomendur.
Nú skulum við nota aðeins öðruvísi vélvirki - tengingar við endurkvæma hlutann í gegnum LATERAL
, sem gerir okkur kleift að fá strax aðgang að reitum endurkvæmu „töflunnar“ og nota samansafnaða aðgerð með síuskilyrði sem byggir á hnút til að draga úr lyklasettinu:
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ð gátum lækkað enn eitt vísitölukallið og unnið meira en 2 sinnum að magni prófarkalestur.
#2. Förum aftur að rótunum
Þetta reiknirit mun vera gagnlegt ef þú þarft að safna gögnum fyrir alla þætti „upp í trénu“, á sama tíma og þú geymir upplýsingar um hvaða heimildarblað (og með hvaða vísbendingum) olli því að það var tekið með í úrtakinu - til dæmis til að búa til yfirlitsskýrslu með samsöfnun í hnúta.
Það sem hér fer á eftir ber að taka eingöngu sem sönnun fyrir hugmyndinni, þar sem beiðnin reynist mjög fyrirferðarmikil. En ef það drottnar yfir gagnagrunninum þínum, ættir þú að hugsa um að nota svipaða tækni.
Við skulum byrja á nokkrum einföldum fullyrðingum:
- Sama skráning úr gagnagrunninum Best að lesa hana bara einu sinni.
- Skrár úr gagnagrunninum Það er skilvirkara að lesa í lotumen einn.
Nú skulum við reyna að búa til beiðnina sem við þurfum.
Skref 1
Augljóslega, þegar endurtekið er frumstillt (hvar værum við án hennar!) verðum við að draga frá skrárnar yfir laufblöðin sjálf byggt á safni upphafsauðkenna:
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
...
Ef einhverjum fannst það undarlegt að „settið“ sé geymt sem strengur en ekki fylki, þá er einföld skýring á þessu. Það er innbyggð aðgerð til að safna „lím“ fyrir strengi string_agg
, en ekki fyrir fylki. Þó hún
Skref 2
Nú myndum við fá sett af hlutaauðkennum sem þarf að lesa frekar. Næstum alltaf verða þau afrituð í mismunandi skrám af upprunalega settinu - svo við myndum gera það flokka þá, en varðveita upplýsingar um upprunablöðin.
En hér bíða okkar þrjú vandræði:
- "undirhverfa" hluti fyrirspurnarinnar getur ekki innihaldið samanlagðar aðgerðir með
GROUP BY
. - Tilvísun í endurkvæma „töflu“ getur ekki verið í hreiðri undirfyrirspurn.
- Beiðni í endurkvæma hlutanum getur ekki innihaldið CTE.
Sem betur fer er auðvelt að vinna úr öllum þessum vandamálum. Byrjum á endanum.
CTE í endurkvæmum hluta
Hér svo ekki vinna:
WITH RECURSIVE tree AS (
...
UNION ALL
WITH T (...)
SELECT ...
)
Og svo virkar þetta, svigarnir gera gæfumuninn!
WITH RECURSIVE tree AS (
...
UNION ALL
(
WITH T (...)
SELECT ...
)
)
Hreiður fyrirspurn gegn endurkvæmri „töflu“
Hmm... Ekki er hægt að nálgast endurkvæma CTE í undirfyrirspurn. En það gæti verið inni í CTE! Og hreiður beiðni getur nú þegar fengið aðgang að þessu CTE!
GROUP BY innri endurkomu
Það er óþægilegt, en... Við höfum einfalda leið til að líkja eftir GROUP BY að nota DISTINCT ON
og gluggaaðgerðir!
SELECT
(rec).pid id
, string_agg(chld::text, ',') chld
FROM
tree
WHERE
(rec).pid IS NOT NULL
GROUP BY 1 -- не работает!
Og svona virkar þetta!
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
Nú sjáum við hvers vegna tölulega auðkenninu var breytt í texta - svo hægt væri að tengja þau saman aðskilin með kommum!
Skref 3
Fyrir úrslitaleikinn eigum við ekkert eftir:
- við lesum „hluta“ færslur byggðar á safni hópauðkenna
- við berum saman frádráttarhlutana við „sett“ upprunalegu blaðanna
- „stækkaðu“ sett-strenginn með því að nota
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;
Heimild: www.habr.com