У складних 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