Sarežģītās ERP sistēmās daudzām entītijām ir hierarhisks raksturskad viendabīgi objekti sarindojas vienā rindā senču un pēcnācēju attiecību koks - tā ir uzņēmuma organizatoriskā struktūra (visas šīs filiāles, nodaļas un darba grupas), un preču katalogs un darba jomas, un tirdzniecības vietu ģeogrāfija,...
Patiesībā tāda nav , kur rezultātā nebūtu nekādas hierarhijas. Bet pat tad, ja jūs nestrādājat "biznesa labā", jūs joprojām varat viegli saskarties ar hierarhiskām attiecībām. Tas ir banāli, pat jūsu ciltskoks vai telpu plāns tirdzniecības centrā ir vienādas struktūras.
Ir daudz veidu, kā saglabāt šādu koku DBVS, taču šodien mēs koncentrēsimies tikai uz vienu iespēju:
CREATE TABLE hier(
id
integer
PRIMARY KEY
, pid
integer
REFERENCES hier
, data
json
);
CREATE INDEX ON hier(pid); -- не забываем, что FK не подразумевает автосоздание индекса, в отличие от PK
Un, kamēr jūs skatāties hierarhijas dziļumos, tas pacietīgi gaida, lai redzētu, cik [ne]efektīvi būs jūsu “naivie” veidi, kā strādāt ar šādu struktūru.
Apskatīsim tipiskās problēmas, kas rodas, to ieviešanu SQL un mēģināsim uzlabot to veiktspēju.
#1. Cik dziļa ir truša bedre?
Konkrētības labad pieņemsim, ka šī struktūra atspoguļos nodaļu pakļautību organizācijas struktūrā: nodaļas, nodaļas, nozares, filiāles, darba grupas... - kā jūs tos saucat.
Vispirms ģenerēsim mūsu 10 XNUMX elementu “koku”.
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;Sāksim ar vienkāršāko uzdevumu - atrast visus darbiniekus, kuri strādā noteiktā sektorā vai hierarhijas ziņā - atrast visus mezgla bērnus. Būtu jauki arī iegūt pēcnācēja “dziļumu”... Tas viss var būt vajadzīgs, piemēram, lai uzbūvētu kādu .
Viss būtu kārtībā, ja ir tikai pāris šo pēcnācēju līmeņu un skaits ir duča robežās, bet, ja ir vairāk nekā 5 līmeņi, un pēcnācēju jau ir desmitiem, var rasties problēmas. Apskatīsim, kā tiek rakstītas (un darbojas) tradicionālās meklēšanas iespējas. Bet vispirms noteiksim, kuri mezgli būs mūsu pētījumam visinteresantākie.
Visvairāk "dziļi" apakškoki:
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}
...Visvairāk "plašs" apakškoki:
...
SELECT
path[1] id
, count(*)
FROM
T
GROUP BY
1
ORDER BY
2 DESC;id | count
------------
5300 | 30
450 | 28
1239 | 27
1573 | 25
Šiem vaicājumiem mēs izmantojām tipiskos rekursīvs JOIN:
Acīmredzot ar šo pieprasījuma modeli iterāciju skaits sakritīs ar kopējo pēcnācēju skaitu (un to ir vairāki desmiti), un tas var aizņemt diezgan ievērojamus resursus un līdz ar to arī laiku.
Pārbaudīsim “plašāko” apakškoku:
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;
Kā gaidīts, mēs atradām visus 30 ierakstus. Bet viņi tam veltīja 60% no kopējā laika, jo viņi arī veica 30 meklējumus rādītājā. Vai ir iespējams izdarīt mazāk?
Lielapjoma korektūra pēc indeksa
Vai mums ir jāizveido atsevišķs indeksa vaicājums katram mezglam? Izrādās, ka nē – varam nolasīt no rādītāja izmantojot vairākus taustiņus vienlaikus vienā zvanā via = ANY(array).
Un katrā šādā identifikatoru grupā mēs varam ņemt visus iepriekšējā solī atrastos ID pēc “mezgliem”. Tas ir, katrā nākamajā solī mēs to darīsim meklēt visus noteikta līmeņa pēcnācējus uzreiz.
Tikai šeit ir problēma, rekursīvajā atlasē jūs nevarat piekļūt sev ligzdotā vaicājumā, bet vajag kaut kā atlasīt tikai iepriekšējā līmenī atrasto... Izrādās, visai atlasei nav iespējams veikt ligzdotu vaicājumu, bet tās konkrētajam laukam gan ir iespējams. Un šis lauks var būt arī masīvs – tas ir tas, kas mums ir jāizmanto ANY.
Tas izklausās nedaudz traki, bet diagrammā viss ir vienkārši.
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;
Un šeit vissvarīgākais nav pat laimē 1.5 reizes, un ka mēs atņēmām mazāk buferu, jo mums ir tikai 5 izsaukumi uz indeksu, nevis 30!
Papildu bonuss ir fakts, ka pēc pēdējās atdalīšanas identifikatori paliks sakārtoti pēc “līmeņiem”.
Mezgla zīme
Nākamais apsvērums, kas palīdzēs uzlabot veiktspēju, ir − "lapām" nevar būt bērni, tas ir, viņiem vispār nav jāskatās “uz leju”. Mūsu uzdevuma formulējumā tas nozīmē, ka, ja mēs sekojām nodaļu ķēdei un sasniedzām darbinieku, tad tālāk pa šo atzaru nav jāskatās.
Ieejam savā galdā papildu boolean-lauks, kas mums uzreiz pateiks, vai šis konkrētais ieraksts mūsu kokā ir “mezgls” – tas ir, vai tam vispār var būt pēcnācēji.
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 мс.Lieliski! Izrādās, tikai nedaudz vairāk kā 30% no visiem koka elementiem ir pēcnācēji.
Tagad izmantosim nedaudz citu mehāniku - savienojumus ar rekursīvo daļu cauri LATERAL, kas ļaus mums nekavējoties piekļūt rekursīvās “tabulas” laukiem un izmantot apkopošanas funkciju ar filtrēšanas nosacījumu, pamatojoties uz mezglu, lai samazinātu atslēgu kopu:
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;
Varējām samazināt vēl vienu indeksa zvanu un apjomā uzvarēja vairāk nekā 2 reizes korektūru.
#2. Atgriezīsimies pie saknēm
Šis algoritms būs noderīgs, ja nepieciešams apkopot ierakstus par visiem elementiem “augšā kokā”, vienlaikus saglabājot informāciju par to, kura avota lapa (un ar kādiem rādītājiem) lika to iekļaut izlasē, piemēram, lai izveidotu kopsavilkuma pārskatu. ar agregāciju mezglos.
Sekojošais ir jāuztver tikai kā jēdziena pierādījums, jo pieprasījums izrādās ļoti apgrūtinošs. Bet, ja tas dominē jūsu datu bāzē, jums vajadzētu padomāt par līdzīgu paņēmienu izmantošanu.
Sāksim ar pāris vienkāršiem apgalvojumiem:
- Tas pats ieraksts no datu bāzes Vislabāk to izlasīt tikai vienu reizi.
- Ieraksti no datu bāzes Daudz efektīvāk ir lasīt pa daļāmnekā vienatnē.
Tagad mēģināsim izveidot vajadzīgo pieprasījumu.
Solis 1
Acīmredzot, inicializējot rekursiju (kur mēs būtu bez tās!), mums būs jāatņem pašu lapu ieraksti, pamatojoties uz sākotnējo identifikatoru kopu:
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
...
Ja kādam šķita dīvaini, ka “kopa” tiek saglabāta kā virkne, nevis masīvs, tad tam ir vienkāršs izskaidrojums. Ir iebūvēta virkņu apkopošanas “līmēšanas” funkcija string_agg, bet ne masīviem. Lai gan viņa .
Solis 2
Tagad mēs iegūtu sadaļu ID kopu, kas būs jālasa tālāk. Gandrīz vienmēr tie tiks dublēti dažādos oriģinālā komplekta ierakstos - tā mēs to darītu sagrupēt tos, vienlaikus saglabājot informāciju par avota lapām.
Bet šeit mūs sagaida trīs nepatikšanas:
- Vaicājuma “apakšrekursīvajā” daļā nedrīkst būt apkopotas funkcijas ar
GROUP BY. - Atsauce uz rekursīvu “tabulu” nevar būt ligzdotā apakšvaicājumā.
- Pieprasījums rekursīvajā daļā nedrīkst saturēt CTE.
Par laimi, visas šīs problēmas ir diezgan viegli novērst. Sāksim no beigām.
CTE rekursīvajā daļā
Kā šis nē darbi:
WITH RECURSIVE tree AS (
...
UNION ALL
WITH T (...)
SELECT ...
)Un tā tas darbojas, iekavās ir atšķirība!
WITH RECURSIVE tree AS (
...
UNION ALL
(
WITH T (...)
SELECT ...
)
)Ligzdots vaicājums pret rekursīvu "tabulu"
Hmm... Rekursīvam CTE nevar piekļūt apakšvaicājumā. Bet tas varētu būt CTE iekšienē! Un ligzdots pieprasījums jau var piekļūt šim CTE!
GROUP BY iekšējā rekursija
Tas ir nepatīkami, bet... Mums ir vienkāršs veids, kā līdzināties GROUP, izmantojot DISTINCT ON un logu funkcijas!
SELECT
(rec).pid id
, string_agg(chld::text, ',') chld
FROM
tree
WHERE
(rec).pid IS NOT NULL
GROUP BY 1 -- не работает!Un tā tas darbojas!
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 NULLTagad mēs redzam, kāpēc ciparu ID tika pārvērsts par tekstu - lai tos varētu savienot kopā, atdalot tos ar komatiem!
Solis 3
Finālam mums nekas neatliek:
- mēs lasām “sadaļu” ierakstus, pamatojoties uz grupētu ID kopu
- mēs salīdzinām atņemtās sadaļas ar oriģinālo lapu “komplektiem”.
- “paplašināt” iestatīto virkni, izmantojot
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;
Avots: www.habr.com