Dans les systèmes ERP complexes de nombreuses entités ont un caractère hiérarchiquelorsque des objets homogènes s'alignent arbre des relations ancêtres-descendants - c'est la structure organisationnelle de l'entreprise (toutes ces branches, départements et groupes de travail), et le catalogue de produits, et les domaines de travail, et la géographie des points de vente,...
En fait, il n'y en a pas , où il n’y aurait donc aucune hiérarchie. Mais même si vous ne travaillez pas « pour l’entreprise », vous pouvez quand même facilement rencontrer des relations hiérarchiques. C’est banal, même votre arbre généalogique ou le plan des locaux d’un centre commercial a la même structure.
Il existe de nombreuses façons de stocker un tel arbre dans un SGBD, mais aujourd'hui nous nous concentrerons sur une seule option :
CREATE TABLE hier(
id
integer
PRIMARY KEY
, pid
integer
REFERENCES hier
, data
json
);
CREATE INDEX ON hier(pid); -- не забываем, что FK не подразумевает автосоздание индекса, в отличие от PK
Et pendant que vous scrutez les profondeurs de la hiérarchie, elle attend patiemment de voir à quel point vos manières « naïves » de travailler avec une telle structure seront [in]efficaces.
Examinons les problèmes typiques qui surviennent, leur implémentation dans SQL et essayons d'améliorer leurs performances.
#1. Quelle est la profondeur du terrier du lapin ?
Admettons, pour être précis, que cette structure reflétera la subordination des départements dans la structure de l'organisation : départements, divisions, secteurs, branches, groupes de travail... - peu importe comment vous les appelez.
Tout d'abord, générons notre « arbre » de 10 XNUMX éléments
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;Commençons par la tâche la plus simple : trouver tous les salariés qui travaillent dans un secteur spécifique, ou en termes de hiérarchie. trouver tous les enfants d'un nœud. Ce serait aussi bien d'avoir la « profondeur » du descendant... Tout cela peut être nécessaire, par exemple, pour construire une sorte de .
Tout irait bien s'il n'y avait que quelques niveaux de ces descendants et que leur nombre était inférieur à une douzaine, mais s'il y avait plus de 5 niveaux et qu'il y avait déjà des dizaines de descendants, des problèmes pourraient survenir. Voyons comment les options de recherche traditionnelles dans l'arborescence sont écrites (et fonctionnent). Mais d’abord, déterminons quels nœuds seront les plus intéressants pour notre recherche.
Plus "profond" sous-arbres :
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}
...Plus "large" sous-arbres :
...
SELECT
path[1] id
, count(*)
FROM
T
GROUP BY
1
ORDER BY
2 DESC;id | count
------------
5300 | 30
450 | 28
1239 | 27
1573 | 25
Pour ces requêtes, nous avons utilisé le type REJOINDRE récursive:
Évidemment, avec ce modèle de requête le nombre d'itérations correspondra au nombre total de descendants (et il y en a plusieurs dizaines), et cela peut prendre des ressources assez importantes, et par conséquent du temps.
Vérifions le sous-arbre « le plus large » :
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;
Comme prévu, nous avons trouvé les 30 enregistrements. Mais ils y ont consacré 60 % du temps total, car ils ont également effectué 30 recherches dans l'index. Est-il possible de faire moins ?
Relecture groupée par index
Devons-nous effectuer une requête d’index distincte pour chaque nœud ? Il s'avère que non - nous pouvons lire dans l'index utiliser plusieurs touches à la fois en un seul appel par = ANY(array).
Et dans chacun de ces groupes d'identifiants, nous pouvons prendre tous les identifiants trouvés à l'étape précédente par « nœuds ». Autrement dit, à chaque étape suivante, nous rechercher tous les descendants d'un certain niveau à la fois.
Seulement, voici le problème, en sélection récursive, vous ne pouvez pas accéder à lui-même dans une requête imbriquée, mais nous devons en quelque sorte sélectionner uniquement ce qui a été trouvé au niveau précédent... Il s'avère qu'il est impossible de faire une requête imbriquée pour l'ensemble de la sélection, mais pour son champ spécifique, c'est possible. Et ce champ peut aussi être un tableau - c'est ce que nous devons utiliser ANY.
Cela semble un peu fou, mais dans le schéma tout est simple.
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;
Et ici, le plus important n'est même pas gagner 1.5 fois dans le temps, et que nous avons soustrait moins de buffers, puisque nous n'avons que 5 appels à l'index au lieu de 30 !
Un bonus supplémentaire est le fait qu'après le désimbrication final, les identifiants resteront classés par « niveaux ».
Signe de nœud
La prochaine considération qui contribuera à améliorer les performances est - "les feuilles" ne peuvent pas avoir d'enfants, c'est-à-dire que pour eux, il n'est pas du tout nécessaire de regarder « en bas ». Dans la formulation de notre tâche, cela signifie que si nous suivons la chaîne des départements et atteignons un employé, alors il n'est pas nécessaire de chercher plus loin dans cette branche.
Entrons dans notre table supplémentaire boolean-domaine, ce qui nous dira immédiatement si cette entrée particulière dans notre arbre est un « nœud », c'est-à-dire si elle peut avoir des descendants.
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 мс.Super! Il s'avère que seulement un peu plus de 30 % de tous les éléments de l'arbre ont des descendants.
Utilisons maintenant une mécanique légèrement différente : les connexions à la partie récursive via LATERAL, ce qui nous permettra d'accéder immédiatement aux champs de la « table » récursive, et d'utiliser une fonction d'agrégation avec une condition de filtrage basée sur un nœud pour réduire l'ensemble des clés :
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;
Nous avons pu réduire un appel d'index supplémentaire et gagné plus de 2 fois en volume relire.
#2. Revenons aux racines
Cet algorithme sera utile si vous devez collecter des enregistrements pour tous les éléments « en haut de l'arborescence », tout en conservant des informations sur quelle feuille source (et avec quels indicateurs) a conduit à son inclusion dans l'échantillon - par exemple, pour générer un rapport de synthèse. avec agrégation en nœuds.
Ce qui suit doit être considéré uniquement comme une preuve de concept, car la demande s'avère très lourde. Mais s’il domine votre base de données, vous devriez penser à utiliser des techniques similaires.
Commençons par quelques déclarations simples :
- Le même enregistrement de la base de données Il est préférable de le lire une seule fois.
- Enregistrements de la base de données Il est plus efficace de lire par lotsque seul.
Essayons maintenant de construire la requête dont nous avons besoin.
Étape 1
Évidemment, lors de l'initialisation de la récursivité (où serions-nous sans elle !) nous devrons soustraire les enregistrements des feuilles elles-mêmes en fonction de l'ensemble des identifiants initiaux :
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
...
S'il semble étrange à quelqu'un que « l'ensemble » soit stocké sous forme de chaîne et non de tableau, alors il existe une explication simple à cela. Il existe une fonction d'agrégation de « collage » intégrée pour les chaînes string_agg, mais pas pour les tableaux. Même si elle .
Étape 2
Nous obtiendrons maintenant un ensemble d’identifiants de section qui devront être lus plus en détail. Presque toujours, ils seront dupliqués dans différents enregistrements de l'ensemble d'origine - nous les regrouper, tout en préservant les informations sur les feuilles sources.
Mais ici, trois problèmes nous attendent :
- La partie « subrécursive » de la requête ne peut pas contenir de fonctions d'agrégation avec
GROUP BY. - Une référence à une « table » récursive ne peut pas se trouver dans une sous-requête imbriquée.
- Une requête dans la partie récursive ne peut pas contenir de CTE.
Heureusement, tous ces problèmes sont assez faciles à contourner. Commençons par la fin.
CTE en partie récursive
comme ça aucun travaux:
WITH RECURSIVE tree AS (
...
UNION ALL
WITH T (...)
SELECT ...
)Et ça marche, les parenthèses font la différence !
WITH RECURSIVE tree AS (
...
UNION ALL
(
WITH T (...)
SELECT ...
)
)Requête imbriquée sur une "table" récursive
Hmm... Un CTE récursif n'est pas accessible dans une sous-requête. Mais cela pourrait être à l’intérieur du CTE ! Et une requête imbriquée peut déjà accéder à ce CTE !
GROUP BY à l'intérieur de la récursivité
C'est désagréable, mais... Nous avons un moyen simple d'émuler GROUP BY en utilisant DISTINCT ON et fonctions de fenêtre !
SELECT
(rec).pid id
, string_agg(chld::text, ',') chld
FROM
tree
WHERE
(rec).pid IS NOT NULL
GROUP BY 1 -- не работает!Et voilà comment ça marche !
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 NULLNous voyons maintenant pourquoi l'identifiant numérique a été transformé en texte - afin qu'ils puissent être réunis, séparés par des virgules !
Étape 3
Pour la finale il ne nous reste plus rien :
- nous lisons les enregistrements de « section » en fonction d'un ensemble d'identifiants regroupés
- on compare les sections soustraites avec les « ensembles » des feuilles originales
- "développez" la chaîne d'ensemble en utilisant
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;
Source: habr.com