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;

Эң жөнөкөй тапшырмадан баштайлы - белгилүү бир сектордо же иерархияда иштеген бардык кызматкерлерди табуу - бир түйүндүн бардык балдарын табуу. Ошондой эле тукумдун «тереңдигин» алса жакшы болмок... Мунун баары, мисалы, кандайдыр бир курулуш куруу үчүн зарыл болушу мүмкүн. бул кызматкерлердин ID тизмеси боюнча комплекстүү тандоо.

Эгерде бул тукумдардын бир-эки гана деңгээли бар болсо жана саны ондогондо болсо, баары жакшы болмок, бирок 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;

[express.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;

[express.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;

[express.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;

[express.tensor.ru сайтынан көрүү]

Source: www.habr.com