Күрделі ERP жүйелерінде көптеген нысандар иерархиялық сипатқа иебіртекті заттар қатар тұрғанда ата-баба қарым-қатынасының ағашы - бұл кәсіпорынның ұйымдық құрылымы (барлық осы филиалдар, бөлімдер мен жұмыс топтары), және тауарлар каталогы, және жұмыс бағыттары, және сату нүктелерінің географиясы,...
Шын мәнінде, жоқ , нәтижесінде ешқандай иерархия болмайды. Бірақ сіз «бизнес үшін» жұмыс істемесеңіз де, иерархиялық қатынастарды оңай кездестіре аласыз. Бұл қарапайым, тіпті сіздің отбасылық ағашыңыз немесе сауда орталығындағы үй-жайлардың жоспары бірдей құрылым.
Мұндай ағашты ДҚБЖ-да сақтаудың көптеген жолдары бар, бірақ бүгін біз тек бір нұсқаға тоқталамыз:
CREATE TABLE hier(
id
integer
PRIMARY KEY
, pid
integer
REFERENCES hier
, data
json
);
CREATE INDEX ON hier(pid); -- не забываем, что FK не подразумевает автосоздание индекса, в отличие от PK
Сіз иерархияның тереңдігіне үңіліп жатқанда, мұндай құрылыммен жұмыс істеудің «аңғал» әдістерінің қаншалықты тиімді болатынын шыдамдылықпен күтеді.
Пайда болатын типтік мәселелерді, олардың SQL жүйесінде орындалуын қарастырайық және олардың өнімділігін жақсартуға тырысайық.
№1. Қоянның шұңқыры қаншалықты терең?
Бұл құрылым ұйым құрылымындағы басқармалардың: департаменттердің, бөлімдердің, секторлардың, филиалдардың, жұмыс топтарының... - оларды қалай атасаңыз да, бағыныстылығын көрсететінін нақтылық үшін қабылдаймыз.
Алдымен 10K элементтен тұратын «ағашты» жасайық
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;Ең қарапайым тапсырмадан бастайық - белгілі бір секторда немесе иерархия тұрғысынан жұмыс істейтін барлық қызметкерлерді табу - түйіннің барлық еншілестерін табыңыз. Ұрпақтың «тереңдігін» алу да жақсы болар еді... Мұның бәрі, мысалы, қандай да бір құрылыс салу үшін қажет болуы мүмкін. .
Бұл ұрпақтардың бірнеше деңгейі болса және саны онға жуық болса, бәрі жақсы болар еді, бірақ 5 деңгейден көп болса және ондаған ұрпақтар болса, проблемалар болуы мүмкін. Дәстүрлі іздеу опциялары қалай жазылғанын (және жұмыс істейтінін) қарастырайық. Бірақ алдымен біздің зерттеуіміз үшін қандай түйіндер ең қызықты болатынын анықтайық.
Ең көп «терең» ішкі ағаштар:
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}
...Ең көп «кең» ішкі ағаштар:
...
SELECT
path[1] id
, count(*)
FROM
T
GROUP BY
1
ORDER BY
2 DESC;id | count
------------
5300 | 30
450 | 28
1239 | 27
1573 | 25
Бұл сұраулар үшін біз әдеттегіні қолдандық рекурсивті JOIN:
Әлбетте, бұл сұраныс үлгісімен қайталану саны ұрпақтардың жалпы санына сәйкес келеді (және олардың бірнеше ондағандары бар) және бұл айтарлықтай ресурстарды және нәтижесінде уақытты қажет етуі мүмкін.
«Ең кең» ішкі ағашты тексерейік:
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;
Күткендей, біз барлық 30 жазбаны таптық. Бірақ олар бұған жалпы уақыттың 60% жұмсады - өйткені олар индексте 30 іздеу жасады. Азырақ істеуге бола ма?
Индекс бойынша жаппай тексеру
Әрбір түйін үшін жеке индекстік сұрау жасау керек пе? Жоқ екен – көрсеткіштен оқи аламыз бір қоңырауда бірден бірнеше пернені пайдалану көмегімен = ANY(array).
Әрбір осындай идентификаторлар тобында біз «түйіндер» бойынша алдыңғы қадамда табылған барлық идентификаторларды қабылдай аламыз. Яғни, әрбір келесі қадамда біз жасаймыз белгілі бір деңгейдегі барлық ұрпақтарды бірден іздеу.
Тек, мәселе осында, рекурсивті таңдауда кірістірілген сұрауда өзіне қол жеткізе алмайсыз, бірақ біз қандай да бір жолмен тек алдыңғы деңгейде табылғанды таңдауымыз керек... Бүкіл таңдау үшін кірістірілген сұраныс жасау мүмкін емес, бірақ оның нақты өрісі үшін бұл мүмкін. Және бұл өріс массив болуы мүмкін - бұл бізге пайдалануымыз керек ANY.
Бұл аздап ақылсыз болып көрінеді, бірақ диаграммада бәрі қарапайым.
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;
Және бұл жерде ең маңыздысы біркелкі емес уақытында 1.5 есе жеңеді, және біз азырақ буферлерді алып тастадық, өйткені бізде индекске 5 емес, тек 30 қоңырау бар!
Қосымша бонус - соңғы жоюдан кейін идентификаторлар «деңгейлер» бойынша реттелген күйде қалады.
Түйін белгісі
Өнімділікті жақсартуға көмектесетін келесі мәселе - «жапырақтар» балалы бола алмайды, яғни олар үшін «төменге» қараудың қажеті жоқ. Міндетімізді тұжырымдағанда, бұл дегеніміз, егер біз бөлімдер тізбегін бақылап, қызметкерге жетсек, онда бұл саланы одан әрі іздеудің қажеті жоқ.
Кәне үстелімізге кірейік қосымша boolean-филд, бұл біздің ағаштағы бұл нақты жазбаның «түйін» екенін, яғни оның ұрпақтары болуы мүмкін екенін бірден көрсетеді.
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 мс.Тамаша! Барлық ағаш элементтерінің 30% -дан сәл астамы ғана ұрпақтары бар екені белгілі болды.
Енді аздап басқа механиканы қолданайық - арқылы рекурсивті бөлікке қосылыстар LATERAL, бұл бізге рекурсивті «кесте» өрістеріне бірден қол жеткізуге және кілттер жинағын азайту үшін түйінге негізделген сүзу шарты бар жиынтық функцияны пайдалануға мүмкіндік береді:
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;
Біз тағы бір индекстік қоңырауды азайта алдық және көлемі бойынша 2 еседен астам жеңіске жетті түзету.
№2. Тамырларға қайта оралайық
Бұл алгоритм қай бастапқы парақ (және қандай көрсеткіштермен) үлгіге қосылуына себеп болғаны туралы ақпаратты сақтай отырып, «ағаштың үстінде» барлық элементтер үшін жазбаларды жинау қажет болса, пайдалы болады - мысалы, жиынтық есепті құру түйіндерге біріктіру арқылы.
Төмендегілерді тек тұжырымдаманың дәлелі ретінде қабылдау керек, өйткені сұрау өте ауыр болып шығады. Бірақ егер ол сіздің дерекқорыңызда басым болса, ұқсас әдістерді пайдалану туралы ойлануыңыз керек.
Бірнеше қарапайым мәлімдемелерден бастайық:
- Деректер базасынан бірдей жазба Бір рет оқыған дұрыс.
- Дерекқордан алынған жазбалар Топтамамен оқу тиімдірекжалғыз қарағанда.
Енді бізге қажетті сұранысты құрастырып көрейік.
қадам 1
Әлбетте, рекурсияны инициализациялау кезінде (онсыз біз қайда болар едік!) біз бастапқы идентификаторлар жиынтығы негізінде жапырақтардың жазбаларын алып тастауымыз керек:
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
...
Егер біреуге «жиын» массив емес, жол ретінде сақталатыны оғаш болып көрінсе, бұл үшін қарапайым түсініктеме бар. Жолдар үшін кіріктірілген біріктіру «жабыстыру» функциясы бар string_agg, бірақ массивтер үшін емес. Ол болса да .
қадам 2
Енді біз одан әрі оқуды қажет ететін бөлім идентификаторларының жинағын аламыз. Әрқашан дерлік олар бастапқы жинақтың әртүрлі жазбаларында қайталанатын болады - біз солай болар едік оларды топтастыру, бастапқы жапырақтар туралы ақпаратты сақтай отырып.
Бірақ бұл жерде бізді үш қиындық күтіп тұр:
- Сұраудың "субрекурсивті" бөлігінде жиынтық функциялар болуы мүмкін емес
GROUP BY. - Рекурсивті «кестеге» сілтеме кірістірілген ішкі сұрауда болуы мүмкін емес.
- Рекурсивті бөліктегі сұрауда CTE болуы мүмкін емес.
Бақытымызға орай, бұл проблемалардың барлығын шешу өте оңай. Соңынан бастайық.
Рекурсивті бөліктегі CTE
Міне осылай емес жұмыстар:
WITH RECURSIVE tree AS (
...
UNION ALL
WITH T (...)
SELECT ...
)Осылайша ол жұмыс істейді, жақшалар айырмашылықты жасайды!
WITH RECURSIVE tree AS (
...
UNION ALL
(
WITH T (...)
SELECT ...
)
)Рекурсивті «кестеге» қарсы кірістірілген сұрау
Хмм... Ішкі сұрауда рекурсивті CTE-ге кіру мүмкін емес. Бірақ бұл CTE ішінде болуы мүмкін! Ал кірістірілген сұрау осы CTE-ге қол жеткізе алады!
GROUP BY ішіндегі рекурсия
Бұл жағымсыз, бірақ... Бізде GROUP BY арқылы еліктеудің қарапайым тәсілі бар DISTINCT ON және терезе функциялары!
SELECT
(rec).pid id
, string_agg(chld::text, ',') chld
FROM
tree
WHERE
(rec).pid IS NOT NULL
GROUP BY 1 -- не работает!Және бұл осылай жұмыс істейді!
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Енді біз сандық идентификатордың неліктен мәтінге айналғанын көреміз - осылайша оларды үтір арқылы біріктіруге болады!
қадам 3
Финалға бізде ештеңе қалмады:
- топтастырылған идентификаторлар жиынтығына негізделген «бөлім» жазбаларын оқимыз
- біз шегерілген бөлімдерді бастапқы парақтардың «жиындарымен» салыстырамыз
- көмегімен жиынтық жолды «кеңейту».
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;
Ақпарат көзі: www.habr.com