Kueri halaman dalam—di mana nomor halaman besar tetapi set hasil kecil—menyebabkan degradasi kinerja parah pada database analitik. PolarDB for MySQL mendesain ulang operator Sort/TopK dalam fitur indeks kolom in-memory (IMCI) untuk menangani halaman dalam secara efisien, menggunakan filter input self-sharpening yang dipercepat SIMD untuk eksekusi in-memory dan pemangkasan berbasis ZoneMap sebagai fallback berbasis disk. Pada dataset TPC-H 100 GB, operator yang didesain ulang menyelesaikan kueri halaman dalam dalam 7,72 detik, dibandingkan dengan 23,07 detik untuk ClickHouse dan 353,15 detik untuk MySQL.
Permasalahan halaman dalam
Pola kueri umum dalam sistem bisnis adalah memfilter catatan, mengurutkan berdasarkan kolom, lalu melakukan paginasi terhadap hasilnya. Dalam SQL:
ORDER BY column LIMIT offset, countUntuk 100 catatan per halaman:
| Halaman | Kueri |
|---|---|
| Halaman 1 | ORDER BY column LIMIT 0, 100 |
| Halaman 10.001 | ORDER BY column LIMIT 1000000, 100 |
Pada kueri kedua, K (offset + count) sama dengan 1.000.100, meskipun hanya 100 catatan yang dikembalikan. Asimetri antara K dan ukuran set hasil ini mendefinisikan halaman dalam—dan mengungkap kelemahan algoritma TopK standar.
Pendekatan industri dan trade-off-nya
Tiga pendekatan utama digunakan dalam praktik. Masing-masing mengurangi operasi pada data di luar set hasil, tetapi masing-masing gagal dengan cara berbeda dalam skenario halaman dalam.
Antrian prioritas (TopK berbasis heap)
Sistem mempertahankan max-heap berukuran K. Untuk setiap catatan yang dipindai, sistem memeriksa apakah catatan tersebut termasuk dalam top K: jika ya, elemen teratas diganti dan heap diseimbangkan ulang. Setelah pemindaian penuh, heap berisi K catatan terbesar.
Pendekatan ini bekerja baik saat K kecil. Pada K besar—seperti 1.000.100—dua masalah muncul:
Tekanan memori: heap mungkin tidak muat di memori.
Ketidakefisienan cache: operasi heap memerlukan akses memori acak. Pada K besar, hal ini menyebabkan cache miss yang sering dan menurunkan throughput.
Pemangkasan selama pengurutan gabungan
Digunakan oleh PolarDB, ClickHouse, SQL Server, dan DuckDB. Sistem menghasilkan run terurut selama proses pengurutan dan memangkas setiap run yang digabung menjadi offset + limit catatan. Hanya catatan dalam rentang [offset, offset + limit) yang relevan, sehingga tidak perlu mengurutkan seluruh data.
Pendekatan ini dapat diskalakan ke disk saat memori tidak mencukupi. Namun, pemangkasan hanya membantu setelah run terurut cukup panjang. Untuk halaman dalam dengan K besar, run terurut pada tahap awal penggabungan sering kali lebih pendek daripada offset + limit, sehingga seluruh dataset harus diurutkan sebelum pemangkasan berlaku.
Filter input self-sharpening
Pertama kali diusulkan oleh Goetz Graefe dan diadopsi oleh ApsaraDB for ClickHouse. Sistem mempertahankan cutoff value—batas atas nilai catatan yang dapat muncul dalam hasil top K. Catatan yang nilainya melebihi cutoff dikecualikan sebelum masuk ke run terurut. Setelah setiap run terurut dibuat, jika panjang run melebihi K, catatan ke-K menjadi cutoff baru. Cutoff baru selalu kurang dari atau sama dengan cutoff lama, sehingga filter terus-menerus semakin tajam.
Contoh (K = 3):
| Batch | Run terurut | Cutoff |
|---|---|---|
| 1 | (1, 2, 10, 15, 21) | 10 |
| 2 | (2, 3, 5, 6, 8) (difilter sebelumnya pada 10) | 5 |
| 3 | (1, 2, 3, 3, 3) (difilter sebelumnya pada 5) | 3 |
Berbeda dengan operasi heap, filter self-sharpening mengakses memori secara sekuensial baik selama filtering cutoff maupun akumulasi run terurut. Hal ini menghindari penalti akses acak dari pemeliharaan heap.
Mengapa halaman dalam merusak kedua pendekatan
Pada LIMIT 1000000, 100, K bernilai 1.000.100 tetapi hanya 100 catatan yang dikembalikan. Hal ini mengungkap batasan masing-masing pendekatan:
Berbasis heap: mempertahankan 1.000.100 entri heap menghasilkan overhead akses memori acak yang parah bahkan ketika memori tersedia.
Pemangkasan pengurutan gabungan: run terurut jarang melebihi 1.000.100 catatan pada tahap awal pengurutan, sehingga pemangkasan tidak dapat diterapkan dan seluruh dataset harus diurutkan.
"Memori mencukupi" di sini berarti struktur data yang mengelola K catatan muat di memori—bukan bahwa seluruh dataset masukan muat. Dalam skenario yang dijelaskan dalam topik ini, data masukan jauh melebihi memori yang tersedia.
Dua persyaratan desain tambahan berlaku:
Algoritma terpadu harus menangani halaman dangkal dan halaman dalam tanpa ambang batas keras di antara keduanya.
Sistem harus memilih eksekusi memori atau disk secara dinamis berdasarkan memori yang tersedia, bukan konfigurasi statis.
Desain solusi
Operator Sort/TopK IMCI PolarDB yang didesain ulang menggabungkan keunggulan pendekatan yang ada sekaligus mengatasi kegagalannya dalam skenario halaman dalam.
Algoritma memori: filter input self-sharpening yang dipercepat SIMD
Saat memori mencukupi, IMCI menggunakan filter input self-sharpening alih-alih antrian prioritas. Alasan tidak menggunakan antrian prioritas pada K besar:
Akses memori acak selama pemeliharaan heap menurunkan kinerja pada K besar.
Ukuran heap harus sama dengan K, sehingga tekanan memori meningkat secara linear seiring K.
Filter self-sharpening menghindari kedua masalah tersebut:
Baik filtering cutoff maupun akumulasi run terurut mengakses memori secara sekuensial.
Filter ini bekerja dengan benar pada nilai K apa pun, mencakup halaman dangkal dan halaman dalam tanpa kondisi batas.
Akselerasi SIMD: Filtering cutoff bersifat sederhana, repetitif, dan sering—membandingkan setiap catatan dengan cutoff saat ini. IMCI mempercepat proses ini menggunakan instruksi single instruction multiple data (SIMD), yang menerapkan perbandingan yang sama pada beberapa catatan secara paralel. Filter ini menggunakan kembali infrastruktur evaluasi ekspresi yang sama dengan filter predikat pemindaian tabel, sehingga tidak diperlukan jalur kode tambahan.
Algoritma disk: pemangkasan berbasis ZoneMap dengan pengurutan gabungan
Saat memori tidak mencukupi, IMCI menggunakan pengurutan gabungan dengan pemangkasan. Alasan tidak menggunakan filter self-sharpening pada disk:
Menyimpan run terurut yang terakumulasi ke disk dan menjalankan pengurutan eksternal selama premerge menghasilkan volume I/O disk yang besar.
Untuk K besar, premerge mungkin memproses jumlah data signifikan di luar rentang
[offset, offset + limit)sebelum cutoff yang berguna ditetapkan.
Pengurutan gabungan dengan pemangkasan menghindari masalah ini, dan pemangkasan berbasis ZoneMap lebih lanjut menghilangkan I/O dengan menggunakan statistik min/maks dari run terurut untuk melewatkan run yang tidak berkontribusi terhadap hasil.
Cara kerja pemangkasan ZoneMap:
Setiap run terurut menyimpan nilai minimum dan maksimumnya. Nilai barrier membagi semua run terurut menjadi tiga tipe:
| Tipe | Kondisi | Contoh |
|---|---|---|
| Tipe A | min dan max keduanya < barrier | Run1, Run2 |
| Tipe B | min < barrier, max > barrier | Run3 |
| Tipe C | min dan max keduanya > barrier | Run4, Run5 |
Dua aturan pemangkasan menghilangkan run terurut yang tidak memengaruhi hasil:
Jika total catatan pada Tipe A + Tipe B <
offset, semua catatan Tipe A berada dalam rentang[0, offset). Kecualikan Tipe A dari penggabungan selanjutnya.Jika total catatan pada Tipe A >
offset + limit, semua catatan Tipe C berada dalam rentang[offset + limit, N). Kecualikan Tipe C dari penggabungan selanjutnya.
Proses pemangkasan:
Buat ZoneMap yang berisi nilai min dan max dari setiap run terurut.
Temukan Barrier 1 (sebesar mungkin) di mana catatan pada Tipe A + Tipe B <
offset.Temukan Barrier 2 (sekecil mungkin) di mana catatan pada Tipe A >
offset + limit.Gunakan Barrier 1 dan Barrier 2 untuk mengecualikan run terurut yang sesuai dari penggabungan selanjutnya.
Pemilihan algoritma dinamis
Alih-alih menggunakan ambang batas K tetap, IMCI secara dinamis memilih algoritma dengan mekanisme fallback:
Selalu mulai dengan algoritma memori.
Jika memori tetap mencukupi sepanjang proses, selesaikan perhitungan di memori.
Jika memori habis—misalnya, tidak cukup ruang untuk menyimpan cache run terurut yang berisi lebih dari K catatan, atau tidak cukup ruang untuk menyelesaikan premerge—picu fallback:
Kumpulkan nilai min/maks dari run terurut di memori dan bangun ZoneMap.
Simpan run terurut tersebut ke disk.
Beralih ke algoritma disk untuk sisa perhitungan.
Selesaikan perhitungan menggunakan algoritma disk.
Kedua algoritma menggunakan struktur data yang sama, sehingga fallback tidak memerlukan reorganisasi data. Run terurut yang terakumulasi selama fase memori langsung digunakan oleh algoritma disk tanpa kehilangan akurasi.
Optimisasi rekayasa
Materialisasi tertunda
Saat membangun run terurut, IMCI hanya mematerialisasi ID baris dan kolom atau ekspresi yang dirujuk dalam ORDER BY. Kolom output diambil dari penyimpanan setelah set hasil TopK ditentukan.
Hal ini mengurangi overhead dalam dua cara:
ID baris bersifat ringkas, sehingga lebih banyak catatan muat dalam anggaran memori yang sama, memperluas rentang penerapan algoritma memori.
Catatan sering diurutkan ulang selama perhitungan TopK melalui operasi Copy dan Swap. Mematerialisasi hanya ID baris meminimalkan biaya per catatan dari operasi ini.
Trade-off-nya: mengambil kolom output berdasarkan ID baris setelah pengurutan mungkin memerlukan I/O acak. Dalam skenario halaman dalam, set hasil aktual kecil (misalnya, 100 catatan), sehingga I/O acak ini dapat diabaikan.
Pushdown komputasi
Selama eksekusi filter self-sharpening, nilai cutoff saat ini didorong ke operator pemindaian tabel sebagai predikat baru. Pemindaian tabel kemudian dapat menerapkan predikat ini menggunakan infrastruktur pruner yang ada, melakukan filtering di tingkat pack atau grup baris sebelum data mencapai operator TopK.
Hal ini mengurangi overhead dalam dua cara:
Pengurangan I/O: pack atau grup baris yang hanya berisi catatan di atas cutoff dilewati sepenuhnya.
Pengurangan komputasi: pack atau grup baris yang difilter tidak diproses oleh operator lapisan atas.
Hasil pengujian
Kueri berikut dijalankan terhadap dataset TPC-H 100 GB:
SELECT
l_orderkey,
sum(l_quantity)
FROM
lineitem
GROUP BY
l_orderkey
ORDER BY
sum(l_quantity) DESC
LIMIT
1000000, 100;| Sistem | Waktu eksekusi |
|---|---|
| PolarDB IMCI | 7,72 detik |
| ClickHouse | 23,07 detik |
| MySQL | 353,15 detik |