Dalam sistem ERP yang kompleks banyak entitas memiliki sifat hierarkisketika benda-benda homogen berbaris pohon hubungan nenek moyang-keturunan - ini adalah struktur organisasi perusahaan (semua cabang, departemen, dan kelompok kerja), dan katalog barang, dan bidang kerja, dan geografi titik penjualan,...
Faktanya, tidak ada , sehingga tidak akan ada hierarki apa pun sebagai hasilnya. Namun meskipun Anda tidak bekerja “untuk bisnis”, Anda masih dapat dengan mudah menemukan hubungan hierarki. Itu basi, bahkan silsilah keluarga atau denah tempat di pusat perbelanjaan Anda memiliki struktur yang sama.
Ada banyak cara untuk menyimpan pohon seperti itu di DBMS, tapi hari ini kita hanya akan fokus pada satu opsi:
CREATE TABLE hier(
id
integer
PRIMARY KEY
, pid
integer
REFERENCES hier
, data
json
);
CREATE INDEX ON hier(pid); -- не забываем, что FK не подразумевает автосоздание индекса, в отличие от PK
Dan saat Anda mengintip ke dalam hierarki, Anda dengan sabar menunggu untuk melihat seberapa efektif cara “naif” Anda dalam bekerja dengan struktur seperti itu.
Mari kita lihat masalah umum yang muncul, implementasinya dalam SQL, dan coba tingkatkan kinerjanya.
#1. Seberapa dalam lubang kelincinya?
Mari kita, agar lebih pasti, menerima bahwa struktur ini akan mencerminkan subordinasi departemen dalam struktur organisasi: departemen, divisi, sektor, cabang, kelompok kerja... - apa pun sebutannya.
Pertama, mari kita buat 'pohon' yang terdiri dari 10 ribu elemen
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;Mari kita mulai dengan tugas paling sederhana - menemukan semua karyawan yang bekerja dalam sektor tertentu, atau berdasarkan hierarki - temukan semua anak dari sebuah node. Akan menyenangkan juga untuk mendapatkan "kedalaman" dari keturunannya... Semua ini mungkin diperlukan, misalnya, untuk membangun semacam .
Semuanya akan baik-baik saja jika level keturunan ini hanya ada beberapa dan jumlahnya dalam selusin, tetapi jika levelnya lebih dari 5, dan keturunannya sudah puluhan, mungkin ada masalah. Mari kita lihat bagaimana opsi pencarian tradisional ditulis (dan berfungsi). Tapi pertama-tama, mari kita tentukan node mana yang paling menarik untuk penelitian kita.
Yang paling "dalam" subpohon:
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}
...Yang paling "lebar" subpohon:
...
SELECT
path[1] id
, count(*)
FROM
T
GROUP BY
1
ORDER BY
2 DESC;id | count
------------
5300 | 30
450 | 28
1239 | 27
1573 | 25
Untuk pertanyaan ini kami menggunakan tipikal GABUNG secara rekursif:
Tentunya dengan model permintaan ini jumlah iterasi akan sesuai dengan jumlah total keturunan (dan jumlahnya ada beberapa lusin), dan hal ini memerlukan sumber daya yang cukup besar, dan akibatnya, waktu.
Mari kita periksa subpohon “terluas”:
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;
Seperti yang diharapkan, kami menemukan 30 catatan tersebut. Namun mereka menghabiskan 60% dari total waktu untuk hal ini - karena mereka juga melakukan 30 pencarian di indeks. Apakah mungkin melakukan lebih sedikit?
Pengoreksian massal berdasarkan indeks
Apakah kita perlu membuat kueri indeks terpisah untuk setiap node? Ternyata tidak - kita bisa membaca dari indeks menggunakan beberapa tombol sekaligus dalam satu panggilan melalui = ANY(array).
Dan di setiap kelompok pengidentifikasi tersebut kita dapat mengambil semua ID yang ditemukan pada langkah sebelumnya dengan “node”. Artinya, pada setiap langkah berikutnya kita akan melakukannya mencari semua keturunan dari level tertentu sekaligus.
Hanya saja, inilah masalahnya, dalam pemilihan rekursif, Anda tidak dapat mengakses dirinya sendiri dalam kueri bersarang, tapi entah bagaimana kita hanya perlu memilih apa yang ditemukan di tingkat sebelumnya... Ternyata tidak mungkin membuat kueri bersarang untuk seluruh pilihan, tetapi untuk bidang spesifiknya hal itu mungkin. Dan bidang ini juga bisa berupa array - itulah yang perlu kita gunakan ANY.
Kedengarannya agak gila, tetapi semuanya sederhana dalam diagram.
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;
Dan di sini yang terpenting bukanlah hal yang genap menang 1.5 kali dalam waktu, dan kami mengurangi buffer lebih sedikit, karena kami hanya memiliki 5 panggilan ke indeks, bukan 30!
Bonus tambahannya adalah kenyataan bahwa setelah unnest terakhir, pengidentifikasi akan tetap diurutkan berdasarkan “level”.
Tanda simpul
Pertimbangan berikutnya yang akan membantu meningkatkan kinerja adalah - "daun" tidak dapat memiliki anakArtinya, bagi mereka tidak perlu melihat “bawah” sama sekali. Dalam rumusan tugas kita, ini berarti jika kita mengikuti rantai departemen dan menjangkau seorang karyawan, maka tidak perlu melihat lebih jauh cabang ini.
Mari masuk ke meja kita tambahan boolean-bidang, yang akan segera memberi tahu kita apakah entri tertentu di pohon kita ini adalah sebuah "simpul" - yaitu, apakah entri tersebut dapat memiliki keturunan atau tidak.
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 мс.Besar! Ternyata hanya lebih dari 30% dari seluruh elemen pohon yang memiliki keturunan.
Sekarang mari kita gunakan mekanisme yang sedikit berbeda - koneksi ke bagian rekursif melalui LATERAL, yang akan memungkinkan kita untuk segera mengakses bidang “tabel” rekursif, dan menggunakan fungsi agregat dengan kondisi pemfilteran berdasarkan node untuk mengurangi kumpulan kunci:
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;
Kami dapat mengurangi satu panggilan indeks lagi dan menang lebih dari 2 kali dalam volume mengoreksi.
#2. Mari kita kembali ke akarnya
Algoritme ini akan berguna jika Anda perlu mengumpulkan catatan untuk semua elemen “di atas pohon”, sambil menyimpan informasi tentang lembar sumber mana (dan dengan indikator apa) yang menyebabkannya dimasukkan dalam sampel - misalnya, untuk menghasilkan laporan ringkasan dengan agregasi menjadi node.
Hal berikut ini harus dianggap semata-mata sebagai pembuktian konsep, karena permintaan tersebut ternyata sangat rumit. Namun jika itu mendominasi database Anda, Anda harus mempertimbangkan untuk menggunakan teknik serupa.
Mari kita mulai dengan beberapa pernyataan sederhana:
- Catatan yang sama dari database Yang terbaik adalah membacanya sekali saja.
- Catatan dari database Lebih efisien jika membaca secara berkelompokdaripada sendirian.
Sekarang mari kita coba membuat permintaan yang kita butuhkan.
Langkah 1
Jelasnya, ketika menginisialisasi rekursi (apa jadinya kita tanpa rekursi!) kita harus mengurangi record dari daun itu sendiri berdasarkan kumpulan pengenal awal:
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
...
Jika seseorang merasa aneh bahwa "set" disimpan sebagai string dan bukan array, maka ada penjelasan sederhana untuk ini. Ada fungsi agregasi “perekatan” bawaan untuk string string_agg, tetapi tidak untuk array. Meskipun dia .
Langkah 2
Sekarang kita akan mendapatkan satu set ID bagian yang perlu dibaca lebih lanjut. Hampir selalu mereka akan diduplikasi dalam rekaman berbeda dari kumpulan aslinya - jadi kami akan melakukannya kelompokkan mereka, sambil menjaga informasi tentang daun sumber.
Namun di sini tiga masalah menanti kita:
- Bagian "subrekursif" dari kueri tidak boleh berisi fungsi agregat dengan
GROUP BY. - Referensi ke “tabel” rekursif tidak boleh berada dalam subkueri bertingkat.
- Permintaan di bagian rekursif tidak boleh berisi CTE.
Untungnya, semua masalah ini cukup mudah untuk diatasi. Mari kita mulai dari akhir.
CTE di bagian rekursif
Disini begitu tidak bekerja:
WITH RECURSIVE tree AS (
...
UNION ALL
WITH T (...)
SELECT ...
)Dan cara ini berhasil, tanda kurunglah yang membuat perbedaan!
WITH RECURSIVE tree AS (
...
UNION ALL
(
WITH T (...)
SELECT ...
)
)Kueri bersarang terhadap "tabel" rekursif
Hmm... CTE rekursif tidak dapat diakses di subquery. Tapi bisa juga di dalam CTE! Dan permintaan bersarang sudah dapat mengakses CTE ini!
GROUP BY di dalam rekursi
Ini tidak menyenangkan, tapi... Kami memiliki cara sederhana untuk meniru penggunaan GROUP BY DISTINCT ON dan fungsi jendela!
SELECT
(rec).pid id
, string_agg(chld::text, ',') chld
FROM
tree
WHERE
(rec).pid IS NOT NULL
GROUP BY 1 -- не работает!Dan inilah cara kerjanya!
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 NULLSekarang kita lihat mengapa ID numerik diubah menjadi teks - sehingga keduanya dapat digabungkan dan dipisahkan dengan koma!
Langkah 3
Untuk final kita tidak punya apa-apa lagi:
- kita membaca catatan "bagian" berdasarkan kumpulan ID yang dikelompokkan
- kami membandingkan bagian yang dikurangi dengan "kumpulan" dari lembaran asli
- "perluas" set-string menggunakan
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;
Sumber: www.habr.com