Karmaşık ERP sistemlerinde birçok varlığın hiyerarşik bir yapısı vardırhomojen nesneler sıralandığında ata-torun ilişkileri ağacı - işletmenin organizasyon yapısı (tüm bu şubeler, departmanlar ve çalışma grupları), malların kataloğu, çalışma alanları ve satış noktalarının coğrafyası,...
Aslında hiçbiri yok sonuç olarak herhangi bir hiyerarşi olmayacaktı. Ancak “iş için” çalışmasanız bile hiyerarşik ilişkilerle kolaylıkla karşılaşabilirsiniz. Soy ağacınız veya bir alışveriş merkezindeki binanın kat planı bile aynı yapıdadır.
Böyle bir ağacı DBMS'de saklamanın birçok yolu vardır, ancak bugün yalnızca bir seçeneğe odaklanacağız:
CREATE TABLE hier(
id
integer
PRIMARY KEY
, pid
integer
REFERENCES hier
, data
json
);
CREATE INDEX ON hier(pid); -- не забываем, что FK не подразумевает автосоздание индекса, в отличие от PK
Ve siz hiyerarşinin derinliklerine bakarken, o da böyle bir yapıyla "naif" çalışma yöntemlerinizin ne kadar etkili olacağını görmek için sabırla bekliyor.
Ortaya çıkan tipik sorunlara, bunların SQL'deki uygulamalarına bakalım ve performanslarını iyileştirmeye çalışalım.
#1. Tavşan deliği ne kadar derin?
Kesin olarak, bu yapının organizasyon yapısındaki departmanların bağlılığını yansıtacağını kabul edelim: departmanlar, bölümler, sektörler, şubeler, çalışma grupları... - onlara ne ad verirseniz verin.
İlk önce 10K öğeden oluşan 'ağacımızı' oluşturalım
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;En basit görevle başlayalım - belirli bir sektörde veya hiyerarşi açısından çalışan tüm çalışanları bulmak - bir düğümün tüm alt öğelerini bul. Soyun "derinliğini" elde etmek de güzel olurdu... Bütün bunlar, örneğin bir tür inşa etmek için gerekli olabilir. .
Bu soyun sadece birkaç seviyesi varsa ve sayı bir düzine civarındaysa her şey yoluna girecek, ancak 5'ten fazla seviye varsa ve zaten düzinelerce torun varsa, sorunlar olabilir. Geleneksel ağaç aşağı arama seçeneklerinin nasıl yazıldığına (ve çalıştığına) bakalım. Ama önce araştırmamız için hangi düğümlerin en ilgi çekici olacağını belirleyelim.
En "derin" alt ağaçlar:
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}
...En "geniş" alt ağaçlar:
...
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 sorgular için tipik olanı kullandık özyinelemeli KATIL:
Açıkçası, bu istek modeliyle yineleme sayısı toplam alt öğe sayısıyla eşleşecektir (ve bunlardan birkaç düzine var) ve bu oldukça önemli kaynaklar ve sonuç olarak zaman alabilir.
“En geniş” alt ağacı kontrol edelim:
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;
Beklendiği gibi 30 kaydın tamamını bulduk. Ancak toplam sürenin %60'ını buna harcadılar çünkü ayrıca dizinde 30 arama da yaptılar. Daha azını yapmak mümkün mü?
Dizine göre toplu düzeltme
Her node için ayrı indeks sorgusu yapmamız gerekiyor mu? Görünüşe göre hayır - dizinden okuyabiliyoruz tek aramada birden fazla tuşun aynı anda kullanılması üzerinden = ANY(array).
Ve bu tür tanımlayıcı gruplarının her birinde, önceki adımda bulunan tüm kimlikleri "düğümler" ile alabiliriz. Yani, bir sonraki her adımda yapacağımız belirli bir seviyedeki tüm soyundan gelenleri aynı anda arayın.
Yalnız sorun şu; özyinelemeli seçimde, iç içe geçmiş bir sorguda kendisine erişemezsiniz, ancak bir şekilde yalnızca önceki düzeyde bulunanı seçmemiz gerekiyor... Seçimin tamamı için iç içe geçmiş bir sorgu yapmanın imkansız olduğu, ancak belirli alanı için mümkün olduğu ortaya çıktı. Ve bu alan aynı zamanda bir dizi de olabilir; bunu kullanmamız gerekiyor ANY.
Biraz çılgınca gelebilir ama şemada her şey basit.
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;
Ve burada en önemli şey bile değil zamanında 1.5 kez kazanve dizine 5 yerine yalnızca 30 çağrımız olduğundan daha az arabellek çıkardığımızı!
Ek bir bonus, son yuvalamadan sonra tanımlayıcıların "seviyelere" göre sıralanmış kalmasıdır.
Düğüm işareti
Performansı artırmaya yardımcı olacak bir sonraki husus: "yapraklar" çocuk sahibi olamazyani onlar için "aşağıya" bakmaya hiç gerek yok. Görevimizin formülasyonunda bu, eğer departmanlar zincirini takip edip bir çalışana ulaşmışsak, bu branşta daha fazla aramamıza gerek olmadığı anlamına geliyor.
Hadi masamıza girelim tamamlayıcı boolean-alanBu bize ağacımızdaki bu belirli girişin bir "düğüm" olup olmadığını, yani onun soyundan olup olamayacağını hemen söyleyecektir.
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 мс.Harika! Tüm ağaç elemanlarının yalnızca %30'undan biraz fazlasının soyundan geldiği ortaya çıktı.
Şimdi biraz farklı bir mekanizma kullanalım: özyinelemeli kısma bağlantılar LATERALözyinelemeli "tablonun" alanlarına anında erişmemize ve anahtar kümesini azaltmak için bir düğüme dayalı filtreleme koşuluna sahip bir toplama işlevi kullanmamıza olanak tanıyacak:
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;
Bir indeks çağrısını daha azaltmayı başardık ve hacim olarak 2 kattan fazla kazandı düzeltme yapmak.
#2. Köklere geri dönelim
Bu algoritma, örneğin bir özet rapor oluşturmak için hangi kaynak sayfasının (ve hangi göstergelerle) örneğe dahil edilmesine neden olduğuna ilişkin bilgileri korurken "ağacın yukarısındaki" tüm öğeler için kayıt toplamanız gerekiyorsa yararlı olacaktır. düğümler halinde toplama ile.
Talebin çok külfetli olduğu ortaya çıktığından, aşağıdakiler yalnızca kavram kanıtı olarak alınmalıdır. Ancak veritabanınıza hakimse benzer teknikleri kullanmayı düşünmelisiniz.
Birkaç basit ifadeyle başlayalım:
- Veritabanından aynı kayıt Bir kez okumak en iyisi.
- Veritabanındaki kayıtlar Toplu olarak okumak daha verimlidiryalnız olmaktansa.
Şimdi ihtiyacımız olan isteği oluşturmaya çalışalım.
1 Adım
Açıkçası, özyinelemeyi başlatırken (onsuz nerede olurduk!) İlk tanımlayıcılar kümesine dayanarak yaprakların kayıtlarını çıkarmamız gerekecek:
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
...
Eğer "kümenin" bir dizi olarak değil de bir dizi olarak saklanması birisine garip geldiyse, bunun basit bir açıklaması vardır. Dizeler için yerleşik bir birleştirme "yapıştırma" işlevi vardır string_agg, ancak diziler için değil. Her ne kadar o .
2 Adım
Artık daha fazla okunması gereken bir dizi bölüm kimliği alacağız. Neredeyse her zaman orijinal setin farklı kayıtlarında kopyalanırlar; onları gruplandır, kaynak yaprakları hakkındaki bilgileri korurken.
Ancak burada üç sıkıntı bizi bekliyor:
- Sorgunun "alt özyinelemeli" kısmı, toplama işlevlerini içeremez.
GROUP BY. - Özyinelemeli bir "tabloya" yapılan başvuru, iç içe geçmiş bir alt sorguda olamaz.
- Özyinelemeli kısımdaki bir istek CTE içeremez.
Neyse ki, tüm bu sorunların çözümü oldukça kolaydır. Sondan başlayalım.
Özyinelemeli kısımda CTE
Böyle hayır İşler:
WITH RECURSIVE tree AS (
...
UNION ALL
WITH T (...)
SELECT ...
)Ve işe yarıyor, parantezler fark yaratıyor!
WITH RECURSIVE tree AS (
...
UNION ALL
(
WITH T (...)
SELECT ...
)
)Özyinelemeli bir "tabloya" karşı iç içe geçmiş sorgu
Hmm... Bir alt sorguda özyinelemeli bir CTE'ye erişilemez. Ama CTE'nin içinde olabilir! Ve iç içe geçmiş bir istek zaten bu CTE'ye erişebilir!
GROUP BY iç özyineleme
Hoş olmayan bir durum ama... kullanarak GROUP BY'yi taklit etmenin basit bir yolu var. DISTINCT ON ve pencere fonksiyonları!
SELECT
(rec).pid id
, string_agg(chld::text, ',') chld
FROM
tree
WHERE
(rec).pid IS NOT NULL
GROUP BY 1 -- не работает!Ve bu şekilde çalışıyor!
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Şimdi sayısal kimliğin neden metne dönüştürüldüğünü görüyoruz; böylece virgülle ayrılarak bir araya getirilebilirler!
3 Adım
Final için hiçbir şeyimiz kalmadı:
- bir dizi gruplandırılmış kimliğe dayalı olarak "bölüm" kayıtlarını okuruz
- çıkarılan bölümleri orijinal sayfaların “kümeleri” ile karşılaştırıyoruz
- kullanarak set-string'i “genişletin”
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;
Kaynak: habr.com