🥇PostgreSQL Антипатерни: колко дълбока е кр rabbit hole? ще разгледаме йерархията

В сложни ERP системи много сущности имат йерархична природа, когато хомогенни обекти се подреждат в дърво на отношенията "предшественик — наследник" — това е както организационната структура на предприятието (всички тези филиали, отдели и работни групи), така и каталог на стоки, и участъци от работа, и география на точки за продажба,…

Всъщност, няма ни една област на автоматизация на бизнеса, в която поне някаква йерархия да не се е появила като резултат. Но дори и ако не работите "в бизнеса", все пак можете лесно да се сблъскате с йерархични връзки. Просто, дори вашето родословно дърво или план на етажите в търговския център — същата структура.

Съществуват много начини за съхранение на такова дърво в СУБД, но днес ще се спрем на само един вариант:

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;

Да започнем с най-простата задача — да намерим всички служители, които работят в конкретен сектор, или в термини на йерархията — да намерим всички наследници на възела. А и "дълбочината" на наследника също не би била зле да получим… Всичко това може да е необходимо, например, за изграждането на някакъв сложен избор по списъка с ID на тези служители.

Всичко би било наред, ако тези потомци са само на няколко нива и количествено в рамките на десет, но ако нивата са над 5, а потомците вече са десетки — могат да възникнат проблеми. Нека видим как се пишат (и работят) традиционните варианти за търсене „надолу по дървото“. Но първо нека определим кои от възлите ще бъдат най-интересни за нашите изследвания.

Най-дълбоките поддеревья: С РЕКУРСИВНО T КАТО ( ИЗБЕРИ id , pid , МАСИВ[id] път ОТ hier КЪДЕ pid Е NULL СЪЮЗ ВСИЧКИ ИЗБЕРИ hier.id , hier.pid , T.path || hier.id ОТ T СВЪРЗАНО hier ON hier.pid = T.id ) ТАБЛИЦА T РЕД ПО реда на array_length(path, 1) СЛИВА;

id  | pid  | път
---------------------------------------------
7624 | 7623 | {7615,7620,7621,7622,7623,7624}
4995 | 4994 | {4983,4985,4988,4993,4994,4995}
4991 | 4990 | {4983,4985,4988,4989,4990,4991}
...

 Широки

Най-дълбоките ... ИЗБЕРИ path[1] id , брой(*) ОТ T ГРУПИРАНЕ ПО 1 РЕД ПО 2 СЛИВА; С РЕКУРСИВНО T КАТО ( ИЗБЕРИ id , pid , МАСИВ[id] път ОТ hier КЪДЕ pid Е NULL СЪЮЗ ВСИЧКИ ИЗБЕРИ hier.id , hier.pid , T.path || hier.id ОТ T СВЪРЗАНО hier ON hier.pid = T.id ) ТАБЛИЦА T РЕД ПО реда на array_length(path, 1) СЛИВА;

id   | брой
------------
5300 |   30
 450 |   28
1239 |   27
1573 |   25

За тези заявки използвахме типичен

рекурсивен JOIN Очевидно, при такава модел на заявката:

броят на итерациите ще отговаря на общия брой потомци (а те са няколко десетки), и това може да заема достатъчно значителни ресурси и, следователно, време. Нека проверим на най-широкото поддърво:

С РЕКУРСИВНО T КАТО ( ИЗБЕРИ id ОТ hier КЪДЕ id = 5300 СЪЮЗ ВСИЧКИ ИЗБЕРИ hier.id ОТ T СВЪРЗАНО hier ON hier.pid = T.id ) ТАБЛИЦА T;

[погледни на explain.tensor.ru]

Както и предполагахме, намерихме всичките 30 записа. Но за това изразходихме 60% от общото време — защото направихме и 30 търсения по индекса. А по-малко — може ли?

Масова изчитане по индекса

А за всяка такава група идентификатори можем да вземем всички намерени на предишната стъпка ID по „възлите“. Тоест на всяка следваща стъпка ще търсим веднага всички потомци на определено ниво.

Само, че нещото е, в рекурсивното избиране не може да се обърнеш към себе си във вложената заявка чрез , а ние всъщност трябва да отберем само това, което е намерено на предишно ниво... Оказва се, че направата на вложена заявка към цялата извадка е невъзможна, но към конкретно поле — е възможно. А това поле може да бъде и масив — което ни е необходимо за използване.

ANY Звучи малко налудничаво, но на схемата — всичко е просто..

Само по себе это вызывает трудности, поскольку в рекурсивной выборке нельзя ссылаться на саму себя в подзапросе., а нам нужно каким-то образом отобрать только то, что было найдено на предыдущем уровне… Оказывается, сделать вложенный запрос ко всей выборке — невозможно, но обратиться к конкретному полю — можно. Это поле может быть массивом — именно это нам и нужно для использования. ANY.

Это звучит несколько странно, но на схеме все выглядит просто.

С РЕКУРСИВЕН T AS (
  ИЗБЕРИ
    МАССИВ[id] id$
  ОТ
    hier
  КЪДЕ
    id = 5300
СЪЮЗ ВСИЧКИ
  ИЗБЕРИ
    МАССИВ(
      ИЗБЕРИ
        id
      ОТ
        hier
      КЪДЕ
        pid = ANY(T.id$)
    ) id$
  ОТ
    T
  КЪДЕ
    coalesce(id$, '{}') <> '{}' -- условие за изход от цикъл - празен масив
)
ИЗБЕРИ
  unnest(id$) id
