У складаных 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).
А ў кожную такую групу ідэнтыфікатараў мы можам узяць усе знойдзеныя на папярэднім кроку ID па "вузлах". Гэта значыць, на кожным наступным кроку мы будзем шукаць адразу ўвогуле ўсіх нашчадкаў пэўнага ўзроўню.
Толькі, вось няўдача, у рэкурсіўнай выбарцы нельга звярнуцца да самой сабе ва ўкладзеным запыце, а нам бо трэба неяк адабраць менавіта толькі знойдзенае на папярэднім узроўні… Аказваецца, зрабіць укладзены запыт да ўсёй выбаркі - нельга, а вось да яе канкрэтнага поля - можна. А гэтае поле можа быць і масівам - што нам і трэба для выкарыстання 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 разы па часе, а што мы адымалі менш buffers, паколькі зваротаў да індэкса ў нас усяго 5 замест 30!
Дадатковым бонусам ідзе той факт, што пасля фінальнага unnest ідэнтыфікатары застануцца спарадкаванымі па "узроўнях".
Прыкмета вузла
Наступнае меркаванне, якое дапаможа палепшыць прадукцыйнасць - у «лісцяў» не можа быць дзяцей, гэта значыць для іх шукаць "уніз" наогул нічога не трэба. У пастаноўцы нашай задачы гэта азначае, што калі мы ішлі па ланцужку аддзелаў і дайшлі да супрацоўніка, то далей па гэтай галінцы шукаць ужо няма чаго.
Давайце ўвядзем у нашу табліцу дадатковае 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. Вернемся да каранёў
Гэты алгарытм будзе карысны, калі вам неабходна сабраць запісы для ўсіх элементаў "уверх па дрэве", захаваўшы пры гэтым інфармацыю, якім зыходным лістом (і з якімі паказчыкамі) выклікана яго трапленне ў выбарку - напрыклад, для фарміравання зводнай справаздачы з агрэгацыяй на вузлы.
Далейшае варта ўспрымаць выключна як proof-of-concept, паколькі запыт атрымліваецца вельмі ўжо грувасткі. Але калі ён дамінуе ў вашай базе - варта задумацца над ужываннем падобных методык.
Пачнём з пары простых сцвярджэнняў:
- Адзін і той жа запіс з базы лепш чытаць усяго адзін раз.
- Запісы з базы больш эфектыўна чытаць «пачкам», чым паасобку.
Цяпер паспрабуем сканструяваць патрэбны нам запыт.
Крок 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
Цяпер нам бы атрымаць набор ID раздзелаў, якія трэба будзе адымаць далей. Амаль заўсёды яны будуць дублявацца ў розных запісаў зыходнага набору - таму нам бы іх згрупаваць, захаваўшы пры гэтым інфармацыю аб лісці-крыніцах.
Але тут нас чакаюць тры непрыемнасці:
- «Подрекурсівная» частка запыту не можа змяшчаць агрэгатных функцый з
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Вось зараз мы бачым, навошта лікавы ID ператвараўся ў тэкст - каб іх можна было склейваць праз коску!
Крок 3
Для фіналу нам засталося ўсяго нічога:
- вычытваем запісы «часткаў» па наборы згрупаваных ID
- супастаўляемы вычытаныя часткі з «наборамі» зыходных лістоў
- «разгортваем» радок-набор з дапамогай
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;
Крыніца: habr.com