En sistemes ERP complexos moltes entitats tenen un caràcter jeràrquicquan s'alineen objectes homogenis arbre de les relacions avantpassats-descendents - aquesta és l'estructura organitzativa de l'empresa (totes aquestes branques, departaments i grups de treball), i el catàleg de béns, i àrees de treball, i la geografia dels punts de venda,...
De fet, no n'hi ha cap , on no hi hauria cap jerarquia com a resultat. Però fins i tot si no treballeu "per al negoci", podeu trobar fàcilment relacions jeràrquiques. És trillat, fins i tot el vostre arbre genealògic o el vostre plànol de locals en un centre comercial és la mateixa estructura.
Hi ha moltes maneres d'emmagatzemar aquest arbre en un SGBD, però avui ens centrarem només en una opció:
CREATE TABLE hier(
id
integer
PRIMARY KEY
, pid
integer
REFERENCES hier
, data
json
);
CREATE INDEX ON hier(pid); -- не забываем, что FK не подразумевает автосоздание индекса, в отличие от PK
I mentre esteu mirant a les profunditats de la jerarquia, s'està esperant pacientment per veure com seran [in]eficaços les vostres maneres "ingenues" de treballar amb aquesta estructura.
Vegem els problemes típics que sorgeixen, la seva implementació en SQL i intentem millorar-ne el rendiment.
#1. Quina profunditat té el forat del conill?
Acceptem, per a certesa, que aquesta estructura reflectirà la subordinació dels departaments en l'estructura de l'organització: departaments, divisions, sectors, oficines, grups de treball... - com els digueu.
Primer, generem el nostre "arbre" de 10K elements
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;Comencem per la tasca més senzilla: trobar tots els empleats que treballen dins d'un sector específic o en termes de jerarquia. trobar tots els fills d'un node. També estaria bé aconseguir la “profunditat” del descendent... Tot això pot ser necessari, per exemple, per construir algun tipus de .
Tot aniria bé si només hi ha un parell de nivells d'aquests descendents i el nombre és d'una dotzena, però si hi ha més de 5 nivells, i ja hi ha desenes de descendents, pot haver-hi problemes. Vegem com s'escriuen (i funcionen) les opcions de cerca tradicionals a l'arbre. Però primer, determinem quins nodes seran els més interessants per a la nostra investigació.
La majoria "profund" subarbres:
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}
...La majoria "ample" subarbres:
...
SELECT
path[1] id
, count(*)
FROM
T
GROUP BY
1
ORDER BY
2 DESC;id | count
------------
5300 | 30
450 | 28
1239 | 27
1573 | 25
Per a aquestes consultes hem utilitzat el típic JOIN recursiu:
Evidentment, amb aquest model de petició el nombre d'iteracions coincidirà amb el nombre total de descendents (i n'hi ha diverses desenes), i això pot requerir recursos força importants i, com a resultat, temps.
Comprovem el subarbre "més ample":
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;
Com era d'esperar, hem trobat els 30 registres. Però van dedicar el 60% del temps total a això, perquè també van fer 30 cerques a l'índex. És possible fer menys?
Correcció massiva per índex
Hem de fer una consulta d'índex independent per a cada node? Resulta que no, podem llegir de l'índex utilitzant diverses tecles alhora en una trucada via = ANY(array).
I en cada grup d'identificadors podem agafar tots els identificadors que es troben al pas anterior per "nodes". És a dir, en cada pas següent ho farem buscar tots els descendents d'un cert nivell alhora.
Només, aquí està el problema, en la selecció recursiva, no podeu accedir a si mateix en una consulta imbricada, però d'alguna manera hem de seleccionar només allò que s'ha trobat al nivell anterior... Resulta que és impossible fer una consulta imbricada per a tota la selecció, però per al seu camp concret és possible. I aquest camp també pot ser una matriu, que és el que hem d'utilitzar ANY.
Sembla una mica boig, però al diagrama tot és senzill.
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;
I aquí el més important no és ni tan sols guanyar 1.5 vegades en el temps, i que hem restat menys buffers, ja que només tenim 5 trucades a l'índex en lloc de 30!
Un avantatge addicional és el fet que després de l'anada final, els identificadors romandran ordenats per "nivells".
Signe del node
La següent consideració que ajudarà a millorar el rendiment és − "Les fulles" no poden tenir fills, és a dir, per a ells no cal mirar cap avall. En la formulació de la nostra tasca, això vol dir que si seguim la cadena de departaments i arribem a un empleat, llavors no cal mirar més en aquesta branca.
Entrem a la nostra taula addicionals boolean-camp, que ens dirà immediatament si aquesta entrada en particular del nostre arbre és un "node", és a dir, si pot tenir descendents.
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 мс.Genial! Resulta que només una mica més del 30% de tots els elements de l'arbre tenen descendència.
Ara fem servir una mecànica lleugerament diferent: connexions a la part recursiva LATERAL, que ens permetrà accedir immediatament als camps de la "taula" recursiva i utilitzar una funció agregada amb una condició de filtrat basada en un node per reduir el conjunt de claus:
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;
Hem pogut reduir una trucada d'índex més i guanyat més de 2 vegades en volum corregit.
#2. Tornem a les arrels
Aquest algorisme us serà útil si necessiteu recopilar registres de tots els elements "amunt de l'arbre", mentre conserveu informació sobre quin full d'origen (i amb quins indicadors) va fer que s'inclogués a la mostra, per exemple, per generar un informe resum. amb l'agregació en nodes.
El que segueix s'ha de prendre únicament com una prova de concepte, ja que la sol·licitud resulta molt feixuga. Però si domina la vostra base de dades, hauríeu de pensar en utilitzar tècniques similars.
Comencem amb un parell d'afirmacions senzilles:
- El mateix registre de la base de dades El millor és llegir-lo només una vegada.
- Registres de la base de dades És més eficient llegir per lotsque sol.
Ara intentem construir la sol·licitud que necessitem.
Pas 1
Òbviament, en inicialitzar la recursivitat (on estaríem sense ella!) haurem de restar els registres de les mateixes fulles en funció del conjunt d'identificadors inicials:
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
...
Si a algú li va semblar estrany que el "conjunt" s'emmagatzemi com una cadena i no com una matriu, hi ha una explicació senzilla per a això. Hi ha una funció d'"enganxament" d'agregació integrada per a les cordes string_agg, però no per a matrius. Encara que ella .
Pas 2
Ara obtindríem un conjunt d'identificacions de secció que caldrà llegir més endavant. Gairebé sempre es duplicaran en diferents registres del conjunt original, així ho faríem agrupar-los, tot conservant la informació sobre les fulles font.
Però aquí ens esperen tres problemes:
- La part "subrecursiva" de la consulta no pot contenir funcions agregades amb
GROUP BY. - Una referència a una "taula" recursiva no pot estar en una subconsulta imbricada.
- Una sol·licitud a la part recursiva no pot contenir un CTE.
Afortunadament, tots aquests problemes són bastant fàcils de solucionar. Comencem pel final.
CTE en part recursiva
Aquí sí no obres:
WITH RECURSIVE tree AS (
...
UNION ALL
WITH T (...)
SELECT ...
)I així funciona, els parèntesis marquen la diferència!
WITH RECURSIVE tree AS (
...
UNION ALL
(
WITH T (...)
SELECT ...
)
)Consulta imbricada contra una "taula" recursiva
Hmm... No es pot accedir a un CTE recursiu en una subconsulta. Però podria ser dins del CTE! I una sol·licitud imbricada ja pot accedir a aquest CTE!
GROUP BY dins de la recursió
És desagradable, però... Tenim una manera senzilla d'emular GROUP BY utilitzant DISTINCT ON i funcions de finestra!
SELECT
(rec).pid id
, string_agg(chld::text, ',') chld
FROM
tree
WHERE
(rec).pid IS NOT NULL
GROUP BY 1 -- не работает!I així és com funciona!
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 NULLAra veiem per què l'identificador numèric es va convertir en text, de manera que es poguessin unir separats per comes!
Pas 3
Per a la final no ens queda res:
- llegim registres de "secció" basats en un conjunt d'identificacions agrupades
- comparem les seccions restants amb els “conjunts” dels fulls originals
- "expandeix" la cadena de definició utilitzant
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;
Font: www.habr.com