Në sistemet komplekse ERP shumë entitete kanë natyrë hierarkikekur objektet homogjene rreshtohen pema e marrëdhënieve paraardhës-pasardhës - kjo është struktura organizative e ndërmarrjes (të gjitha këto degë, departamente dhe grupe pune), dhe katalogu i mallrave, dhe fushat e punës, dhe gjeografia e pikave të shitjes, ...
Në fakt, nuk ka asnjë , ku si rezultat nuk do të kishte asnjë hierarki. Por edhe nëse nuk punoni "për biznesin", prapë mund të hasni lehtësisht marrëdhënie hierarkike. Është e rëndomtë, madje edhe pema juaj familjare ose planimetria e ambienteve në një qendër tregtare është e njëjta strukturë.
Ka shumë mënyra për të ruajtur një pemë të tillë në një DBMS, por sot ne do të përqendrohemi vetëm në një opsion:
CREATE TABLE hier(
id
integer
PRIMARY KEY
, pid
integer
REFERENCES hier
, data
json
);
CREATE INDEX ON hier(pid); -- не забываем, что FK не подразумевает автосоздание индекса, в отличие от PK
Dhe ndërkohë që po shikoni në thellësi të hierarkisë, ai me durim pret të shohë se sa [jo]efektive do të jenë mënyrat tuaja “naive” të punës me një strukturë të tillë.
Le të shohim problemet tipike që dalin, zbatimin e tyre në SQL dhe të përpiqemi të përmirësojmë performancën e tyre.
#1. Sa e thellë është vrima e lepurit?
Le të pranojmë me siguri se kjo strukturë do të pasqyrojë vartësinë e departamenteve në strukturën e organizatës: departamente, divizione, sektorë, degë, grupe pune... - si t'i quani ato.
Së pari, le të gjenerojmë 'pemën' tonë prej 10K elementësh
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;Le të fillojmë me detyrën më të thjeshtë - gjetjen e të gjithë punonjësve që punojnë brenda një sektori specifik, ose në aspektin e hierarkisë - gjeni të gjithë fëmijët e një nyje. Gjithashtu do të ishte mirë të merrej "thellësia" e pasardhësit... E gjithë kjo mund të jetë e nevojshme, për shembull, për të ndërtuar një lloj .
Gjithçka do të ishte mirë nëse do të kishte vetëm disa nivele të këtyre pasardhësve dhe numri është brenda një duzine, por nëse ka më shumë se 5 nivele dhe tashmë ka dhjetëra pasardhës, mund të ketë probleme. Le të shohim se si shkruhen (dhe funksionojnë) opsionet tradicionale të kërkimit poshtë-the-tree. Por së pari, le të përcaktojmë se cilat nyje do të jenë më interesante për kërkimin tonë.
Më së shumti "thellë" nënpemë:
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}
...Më së shumti "i gjerë" nënpemë:
...
SELECT
path[1] id
, count(*)
FROM
T
GROUP BY
1
ORDER BY
2 DESC;id | count
------------
5300 | 30
450 | 28
1239 | 27
1573 | 25
Për këto pyetje kemi përdorur tipiken rekursive JOIN:
Natyrisht, me këtë model kërkese numri i përsëritjeve do të përputhet me numrin total të pasardhësve (dhe ka disa dhjetra prej tyre), dhe kjo mund të marrë burime mjaft të rëndësishme, dhe, si rezultat, kohë.
Le të kontrollojmë nënpemën "më të gjerë":
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;
Siç pritej, gjetëm të 30 rekordet. Por ata shpenzuan 60% të kohës totale për këtë - sepse ata gjithashtu bënë 30 kërkime në indeks. A është e mundur të bësh më pak?
Korrigjimi në masë sipas indeksit
A duhet të bëjmë një pyetje të veçantë të indeksit për secilën nyje? Rezulton se jo - ne mund të lexojmë nga indeksi duke përdorur disa çelësa njëherësh në një telefonatë me ndihmën e = ANY(array).
Dhe në secilin grup të tillë identifikuesish ne mund të marrim të gjitha ID-të e gjetura në hapin e mëparshëm sipas "nyjeve". Kjo do të thotë, në çdo hap tjetër do ta bëjmë kërkoni për të gjithë pasardhësit e një niveli të caktuar menjëherë.
Vetëm këtu është problemi, në përzgjedhjen rekursive, nuk mund të hyni në vetvete në një pyetje të ndërthurur, por duhet të zgjedhim disi vetëm atë që është gjetur në nivelin e mëparshëm... Rezulton se është e pamundur të bësh një pyetje të ndërthurur për të gjithë përzgjedhjen, por për fushën e saj specifike është e mundur. Dhe kjo fushë mund të jetë gjithashtu një grup - që është ajo që duhet të përdorim ANY.
Tingëllon pak e çmendur, por në diagram gjithçka është e thjeshtë.
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;
Dhe këtu gjëja më e rëndësishme nuk është as fitoni 1.5 herë në kohë, dhe se kemi zbritur më pak bufera, pasi kemi vetëm 5 thirrje në indeks në vend të 30!
Një bonus shtesë është fakti që pas çrrënjosjes përfundimtare, identifikuesit do të mbeten të renditur sipas "niveleve".
Shenja e nyjës
Konsiderata tjetër që do të ndihmojë në përmirësimin e performancës është − "gjethet" nuk mund të kenë fëmijë, domethënë, për ta nuk ka nevojë të shikojnë fare "poshtë". Në formulimin e detyrës sonë, kjo do të thotë që nëse kemi ndjekur zinxhirin e departamenteve dhe kemi arritur një punonjës, atëherë nuk ka nevojë të shikojmë më tej përgjatë kësaj dege.
Le të hyjmë në tryezën tonë shtesë boolean-fushë, i cili do të na tregojë menjëherë nëse kjo hyrje e veçantë në pemën tonë është një "nyje" - domethënë nëse mund të ketë fare pasardhës.
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 мс.E madhe! Rezulton se vetëm pak më shumë se 30% e të gjithë elementëve të pemës kanë pasardhës.
Tani le të përdorim një mekanik paksa të ndryshëm - lidhjet me pjesën rekursive përmes LATERAL, i cili do të na lejojë të aksesojmë menjëherë fushat e "tabelës" rekursive dhe të përdorim një funksion agregat me një kusht filtrimi të bazuar në një nyje për të zvogëluar grupin e çelësave:
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;
Ne ishim në gjendje të reduktonim edhe një thirrje indeksuese dhe fitoi më shumë se 2 herë në vëllim korrigjohet.
#2. Le të kthehemi te rrënjët
Ky algoritëm do të jetë i dobishëm nëse keni nevojë për të mbledhur regjistrime për të gjithë elementët "lart në pemë", duke ruajtur informacionin se cila fletë burimi (dhe me çfarë treguesish) e ka shkaktuar përfshirjen e tij në mostër - për shembull, për të gjeneruar një raport përmbledhës me agregim në nyje.
Ajo që vijon duhet të merret vetëm si një provë e konceptit, pasi kërkesa rezulton të jetë shumë e rëndë. Por nëse dominon bazën tuaj të të dhënave, duhet të mendoni për përdorimin e teknikave të ngjashme.
Le të fillojmë me disa deklarata të thjeshta:
- I njëjti rekord nga baza e të dhënave Është më mirë ta lexoni vetëm një herë.
- Të dhënat nga baza e të dhënave Është më efikase të lexosh në grupese sa vetëm.
Tani le të përpiqemi të ndërtojmë kërkesën që na nevojitet.
Hapi 1
Natyrisht, kur inicializojmë rekursionin (ku do të ishim pa të!) do të duhet të zbresim vetë të dhënat e gjetheve bazuar në grupin e identifikuesve fillestarë:
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
...
Nëse dikujt i është dukur e çuditshme që "seti" ruhet si varg dhe jo si një grup, atëherë ekziston një shpjegim i thjeshtë për këtë. Ekziston një funksion i integruar "ngjitës" i grumbullimit për vargjet string_agg, por jo për vargje. Edhe pse ajo .
Hapi 2
Tani do të merrnim një grup ID seksionesh që do të duhet të lexohen më tej. Pothuajse gjithmonë ato do të dublikohen në regjistrime të ndryshme të grupit origjinal - kështu do të bënim ne grupojini ato, duke ruajtur informacionin për gjethet burimore.
Por këtu na presin tre telashe:
- Pjesa "nënkursive" e pyetjes nuk mund të përmbajë funksione agreguese me
GROUP BY. - Një referencë për një "tabelë" rekursive nuk mund të jetë në një nënpyetje të mbivendosur.
- Një kërkesë në pjesën rekursive nuk mund të përmbajë një CTE.
Për fat të mirë, të gjitha këto probleme janë mjaft të lehta për t'u zgjidhur. Le të fillojmë nga fundi.
CTE në pjesën rekursive
Ja kështu jo duke punuar:
WITH RECURSIVE tree AS (
...
UNION ALL
WITH T (...)
SELECT ...
)Dhe kështu funksionon, kllapat bëjnë diferencën!
WITH RECURSIVE tree AS (
...
UNION ALL
(
WITH T (...)
SELECT ...
)
)Kërkesa e mbivendosur kundrejt një "tabele" rekursive
Hmm... Një CTE rekursive nuk mund të aksesohet në një nënpyetje. Por mund të jetë brenda CTE! Dhe një kërkesë e ndërthurur tashmë mund të hyjë në këtë CTE!
GRUP BY brenda rekursionit
Është e pakëndshme, por... Ne kemi një mënyrë të thjeshtë për të imituar GROUP BY duke përdorur DISTINCT ON dhe funksionet e dritares!
SELECT
(rec).pid id
, string_agg(chld::text, ',') chld
FROM
tree
WHERE
(rec).pid IS NOT NULL
GROUP BY 1 -- не работает!Dhe kështu funksionon!
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 NULLTani shohim pse ID-ja numerike u kthye në tekst - në mënyrë që ato të mund të bashkohen së bashku të ndara me presje!
Hapi 3
Për finalen nuk na mbetet asgjë:
- ne lexojmë të dhënat e "seksioneve" bazuar në një grup ID-sh të grupuara
- ne krahasojmë seksionet e zbritura me "bashkësitë" e fletëve origjinale
- "zgjeroni" vargun e setit duke përdorur
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;
Burimi: www.habr.com