Antipatróns de PostgreSQL: que profundidade ten o coello? imos pola xerarquía

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 áreas de automatización empresarial, onde non habería ningunha xerarquía como resultado. Pero aínda que non traballes "para o negocio", podes atopar facilmente relacións xerárquicas. É trillado, incluso a túa árbore xenealóxica ou o plano do local dun centro comercial é a mesma estrutura.

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 selección complexa baseada na lista de DNI destes empregados.

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;

[Mira explicar.tensor.ru]

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;

[Mira explicar.tensor.ru]

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;

[Mira explicar.tensor.ru]

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 fácil de implementar por si mesmo.

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:

1. A parte "subrecursiva" da consulta non pode conter funcións agregadas con GROUP BY.
2. Unha referencia a unha "táboa" recursiva non pode estar nunha subconsulta aniñada.
3. 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;

[Mira explicar.tensor.ru]

Fonte: www.habr.com