W złożonych systemach ERP wiele encji ma hierarchiczną naturę, kiedy jednorodne obiekty są uporządkowane w drzewo relacji „rodzic — potomek” — to i struktura organizacyjna przedsiębiorstwa (wszystkie te filie, działy i grupy robocze), i katalog produktów, i obszary robocze, i geografia punktów sprzedaży,…
Faktycznie nie ma żadnej , w której nie występowałaby hierarchia. Ale nawet jeśli nie pracujesz „na biznesie”, i tak możesz łatwo natknąć się na relacje hierarchiczne. Prosto mówiąc, twoje drzewo genealogiczne lub plan pięter w centrum handlowym to również taka struktura.
Istnieje wiele sposobów przechowywania takiego drzewa w bazach danych, ale dzisiaj zatrzymamy się tylko na jednej opcji:
CREATE TABLE hier(
id
integer
PRIMARY KEY
, pid
integer
REFERENCES hier
, data
json
);
CREATE INDEX ON hier(pid); -- nie zapominaj, że FK nie zakłada automatycznego tworzenia indeksu, w przeciwieństwie do PK
I podczas gdy przyglądasz się głębokości hierarchii, cierpliwie czeka, jakie [nie]efektywne będą twoje „naiwne” sposoby pracy z taką strukturą.
Przyjrzyjmy się typowym zadaniom, ich implementacji w SQL i spróbujmy poprawić ich wydajność.
#1. Насколько глубока кроличья нора?
Dla pewności załóżmy, że ta struktura będzie odzwierciedlać podporządkowanie działów w strukturze organizacyjnej: departamenty, dywizje, sektory, filie, grupy robocze,… — jakkolwiek je nazwiesz.
Najpierw wygenerujemy nasze 'drzewo' z 10K 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 — znaleźć wszystkich pracowników, którzy pracują w danym sektorze, czy w terminologii hierarchii — znaleźć wszystkich potomków węzła. A także byłoby dobrze uzyskać „głębokość” potomka… Wszystko to może być potrzebne, na przykład, do budowy jakiegoś .
Wszystko byłoby w porządku, gdyby tych potomków było tylko kilka poziomów i w granicach dziesięciu, ale jeśli poziomów jest więcej niż 5, a potomków już dziesiątki — mogą być problemy. Zobaczmy, jak pisane są (i działają) tradycyjne wersje wyszukiwania „w dół drzewa”. Ale najpierw określmy, które węzły będą najbardziej interesujące dla naszych badań.
Najbardziej „głębokie” 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 „szerokie” 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
Do tych zapytań skorzystaliśmy z typowego rekursywnego JOIN:
Oczywiście, w takim modelu zapytania liczba iteracji będzie odpowiadać całkowitej liczbie potomków (a jest ich naprawdę kilka dziesiątek), a zajmowanie tego może wymagać dość znaczących zasobów, a co za tym idzie, czasu.
Sprawdźmy na najbardziej „szerokim” poddrzewie:
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; 
Jak się spodziewaliśmy, znaleźliśmy wszystkie 30 rekordów. Ale zajęło to 60% całego czasu — ponieważ zrobiliśmy jednocześnie 30 wyszukiwań po indeksie. A czy można mniej?
Masowa analiza indeksu
Czy dla każdego węzła musimy robić osobne zapytanie do indeksu? Okazuje się, że nie — możemy czytać z indeksu od razu po kilku kluczach w jednym zapytaniu z pomocą = ANY(array).
A w każdej takiej grupie identyfikatorów możemy wziąć wszystkie znalezione na poprzednim kroku ID po „węzłach”. To znaczy, na każdym kolejnym kroku będziemy szukać od razu wszystkich potomków danego poziomu.
Tylko, że jest pewien problem, w rekursywnym wyborze nie można odwołać się do samego siebie w zagnieżdżonym zapytaniu, a musimy jakoś wybrać tylko to, co znaleziono na poprzednim poziomie… Okazuje się, że zrobienie zagnieżdżonego zapytania do całego zbioru — nie jest możliwe, ale do jego konkretnego pola — można. A to pole może być także tablicą — co nam odpowiada. , lub.
Brzmi to nieco dziwnie, ale na schemacie — wszystko jest proste.
Z REKURSYJNE T JAKO (
WYBIERZ
TABLICA[id] id$
Z
hier
GDZIE
id = 5300
UNION ALL
WYBIERZ
TABLICA(
WYBIERZ
id
Z
hier
GDZIE
pid = DOWOLNE(T.id$)
) id$
Z
T
GDZIE
współczynnik(id$, '{}') <> '{}' -- warunek wyjścia z pętli - pusty zestaw
)
WYBIERZ
unnest(id$) id
Z
T; 
Najważniejsze jest to, że uzyskaliśmy 1,5 razy więcej czasu, a to, że odczytaliśmy mniej buforów, ponieważ odwołania do indeksu mamy tylko 5 zamiast 30!
Dodatkowym bonusem jest fakt, że po końcowym unnest identyfikatory pozostaną uporządkowane według „poziomów”.
Cechą węzła
Następna uwaga, która pomoże poprawić wydajność — liście nie mogą mieć dzieci, co oznacza, że w ich przypadku nie musimy szukać „w dół”. W kontekście naszego zadania oznacza to, że jeśli szliśmy przez łańcuch działów i dotarliśmy do pracownika, to dalsze poszukiwania po tej gałęzi są już zbędne.
Wprowadźmy do naszej tabeli dodatkowe boolean-pole, które od razu powie nam, czy ta konkretna wpis w naszym drzewie jest „węzłem” — to znaczy, czy mogą istnieć jego potomkowie.
ALTER TABLE hier
DODAJ KOLUMNĘ branch boolean;
AKTUALIZUJ
hier T
USTAW
branch = PRAWDA
GDZIE
ISTNIEJE(
WYBIERZ
NULL
Z
hier
GDZIE
pid = T.id
LIMIT 1
);
-- Zapytanie zostało pomyślnie wykonane: 3033 wierszy zmienionych w 42 ms.Świetnie! Okazuje się, że tylko nieco ponad 30% wszystkich elementów drzewa ma potomków.
Teraz zastosujemy nieco inną mechanikę — złączenia z częścią rekurencyjną przez LATERAL, co pozwoli nam od razu uzyskać dostęp do pól rekurencyjnej „tabeli”, a funkcję agregującą z warunkiem filtrowania według cechy węzła wykorzystamy do zmniejszenia zestawu kluczy:
Z REKURSYJNE T JAKO (
WYBIERZ
array_agg(id) id$
, array_agg(id) FILTRUJ(GDZIE branch) ns$
Z
hier
GDZIE
id = 5300
UNION ALL
WYBIERZ
X.*
Z
T
DOŁĄCZ LATERAL (
WYBIERZ
array_agg(id) id$
, array_agg(id) FILTRUJ(GDZIE branch) ns$
Z
hier
GDZIE
pid = DOWOLNE(T.ns$)
) X
NA współczynnik(T.ns$, '{}') <> '{}'
)
WYBIERZ
unnest(id$) id
Z
T; 
Udało nam się jeszcze skrócić odwołanie do indeksu i zyskaliśmy ponad 2 razy w wolumenie odczytu.
#2. Вернемся к корням
Ten algorytm będzie przydatny, jeśli musisz zebrać wpisy dla wszystkich elementów „w górę po drzewie”, zachowując jednocześnie informacje, który pierwotny liść (i z jakimi wskaźnikami) spowodował jego pojawienie się w zestawie — na przykład w celu sporządzenia zbiorczego raportu z agregacją na węzły.
Dalsze informacje należy traktować wyłącznie jako dowód koncepcji, ponieważ zapytanie staje się dość rozbudowane. Jednak jeśli dominuje w Twojej bazie — warto rozważyć zastosowanie podobnych metod.
Zacznijmy od kilku prostych stwierdzeń:
- Tę samą wartość z bazy lepiej czytać tylko raz.
- Wartości z bazy efektywniej czytać „partiami”, niż pojedynczo.
Teraz spróbujmy skonstruować potrzebne nam zapytanie.
Krok 1
Oczywiście, na początku rekurencji (gdzież bez niej!) będziemy musieli wczytać same liście według zestawu identyfikatorów:
WITH RECURSIVE tree AS (
SELECT
rec -- to cała wartość tabeli
, id::text chld -- to "zestaw" prowadzących do tych liści
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 ktoś uznał, że przechowywanie "zestawu" jako ciągu tekstowego zamiast tablicy jest dziwne, to jest na to proste wytłumaczenie. Dla ciągów jest wbudowana funkcja agregująca "sklejająca" string_agg, a dla tablic — nie. Mimo że można ją .
Krok 2
Teraz chcielibyśmy uzyskać zestaw identyfikatorów sekcji, które będziemy musieli wczytać dalej. Prawie zawsze będą się one powtarzać w różnych wartościach pierwotnego zestawu — dlatego powinniśmy je pogrupować, zachowując jednocześnie informacje o źródłowych liściach.
Ale tutaj czekają na nas trzy nieprzyjemności:
- Część zapytania 'podrekurencyjnego' nie może zawierać funkcji agregujących.
COUNT_BIG(*). - Odwołanie do rekurencyjnej "tabeli" nie może znajdować się w zagnieżdżonym podzapytaniu.
- Zapytanie w rekurencyjnej części nie może zawierać CTE.
Na szczęście, wszystkie te problemy można dość łatwo obejść. Zacznijmy od końca.
CTE w rekurencyjnej części
W ten sposób nie działa:
WITH RECURSIVE tree AS (
...
UNION ALL
WITH T (...)
SELECT ...
)A tak — działa, nawiasy rozwiązują sprawę!
WITH RECURSIVE tree AS (
...
UNION ALL
(
WITH T (...)
SELECT ...
)
)Zagnieżdżone zapytanie do rekurencyjnej "tabeli"
Hmm… Odwołanie do rekurencyjnego CTE nie może być w zagnieżdżonym zapytaniu. Ale może być w CTE! A zagnieżdżone zapytanie może odnosić się już do tego CTE!
GROUP BY wewnątrz rekurencji
Niemiło, ale… Mamy prosty sposób na symulację GROUP BY za pomocą DISTINCT ON i funkcji okiennych!
SELECT
(rec).pid id
, string_agg(chld::text, ',') chld
FROM
tree
WHERE
(rec).pid IS NOT NULL
GROUP BY 1 -- nie działa!A tak — 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 ID zamieniał się w tekst — aby można je było łączyć za pomocą przecinka!
Krok 3
Pozostało nam tylko kilka kroków do końca:
- sprawdzamy wpisy 'sekcji' dla zbioru pogrupowanych ID
- dopasowujemy wyczytane sekcje do 'zbiorów' pierwotnych arkuszy
- rozwijamy ciąg-zbiór przy użyciu
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: habr.com
