V komplexních ERP systémech mnoho entit má hierarchickou povahukdyž se seřadí homogenní předměty strom vztahů předek-potomek - jedná se o organizační strukturu podniku (všechny tyto obory, oddělení a pracovní skupiny), dále katalog zboží a oblasti práce a geografie prodejních míst,...
Ve skutečnosti žádná není , kde by v důsledku toho neexistovala žádná hierarchie. Ale i když nepracujete „pro firmu“, stále můžete snadno narazit na hierarchické vztahy. Je to banální, i váš rodokmen nebo půdorys prostor v obchodním centru je stejná struktura.
Existuje mnoho způsobů, jak uložit takový strom v DBMS, ale dnes se zaměříme pouze na jednu možnost:
CREATE TABLE hier(
id
integer
PRIMARY KEY
, pid
integer
REFERENCES hier
, data
json
);
CREATE INDEX ON hier(pid); -- не забываем, что FK не подразумевает автосоздание индекса, в отличие от PK
A zatímco vy nahlížíte do hlubin hierarchie, ta trpělivě čeká, jak [ne]efektivní budou vaše „naivní“ způsoby práce s takovou strukturou.
Podívejme se na typické problémy, které se objevují, jejich implementaci v SQL a pokusme se zlepšit jejich výkon.
#1. Jak hluboká je králičí nora?
Pro definitivnost připusťme, že tato struktura bude odrážet podřízenost oddělení ve struktuře organizace: oddělení, divize, sektory, pobočky, pracovní skupiny... - jak je nazvete.
Nejprve vygenerujme náš „strom“ 10K prvků
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;Začněme tím nejjednodušším úkolem – najít všechny zaměstnance, kteří pracují v určitém sektoru nebo z hlediska hierarchie – najít všechny potomky uzlu. Také by bylo fajn získat „hloubku“ potomka... To vše může být nutné např. k vybudování nějaké .
Vše by bylo v pořádku, pokud existuje pouze několik úrovní těchto potomků a počet je do tuctu, ale pokud je úrovní více než 5 a jsou zde již desítky potomků, mohou nastat problémy. Podívejme se, jak jsou napsány (a fungují) tradiční možnosti vyhledávání ve stromu. Nejprve však určíme, které uzly budou pro náš výzkum nejzajímavější.
Většina "hluboký" podstromy:
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}
...Většina "široký" podstromy:
...
SELECT
path[1] id
, count(*)
FROM
T
GROUP BY
1
ORDER BY
2 DESC;id | count
------------
5300 | 30
450 | 28
1239 | 27
1573 | 25
Pro tyto dotazy jsme použili typické rekurzivní JOIN:
Samozřejmě s tímto modelem požadavku počet iterací bude odpovídat celkovému počtu potomků (a je jich několik desítek), což může vyžadovat značné prostředky a v důsledku toho i čas.
Podívejme se na „nejširší“ podstrom:
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;
Podle očekávání jsme našli všech 30 záznamů. Ale věnovali tomu 60 % celkového času – protože také provedli 30 vyhledávání v indexu. Je možné udělat méně?
Hromadná korektura podle indexu
Musíme vytvořit samostatný indexový dotaz pro každý uzel? Ukazuje se, že ne - můžeme číst z indexu pomocí několika tlačítek najednou v jednom hovoru přes = ANY(array).
A v každé takové skupině identifikátorů můžeme vzít všechna ID nalezená v předchozím kroku jako „uzly“. To znamená, že při každém dalším kroku budeme hledat všechny potomky určité úrovně najednou.
Jen, tady je problém, v rekurzivním výběru nemůžete přistupovat k sobě samému ve vnořeném dotazu, ale musíme nějak vybrat jen to, co bylo nalezeno na předchozí úrovni... Ukazuje se, že není možné udělat vnořený dotaz pro celý výběr, ale pro jeho konkrétní pole to možné je. A toto pole může být také pole – což je to, co musíme použít ANY.
Zní to trochu bláznivě, ale v diagramu je vše jednoduché.
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 tady to nejdůležitější není ani vyhrát 1.5krát v časea že jsme odečetli méně vyrovnávacích pamětí, protože máme pouze 5 volání indexu místo 30!
Dodatečným bonusem je skutečnost, že po závěrečném unnest zůstanou identifikátory seřazeny podle „úrovní“.
Uzel znamení
Další úvaha, která pomůže zlepšit výkon, je − "listy" nemohou mít děti, to znamená, že pro ně není vůbec potřeba dívat se „dolů“. Ve formulaci našeho úkolu to znamená, že pokud jsme sledovali řetězec oddělení a dostali se k zaměstnanci, není třeba se po této větvi rozhlížet.
Vstupme do našeho stolu další boolean-pole, který nám okamžitě řekne, zda je tento konkrétní záznam v našem stromě „uzel“ – tedy zda vůbec může mít potomky.
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 мс.Skvělý! Ukazuje se, že pouze o něco více než 30 % všech prvků stromu má potomky.
Nyní použijeme trochu jinou mechaniku - připojení k rekurzivní části skrz LATERAL, což nám umožní okamžitý přístup k polím rekurzivní „tabulky“ a použití agregační funkce s filtrační podmínkou založenou na uzlu ke snížení sady klíčů:
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;
Podařilo se nám snížit další volání indexu a vyhrál více než 2krát v objemu zkorigovat.
#2. Vraťme se ke kořenům
Tento algoritmus bude užitečný, pokud potřebujete shromáždit záznamy pro všechny prvky „ve stromě“, a zároveň zachovat informace o tom, který zdrojový list (a s jakými indikátory) způsobil, že byl zahrnut do vzorku – například pro generování souhrnné zprávy. s agregací do uzlů.
To, co následuje, by mělo být bráno pouze jako důkaz koncepce, protože požadavek se ukazuje jako velmi těžkopádný. Ale pokud dominuje vaší databázi, měli byste přemýšlet o použití podobných technik.
Začněme několika jednoduchými prohlášeními:
- Stejný záznam z databáze Nejlepší je si to přečíst jednou.
- Záznamy z databáze Je efektivnější číst v dávkáchnež sám.
Nyní se pokusíme vytvořit požadavek, který potřebujeme.
Krok 1
Je zřejmé, že při inicializaci rekurze (kde bychom bez ní byli!) budeme muset odečíst záznamy samotných listů na základě sady počátečních identifikátorů:
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
...
Pokud by se někomu zdálo divné, že „set“ je uložen jako řetězec a ne jako pole, pak pro to existuje jednoduché vysvětlení. Pro struny je vestavěna agregační funkce „lepení“. string_agg, ale ne pro pole. I když ona .
Krok 2
Nyní bychom získali sadu ID sekcí, které bude třeba dále číst. Téměř vždy budou duplikovány v různých záznamech původního souboru - tak bychom to udělali seskupit je, při zachování informací o zdrojových listech.
Ale tady nás čekají tři problémy:
- "Subrekurzivní" část dotazu nemůže obsahovat agregační funkce s
GROUP BY. - Odkaz na rekurzivní „tabulku“ nemůže být ve vnořeném poddotazu.
- Požadavek v rekurzivní části nemůže obsahovat CTE.
Naštěstí se všechny tyto problémy dají celkem snadno obejít. Začněme od konce.
CTE v rekurzivní části
takhle ne funguje:
WITH RECURSIVE tree AS (
...
UNION ALL
WITH T (...)
SELECT ...
)A tak to funguje, závorky dělají rozdíl!
WITH RECURSIVE tree AS (
...
UNION ALL
(
WITH T (...)
SELECT ...
)
)Vnořený dotaz proti rekurzivní "tabulce"
Hmm... V dílčím dotazu nelze získat přístup k rekurzivnímu CTE. Ale mohlo by to být uvnitř CTE! A vnořený požadavek již může přistupovat k tomuto CTE!
GROUP BY vnitřní rekurze
Je to nepříjemné, ale... Máme jednoduchý způsob, jak napodobit GROUP BY pomocí DISTINCT ON a funkce oken!
SELECT
(rec).pid id
, string_agg(chld::text, ',') chld
FROM
tree
WHERE
(rec).pid IS NOT NULL
GROUP BY 1 -- не работает!A takhle to funguje!
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 NULLNyní vidíme, proč se číselné ID změnilo na text - aby je bylo možné spojit a oddělit čárkami!
Krok 3
Na finále nám nic jiného nezbývá:
- čteme záznamy „sekcí“ na základě sady seskupených ID
- porovnáváme odečtené řezy se „sadami“ původních listů
- „rozbalte“ řetězec nastavení 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;
Zdroj: www.habr.com