Nei sistemi ERP complessi molte entità hanno una natura gerarchicaquando oggetti omogenei si allineano albero dei rapporti antenati-discendenti - questa è la struttura organizzativa dell'impresa (tutti questi rami, dipartimenti e gruppi di lavoro), il catalogo delle merci, le aree di lavoro e la geografia dei punti vendita,...
In realtà non ce n'è , dove di conseguenza non ci sarebbe alcuna gerarchia. Ma anche se non lavori “per l’azienda”, puoi comunque facilmente incontrare relazioni gerarchiche. È banale, anche il tuo albero genealogico o la planimetria dei locali di un centro commerciale hanno la stessa struttura.
Esistono molti modi per archiviare un albero di questo tipo in un DBMS, ma oggi ci concentreremo su una sola opzione:
CREATE TABLE hier(
id
integer
PRIMARY KEY
, pid
integer
REFERENCES hier
, data
json
);
CREATE INDEX ON hier(pid); -- не забываем, что FK не подразумевает автосоздание индекса, в отличие от PK
E mentre scruti nelle profondità della gerarchia, stai aspettando pazientemente di vedere quanto saranno [in]efficaci i tuoi modi “ingenui” di lavorare con una tale struttura.
Diamo un'occhiata ai problemi tipici che si presentano, alla loro implementazione in SQL e proviamo a migliorarne le prestazioni.
#1. Quanto è profonda la tana del coniglio?
Accettiamo, per chiarezza, che questa struttura rifletta la subordinazione dei dipartimenti nella struttura dell'organizzazione: dipartimenti, divisioni, settori, filiali, gruppi di lavoro... - come li chiamate.
Innanzitutto, generiamo il nostro "albero" di 10 elementi
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;Cominciamo con il compito più semplice: trovare tutti i dipendenti che lavorano in un settore specifico o in termini di gerarchia. trova tutti i figli di un nodo. Sarebbe bello anche cogliere la “profondità” del discendente... Tutto ciò può essere necessario, ad esempio, per costruire una sorta di .
Tutto andrebbe bene se ci fossero solo un paio di livelli di questi discendenti e il numero fosse compreso tra una dozzina, ma se ci sono più di 5 livelli e ci sono già dozzine di discendenti, potrebbero esserci problemi. Diamo un'occhiata a come vengono scritte (e funzionano) le tradizionali opzioni di ricerca down-the-tree. Ma prima determiniamo quali nodi saranno i più interessanti per la nostra ricerca.
Più "profondo" sottoalberi:
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}
...Più "Largo" sottoalberi:
...
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 queste query abbiamo utilizzato il tipico JOIN ricorsivo:
Ovviamente con questo modello di richiesta il numero di iterazioni corrisponderà al numero totale di discendenti (e ce ne sono diverse dozzine), e questo può richiedere risorse piuttosto significative e, di conseguenza, tempo.
Controlliamo il sottoalbero “più ampio”:
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;
Come previsto, abbiamo trovato tutti e 30 i record. Ma hanno dedicato a questo il 60% del tempo totale, perché hanno effettuato anche 30 ricerche nell'indice. È possibile fare di meno?
Correzione di bozze in blocco per indice
Dobbiamo creare una query di indice separata per ciascun nodo? Si scopre che no: possiamo leggere dall'indice utilizzando più tasti contemporaneamente in una chiamata via = ANY(array).
E in ciascuno di questi gruppi di identificatori possiamo prendere tutti gli ID trovati nel passaggio precedente come “nodi”. Cioè, ad ogni passo successivo lo faremo cercare tutti i discendenti di un certo livello contemporaneamente.
Solo che ecco il problema nella selezione ricorsiva, non è possibile accedere a se stesso in una query nidificata, ma dobbiamo in qualche modo selezionare solo ciò che è stato trovato al livello precedente... Risulta che è impossibile effettuare una query nidificata per l'intera selezione, ma per il suo campo specifico è possibile. E questo campo può anche essere un array, che è ciò che dobbiamo usare ANY.
Sembra un po' folle, ma nel diagramma tutto è semplice.
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;
E qui la cosa più importante non è nemmeno vincere 1.5 volte in tempo, e che abbiamo sottratto meno buffer, poiché abbiamo solo 5 chiamate all'indice invece di 30!
Un ulteriore vantaggio è il fatto che dopo l'unnest finale gli identificatori rimarranno ordinati per “livelli”.
Segno del nodo
La considerazione successiva che aiuterà a migliorare le prestazioni è − Le "foglie" non possono avere figli, cioè per loro non c'è affatto bisogno di guardare “in basso”. Nella formulazione del nostro compito, ciò significa che se seguiamo la catena dei dipartimenti e raggiungiamo un dipendente, non è necessario guardare oltre lungo questo ramo.
Entriamo nel nostro tavolo дополнительное boolean-campo, che ci dirà immediatamente se questa particolare voce nel nostro albero è un "nodo", cioè se può avere discendenti.
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 мс.Grande! Risulta che solo poco più del 30% di tutti gli elementi dell'albero hanno discendenti.
Ora utilizziamo una meccanica leggermente diversa: connessioni alla parte ricorsiva LATERAL, che ci permetterà di accedere immediatamente ai campi della “tabella” ricorsiva, e utilizzare una funzione aggregata con una condizione di filtraggio basata su un nodo per ridurre il set di chiavi:
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;
Siamo stati in grado di ridurre un'altra chiamata all'indice e ha vinto più di 2 volte in volume correggere le bozze.
#2. Torniamo alle radici
Questo algoritmo sarà utile se è necessario raccogliere record per tutti gli elementi "sull'albero", conservando allo stesso tempo le informazioni su quale foglio sorgente (e con quali indicatori) ne ha causato l'inclusione nel campione, ad esempio per generare un rapporto di riepilogo con aggregazione in nodi.
Quanto segue è da considerarsi esclusivamente come una prova di concetto, in quanto la richiesta risulta essere molto macchinosa. Ma se domina il tuo database, dovresti pensare di utilizzare tecniche simili.
Cominciamo con un paio di semplici affermazioni:
- Lo stesso record dal database È meglio leggerlo una volta sola.
- Record dal database È più efficiente leggere in batchche da solo.
Ora proviamo a costruire la richiesta di cui abbiamo bisogno.
Passo 1
Ovviamente, quando inizializziamo la ricorsione (dove saremmo senza di essa!) dovremo sottrarre i record delle foglie stesse in base all'insieme di identificatori iniziali:
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
...
Se a qualcuno sembra strano che il "set" sia memorizzato come una stringa e non come un array, allora c'è una spiegazione semplice per questo. Esiste una funzione incorporata di "incollaggio" di aggregazione per le stringhe string_agg, ma non per gli array. Anche se lei .
Passo 2
Ora otterremmo una serie di ID di sezione che dovranno essere letti ulteriormente. Quasi sempre verranno duplicati in diverse registrazioni del set originale, quindi lo faremmo anche noi raggrupparli, preservando le informazioni sulla fonte.
Ma qui ci aspettano tre guai:
- La parte "sottoricorsiva" della query non può contenere funzioni aggregate con
GROUP BY. - Un riferimento a una "tabella" ricorsiva non può essere contenuto in una sottoquery nidificata.
- Una richiesta nella parte ricorsiva non può contenere una CTE.
Fortunatamente, tutti questi problemi sono abbastanza facili da aggirare. Cominciamo dalla fine.
CTE nella parte ricorsiva
Ti piace questa no lavori:
WITH RECURSIVE tree AS (
...
UNION ALL
WITH T (...)
SELECT ...
)E così funziona, le parentesi fanno la differenza!
WITH RECURSIVE tree AS (
...
UNION ALL
(
WITH T (...)
SELECT ...
)
)Query nidificata su una "tabella" ricorsiva
Hmm... Non è possibile accedere a un CTE ricorsivo in una sottoquery. Ma potrebbe essere all'interno del CTE! E una richiesta nidificata può già accedere a questo CTE!
GRUPPO PER ricorsione interna
È spiacevole, ma... Abbiamo un modo semplice per emulare l'utilizzo di GROUP BY DISTINCT ON e funzioni della finestra!
SELECT
(rec).pid id
, string_agg(chld::text, ',') chld
FROM
tree
WHERE
(rec).pid IS NOT NULL
GROUP BY 1 -- не работает!Ed è così che funziona!
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 NULLOra vediamo perché gli ID numerici sono stati trasformati in testo - in modo che potessero essere uniti separati da virgole!
Passo 3
Per la finale non ci resta più nulla:
- leggiamo i record di “sezione” in base a una serie di ID raggruppati
- confrontiamo le sezioni sottratte con le “serie” dei fogli originali
- "espandere" la stringa impostata utilizzando
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;
Fonte: habr.com