PostgreSQL Antipatterns: Колко дълбока е заешката дупка? да минем през йерархията

В сложни 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;

Нека започнем с най-простата задача - намиране на всички служители, които работят в определен сектор или от гледна точка на йерархията - намерете всички деца на възел. Също така би било хубаво да се получи „дълбочината“ на потомъка... Всичко това може да е необходимо, например, за изграждане на някакъв вид комплексен подбор въз основа на списъка с идентификационни номера на тези служители.

Всичко би било наред, ако има само няколко нива на тези наследници и броят им е в рамките на дузина, но ако има повече от 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;

[вижте expand.tensor.ru]

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

Масова корекция по индекс

Трябва ли да направим отделна заявка за индекс за всеки възел? Оказва се, че не - можем да четем от индекса използване на няколко клавиша наведнъж в едно повикване през = ANY(array).

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

Само че тук е проблемът, при рекурсивна селекция не можете да получите достъп до себе си във вложена заявка, но трябва по някакъв начин да селектираме само това, което е намерено на предишното ниво... Оказва се, че е невъзможно да се направи вложена заявка за цялата селекция, но за нейното конкретно поле е възможно. И това поле може да бъде и масив - което трябва да използваме 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;

[вижте expand.tensor.ru]

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

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

Знак за възел

Следващото съображение, което ще помогне за подобряване на производителността, е − "листа" не може да има деца, тоест за тях изобщо няма нужда да гледат „надолу“. При формулирането на нашата задача това означава, че ако сме следвали веригата от отдели и сме стигнали до служител, тогава няма нужда да търсим по-нататък по този клон.

Да влезем в нашата маса допълнителен 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;

[вижте expand.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 вътрешна рекурсия

Неприятно е, но... Имаме лесен начин да емулираме 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

Сега разбираме защо числовият идентификатор беше превърнат в текст - за да могат да бъдат съединени заедно, разделени със запетаи!

Стъпка 3

За финал не ни остана нищо:

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

[вижте expand.tensor.ru]

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