🥇PostgreSQL antipatternlari: quyon teshigi qanchalik chuqur? ierarxiyadan o'tamiz

Murakkab ERP tizimlarida ko'p ob'ektlar ierarxik xususiyatga egabir hil jismlar tizilganda ajdod-avlod munosabatlari daraxti - bu korxonaning tashkiliy tuzilmasi (barcha ushbu filiallar, bo'limlar va ishchi guruhlar) va tovarlar katalogi, ish yo'nalishlari va savdo nuqtalarining geografiyasi,...

Aslida, hech kim yo'q biznesni avtomatlashtirish sohalari, bu erda natijada hech qanday ierarxiya bo'lmaydi. Ammo siz "biznes uchun" ishlamasangiz ham, ierarxik munosabatlarga osongina duch kelishingiz mumkin. Bu juda oddiy, hatto sizning oilaviy daraxtingiz yoki savdo markazidagi binolarning rejasi ham bir xil tuzilishga ega.

Bunday daraxtni DBMSda saqlashning ko'plab usullari mavjud, ammo bugun biz faqat bitta variantga e'tibor qaratamiz:

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

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

Va siz ierarxiyaning chuqurligiga nazar tashlayotganingizda, bunday tuzilma bilan ishlashning "sodda" usullari qanchalik samarali bo'lishini sabr bilan kutmoqda.

Keling, paydo bo'ladigan tipik muammolarni, ularni SQLda amalga oshirishni ko'rib chiqaylik va ularning ishlashini yaxshilashga harakat qilaylik.

#1. Quyon teshigi qanchalik chuqur?

Aniqlik uchun qabul qilaylikki, ushbu tuzilma tashkilot tuzilmasida bo'limlarning bo'ysunishini aks ettiradi: bo'limlar, bo'limlar, sektorlar, filiallar, ishchi guruhlar ... - ularni qanday nomlasangiz ham.

Birinchidan, 10K elementdan iborat "daraxtimizni" yarataylik

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;

Keling, eng oddiy vazifadan boshlaylik - ma'lum bir sektorda yoki ierarxiya nuqtai nazaridan ishlaydigan barcha xodimlarni topish - tugunning barcha bolalarini toping. Shuningdek, naslning "chuqurligi" ni olish yaxshi bo'lar edi ... Bularning barchasi, masalan, qandaydir qurilish uchun zarur bo'lishi mumkin. ushbu xodimlarning identifikatorlari ro'yxatiga asoslangan kompleks tanlash.

Agar bu avlodlarning bir nechta darajasi bo'lsa va ularning soni o'nlab bo'lsa, hamma narsa yaxshi bo'lar edi, lekin agar 5 darajadan ortiq bo'lsa va o'nlab avlodlar mavjud bo'lsa, muammolar bo'lishi mumkin. Keling, an'anaviy qidiruv variantlari qanday yozilishini (va ishlashini) ko'rib chiqaylik. Lekin birinchi navbatda, tadqiqotimiz uchun qaysi tugunlar eng qiziqarli bo'lishini aniqlaymiz.

eng yaxshi "chuqur" pastki daraxtlar:

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

eng yaxshi "keng" pastki daraxtlar:

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

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

Ushbu so'rovlar uchun biz odatdagidan foydalandik rekursiv JOIN:

Shubhasiz, bu so'rov modeli bilan takrorlashlar soni avlodlarning umumiy soniga mos keladi (va ularning o'nlablari bor) va bu juda katta resurslarni va natijada vaqtni talab qilishi mumkin.

Keling, "eng keng" pastki daraxtni tekshiramiz:

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 saytiga qarang]

Kutilganidek, biz barcha 30 ta yozuvni topdik. Ammo ular umumiy vaqtning 60 foizini bunga sarflashdi - chunki ular indeksda 30 ta qidiruvni ham qilishdi. Kamroq qilish mumkinmi?

Indeks bo'yicha ommaviy tekshirish

Har bir tugun uchun alohida indeks so'rovini qilishimiz kerakmi? Ma'lum bo'lishicha, yo'q - biz indeksdan o'qishimiz mumkin bitta qo'ng'iroqda bir vaqtning o'zida bir nechta tugmalardan foydalanish yordamida = ANY(array).

Va har bir bunday identifikatorlar guruhida biz oldingi bosqichda topilgan barcha identifikatorlarni "tugunlar" orqali olishimiz mumkin. Ya'ni, har bir keyingi qadamda biz buni qilamiz bir vaqtning o'zida ma'lum darajadagi barcha avlodlarni qidiring.

Faqat bu erda muammo, rekursiv tanlovda siz ichki so'rovda o'zingizga kira olmaysiz, lekin biz qandaydir tarzda faqat oldingi darajada topilgan narsani tanlashimiz kerak... Ma'lum bo'lishicha, butun tanlov uchun ichki so'rovni amalga oshirish mumkin emas, lekin uning maxsus maydoni uchun bu mumkin. Va bu maydon massiv ham bo'lishi mumkin - biz undan foydalanishimiz kerak ANY.

Bu biroz aqldan ozgandek tuyuladi, lekin diagrammada hamma narsa oddiy.

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 saytiga qarang]

Va bu erda eng muhimi, hatto emas vaqt ichida 1.5 marta g'alaba qozonish, va biz kamroq buferlarni olib tashladik, chunki bizda indeksga 5 o'rniga 30 ta qo'ng'iroq bor!

Qo'shimcha bonus - yakuniy unnestdan keyin identifikatorlar "darajalar" bo'yicha tartiblangan bo'lib qoladi.

Tugun belgisi

