Nei complessi sistemi ERP molte entità hanno una natura gerarchica, quando oggetti omogenei si dispongono in un albero di relazioni "genitore - figlio" — sia come struttura organizzativa dell'impresa (tutti quegli uffici, dipartimenti e gruppi di lavoro), sia come catalogo di prodotti, come aree di lavoro e come geografia dei punti vendita,…
Infatti, non esiste alcuna , in cui non sia presente qualche forma di gerarchia. Ma anche se non lavori "nel business", potresti comunque imbattersi facilmente in relazioni gerarchiche. Banale, anche il tuo albero genealogico o la pianta dei piani in un centro commerciale — costituiscono la stessa struttura.
Esistono molti modi per memorizzare tale albero in un DBMS, ma oggi ci concentreremo solo su una variante:
CREATE TABLE hier(
id
integer
PRIMARY KEY
, pid
integer
REFERENCES hier
, data
json
);
CREATE INDEX ON hier(pid); -- non dimentichiamoci che l'FK non implica la creazione automatica dell'indice, a differenza dell'PK
E mentre ti immergi nella profondità della gerarchia, essa attende pazientemente quanto saranno [non]efficaci i tuoi approcci "naïf" per gestire tale struttura.
Analizziamo i problemi tipici che si presentano, la loro implementazione in SQL e cerchiamo di migliorare le loro prestazioni.
#1. Насколько глубока кроличья нора?
Per chiarezza, supponiamo che questa struttura rifletta la subordinazione dei reparti nella struttura organizzativa: dipartimenti, divisioni, settori, filiali, gruppi di lavoro,… — come vuoi chiamarli.
Iniziamo generando il nostro 'albero' con 10K 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;Iniziamo con il compito più semplice: trovare tutti i dipendenti che lavorano all'interno di un settore specifico, o in termini gerarchici — trovare tutti i discendenti di un nodo. E sarebbe utile ottenere anche la "profondità" di un discendente... Tutto ciò può essere necessario, ad esempio, per costruire una .
Tutto sarebbe a posto se ci fossero solo un paio di livelli di discendenti, in un numero che si aggira intorno a una decina, ma se ci sono più di 5 livelli e decine di discendenti, potrebbero sorgere dei problemi. Esaminiamo come funzionano (e come si scrivono) le tradizionali opzioni di ricerca "verso il basso nell'albero". Ma prima definiamo quali nodi saranno i più interessanti per le nostre ricerche.
I più «profondi» sottodomini:
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}
...I più «ampî» sottodomini:
...
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 usato un tipico JOIN ricorsivo:
È evidente che con un tale modello di query il numero di iterazioni coinciderà con il totale dei discendenti (che sono diversi decine), e questo potrebbe richiedere risorse notevoli e, di conseguenza, tempo.
Controlliamo sul sottodominio "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 prevedevamo, abbiamo trovato tutte e 30 le voci. Ma abbiamo impiegato il 60% del tempo totale — perché abbiamo effettuato anche 30 ricerche sull'indice. E si può fare di meno?
Lettura massiva dall'indice
E per ogni nodo abbiamo bisogno di eseguire una query separata sull'indice? A quanto pare no — possiamo leggere dall'indice immediatamente su più chiavi in un'unica chiamata utilizzando = ANY(array).
E in ogni gruppo di identificatori possiamo prendere tutti gli ID trovati nel passo precedente per i "nodi". Cioè a ogni passo successivo cercheremo tutti i discendenti di un determinato livello.
Ma ecco il problema, nella selezione ricorsiva non si può riferire a se stessa in una subquery, e dobbiamo comunque selezionare solo quanto trovato nel livello precedente... Si scopre che è impossibile fare una subquery su tutta la selezione — ma su un suo campo specifico — sì. E questo campo può essere un array — cosa di cui abbiamo bisogno per usare ANY.
Sembra un po' strano, ma nello schema — è tutto semplice.
CON RECORSO T COME (
SELEZIONA
ARRAY[id] id$
DA
hier
DOVE
id = 5300
UNIONE TUTTO
SELEZIONA
ARRAY(
SELEZIONA
id
DA
hier
DOVE
pid = ANY(T.id$)
) id$
DA
T
DOVE
coalesce(id$, '{}') >> '{}' -- condizione di uscita dal ciclo - array vuoto
)
SELEZIONA
unnest(id$) id
DA
T; 
E qui la cosa più importante non è neanche il guadagno di 1,5 volte in tempo, ma il fatto che abbiamo ridotto il numero di buffer, poiché le chiamate all'indice sono solo 5 invece di 30!
Un ulteriore vantaggio è il fatto che dopo il unnest finale, gli identificatori rimarranno ordinati per "livelli".
Caratteristica del nodo
Il pensiero successivo che aiuterà a migliorare le prestazioni è che le "foglie" non possono avere figli, cioè non c'è bisogno di cercare "in giù" per loro. Nella formulazione del nostro problema, questo significa che se abbiamo seguito una catena di reparti e siamo arrivati a un dipendente, non c'è motivo di cercare ulteriormente in quel ramo.
Introduciamo nella nostra tabella un campo-campo, che ci dirà immediatamente se questo specifico record nel nostro albero è un "nodo" — cioè se possono esistere discendenti.
ALTER TABLE hier
AGGIUNGI COLONNA branch boolean;
AGGIORNA
hier T
SETTA
branch = TRUE
DOVE
ESISTE(
SELEZIONA
NULL
DA
hier
DOVE
pid = T.id
LIMIT 1
);
-- Richiesta eseguita con successo: 3033 righe modificate in 42 ms.Ottimo! Si scopre che solo poco più del 30% di tutti gli elementi dell'albero hanno discendenti.
Ora applichiamo una meccanica leggermente diversa — join con la parte ricorsiva tramite LATERALE, il che ci permetterà di accedere immediatamente ai campi della "tabella" ricorsiva, e utilizziamo una funzione aggregata con condizione di filtraggio per la caratteristica del nodo per ridurre il set di chiavi:
CON RECORSO T COME (
SELEZIONA
array_agg(id) id$
, array_agg(id) FILTRATO(DOVE branch) ns$
DA
hier
DOVE
id = 5300
UNIONE TUTTO
SELEZIONA
X.*
DA
T
JOIN LATERALE (
SELEZIONA
array_agg(id) id$
, array_agg(id) FILTRATO(DOVE branch) ns$
DA
hier
DOVE
pid = ANY(T.ns$)
) X
ON coalesce(T.ns$, '{}') >> '{}'
)
SELEZIONA
unnest(id$) id
DA
T; 
Siamo riusciti a ridurre un'altra chiamata all'indice e abbiamo guadagnato più di 2 volte in volume lettura.
#2. Вернемся к корням
Questo algoritmo sarà utile se hai bisogno di raccogliere registrazioni per tutti gli elementi "verso l'alto nell'albero", mantenendo comunque l'informazione su quale foglia originale (e con quali indicatori) ha causato il suo inserimento nel campionamento — ad esempio, per formare un rapporto aggregato sui nodi.
Il prosieguo va considerato esclusivamente come proof-of-concept, poiché la richiesta risulta piuttosto ingombrante. Ma se domina nel tuo database, vale la pena riflettere sull'applicazione di metodologie simili.
Iniziamo con un paio di affermazioni semplici:
- La stessa registrazione dal database è meglio leggerla solo una volta.
- Le registrazioni dal database sono più efficaci da leggere in "gruppo", piuttosto che singolarmente.
Ora proveremo a costruire la richiesta necessaria.
Passo 1
È ovvio che all'inizio della ricorsione (dove andremmo senza di essa!) dovremo estrarre le registrazioni delle foglie utilizzando un insieme di identificatori di partenza:
WITH RECURSIVE tree AS (
SELECT
rec -- questa è la registrazione intera della tabella
, id::text chld -- questo è il "set" delle foglie di partenza che portano qui
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 è sembrato strano che il "set" sia memorizzato come stringa e non come array, c'è una spiegazione semplice. Per le stringhe esiste una funzione aggregante "concatenante" incorporata string_agg, mentre per gli array non esiste. Anche se è .
Passo 2
Ora dobbiamo ottenere un insieme di ID delle sezioni che dobbiamo estrarre ulteriormente. Quasi sempre saranno duplicati in diverse registrazioni del set di partenza, quindi dovremmo raggrupparli, mantenendo nel contempo le informazioni sulle foglie di origine.
Ma qui ci aspettano tre spiacevoli sorprese:
- La parte "pre-ricorsiva" della richiesta non può contenere funzioni aggregate con
GROUP BY.. - L'accesso alla "tabella" ricorsiva non può trovarsi in una sottora richiesta.
- La richiesta nella parte ricorsiva non può contenere CTE.
Fortunatamente, tutti questi problemi possono essere aggirati abbastanza facilmente. Iniziamo dalla fine.
CTE nella parte ricorsiva
Ecco come non funziona:
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 ...
)
)Richiesta nidificata alla "tabella" ricorsiva
Hmm… L'accesso alla CTE ricorsiva non può essere in una sottora richiesta. Ma può essere all'interno della CTE! E una richiesta nidificata può già riferirsi a questa CTE!
GROUP BY all'interno della ricorsione
Sgradevole, ma… Abbiamo un modo semplice per simulare GROUP BY utilizzando DISTINCT ON e funzioni di finestra!
SELECT
(rec).pid id
, string_agg(chld::text, ',') chld
FROM
tree
WHERE
(rec).pid IS NOT NULL
GROUP BY 1 -- non funziona!Ma in questo modo — 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é l'ID numerico si è trasformato in testo: così da poterli unire tramite una virgola!
Passo 3
Per il finale ci rimane soltanto un piccolo passaggio:
- rivediamo le registrazioni delle "sezioni" per un insieme di ID raggruppati
- associamo le sezioni estratte con i "set" dei fogli di origine
- "espandiamo" la stringa-set con l'aiuto di
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