ОТ
  T;

А тук най-важното не е дори печалбата от 1.5 пъти по време, а това, че по-малко са снижените буфери, тъй като имаме само 5 запитвания към индекса вместо 30!

Допълнителен бонус е фактът, че след финалния unnest идентификаторите ще останат подредени по "нивото".

Признак на възел

Следващата идея, която ще помогне за подобряване на производителността — при "листата" не може да има деца, тоест за тях не е необходимо да се търси "надолу" изобщо. В рамките на нашата задача това означава, че ако сме преминали по веригата на отдели и сме стигнали до служител, не е нужно да търсим по тази клонка.

Нека добавим в нашата таблица допълнително булев-поле, което ще ни казва веднага, дали тази конкретна записа в нашето дърво е "възел" — тоест, може ли изобщо да съществуват потомци.

ALTER TABLE hier
  ADD COLUMN branch boolean;

UPDATE
  hier T
SET
  branch = TRUE
КЪДЕ
  СЪЩЕСТВУВА(
    ИЗБЕРИ
      NULL
    ОТ
      hier
    КЪДЕ
      pid = T.id
    LIMIT 1
);
-- Запитването е успешно изпълнено: 3033 реда променени за 42 мс.

Страхотно! Оказва се, че имаме само малко над 30% от всички елементи на дървото, които имат потомци.

Сега ще приложим малко друга механика — свързване с рекурсивната част чрез LATERAL, което ще ни позволи веднага да се обърнем към полетата на рекурсивната "таблица", а агрегатната функция със условие за филтриране по признак на възел ще използваме за намаляване на набора от ключове:

С РЕКУРСИВЕН T AS (
  ИЗБЕРИ
    array_agg(id) id$
  , array_agg(id) FILTER(WHERE branch) ns$
  ОТ
    hier
  КЪДЕ
    id = 5300
СЪЮЗ ВСИЧКИ
  ИЗБЕРИ
    X.*
  ОТ
    T
  JOIN LATERAL (
    ИЗБЕРИ
      array_agg(id) id$
    , array_agg(id) FILTER(WHERE branch) ns$
    ОТ
      hier
    КЪДЕ
      pid = ANY(T.ns$)
  ) X
    ON coalesce(T.ns$, '{}') <> '{}'
)
ИЗБЕРИ
  unnest(id$) id
ОТ
  T;

Успяхме да намалим още едно запитване към индекса и спечелихме повече от 2 пъти по обем извлечено.

#2. Вернемся к корням

Този алгоритъм ще бъде полезен, ако е необходимо да съберете записи за всички елементи "нагоре по дървото", запазвайки информацията, кой изходен лист (и с какви показатели) е предизвикал неговото попадане в избора — например, за формулиране на обобщен отчет с агрегация на възлите.

По-нататък трябва да се възприема изключително като proof-of-concept, тъй като заявката става наистина тежка. Но ако доминира в базата ви — е добре да се замислите за прилагането на подобни методи.

Да започнем с няколко прости твърдения:

Една и съща запис от базата е по-добре да се чете само веднъж.
Записите от базата са по-ефективно да се четат на "пакет", отколкото поединично.

Сега ще опитаме да конструираме необходимата заявка.

Стъпка 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

Сега искаме да получим набор от ID на разделите, които ще трябва да извлечем по-нататък. Почти винаги те ще се дублират в различни записи на изходния набор — затова трябва да ги групираме, запазвайки информацията за източниците-листи.

Но тук ни чакат три неприятности:

"Подрекурсивната" част на заявката не може да съдържа агрегатни функции с GROUP BY.
Обращението към рекурсивната "таблица" не може да бъде в вложена подзаявка.
Заявката в рекурсивната част не може да съдържа 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 вътре в рекурсията

Неприятно, но… Имаме прост начин, как да симулираме 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 (
  ИЗБЕРИ
    rec
  , id::text chld
  ОТ
    hier rec
  КЪДЕ
    id = ANY('{1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192}'::integer[])
СЪВМЕСТНО ВСИЧКИ
  (
    С prnt AS (
      ИЗБЕРИ DISTINCT ON((rec).pid)
        (rec).pid id
      , string_agg(chld::text, ',') OVER(PARTITION BY (rec).pid) chld
      ОТ
        tree
      КЪДЕ
        (rec).pid IS NOT NULL
    )
    , nodes AS (
      ИЗБЕРИ
        rec
      ОТ
        hier rec
      КЪДЕ
        id = ANY(ARRAY(
          ИЗБЕРИ
            id
          ОТ
            prnt
        ))
    )
    ИЗБЕРИ
      nodes.rec
    , prnt.chld
    ОТ
      prnt
    JOIN
      nodes
        ON (nodes.rec).id = prnt.id
  )
)
ИЗБЕРИ
  unnest(string_to_array(chld, ',')::integer[]) leaf
, (rec).* 
ОТ
  tree;

Както и предполагахме, намерихме всичките 30 записа. Но за това изразходихме 60% от общото време — защото направихме и 30 търсения по индекса. А по-малко — може ли?

Източник: habr.com