Антишеми на PostgreSQL: Колку е длабока дупката за зајакот? ајде да поминеме низ хиерархијата

Во сложени ERP системи многу ентитети имаат хиерархиска природакога се редат хомогени предмети дрво на односите предок-потомок - ова е организациската структура на претпријатието (сите овие гранки, одделенија и работни групи), и каталогот на стоки, и областите на работа, и географијата на продажните места,...

Всушност, не постои области за бизнис автоматизација, каде што како резултат не би имало никаква хиерархија. Но, дури и ако не работите „за бизнисот“, сепак можете лесно да наидете на хиерархиски односи. Необично е, дури и вашето семејно стебло или планот на просториите во трговски центар се со иста структура.

Постојат многу начини за складирање на такво дрво во DBMS, но денес ќе се фокусираме на само една опција:

CREATE TABLE hier(
  id
    integer
      PRIMARY KEY
, pid
    integer
      REFERENCES hier
, data
    json
);

CREATE INDEX ON hier(pid); -- не забываем, что FK не подразумевает автосоздание индекса, в отличие от PK

И додека ѕиркате во длабочините на хиерархијата, трпеливо чека да видите колку вашите „наивни“ начини на работа со таква структура ќе бидат [не]ефективни.

Да ги погледнеме типичните проблеми што се појавуваат, нивната имплементација во SQL и да се обидеме да ги подобриме нивните перформанси.

#1. Колку длабока е зајачката дупка?

Ајде, со сигурност, да прифатиме дека оваа структура ќе ја одразува подреденоста на одделенијата во структурата на организацијата: одделенија, одделенија, сектори, гранки, работни групи... - како и да ги нарекувате.

Прво, да го генерираме нашето „дрво“ од 10K елементи

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;

Да почнеме со наједноставната задача - да ги најдеме сите вработени кои работат во одреден сектор, или во смисла на хиерархија - најдете ги сите деца од еден јазол. Исто така, би било убаво да се добие „длабочината“ на потомокот... Сето ова можеби е неопходно, на пример, да се изгради некој вид на комплексен избор врз основа на списокот на лични карти на овие вработени.

Сè би било добро ако има само неколку нивоа од овие потомци и бројот е во рамките на десетина, но ако има повеќе од 5 нивоа, а веќе има десетици потомци, може да има проблеми. Ајде да погледнеме како се напишани (и функционираат) традиционалните опции за пребарување низ дрвото. Но, прво, да одредиме кои јазли ќе бидат најинтересни за нашето истражување.

Најмногу "длабоко" поддрва:

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}
...

Најмногу "широк" поддрва:

...
SELECT
  path[1] id
, count(*)
FROM
  T
GROUP BY
  1
ORDER BY
  2 DESC;

id   | count
------------
5300 |   30
 450 |   28
1239 |   27
1573 |   25

За овие прашања го користевме типичното рекурзивен JOIN:


Очигледно, со овој модел на барање бројот на повторувања ќе одговара на вкупниот број на потомци (и има неколку десетици од нив), и ова може да потрае доста значителни ресурси и, како резултат на тоа, време.

Ајде да го провериме „најширокото“ поддрво:

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;

[погледнете на објаснување.tensor.ru]

Очекувано ги најдовме сите 30 записи. Но, тие потрошија 60% од вкупното време на ова - затоа што направија и 30 пребарувања во индексот. Дали е можно да се направи помалку?

Масовно лекторирање по индекс

Дали треба да направиме посебно индексно барање за секој јазол? Излегува дека не - можеме да прочитаме од индексот користејќи неколку копчиња одеднаш во еден повик со помош на = ANY(array).

И во секоја таква група на идентификатори можеме да ги земеме сите ID-и пронајдени во претходниот чекор по „јазли“. Тоа е, на секој следен чекор ние ќе побарајте ги сите потомци на одредено ниво одеднаш.

Само, тука е проблемот, во рекурзивен избор, не можете да си пристапите во вгнездено барање, но треба некако да го избереме само она што е пронајдено на претходното ниво... Излегува дека е невозможно да се направи вгнездено барање за целиот избор, но за неговото специфично поле е можно. И ова поле може да биде и низа - што е она што треба да го користиме ANY.

Звучи малку лудо, но на дијаграмот сè е едноставно.

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;

[погледнете на објаснување.tensor.ru]

И тука најважното не е рамномерно победи 1.5 пати во времето, и дека одзедовме помалку бафери, бидејќи имаме само 5 повици до индексот наместо 30!

Дополнителен бонус е фактот што по конечното откачување, идентификаторите ќе останат подредени по „нивоа“.

