En kompleksaj ERP-sistemoj multaj estaĵoj havas hierarkian naturonkiam homogenaj objektoj viciĝas en arbo de praul-devenaj rilatoj - ĉi tio estas la organiza strukturo de la entrepreno (ĉiuj tiuj branĉoj, fakoj kaj laborgrupoj), kaj la katalogo de varoj, kaj laborfakoj, kaj la geografio de vendopunktoj,...
Fakte, ekzistas neniu , kie ne ekzistus ajna hierarkio kiel rezulto. Sed eĉ se vi ne laboras "por la komerco", vi ankoraŭ povas facile renkonti hierarkiajn rilatojn. Estas banala, eĉ via genealogia arbo aŭ etaĝa plano de loko en butikcentro estas la sama strukturo.
Estas multaj manieroj konservi tian arbon en DBMS, sed hodiaŭ ni fokusos nur unu opcion:
CREATE TABLE hier(
id
integer
PRIMARY KEY
, pid
integer
REFERENCES hier
, data
json
);
CREATE INDEX ON hier(pid); -- не забываем, что FK не подразумевает автосоздание индекса, в отличие от PK
Kaj dum vi rigardas en la profundon de la hierarkio, ĝi pacience atendas vidi kiom [ne]efikaj estos viaj "naivaj" manieroj labori kun tia strukturo.
Ni rigardu tipajn problemojn, kiuj aperas, ilian efektivigon en SQL, kaj provu plibonigi ilian agadon.
#1. Kiom profunda estas la kuniklotruo?
Ni, por certeco, akceptu, ke tiu ĉi strukturo spegulos la subordigon de fakoj en la strukturo de la organizo: fakoj, sekcioj, sektoroj, branĉoj, laborgrupoj... — kiel ajn vi nomos ilin.
Unue, ni generu nian 'arbon' de 10K elementoj
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;Ni komencu per la plej simpla tasko - trovi ĉiujn dungitojn, kiuj laboras ene de specifa sektoro, aŭ laŭ hierarkio - trovi ĉiujn filojn de nodo. Ankaŭ estus bone akiri la "profundon" de la posteulo... Ĉio ĉi eble estos necesa, ekzemple, por konstrui ian .
Ĉio estus en ordo, se ekzistas nur kelkaj niveloj de ĉi tiuj posteuloj kaj la nombro estas ene de dekduo, sed se estas pli ol 5 niveloj, kaj jam estas dekoj da posteuloj, povas esti problemoj. Ni rigardu kiel tradiciaj subarbaj serĉopcioj estas skribitaj (kaj funkcias). Sed unue, ni determinu, kiuj nodoj estos la plej interesaj por nia esplorado.
Plej multaj "profunde" subarboj:
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}
...Plej multaj "larĝa" subarboj:
...
SELECT
path[1] id
, count(*)
FROM
T
GROUP BY
1
ORDER BY
2 DESC;id | count
------------
5300 | 30
450 | 28
1239 | 27
1573 | 25
Por ĉi tiuj demandoj ni uzis la tipan rekursiva JOIN:
Evidente, kun ĉi tiu peto-modelo la nombro da ripetoj kongruos kun la totala nombro de posteuloj (kaj estas pluraj dekoj da ili), kaj ĉi tio povas preni sufiĉe signifajn rimedojn, kaj, kiel rezulto, tempon.
Ni kontrolu la "plej larĝan" subarbon:
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;
Kiel atendite, ni trovis ĉiujn 30 diskojn. Sed ili pasigis 60% de la tuta tempo por tio - ĉar ili ankaŭ faris 30 serĉojn en la indekso. Ĉu eblas fari malpli?
Pogranda provlegado per indekso
Ĉu ni bezonas fari apartan indeksan demandon por ĉiu nodo? Montriĝas, ke ne - ni povas legi el la indekso uzante plurajn klavojn samtempe en unu voko kun helpo de = ANY(array).
Kaj en ĉiu tia grupo de identigiloj ni povas preni ĉiujn identigilojn trovitajn en la antaŭa paŝo per "nodoj". Tio estas, ĉe ĉiu sekva paŝo ni faros serĉu ĉiujn posteulojn de certa nivelo samtempe.
Nur, jen la problemo, en rekursiva elekto, vi ne povas aliri sin en nestita demando, sed ni devas iel elekti nur tion, kio troviĝis ĉe la antaŭa nivelo... Montriĝas, ke estas neeble fari nestitan demandon por la tuta elekto, sed por ĝia specifa kampo eblas. Kaj ĉi tiu kampo ankaŭ povas esti tabelo - kio estas kion ni bezonas uzi ANY.
Sonas iom freneze, sed en la diagramo ĉio estas simpla.
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;
Kaj ĉi tie la plej grava afero eĉ ne estas gajnu 1.5 fojojn ĝustatempe, kaj ke ni subtrahis malpli da bufroj, ĉar ni havas nur 5 vokojn al la indekso anstataŭ 30!
Plia bonuso estas la fakto, ke post la fina malnestiĝo, la identigiloj restos ordigitaj per "niveloj".
Noda signo
La sekva konsidero, kiu helpos plibonigi rendimenton, estas − "folioj" ne povas havi infanojn, tio estas, por ili tute ne necesas rigardi "malsupren". En la formulado de nia tasko, tio signifas, ke se ni sekvis la ĉenon de fakoj kaj atingis dungiton, tiam ne necesas rigardi plu laŭ ĉi tiu branĉo.
Ni eniru en nian tablon aldonaj boolean-kampo, kiu tuj diros al ni, ĉu ĉi tiu aparta eniro en nia arbo estas "nodo" - tio estas, ĉu ĝi povas entute havi posteulojn.
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 мс.Bonege! Rezultas, ke nur iom pli ol 30% de ĉiuj arbaj elementoj havas posteulojn.
Nun ni uzu iomete malsaman mekanikon - ligojn al la rekursiva parto tra LATERAL, kiu permesos al ni tuj aliri la kampojn de la rekursiva "tabelo", kaj uzi entuta funkcion kun filtra kondiĉo bazita sur nodo por redukti la aron de ŝlosiloj:
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;
Ni povis redukti unu plian indeksvokon kaj gajnis pli ol 2 fojojn en volumeno provlegis.
#2. Ni reiru al la radikoj
Ĉi tiu algoritmo estos utila se vi bezonos kolekti rekordojn por ĉiuj elementoj "supren la arbo", konservante informojn pri kiu fontfolio (kaj kun kiuj indikiloj) igis ĝin esti inkludita en la specimeno - ekzemple, por generi resuman raporton. kun agregado en nodojn.
Kio sekvas devus esti prenita nur kiel pruvo de koncepto, ĉar la peto montriĝas esti tre maloportuna. Sed se ĝi regas vian datumbazon, vi devus pensi pri uzado de similaj teknikoj.
Ni komencu per kelkaj simplaj deklaroj:
- La sama rekordo de la datumbazo Plej bone legi ĝin nur unufoje.
- Rekordoj el la datumbazo Estas pli efika legi en arojol sola.
Nun ni provu konstrui la peton, kiun ni bezonas.
paŝi 1
Evidente, dum pravalorigo de rekurso (kie ni estus sen ĝi!) ni devos subtrahi la registrojn de la folioj mem surbaze de la aro de komencaj identigiloj:
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
...
Se al iu ŝajnis strange, ke la "aro" estas konservita kiel ŝnuro kaj ne tabelo, tiam estas simpla klarigo por tio. Estas enkonstruita agregacia "gluado" funkcio por ŝnuroj string_agg, sed ne por tabeloj. Kvankam ŝi .
paŝi 2
Nun ni ricevus aron da sekciaj identigiloj, kiuj devos esti legitaj plu. Preskaŭ ĉiam ili estos duobligitaj en malsamaj registroj de la originala aro - tiel ni farus grupigu ilin, konservante informojn pri la fontfolioj.
Sed ĉi tie atendas nin tri problemoj:
- La "subrekursiva" parto de la demando ne povas enhavi entutajn funkciojn kun
GROUP BY. - Referenco al rekursiva "tabelo" ne povas esti en nestita subdemando.
- Peto en la rekursiva parto ne povas enhavi CTE.
Feliĉe, ĉiuj ĉi tiuj problemoj estas sufiĉe facile solvi. Ni komencu de la fino.
CTE en rekursiva parto
Ĉi tie ne verkoj:
WITH RECURSIVE tree AS (
...
UNION ALL
WITH T (...)
SELECT ...
)Kaj tiel funkcias, la krampoj faras la diferencon!
WITH RECURSIVE tree AS (
...
UNION ALL
(
WITH T (...)
SELECT ...
)
)Nestita demando kontraŭ rekursiva "tabelo"
Hmm... Rekursiva CTE ne estas alirebla en subdemando. Sed ĝi povus esti ene de CTE! Kaj nestita peto jam povas aliri ĉi tiun CTE!
GROUP BY ene de rekurso
Estas malagrabla, sed... Ni havas simplan manieron kopii GROUP BY uzante DISTINCT ON kaj fenestrofunkcioj!
SELECT
(rec).pid id
, string_agg(chld::text, ',') chld
FROM
tree
WHERE
(rec).pid IS NOT NULL
GROUP BY 1 -- не работает!Kaj jen kiel ĝi funkcias!
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 NULLNun ni vidas kial la nombra ID estis igita teksto - tiel ke ili povus esti kunigitaj kune apartigitaj per komoj!
paŝi 3
Por la finalo ni restas nenio:
- ni legas "sekciajn" rekordojn bazitajn sur aro de grupigitaj identigiloj
- ni komparas la subtrahitajn sekciojn kun la "aroj" de la originalaj folioj
- "vastigi" la aro-ŝnuro uzante
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;
fonto: www.habr.com