W złożonych systemach ERP wiele podmiotów ma charakter hierarchicznygdy jednorodne obiekty ustawiają się w jednej linii drzewo powiązań przodków i potomków - jest to struktura organizacyjna przedsiębiorstwa (wszystkie te oddziały, działy i grupy robocze), katalog towarów i obszary pracy oraz geografia punktów sprzedaży,...
W rzeczywistości nie ma żadnego , gdzie w rezultacie nie byłoby żadnej hierarchii. Ale nawet jeśli nie pracujesz „dla biznesu”, nadal możesz łatwo spotkać się z relacjami hierarchicznymi. To banalne, nawet Twoje drzewo genealogiczne czy plan piętra lokalu w centrum handlowym ma tę samą strukturę.
Istnieje wiele sposobów przechowywania takiego drzewa w systemie DBMS, ale dzisiaj skupimy się tylko na jednej opcji:
CREATE TABLE hier(
id
integer
PRIMARY KEY
, pid
integer
REFERENCES hier
, data
json
);
CREATE INDEX ON hier(pid); -- не забываем, что FK не подразумевает автосоздание индекса, в отличие от PK
A kiedy zaglądasz w głąb hierarchii, ona cierpliwie czeka, aby zobaczyć, jak [nie]efektywne będą twoje „naiwne” sposoby pracy z taką strukturą.
Przyjrzyjmy się typowym problemom, które się pojawiają, ich implementacji w SQL i spróbujmy poprawić ich wydajność.
#1. Jak głęboka jest królicza nora?
Przyjmijmy dla ścisłości, że ta struktura będzie odzwierciedlała podporządkowanie działów w strukturze organizacji: działów, oddziałów, sektorów, oddziałów, grup roboczych... - jakkolwiek je nazwiecie.
Najpierw wygenerujmy nasze „drzewo” składające się z 10 tys. elementów
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;Zacznijmy od najprostszego zadania – znalezienia wszystkich pracowników, którzy pracują w konkretnym sektorze, czyli według hierarchii – znajdź wszystkie dzieci węzła. Przydałoby się też uzyskać „głębokość” potomka... Wszystko to może być potrzebne np. do zbudowania jakiegoś rodzaju .
Wszystko byłoby dobrze, gdyby poziomów tych potomków było tylko kilka i liczba ta mieściła się w granicach kilkunastu, natomiast jeśli poziomów jest więcej niż 5, a potomków jest już kilkudziesięciu, mogą być problemy. Przyjrzyjmy się, jak są zapisywane (i jak działają) tradycyjne opcje wyszukiwania w dół drzewa. Ale najpierw ustalmy, które węzły będą najciekawsze dla naszych badań.
Najbardziej "głęboko" poddrzewa:
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}
...Najbardziej "szeroki" poddrzewa:
...
SELECT
path[1] id
, count(*)
FROM
T
GROUP BY
1
ORDER BY
2 DESC;id | count
------------
5300 | 30
450 | 28
1239 | 27
1573 | 25
W przypadku tych zapytań użyliśmy typowego rekurencyjne DOŁĄCZ:
Oczywiście z tym modelem żądania liczba iteracji będzie równa całkowitej liczbie potomków (a jest ich kilkadziesiąt), a to może wymagać dość znacznych zasobów, a co za tym idzie, czasu.
Sprawdźmy „najszersze” poddrzewo:
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;
Zgodnie z oczekiwaniami znaleźliśmy wszystkie 30 rekordów. Ale spędzili na tym 60% całkowitego czasu – ponieważ przeprowadzili także 30 wyszukiwań w indeksie. Czy można zrobić mniej?
Korekta zbiorcza według indeksu
Czy musimy wykonać osobne zapytanie indeksowe dla każdego węzła? Okazuje się, że nie – możemy odczytać z indeksu używanie kilku klawiszy jednocześnie w jednym połączeniu przez = ANY(array).
I w każdej takiej grupie identyfikatorów możemy przyjąć wszystkie identyfikatory znalezione w poprzednim kroku przez „węzły”. Oznacza to, że na każdym kolejnym kroku będziemy to robić wyszukaj jednocześnie wszystkich potomków określonego poziomu.
Tylko tu jest problem w przypadku wyboru rekurencyjnego nie można uzyskać dostępu do samego siebie w zagnieżdżonym zapytaniu, ale trzeba jakoś zaznaczyć tylko to, co zostało znalezione na poprzednim poziomie... Okazuje się, że nie da się zrobić zapytania zagnieżdżonego dla całej selekcji, ale dla jej konkretnego pola jest to możliwe. Pole to może być także tablicą – i właśnie tego musimy użyć ANY.
Brzmi to trochę szalenie, ale na schemacie wszystko jest proste.
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;
A tutaj najważniejsze nie jest równo wygraj 1.5 razy na czasi że odjęliśmy mniej buforów, ponieważ zamiast 5 mamy tylko 30 wywołań indeksu!
Dodatkowym bonusem jest fakt, że po ostatecznym rozgnieceniu identyfikatory pozostaną uporządkowane według „poziomów”.
Znak węzła
Następną kwestią, która pomoże poprawić wydajność, jest − „liście” nie mogą mieć dzieci, to znaczy, że dla nich w ogóle nie trzeba patrzeć „w dół”. W sformułowaniu naszego zadania oznacza to, że jeśli podążaliśmy łańcuchem działów i dotarliśmy do pracownika, to nie ma potrzeby szukać dalej wzdłuż tej gałęzi.
Wejdźmy do naszego stołu dodatkowy boolean-pole, co od razu nam powie, czy ten konkretny wpis w naszym drzewie jest „węzłem” – czyli czy w ogóle może mieć potomków.
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 мс.Świetnie! Okazuje się, że tylko nieco ponad 30% wszystkich elementów drzewa ma potomków.
Teraz zastosujmy nieco inną mechanikę - połączenia z częścią rekursywną LATERAL, co umożliwi nam natychmiastowy dostęp do pól rekurencyjnej „tabeli” i wykorzystanie funkcji agregującej z warunkiem filtrowania na podstawie węzła w celu zmniejszenia zestawu kluczy:
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;
Udało nam się zredukować jeszcze jedno wywołanie indeksu i wygrał ponad 2 razy pod względem wolumenu czytać korektę.
#2. Wróćmy do korzeni
Algorytm ten przyda się, jeśli zajdzie potrzeba zebrania rekordów dla wszystkich elementów „z góry drzewa”, zachowując przy tym informację, który arkusz źródłowy (i przy jakich wskaźnikach) spowodował, że znalazł się on w próbie – np. w celu wygenerowania raportu zbiorczego z agregacją w węzły.
Poniższe informacje należy traktować wyłącznie jako dowód słuszności koncepcji, ponieważ żądanie okazuje się bardzo kłopotliwe. Jeśli jednak dominuje w Twojej bazie danych, powinieneś pomyśleć o zastosowaniu podobnych technik.
Zacznijmy od kilku prostych stwierdzeń:
- Ten sam rekord z bazy danych Najlepiej przeczytać ją chociaż raz.
- Zapisy z bazy Czytanie partiami jest bardziej efektywneniż sam.
Spróbujmy teraz skonstruować żądanie, którego potrzebujemy.
Krok 1
Oczywiście inicjując rekurencję (gdzie byśmy bez niej byli!) będziemy musieli odjąć rekordy samych liści w oparciu o zestaw początkowych identyfikatorów:
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
...
Jeśli komuś wydawało się dziwne, że „zestaw” był przechowywany jako ciąg znaków, a nie tablica, istnieje na to proste wyjaśnienie. Istnieje wbudowana funkcja agregująca „sklejanie” ciągów string_agg, ale nie dla tablic. Chociaż ona .
Krok 2
Teraz otrzymalibyśmy zestaw identyfikatorów sekcji, które trzeba będzie przeczytać dalej. Prawie zawsze będą one powielane w różnych zapisach oryginalnego zestawu – i my to zrobimy pogrupuj je, przy jednoczesnym zachowaniu informacji o liściach źródłowych.
Ale tutaj czekają na nas trzy kłopoty:
- Część „subrekursywna” zapytania nie może zawierać funkcji agregujących
GROUP BY. - Odwołanie do rekurencyjnej „tabeli” nie może znajdować się w zagnieżdżonym podzapytaniu.
- Żądanie w części rekurencyjnej nie może zawierać CTE.
Na szczęście wszystkie te problemy można dość łatwo obejść. Zacznijmy od końca.
CTE w części rekurencyjnej
Tutaj tak nie Pracuje:
WITH RECURSIVE tree AS (
...
UNION ALL
WITH T (...)
SELECT ...
)I tak to działa, nawiasy robią różnicę!
WITH RECURSIVE tree AS (
...
UNION ALL
(
WITH T (...)
SELECT ...
)
)Zagnieżdżone zapytanie dotyczące rekurencyjnej „tabeli”
Hmm... W podzapytaniu nie można uzyskać dostępu do rekurencyjnego CTE. Ale to może być w CTE! Zagnieżdżone żądanie może już uzyskać dostęp do tego CTE!
GROUP BY wewnątrz rekurencji
To nieprzyjemne, ale... Mamy prosty sposób na emulację GROUP BY za pomocą DISTINCT ON i funkcje okna!
SELECT
(rec).pid id
, string_agg(chld::text, ',') chld
FROM
tree
WHERE
(rec).pid IS NOT NULL
GROUP BY 1 -- не работает!I tak to działa!
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 NULLTeraz widzimy, dlaczego numeryczny identyfikator został zamieniony na tekst - aby można było je połączyć, oddzielając je przecinkami!
Krok 3
Do finału nie zostało nam już nic:
- rekordy „sekcyjne” czytamy na podstawie zestawu zgrupowanych identyfikatorów
- porównujemy odjęte sekcje z „zestawami” oryginalnych arkuszy
- „rozwiń” ciąg znaków za pomocą
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;
Źródło: www.habr.com