У сложеним ЕРП системима многи ентитети имају хијерархијску природукада се хомогени објекти поређају стабло односа предака и потомака - ово је организациона структура предузећа (све ове гране, одељења и радне групе), и каталог робе, и области рада, и географија продајних места,...
У ствари, нема је , где као резултат не би било никакве хијерархије. Али чак и ако не радите „за посао“, и даље можете лако наићи на хијерархијске односе. Отрцано је, чак је и ваше породично стабло или тлоцрт просторија у тржном центру иста структура.
Постоји много начина за складиштење таквог стабла у ДБМС, али данас ћемо се фокусирати на само једну опцију:
CREATE TABLE hier(
id
integer
PRIMARY KEY
, pid
integer
REFERENCES hier
, data
json
);
CREATE INDEX ON hier(pid); -- не забываем, что FK не подразумевает автосоздание индекса, в отличие от PK
И док ви завирујете у дубину хијерархије, она стрпљиво чека да види колико ће ваши „наивни“ начини рада са таквом структуром бити [не]ефикасни.
Хајде да погледамо типичне проблеме који се јављају, њихову имплементацију у СКЛ-у и покушамо да побољшамо њихове перформансе.
#1. Колико је дубока зечја рупа?
Дефинитивно прихватимо да ће ова структура одражавати субординацију одељења у структури организације: одељења, одељења, сектора, филијале, радне групе... - како год да их назовете.
Прво, хајде да генеришемо наше 'стабло' од 10К елемената
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
За ове упите користили смо типичан рекурзивни ЈОИН:
Очигледно, са овим моделом захтева број итерација ће бити исти као и укупан број потомака (а има их неколико десетина), а то може одузети прилично значајна средства и, као резултат, време.
Хајде да проверимо „најшире“ подстабло:
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. Вратимо се коренима
Овај алгоритам ће бити користан ако је потребно да прикупите записе за све елементе „горе у стаблу“, док задржавате информације о томе који изворни лист (и са којим индикаторима) је довео до његовог укључивања у узорак – на пример, да бисте генерисали сажети извештај са агрегацијом у чворове.
Оно што следи треба узети само као доказ концепта, пошто се испоставља да је захтев веома тежак. Али ако доминира вашом базом података, требало би да размислите о коришћењу сличних техника.
Почнимо са неколико једноставних изјава:
- Исти запис из базе података Најбоље је да га прочитате само једном.
- Записи из базе података Ефикасније је читати у серијаманего сама.
Покушајмо сада да конструишемо захтев који нам је потребан.
Корак КСНУМКС
Очигледно, приликом иницијализације рекурзије (где бисмо били без ње!) мораћемо да одузмемо записе самих листова на основу скупа почетних идентификатора:
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, али не и за низове. Иако је она .
Корак КСНУМКС
Сада бисмо добили скуп ИД-ова секција које ће морати даље да се читају. Скоро увек ће они бити дуплирани у различитим записима оригиналног скупа - тако бисмо и ми групишу их, уз очување података о изворним листовима.
Али овде нас чекају три невоље:
- „Субрекурзивни“ део упита не може да садржи агрегатне функције са
GROUP BY. - Референца на рекурзивну „табелу“ не може бити у угнежђеном потупиту.
- Захтев у рекурзивном делу не може да садржи ЦТЕ.
На срећу, сви ови проблеми су прилично лаки за решавање. Почнимо од краја.
ЦТЕ у рекурзивном делу
Тако не Извођење радова:
WITH RECURSIVE tree AS (
...
UNION ALL
WITH T (...)
SELECT ...
)И тако функционише, заграде чине разлику!
WITH RECURSIVE tree AS (
...
UNION ALL
(
WITH T (...)
SELECT ...
)
)Угнежђени упит у односу на рекурзивну „табелу“
Хмм... Рекурзивном ЦТЕ-у се не може приступити у потупиту. Али може бити унутар ЦТЕ! А угнежђени захтев већ може да приступи овом ЦТЕ!
ГРОУП БИ унутрашња рекурзија
Непријатно је, али... Имамо једноставан начин да опонашамо ГРОУП БИ користећи 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Сада видимо зашто је бројчани ИД претворен у текст - да би се могли спојити заједно раздвојени зарезима!
Корак КСНУМКС
За финале нам није остало ништа:
- читамо записе „секције“ на основу скупа груписаних ИД-ова
- поредимо одузете делове са „скуповима“ оригиналних листова
- „прошири“ сет-стринг користећи
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;
Извор: ввв.хабр.цом