Összetett ERP rendszerekben sok entitás hierarchikus jellegűamikor homogén tárgyak sorakoznak fel ős-utód kapcsolatok fája - ez a vállalkozás szervezeti felépítése (ezek az ágazatok, részlegek és munkacsoportok), és az árukatalógus, és a munkaterületek, valamint az értékesítési pontok földrajzi elhelyezkedése,...
Valójában nincs ilyen
Számos módja van egy ilyen fa DBMS-ben való tárolásának, de ma csak egy lehetőségre összpontosítunk:
CREATE TABLE hier(
id
integer
PRIMARY KEY
, pid
integer
REFERENCES hier
, data
json
);
CREATE INDEX ON hier(pid); -- не забываем, что FK не подразумевает автосоздание индекса, в отличие от PK
És miközben a hierarchia legmélyére pillant, türelmesen várja, hogy mennyire [hiányos] lesz az Ön „naiv” munkamódszere egy ilyen struktúrával.
Nézzük meg a felmerülő tipikus problémákat, azok megvalósítását SQL-ben, és próbáljuk meg javítani a teljesítményüket.
#1. Milyen mély a nyúllyuk?
A határozottság kedvéért fogadjuk el, hogy ez a struktúra tükrözi majd a szervezeti felépítésben az osztályok alárendeltségét: osztályok, részlegek, ágazatok, fiókok, munkacsoportok... - nevezzük akárhogy is.
Először is állítsuk elő a 10 XNUMX elemből álló „fánkat”.
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;
Kezdjük a legegyszerűbb feladattal – keressük meg az összes alkalmazottat, aki egy adott szektoron belül vagy hierarchiában dolgozik – megtalálja a csomópont összes gyermekét. Jó lenne a leszármazott „mélységét” is megszerezni... Minderre szükség lehet például valamiféle
Minden rendben lenne, ha ezeknek a leszármazottaknak csak néhány szintje van, és a szám egy tucaton belül van, de ha 5-nél több szint van, és már több tucat leszármazott van, akkor problémák adódhatnak. Nézzük meg, hogyan vannak megírva (és hogyan működnek) a hagyományos, a fán húzódó keresési lehetőségek. Először azonban határozzuk meg, mely csomópontok lesznek a legérdekesebbek kutatásunk szempontjából.
A legtöbbet "mély" részfák:
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}
...
A legtöbbet "széles" részfák:
...
SELECT
path[1] id
, count(*)
FROM
T
GROUP BY
1
ORDER BY
2 DESC;
id | count
------------
5300 | 30
450 | 28
1239 | 27
1573 | 25
Ezekhez a lekérdezésekhez a tipikus rekurzív JOIN:
Nyilvánvalóan ezzel a kérési modellel az iterációk száma megegyezik a leszármazottak teljes számával (és több tucat van belőlük), és ez meglehetősen jelentős erőforrásokat, és ennek következtében időt vehet igénybe.
Nézzük a „legszélesebb” részfát:
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;
Ahogy az várható volt, mind a 30 rekordot megtaláltuk. De a teljes idő 60%-át erre fordították – mert 30 keresést is végeztek az indexben. Lehetséges kevesebbet csinálni?
Tömeges lektorálás index szerint
Minden csomóponthoz külön indexlekérdezést kell készítenünk? Kiderül, hogy nem – olvashatjuk az indexből több billentyűt egyszerre használva egy hívás során keresztül = ANY(array)
.
És minden ilyen azonosítócsoportban „csomópontonként” vehetjük az előző lépésben talált összes azonosítót. Vagyis minden következő lépésnél megtesszük egy bizonyos szint összes leszármazottját keresse meg egyszerre.
Csak itt a probléma, rekurzív kijelölésben nem férhet hozzá önmagához egy beágyazott lekérdezésben, de valahogy csak azt kell kijelölnünk, amit az előző szinten találtunk... Kiderült, hogy a teljes kijelölésre nem lehet beágyazott lekérdezést készíteni, de az adott mezőre igen. Ez a mező pedig lehet tömb is – ezt kell használnunk ANY
.
Kicsit őrülten hangzik, de az ábrán minden egyszerű.
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;
És itt a legfontosabb dolog nem páros 1.5-szer nyerni időben, és hogy kevesebb puffert vontunk le, mivel 5 helyett csak 30 hívásunk van az indexre!
További bónusz, hogy a végső unnest után az azonosítók „szintek” sorrendben maradnak.
Csomópont jele
A következő szempont, amely segít a teljesítmény javításában, a − "leveleknek" nem lehet gyereke, vagyis számukra egyáltalán nem kell „lefelé” nézni. Feladatunk megfogalmazásában ez azt jelenti, hogy ha az osztályok láncolatát követve elértünk egy dolgozót, akkor ezen az ágon nem kell tovább nézni.
Lépjünk be az asztalunkba további boolean
-terület, amely azonnal megmondja, hogy a fánk adott bejegyzése „csomópont”-e – vagyis lehet-e egyáltalán leszármazottja.
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 мс.
Nagy! Kiderült, hogy az összes faelemnek csak valamivel több, mint 30%-ának van leszármazottja.
Most használjunk egy kicsit más mechanikát – a rekurzív részhez való csatlakozásokat LATERAL
, amely lehetővé teszi számunkra, hogy azonnal hozzáférjünk a rekurzív „tábla” mezőihez, és egy csomóponton alapuló szűrési feltétellel rendelkező összesítő függvényt használjunk a kulcskészlet csökkentésére:
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;
Még egy indexhívást tudtunk csökkenteni és kötetben több mint 2-szer nyert lektorált.
#2. Térjünk vissza a gyökerekhez
Ez az algoritmus akkor lesz hasznos, ha minden elemhez rekordokat kell gyűjtenie a „fán felfelé”, miközben megőrzi az információt arról, hogy melyik forráslap (és milyen mutatókkal) került be a mintába – például összefoglaló jelentés készítéséhez. csomópontokba történő összesítéssel.
A következőket kizárólag a koncepció bizonyítékának kell tekinteni, mivel a kérés nagyon nehézkesnek bizonyul. De ha ez uralja az adatbázist, érdemes hasonló technikák alkalmazásán gondolkodni.
Kezdjük néhány egyszerű kijelentéssel:
- Ugyanaz a rekord az adatbázisból A legjobb, ha egyszer elolvasod.
- Feljegyzések az adatbázisból Hatékonyabb a kötegelt olvasásmint egyedül.
Most próbáljuk meg felépíteni a szükséges kérést.
Lépés 1
Nyilvánvalóan a rekurzió inicializálásánál (hol lennénk nélküle!) maguknak a leveleknek a rekordjait kell kivonnunk a kezdeti azonosítók halmaza alapján:
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
...
Ha valakinek furcsának tűnt, hogy a „halmaz” karakterláncként és nem tömbként van tárolva, akkor ennek egyszerű magyarázata van. Van egy beépített összesítő „ragasztó” funkció a húrokhoz string_agg
, de nem tömbökhöz. Bár ő
Lépés 2
Most kapunk egy sor szakaszazonosítót, amelyet tovább kell olvasni. Szinte mindig az eredeti készlet különböző rekordjain lesznek megismételve – így mi is tennénk csoportosítsa őket, miközben megőrzi a forráslevelekkel kapcsolatos információkat.
De itt három baj vár ránk:
- A lekérdezés "szubrekurzív" része nem tartalmazhat aggregált függvényeket
GROUP BY
. - Egy rekurzív „táblázatra” való hivatkozás nem lehet beágyazott segédlekérdezésben.
- A rekurzív részben lévő kérés nem tartalmazhat CTE-t.
Szerencsére ezeket a problémákat nagyon könnyű megkerülni. Kezdjük a végéről.
CTE rekurzív részben
Itt van nincs dolgozó:
WITH RECURSIVE tree AS (
...
UNION ALL
WITH T (...)
SELECT ...
)
És így működik, a zárójelek jelentik a különbséget!
WITH RECURSIVE tree AS (
...
UNION ALL
(
WITH T (...)
SELECT ...
)
)
Beágyazott lekérdezés egy rekurzív "táblázathoz"
Hmm... Egy rekurzív CTE nem érhető el egy részlekérdezésben. De lehet, hogy a CTE-n belül van! És egy beágyazott kérés már hozzáférhet ehhez a CTE-hez!
GROUP BY belső rekurzió
Kellemetlen, de... Van egy egyszerű módszerünk a GROUP BY emulálására DISTINCT ON
és ablakfunkciók!
SELECT
(rec).pid id
, string_agg(chld::text, ',') chld
FROM
tree
WHERE
(rec).pid IS NOT NULL
GROUP BY 1 -- не работает!
És ez így működik!
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
Most látjuk, hogy a numerikus azonosító miért lett szöveggé alakítva - hogy vesszővel elválasztva össze lehessen őket kapcsolni!
Lépés 3
A döntőre nem maradt más hátra:
- csoportosított azonosítók halmaza alapján olvasunk „szakasz” rekordokat
- a kivont szakaszokat összehasonlítjuk az eredeti lapok „halmazaival”.
- „bontsa ki” a set-karakterláncot a segítségével
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;