Antipatterns 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. Сӯрохи харгӯш чӣ қадар чуқур аст?

Биёед, ба таври дакик кабул кунем, ки ин структура тобеияти шуъбахоро дар сохтори ташкилот инъикос мекунад: шуъбахо, шуъбахо, секторхо, филиалхо, гуруххои корй... — хар чи мегуед.

Аввалан, биёед "дарахти"-и худро аз 10К элемент тавлид кунем

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;

[нигаред дар explain.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;

[нигаред дар explain.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;

[нигаред дар explain.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

Ҳоло мо маҷмӯи ID-ҳои бахшро мегирем, ки бояд минбаъд хонда шаванд. Қариб ҳамеша онҳо дар сабтҳои гуногуни маҷмӯи аслӣ такрор карда мешаванд - ҳамин тавр мо онҳоро гурӯҳбандӣ кунед, ҳангоми нигоҳ доштани маълумот дар бораи манбаъ баргҳо.

Аммо дар ин ҷо моро се мушкилӣ интизор аст:

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

Дархости воридшуда бар зидди "ҷадвал"-и рекурсивӣ

Hmm... CTE-и рекурсивӣ дар зерпурсиш дастрас шудан мумкин нест. Аммо он метавонад дар дохили CTE бошад! Ва дархости воридшуда аллакай метавонад ба ин CTE дастрасӣ пайдо кунад!

GROUP BY рекурсияи дохили

Ин ногувор аст, аммо... Мо як роҳи оддии тақлид кардани GROUP бо истифода дорем 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;

[нигаред дар explain.tensor.ru]

Манбаъ: will.com