Знак за јазол

Следното размислување што ќе помогне да се подобрат перформансите е − „листовите“ не можат да имаат деца, односно за нив воопшто нема потреба да гледаат „долу“. Во формулацијата на нашата задача, тоа значи дека ако го следевме синџирот на одделенија и стигнавме до вработен, тогаш нема потреба да гледаме понатаму по оваа гранка.

Ајде да влеземе во нашата маса дополнителни boolean-Поле, што веднаш ќе ни каже дали овој конкретен запис во нашето дрво е „јазол“ - односно дали воопшто може да има потомци.

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 мс.

Одлично! Излегува дека само малку повеќе од 30% од сите елементи на дрво имаат потомци.

Сега ајде да користиме малку поинаков механичар - врски со рекурзивниот дел преку LATERAL, што ќе ни овозможи веднаш да пристапиме до полињата на рекурзивната „табела“ и да користиме збирна функција со услов за филтрирање врз основа на јазол за да го намалиме множеството клучеви:

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;

[погледнете на објаснување.tensor.ru]

Успеавме да намалиме уште еден индексен повик и освои повеќе од 2 пати во обем лекторирани.

#2. Да се ​​вратиме на корените

Овој алгоритам ќе биде корисен ако треба да соберете записи за сите елементи „горе на дрвото“, притоа задржувајќи информации за тоа кој изворен лист (и со кои индикатори) го предизвикал тој да биде вклучен во примерокот - на пример, да генерира збирен извештај со агрегација во јазли.

Она што следи треба да се земе само како доказ за концепт, бидејќи барањето се покажува како многу незгодно. Но, ако доминира во вашата база на податоци, треба да размислите за користење слични техники.

Да почнеме со неколку едноставни изјави:

• Истиот запис од базата на податоци Најдобро е да го прочитате само еднаш.
• Записи од базата на податоци Поефикасно е да се чита во серииотколку сам.

Сега да се обидеме да го конструираме барањето што ни треба.

Чекор 1

Очигледно, при иницијализирање на рекурзијата (каде ќе бевме без неа!) ќе треба да ги одземеме записите на самите листови врз основа на множеството почетни идентификатори:

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
  ...

Ако некој мислеше дека е чудно што „множеството“ е зачувано како низа, а не како низа, тогаш има едноставно објаснување за ова. Има вградена функција за собирање „лепење“ за жици string_agg, но не и за низи. Иако таа лесно да се спроведе самостојно.

Чекор 2

Сега ќе добиеме збир на идентификатори на секции кои ќе треба да се прочитаат понатаму. Речиси секогаш тие ќе бидат дуплирани во различни записи од оригиналниот сет - така и ние би групирајте ги, притоа зачувувајќи ги информациите за изворните листови.

Но, тука не чекаат три неволји:

1. „Субрекурзивниот“ дел од барањето не може да содржи збирни функции со GROUP BY.
2. Референцата за рекурзивна „табела“ не може да биде во вгнездено подпрашање.
3. Барањето во рекурзивниот дел не може да содржи CTE.

За среќа, сите овие проблеми се прилично лесни за решавање. Да почнеме од крајот.

CTE во рекурзивен дел

Овде, така Нема работи:

WITH RECURSIVE tree AS (
  ...
UNION ALL
  WITH T (...)
  SELECT ...
)

И така функционира, заградите ја прават разликата!

WITH RECURSIVE tree AS (
  ...
UNION ALL
  (
    WITH T (...)
    SELECT ...
  )
)

Вгнездено барање против рекурзивна „табела“

Хм... Не може да се пристапи до рекурзивен CTE во подпрашање. Но, тоа може да биде во CTE! И вгнезденото барање веќе може да пристапи до овој CTE!

ГРУПА ПО внатре рекурзија

Непријатно е, но... Имаме едноставен начин да ја имитираме GROUP BY DISTINCT ON и функции на прозорци!

SELECT
  (rec).pid id
, string_agg(chld::text, ',') chld
FROM
  tree
WHERE
  (rec).pid IS NOT NULL
GROUP BY 1 -- не работает!

И вака функционира!

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

Сега гледаме зошто нумеричкиот ID е претворен во текст - за да може да се спојат, разделени со запирки!

Чекор 3

За финалето не ни преостанува ништо:

• читаме записи „секција“ врз основа на збир на групирани ID
• ги споредуваме одземените делови со „множествата“ на оригиналните листови
• „проширете ја“ низата со множества користејќи 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;

[погледнете на објаснување.tensor.ru]

Извор: www.habr.com