Em sistemas ERP complexos muitas entidades têm uma natureza hierárquicaquando objetos homogêneos se alinham árvore de relacionamentos ancestrais-descendentes - esta é a estrutura organizacional da empresa (todas essas filiais, departamentos e grupos de trabalho), e o catálogo de mercadorias, e áreas de trabalho, e a geografia dos pontos de venda,...
Na verdade, não há nenhum , onde não haveria nenhuma hierarquia como resultado. Mas mesmo que você não trabalhe “para o negócio”, ainda poderá encontrar facilmente relacionamentos hierárquicos. É banal, até mesmo a sua árvore genealógica ou a planta das instalações de um shopping center têm a mesma estrutura.
Existem muitas maneiras de armazenar tal árvore em um SGBD, mas hoje vamos nos concentrar em apenas uma opção:
CREATE TABLE hier(
id
integer
PRIMARY KEY
, pid
integer
REFERENCES hier
, data
json
);
CREATE INDEX ON hier(pid); -- не забываем, что FK не подразумевает автосоздание индекса, в отличие от PK
E enquanto você olha para as profundezas da hierarquia, ela espera pacientemente para ver quão [in]eficazes serão as suas formas “ingénuas” de trabalhar com tal estrutura.
Vejamos os problemas típicos que surgem, sua implementação em SQL e tentemos melhorar seu desempenho.
#1. Qual a profundidade da toca do coelho?
Aceitemos, para maior certeza, que esta estrutura refletirá a subordinação dos departamentos na estrutura da organização: departamentos, divisões, setores, filiais, grupos de trabalho... - como quer que você os chame.
Primeiro, vamos gerar nossa 'árvore' de 10 mil 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;Vamos começar pela tarefa mais simples - encontrar todos os funcionários que trabalham dentro de um setor específico, ou em termos de hierarquia - encontrar todos os filhos de um nó. Também seria bom obter a “profundidade” do descendente... Tudo isso pode ser necessário, por exemplo, para construir algum tipo de .
Tudo ficaria bem se houvesse apenas alguns níveis desses descendentes e o número estivesse dentro de uma dúzia, mas se houvesse mais de 5 níveis e já existissem dezenas de descendentes, pode haver problemas. Vejamos como as opções tradicionais de pesquisa descendente na árvore são escritas (e funcionam). Mas primeiro, vamos determinar quais nós serão mais interessantes para nossa pesquisa.
Mais "profundo" subárvores:
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}
...Mais "largo" subárvores:
...
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 essas consultas usamos o típico JOIN recursivo:
Obviamente, com este modelo de solicitação o número de iterações corresponderá ao número total de descendentes (e existem várias dezenas deles), e isso pode consumir recursos bastante significativos e, como resultado, tempo.
Vamos verificar a subárvore “mais larga”:
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 esperado, encontramos todos os 30 registros. Mas eles gastaram 60% do tempo total nisso – porque também fizeram 30 pesquisas no índice. É possível fazer menos?
Revisão em massa por índice
Precisamos fazer uma consulta de índice separada para cada nó? Acontece que não - podemos ler no índice usando várias teclas ao mesmo tempo em uma chamada via = ANY(array).
E em cada um desses grupos de identificadores podemos pegar todos os IDs encontrados na etapa anterior por “nós”. Ou seja, a cada passo seguinte iremos procure todos os descendentes de um determinado nível de uma só vez.
Só que aqui está o problema, na seleção recursiva, você não pode acessar a si mesmo em uma consulta aninhada, mas precisamos selecionar de alguma forma apenas o que foi encontrado no nível anterior... Acontece que é impossível fazer uma consulta aninhada para toda a seleção, mas para seu campo específico é possível. E esse campo também pode ser um array - que é o que precisamos usar ANY.
Parece um pouco maluco, mas no diagrama tudo é simples.
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 aqui o mais importante nem é ganhe 1.5 vezes no tempo, e subtraímos menos buffers, já que temos apenas 5 chamadas para o índice em vez de 30!
Um bônus adicional é o fato de que após o desaninhamento final, os identificadores permanecerão ordenados por “níveis”.
Sinal de nó
A próxima consideração que ajudará a melhorar o desempenho é - "folhas" não podem ter filhos, ou seja, para eles não há necessidade de olhar “para baixo”. Na formulação da nossa tarefa, isso significa que se seguirmos a cadeia de departamentos e chegarmos a um funcionário, não há necessidade de procurar mais neste ramo.
Vamos entrar em nossa mesa adicional boolean-campo, que nos dirá imediatamente se esta entrada específica em nossa árvore é um “nó” - isto é, se ela 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 мс.Ótimo! Acontece que apenas pouco mais de 30% de todos os elementos da árvore têm descendentes.
Agora vamos usar uma mecânica um pouco diferente - conexões com a parte recursiva através LATERAL, o que nos permitirá acessar imediatamente os campos da “tabela” recursiva e utilizar uma função agregada com condição de filtragem baseada em um nó para reduzir o conjunto de chaves:
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;
Conseguimos reduzir mais uma chamada de índice e ganhou mais de 2 vezes em volume revisar.
#2. Vamos voltar às raízes
Este algoritmo será útil se você precisar coletar registros para todos os elementos “acima da árvore”, ao mesmo tempo que retém informações sobre qual planilha de origem (e com quais indicadores) fez com que ela fosse incluída na amostra - por exemplo, para gerar um relatório resumido com agregação em nós.
O que se segue deve ser tomado apenas como uma prova de conceito, uma vez que o pedido se revela muito complicado. Mas se dominar seu banco de dados, você deve pensar em usar técnicas semelhantes.
Vamos começar com algumas declarações simples:
- O mesmo registro do banco de dados É melhor ler apenas uma vez.
- Registros do banco de dados É mais eficiente ler em lotesdo que sozinho.
Agora vamos tentar construir a solicitação que precisamos.
Passo 1
Obviamente, ao inicializar a recursão (onde estaríamos sem ela!) teremos que subtrair os registros das próprias folhas com base no conjunto 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 pareceu estranho para alguém que o “conjunto” seja armazenado como uma string e não como um array, então há uma explicação simples para isso. Existe uma função integrada de agregação de “colagem” para strings string_agg, mas não para matrizes. Embora ela .
Passo 2
Agora obteríamos um conjunto de IDs de seção que precisarão ser lidos mais detalhadamente. Quase sempre eles serão duplicados em registros diferentes do conjunto original - então gostaríamos agrupe-os, preservando informações sobre as folhas de origem.
Mas aqui três problemas nos aguardam:
- A parte "subrecursiva" da consulta não pode conter funções agregadas com
GROUP BY. - Uma referência a uma “tabela” recursiva não pode estar em uma subconsulta aninhada.
- Uma solicitação na parte recursiva não pode conter um CTE.
Felizmente, todos esses problemas são bastante fáceis de solucionar. Vamos começar do fim.
CTE na parte recursiva
Aqui tão não funciona:
WITH RECURSIVE tree AS (
...
UNION ALL
WITH T (...)
SELECT ...
)E assim funciona, os parênteses fazem a diferença!
WITH RECURSIVE tree AS (
...
UNION ALL
(
WITH T (...)
SELECT ...
)
)Consulta aninhada em uma "tabela" recursiva
Hmm... Um CTE recursivo não pode ser acessado em uma subconsulta. Mas pode ser dentro do CTE! E uma solicitação aninhada já pode acessar esse CTE!
GROUP BY dentro da recursão
É desagradável, mas... Temos uma maneira simples de emular GROUP BY usando DISTINCT ON e funções de janela!
SELECT
(rec).pid id
, string_agg(chld::text, ',') chld
FROM
tree
WHERE
(rec).pid IS NOT NULL
GROUP BY 1 -- не работает!E é assim que 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 NULLAgora vemos porque o ID numérico foi transformado em texto - para que pudessem ser unidos separados por vírgulas!
Passo 3
Para a final não nos resta mais nada:
- lemos registros de “seção” com base em um conjunto de IDs agrupados
- comparamos as seções subtraídas com os “conjuntos” das folhas originais
- “expandir” a string definida 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;
Fonte: habr.com