Ishlash samaradorligini oshirishga yordam beradigan keyingi fikr - "barglar" farzandli bo'lolmaydi, ya'ni ular uchun umuman "pastga" qarashning hojati yo'q. Vazifamizni shakllantirishda bu shuni anglatadiki, agar biz bo'limlar zanjiriga amal qilsak va xodimga erishgan bo'lsak, unda ushbu filial bo'ylab uzoqroqqa qarashning hojati yo'q.

Keling, stolimizga kiraylik qo'shimcha boolean-maydon, bu bizning daraxtimizdagi ushbu maxsus yozuv "tugun" ekanligini, ya'ni uning avlodlari bo'lishi mumkinligini darhol aytib beradi.

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

Ajoyib! Ma'lum bo'lishicha, barcha daraxt elementlarining atigi 30% dan bir oz ko'prog'i avlodlarga ega.

Endi biroz boshqacha mexanikdan foydalanamiz - rekursiv qismga ulanishlar orqali LATERAL, bu bizga rekursiv "jadval" maydonlariga zudlik bilan kirishga va tugmalar to'plamini kamaytirish uchun tugunga asoslangan filtrlash sharti bilan agregat funktsiyasidan foydalanishga imkon beradi:

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 saytiga qarang]

Biz yana bir indeks chaqiruvini kamaytirishga muvaffaq bo'ldik va hajmi bo'yicha 2 martadan ortiq g'olib chiqdi tuzatish.

#2. Keling, ildizlarga qaytaylik

Ushbu algoritm, agar siz "daraxt tepasida" barcha elementlar uchun yozuvlarni to'plashingiz kerak bo'lsa, qaysi manba varaqasi (va qanday ko'rsatkichlar bilan) namunaga kiritilishiga sabab bo'lganligi haqida ma'lumotni saqlashingiz kerak bo'lsa foydali bo'ladi - masalan, xulosa hisobotini yaratish tugunlarga yig'ish bilan.

Quyidagilarni faqat kontseptsiyaning isboti sifatida qabul qilish kerak, chunki so'rov juda og'ir bo'lib chiqadi. Ammo agar u sizning ma'lumotlar bazasida ustunlik qilsa, shunga o'xshash usullardan foydalanish haqida o'ylashingiz kerak.

Keling, bir nechta oddiy bayonotlardan boshlaylik:

Ma'lumotlar bazasidan bir xil yozuv Uni faqat bir marta o'qish yaxshidir.
Ma'lumotlar bazasidan olingan yozuvlar To'plamlarda o'qish samaraliroqyolg'izdan ko'ra.

Keling, kerakli so'rovni tuzishga harakat qilaylik.

1 bosqichma

Shubhasiz, rekursiyani ishga tushirishda (biz usiz qayerda bo'lardik!) biz dastlabki identifikatorlar to'plamiga asoslanib, barglarning o'z yozuvlarini ayirishimiz kerak bo'ladi:

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

Agar "to'plam" massiv emas, balki satr sifatida saqlanganligi kimgadir g'alati tuyulgan bo'lsa, unda buning oddiy tushuntirishi bor. Satrlar uchun o'rnatilgan birlashtiruvchi "yopishtiruvchi" funksiya mavjud string_agg, lekin massivlar uchun emas. Garchi u mustaqil ravishda amalga oshirish oson.

2 bosqichma

Endi biz ko'proq o'qilishi kerak bo'lgan bo'lim identifikatorlari to'plamini olamiz. Deyarli har doim ular asl to'plamning turli yozuvlarida takrorlanadi - biz shunday qilamiz ularni guruhlash, manba barglari haqidagi ma'lumotlarni saqlab qolgan holda.

Ammo bu erda bizni uchta muammo kutmoqda:

So'rovning "subrekursiv" qismi bilan jamlangan funktsiyalarni o'z ichiga olmaydi GROUP BY.
Rekursiv "jadval"ga havola ichki quyi so'rovda bo'lishi mumkin emas.
Rekursiv qismdagi so'rovda CTE bo'lishi mumkin emas.

Yaxshiyamki, bu muammolarni hal qilish juda oson. Keling, oxiridan boshlaylik.

Rekursiv qismda CTE

Mana bunday yo'q ishlari:

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

Va shunday ishlaydi, qavslar farq qiladi!

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

Rekursiv "jadval" ga qarshi o'rnatilgan so'rov

Hmm... Rekursiv CTE ga quyi so'rovda kirish mumkin emas. Ammo bu CTE ichida bo'lishi mumkin! Va ichki so'rov allaqachon ushbu CTE-ga kirishi mumkin!

GROUP BY ichki rekursiya

Bu yoqimsiz, lekin... Bizda GROUP BY yordamida taqlid qilishning oddiy usuli bor DISTINCT ON va oyna funktsiyalari!

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

Va bu shunday ishlaydi!

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

Endi biz raqamli identifikator nima uchun matnga aylantirilganini ko'ramiz - ular vergul bilan ajratilgan holda birlashtirilishi uchun!

3 bosqichma

Finalga bizda hech narsa qolmadi:

biz guruhlangan identifikatorlar to'plamiga asoslangan "bo'lim" yozuvlarini o'qiymiz
biz olib tashlangan qismlarni asl varaqlarning "to'plamlari" bilan taqqoslaymiz
yordamida to'plam qatorini "kengaytiring" 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 saytiga qarang]

Manba: www.habr.com

PostgreSQL antipatternlari: quyon teshigi qanchalik chuqur? Keling, ierarxiyadan o'tamiz

#1. Quyon teshigi qanchalik chuqur?

Indeks bo'yicha ommaviy tekshirish

Tugun belgisi

#2. Keling, ildizlarga qaytaylik

1 bosqichma

2 bosqichma

Rekursiv qismda CTE

Rekursiv "jadval" ga qarshi o'rnatilgan so'rov

GROUP BY ichki rekursiya

3 bosqichma

a Izoh qo'shish Bu savolga javob bekor