En sistemas ERP complexos moitas entidades teñen un carácter xerárquicocando se aliñan obxectos homoxéneos árbore das relacións antepasados-descendentes - Esta é a estrutura organizativa da empresa (todas estas ramas, departamentos e grupos de traballo), e o catálogo de bens e áreas de traballo, e a xeografía dos puntos de venda,...
De feito, non hai ningunha
Hai moitas formas de almacenar tal árbore nun DBMS, pero hoxe centrarémonos só nunha opción:
CREATE TABLE hier(
id
integer
PRIMARY KEY
, pid
integer
REFERENCES hier
, data
json
);
CREATE INDEX ON hier(pid); -- не забываем, что FK не подразумевает автосоздание индекса, в отличие от PK
E mentres estás mirando as profundidades da xerarquía, estás a esperar pacientemente para ver o [in]eficaz que serán as túas formas "inxenuas" de traballar con tal estrutura.
Vexamos os problemas típicos que xorden, a súa implementación en SQL e intentemos mellorar o seu rendemento.
#1. Que profundidade ten o coello?
Aceptemos, para a certeza, que esta estrutura reflectirá a subordinación dos departamentos na estrutura da organización: departamentos, divisións, sectores, ramas, grupos de traballo... -como se chame.
Primeiro, imos xerar a nosa "árbore" de 10K elementos
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;
Comecemos pola tarefa máis sinxela: atopar todos os empregados que traballen nun sector específico ou en termos de xerarquía. atopar todos os fillos dun nodo. Tamén sería bo conseguir a “profundidade” do descendente... Todo isto pode ser necesario, por exemplo, para construír algún tipo de
Todo estaría ben se só hai un par de niveis destes descendentes e o número está dentro dunha ducia, pero se hai máis de 5 niveis, e xa hai ducias de descendentes, pode haber problemas. Vexamos como se escriben (e funcionan) as opcións tradicionais de busca na árbore. Pero primeiro, imos determinar cales nodos serán os máis interesantes para a nosa investigación.
O máis "profundo" subárboles:
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}
...
O máis "ancho" subárboles:
...
SELECT
path[1] id
, count(*)
FROM
T
GROUP BY
1
ORDER BY
2 DESC;
id | count
------------
5300 | 30
450 | 28
1239 | 27
1573 | 25
Para estas consultas utilizamos o típico JOIN recursivo:
Obviamente, con este modelo de solicitude o número de iteracións coincidirá co número total de descendentes (e hai varias ducias deles), e isto pode levar recursos bastante importantes e, como resultado, tempo.
Vexamos a subárbore "máis ampla":
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;
Como era de esperar, atopamos os 30 rexistros. Pero dedicaron o 60% do tempo total a isto, porque tamén fixeron 30 buscas no índice. É posible facer menos?
Corrección masiva por índice
Necesitamos facer unha consulta de índice separada para cada nodo? Acontece que non - podemos ler desde o índice usando varias teclas á vez nunha chamada coa axuda = ANY(array)
.
E en cada un destes grupos de identificadores podemos tomar todos os ID atopados no paso anterior por "nodos". É dicir, en cada seguinte paso faremos buscar todos os descendentes dun certo nivel á vez.
Só, aquí está o problema, na selección recursiva, non pode acceder a si mesmo nunha consulta aniñada, pero necesitamos seleccionar dalgún xeito só o que se atopou no nivel anterior... Resulta que é imposible facer unha consulta aniñada para toda a selección, pero para o seu campo específico é posible. E este campo tamén pode ser unha matriz, que é o que necesitamos usar ANY
.
Parece un pouco tolo, pero no diagrama todo é sinxelo.
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 aquí o máis importante nin sequera gañar 1.5 veces no tempo, e que restamos menos buffers, xa que só temos 5 chamadas ao índice en lugar de 30!
Unha bonificación adicional é o feito de que, despois do desencofrado final, os identificadores permanecerán ordenados por "niveis".
Sinal de nodo
A seguinte consideración que axudará a mellorar o rendemento é − as "follas" non poden ter fillos, é dicir, para eles non hai que mirar "abaixo" en absoluto. Na formulación da nosa tarefa, isto significa que se seguimos a cadea de departamentos e chegamos a un empregado, non hai que buscar máis adiante nesta rama.
Imos entrar na nosa mesa adicional boolean
-campo, que nos indicará inmediatamente se esta entrada particular da nosa árbore é un "nodo", é dicir, se pode ter descendentes.
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 só un pouco máis do 30% de todos os elementos da árbore teñen descendentes.
Agora imos usar unha mecánica lixeiramente diferente: conexións coa parte recursiva a través LATERAL
, que nos permitirá acceder inmediatamente aos campos da "táboa" recursiva e utilizar unha función agregada cunha condición de filtrado baseada nun nodo para reducir o conxunto de claves:
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;
Puidemos reducir unha chamada de índice máis e gañou máis de 2 veces en volume corrixir.
#2. Volvamos ás raíces
Este algoritmo será útil se precisa recoller rexistros de todos os elementos "arriba da árbore", mantendo a información sobre que folla de orixe (e con que indicadores) fixo que se incluíse na mostra, por exemplo, para xerar un informe resumo. con agregación en nodos.
O que segue debe ser tomado unicamente como unha proba de concepto, xa que a solicitude resulta moi engorrosa. Pero se domina a túa base de datos, deberías pensar en usar técnicas similares.
Comecemos cun par de afirmacións sinxelas:
- O mesmo rexistro da base de datos É mellor lelo só unha vez.
- Rexistros da base de datos É máis eficiente ler por lotesque só.
Agora imos tentar construír a solicitude que necesitamos.
Paso 1
Obviamente, ao inicializar a recursión (onde estaríamos sen ela!) teremos que restar os rexistros das propias follas en función do conxunto de identificadores iniciais:
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 alguén pensou estraño que o "conxunto" se almacenase como unha cadea e non como unha matriz, entón hai unha explicación sinxela para isto. Hai unha función de "pegado" de agregación incorporada para as cadeas string_agg
, pero non para matrices. Aínda que ela
Paso 2
Agora obteriamos un conxunto de ID de sección que haberá que ler máis adiante. Case sempre duplicaranse en diferentes rexistros do conxunto orixinal, así o fariamos agrupalos, conservando a información sobre as follas de orixe.
Pero aquí nos esperan tres problemas:
- A parte "subrecursiva" da consulta non pode conter funcións agregadas con
GROUP BY
. - Unha referencia a unha "táboa" recursiva non pode estar nunha subconsulta aniñada.
- Unha solicitude na parte recursiva non pode conter un CTE.
Afortunadamente, todos estes problemas son bastante fáciles de solucionar. Comecemos polo final.
CTE en parte recursiva
Entón non traballando:
WITH RECURSIVE tree AS (
...
UNION ALL
WITH T (...)
SELECT ...
)
E así funciona, os parénteses marcan a diferenza!
WITH RECURSIVE tree AS (
...
UNION ALL
(
WITH T (...)
SELECT ...
)
)
Consulta anidada contra unha "táboa" recursiva
Hmm... Non se pode acceder a un CTE recursivo nunha subconsulta. Pero podería estar dentro do CTE! E unha solicitude aniñada xa pode acceder a este CTE!
GROUP BY dentro de recursividade
É desagradable, pero... Temos un xeito sinxelo de emular GROUP BY usando DISTINCT ON
e funcións de fiestra!
SELECT
(rec).pid id
, string_agg(chld::text, ',') chld
FROM
tree
WHERE
(rec).pid IS NOT NULL
GROUP BY 1 -- не работает!
E así é como 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 NULL
Agora vemos por que o ID numérico se converteu en texto, para que se poidan unir separados por comas.
Paso 3
Para a final non nos queda nada:
- lemos rexistros de "sección" baseados nun conxunto de ID agrupados
- comparamos as seccións subtraídas cos “conxuntos” das follas orixinais
- "expandir" o set-string usando
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;