Mürəkkəb ERP sistemlərində bir çox qurumlar iyerarxik təbiətə malikdirhomojen obyektlər düzüldükdə əcdad-nəsil əlaqələrinin ağacı - bu, müəssisənin təşkilati strukturu (bütün bu filiallar, şöbələr və işçi qrupları) və malların kataloqu, iş sahələri və satış məntəqələrinin coğrafiyası,...
Əslində heç biri yoxdur
Belə bir ağacı DBMS-də saxlamağın bir çox yolu var, lakin bu gün biz yalnız bir seçim üzərində dayanacağıq:
CREATE TABLE hier(
id
integer
PRIMARY KEY
, pid
integer
REFERENCES hier
, data
json
);
CREATE INDEX ON hier(pid); -- не забываем, что FK не подразумевает автосоздание индекса, в отличие от PK
Və siz iyerarxiyanın dərinliklərinə nəzər salarkən, belə bir strukturla işləmək üçün “sadəlövh” üsullarınızın nə qədər təsirli olacağını səbirlə gözləyir.
Yaranan tipik problemlərə, onların SQL-də tətbiqinə nəzər salaq və onların işini yaxşılaşdırmağa çalışaq.
#1. Dovşan çuxurunun dərinliyi nə qədərdir?
Qəbul edək ki, bu struktur qurumun strukturunda departamentlərin tabeliyini əks etdirəcək: departamentlər, şöbələr, sektorlar, filiallar, işçi qruplar... - onları nə adlandırırsınızsa.
Əvvəlcə 10K elementdən ibarət “ağacımızı” yaradaq
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;
Ən sadə vəzifədən başlayaq - müəyyən bir sektorda və ya iyerarxiya baxımından işləyən bütün işçiləri tapmaq - node bütün uşaqları tapın. Nəslin “dərinliyini” əldə etmək də gözəl olardı... Bütün bunlar, məsələn, bir növ bina tikmək üçün lazım ola bilər.
Bu nəsillərin cəmi bir neçə səviyyəsi olsa və sayı onlarla olsa, hər şey yaxşı olardı, lakin 5-dən çox səviyyə varsa və artıq onlarla nəsil varsa, problemlər ola bilər. Ənənəvi axtarış variantlarının necə yazıldığına (və işlədiyinə) baxaq. Ancaq əvvəlcə araşdırmamız üçün hansı qovşaqların ən maraqlı olacağını müəyyən edək.
Ən çox "dərin" alt ağaclar:
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}
...
Ən çox "geniş" alt ağaclar:
...
SELECT
path[1] id
, count(*)
FROM
T
GROUP BY
1
ORDER BY
2 DESC;
id | count
------------
5300 | 30
450 | 28
1239 | 27
1573 | 25
Bu sorğular üçün tipikdən istifadə etdik rekursiv JOIN:
Aydındır ki, bu sorğu modeli ilə təkrarların sayı nəsillərin ümumi sayına uyğun olacaq (və onlardan bir neçə onlarla var) və bu, olduqca əhəmiyyətli resurslar və nəticədə vaxt tələb edə bilər.
Gəlin "ən geniş" alt ağacı yoxlayaq:
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;
Gözlənildiyi kimi, biz 30 qeydin hamısını tapdıq. Amma onlar ümumi vaxtın 60%-ni buna sərf ediblər - çünki onlar indeksdə 30 axtarış da ediblər. Daha az iş görmək mümkündürmü?
İndeks üzrə toplu yoxlama
Hər bir qovşaq üçün ayrıca indeks sorğusu etməliyikmi? Belə çıxır ki, biz indeksdən oxuya bilərik bir zəngdə eyni anda bir neçə düymədən istifadə etmək köməyi ilə = ANY(array)
.
Və hər bir belə identifikator qrupunda biz əvvəlki addımda tapılan bütün identifikatorları “qovşaqlar”la götürə bilərik. Yəni, hər növbəti addımda biz edəcəyik bir anda müəyyən səviyyəli bütün nəsilləri axtarın.
Sadəcə, problem buradadır, rekursiv seçimdə iç içə sorğuda özünə daxil ola bilməzsiniz, lakin biz hansısa şəkildə yalnız əvvəlki səviyyədə tapılanı seçməliyik... Belə çıxır ki, siz bütün seçim üçün iç içə sorğu edə bilməzsiniz, ancaq onun xüsusi sahəsi üçün edə bilərsiniz. Və bu sahə həm də massiv ola bilər – hansı ki, istifadə etməliyik ANY
.
Bir az dəli səslənir, amma diaqramda hər şey sadədir.
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;
Və burada ən vacib şey hətta deyil vaxtında 1.5 dəfə qalib gəlir, və biz daha az buferləri çıxardıq, çünki indeksə 5 əvəzinə cəmi 30 çağırışımız var!
Əlavə bir bonus, son boşluqdan sonra identifikatorların "səviyyələrə" görə sıralanmasıdır.
Düyün işarəsi
Performansı yaxşılaşdırmağa kömək edəcək növbəti məsələ - "yarpaqlar" uşaq sahibi ola bilməz, yəni onlar üçün ümumiyyətlə “aşağıya” baxmağa ehtiyac yoxdur. Tapşırığımızın tərtibində bu o deməkdir ki, əgər biz şöbələr zəncirini izləmişiksə və bir işçiyə çatmışıqsa, bu filialı daha çox axtarmağa ehtiyac yoxdur.
Gəlin masamıza daxil olaq əlavə boolean
- sahə, bu dərhal bizə ağacımızdaki bu xüsusi girişin bir "düyün" olub olmadığını, yəni ümumiyyətlə nəsillərə sahib olub olmadığını söyləyəcək.
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 мс.
Əla! Məlum oldu ki, bütün ağac elementlərinin yalnız 30% -dən bir qədər çoxunun nəsilləri var.
İndi bir az fərqli mexaniki istifadə edək - rekursiv hissəyə keçid vasitəsilə LATERAL
, bu bizə rekursiv "cədvəl" sahələrinə dərhal daxil olmağa və düymələr dəstini azaltmaq üçün qovşaq əsasında filtrləmə şərti ilə məcmu funksiyadan istifadə etməyə imkan verəcəkdir:
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;
Biz daha bir indeks çağırışını azalda bildik və həcmdə 2 dəfədən çox qalib gəldi korrektə.
#2. Köklərə qayıdaq
Bu alqoritm, hansı mənbə vərəqinin (və hansı göstəricilərlə) nümunəyə daxil edilməsinə səbəb olduğu barədə məlumatı saxlamaqla, məsələn, xülasə hesabat yaratmaq üçün "ağacın yuxarısında" bütün elementlər üçün qeydlər toplamaq lazım olduqda faydalı olacaq. qovşaqlara yığılması ilə.
Aşağıdakılar yalnız konsepsiyanın sübutu kimi qəbul edilməlidir, çünki sorğu çox çətin olur. Ancaq verilənlər bazanızda üstünlük təşkil edirsə, oxşar üsullardan istifadə etməyi düşünməlisiniz.
Bir neçə sadə ifadə ilə başlayaq:
- Verilənlər bazasından eyni qeyd Ən yaxşısı onu bir dəfə oxumaqdır.
- Verilənlər bazasından qeydlər Dəstələrlə oxumaq daha səmərəlidirtəklikdən.
İndi bizə lazım olan sorğunu qurmağa çalışaq.
1 addım
Aydındır ki, rekursiyanı işə salarkən (onsuz biz harada olardıq!) biz ilkin identifikatorlar toplusuna əsasən yarpaqların qeydlərini çıxarmalı olacağıq:
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
...
Əgər kiməsə “dəst”in massiv kimi deyil, sətir kimi saxlanması qəribə görünürdüsə, bunun sadə izahı var. Simlər üçün daxili birləşdirici "yapışdırma" funksiyası var string_agg
, lakin massivlər üçün deyil. Baxmayaraq ki, o
2 addım
İndi biz daha çox oxunmalı olan bir sıra bölmə identifikatorları alacağıq. Demək olar ki, həmişə onlar orijinal dəstin müxtəlif qeydlərində təkrarlanacaqlar - biz də belə edərdik onları qruplaşdırın, mənbə haqqında məlumatları qoruyarkən yarpaq.
Ancaq burada bizi üç bəla gözləyir:
- Sorğunun "subrekursiv" hissəsi ilə məcmu funksiyalar ola bilməz
GROUP BY
. - Rekursiv “cədvəl”ə istinad daxili alt sorğuda ola bilməz.
- Rekursiv hissədəki sorğuda CTE ola bilməz.
Xoşbəxtlikdən, bütün bu problemləri həll etmək olduqca asandır. Sondan başlayaq.
Rekursiv hissədə CTE
Burada belədir heç bir işləri:
WITH RECURSIVE tree AS (
...
UNION ALL
WITH T (...)
SELECT ...
)
Və beləliklə işləyir, mötərizələr fərq yaradır!
WITH RECURSIVE tree AS (
...
UNION ALL
(
WITH T (...)
SELECT ...
)
)
Rekursiv "cədvəl"ə qarşı iç-içə sorğu
Hmm... Alt sorğuda rekursiv CTE-yə daxil olmaq mümkün deyil. Ancaq bu, CTE daxilində ola bilər! Daxili sorğu artıq bu CTE-yə daxil ola bilər!
GROUP BY daxili rekursiya
Bu, xoşagəlməzdir, lakin... Bizdə QRUPU-nu istifadə etməklə təqlid etmək üçün sadə bir yolumuz var DISTINCT ON
və pəncərə funksiyaları!
SELECT
(rec).pid id
, string_agg(chld::text, ',') chld
FROM
tree
WHERE
(rec).pid IS NOT NULL
GROUP BY 1 -- не работает!
Və bu belə işləyir!
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
İndi biz rəqəmsal identifikatorun niyə mətnə çevrildiyini görürük - belə ki, onlar vergüllə ayrılaraq birləşdirilə bilsinlər!
3 addım
Finala heç nə qalmayıb:
- qruplaşdırılmış identifikatorlar dəsti əsasında “bölmə” qeydlərini oxuyuruq
- çıxılan bölmələri orijinal vərəqlərin "dəstləri" ilə müqayisə edirik
- istifadə edərək set-sətri "genişləndirin"
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;