Saya awalnya memikirkan penggabungan lateral seperti pada pendekatan lain yang disarankan (misalnya, kueri terakhir oleh Erwin Brandstetter, di mana ia menggunakan int8 sederhana tipe data dan indeks sederhana), tetapi tidak ingin menulisnya di jawaban, karena saya pikir itu tidak terlalu efisien. Saat Anda mencoba menemukan semua netblock rentang yang mencakup rentang yang diberikan, indeks tidak banyak membantu.
Saya akan mengulangi pertanyaan Erwin Brandstetter di sini:
SELECT * -- only select columns you need to make it faster
FROM routing_details r
, LATERAL (
SELECT *
FROM netblock_details n
WHERE n.ip_min <= r.ip_min
AND n.ip_max >= r.ip_max
ORDER BY n.ip_max - n.ip_min
LIMIT 1
) n;
Ketika Anda memiliki indeks di netblock_details, seperti ini:
CREATE INDEX netblock_details_ip_min_max_idx ON netblock_details
(ip_min, ip_max DESC NULLS LAST);
Anda dapat dengan cepat (di O(logN) ) temukan titik awal pemindaian di netblock_details tabel - baik maksimum n.ip_min yang kurang dari r.ip_min , atau minimum n.ip_max itu lebih dari r.ip_max . Tetapi kemudian Anda harus memindai/membaca sisa indeks/tabel dan untuk setiap baris lakukan pemeriksaan bagian kedua dan filter sebagian besar baris.
Dengan kata lain, indeks ini membantu dengan cepat menemukan baris awal yang memenuhi kriteria pencarian pertama:n.ip_min <= r.ip_min , tetapi kemudian Anda akan melanjutkan membaca semua baris yang memenuhi kriteria ini dan untuk setiap baris tersebut lakukan pemeriksaan kedua n.ip_max >= r.ip_max . Rata-rata (jika data memiliki distribusi yang merata) Anda harus membaca setengah dari baris netblock_details meja. Pengoptimal dapat memilih untuk menggunakan indeks untuk mencari n.ip_max >= r.ip_max pertama lalu terapkan filter kedua n.ip_min <= r.ip_min , tetapi Anda tidak dapat menggunakan indeks ini untuk menerapkan kedua filter secara bersamaan.
Hasil akhir:untuk setiap baris dari routing_details kita akan membaca setengah baris dari netblock_details . 600K * 4M =2.400.000.000.000 baris. Ini 2 kali lebih baik dari produk Cartesian. Anda dapat melihat nomor ini (produk Cartesian) pada output EXPLAIN ANALYZE dalam pertanyaan.
592,496 * 8,221,675 = 4,871,309,550,800
Tidak heran kueri Anda kehabisan ruang disk saat mencoba mewujudkan dan mengurutkan ini.
Keseluruhan proses tingkat tinggi untuk mencapai hasil akhir:
-
gabungkan dua tabel (tanpa menemukan yang paling cocok). Dalam kasus terburuk itu adalah produk Cartesian, dalam kasus terbaik itu semua mencakup rentang dari
netblock_detailsuntuk setiap rentang darirouting_details. Anda mengatakan bahwa ada beberapa entri dinetblock_detailsuntuk setiap entri dirouting_details, mulai dari 3 hingga sekitar 10. Jadi, hasil penggabungan ini dapat memiliki ~6 juta baris (tidak terlalu banyak) -
urutkan/partisi hasil join dengan
routing_detailsrentang dan untuk setiap rentang tersebut temukan rentang cakupan terbaik (terkecil) darinetblock_details.
Ide saya adalah membalikkan kueri. Alih-alih menemukan semua rentang cakupan dari netblock_details yang lebih besar untuk setiap baris dari routing_details yang lebih kecil tabel Saya sarankan untuk menemukan semua rentang yang lebih kecil dari routing_details yang lebih kecil untuk setiap baris dari netblock_details yang lebih besar .
Proses dua langkah
Untuk setiap baris dari netblock_details yang lebih besar temukan semua rentang dari routing_details yang ada di dalam netblock jangkauan.
Saya akan menggunakan skema berikut dalam kueri. Saya telah menambahkan kunci utama ID ke kedua tabel.
CREATE TABLE routing_details (
ID int
,ip_min int8
,ip_max int8
,asn text
,netblock text
);
CREATE TABLE netblock_details (
ID int
,ip_min int8
,ip_max int8
,name text
,country text
,source text
);
SELECT
netblock_details.ID AS n_ID
,netblock_details.ip_max - netblock_details.ip_min AS n_length
,r.ID AS r_ID
FROM
netblock_details
INNER JOIN LATERAL
(
SELECT routing_details.ID
FROM routing_details
WHERE
routing_details.ip_min >= netblock_details.ip_min
AND routing_details.ip_min <= netblock_details.ip_max
-- note how routing_details.ip_min is limited from both sides
-- this would make it possible to scan only (hopefully) small
-- portion of the table instead of full or half table
AND routing_details.ip_max <= netblock_details.ip_max
-- this clause ensures that the whole routing range
-- is inside the netblock range
) AS r ON true
Kami membutuhkan indeks pada routing_details di (ip_min, ip_max) . Hal utama di sini adalah indeks pada ip_min . Memiliki kolom kedua dalam indeks membantu menghilangkan kebutuhan untuk melakukan pencarian nilai ip_max; itu tidak membantu dalam pencarian pohon.
Perhatikan bahwa subquery lateral tidak memiliki LIMIT . Ini belum merupakan hasil akhir. Kueri ini harus mengembalikan ~6 juta baris. Simpan hasil ini di tabel sementara. Tambahkan indeks ke tabel sementara di (r_ID, n_length, n_ID) . n_ID lagi hanya untuk menghapus pencarian tambahan. Kami membutuhkan indeks, hindari menyortir data untuk setiap r_ID .
Langkah terakhir
Untuk setiap baris dari routing_details temukan n_ID dengan n_length terkecil . Sekarang kita dapat menggunakan sambungan lateral dalam urutan yang "tepat". Di sini temp tabel adalah hasil dari langkah sebelumnya dengan indeks .
SELECT
routing_details.*
,t.n_ID
,netblock_details.*
FROM
routing_details
INNER JOIN LATERAL
(
SELECT temp.n_ID
FROM temp
WHERE temp.r_ID = routing_details.ID
ORDER BY temp.n_length
LIMIT 1
) AS t ON true
INNER JOIN netblock_details ON netblock_details.ID = t.n_ID
Di sini subquery harus mencari indeks, bukan memindai. Pengoptimal harus cukup pintar untuk melakukan pencarian dan mengembalikan hasil pertama yang ditemukan karena LIMIT 1 , jadi Anda akan memiliki 600 ribu pencarian indeks di tabel temp baris 6 juta.
Jawaban asli (saya akan menyimpannya hanya untuk diagram rentang):
Bisakah Anda "menipu"?
Jika saya memahami kueri Anda dengan benar, untuk setiap routing_details.range anda ingin menemukan netblock_details.range terkecil yang mencakup/lebih besar dari routing_details.range .
Diberikan contoh berikut, di mana r adalah rentang perutean dan n1, ..., n8 adalah rentang netblock, jawaban yang benar adalah n5 .
|---|
n1
|------------------|
n2
|---------------|
n3
|-----|
n4
|------------------|
n5
|--------------------------------------|
n6
|---------------------------|
n7
|-----|
n8
|------------|
r
start end
n.start <= r.start AND n.end >= r.end
order by n.length
limit 1
Kueri yang memakan waktu 14 jam menunjukkan bahwa pemindaian indeks membutuhkan waktu 6 md, tetapi pengurutan berdasarkan panjang rentang membutuhkan waktu 80 md.
Dengan pencarian semacam ini tidak ada urutan data 1D yang sederhana. Anda menggunakan n.start bersama dengan n.end dan bersama dengan n.length . Namun, mungkin data Anda tidak terlalu umum, atau boleh saja mengembalikan hasil yang agak berbeda.
Misalnya, jika boleh mengembalikan n6 sebagai hasilnya, itu bisa bekerja lebih cepat. n6 adalah rentang cakupan yang memiliki start terbesar :
n.start <= r.start AND n.end >= r.end
order by n.start desc
limit 1
Atau, Anda bisa menggunakan n7 , yang memiliki end smallest terkecil :
n.start <= r.start AND n.end >= r.end
order by n.end
limit 1
Pencarian semacam ini akan menggunakan indeks sederhana pada n.start (atau n.end ) tanpa penyortiran ekstra.
Pendekatan kedua yang sama sekali berbeda. Berapa besar/panjang rentangnya? Jika jumlahnya relatif pendek (beberapa angka), maka Anda dapat mencoba menyimpannya sebagai daftar bilangan bulat eksplisit, alih-alih rentang. Misalnya, rentang [5-8] akan disimpan sebagai 4 baris:(5, 6, 7, 8) . Dengan model penyimpanan ini, mungkin lebih mudah untuk menemukan perpotongan rentang.
