PolarDB：Implementasi operator TopK pada IMCI

Informasi latar belakang

Dalam sistem bisnis, skenario umum adalah pengguna ingin menyaring rekaman untuk menemukan set rekaman tertentu, mengurutkan hasil berdasarkan kondisi, dan menampilkan hasilnya per halaman. Sebagai contoh, pengguna mungkin ingin menyaring produk yang dijual untuk menemukan produk yang dijual oleh pedagang tertentu, mengurutkan hasil berdasarkan volume penjualan, dan menampilkan hasilnya per halaman. Skenario tersebut biasanya diimplementasikan dalam database menggunakan pernyataan query seperti ORDER BY column LIMIT n, m.

Jika 100 rekaman ditampilkan per halaman dalam sistem bisnis, Anda dapat mengeksekusi pernyataan berikut untuk menampilkan rekaman pada halaman tertentu:

• Eksekusi pernyataan ORDER BY column LIMIT 0, 100 untuk menampilkan rekaman pada halaman 1.

• Eksekusi pernyataan ORDER BY column LIMIT 1.000.000, 100 untuk menampilkan rekaman pada halaman 10.001.

Dalam kasus indeks tidak ada, query semacam itu diimplementasikan menggunakan algoritma TopK berbasis heap klasik dalam database berdasarkan logika berikut: Sistem mempertahankan heap berukuran K di memori. Elemen teratas dalam heap adalah elemen terkecil. Sistem membandingkan elemen yang dilintasi dengan elemen teratas. Jika sebuah elemen lebih besar dari elemen teratas, elemen teratas diganti dengan elemen baru dan heap dibangun ulang. Setelah semua elemen dilintasi, elemen-elemen dalam heap adalah elemen K terbesar pertama. Jika nomor halaman halaman yang ingin ditampilkan kecil, seperti halaman 1 dalam contoh sebelumnya, K relatif kecil. Dalam hal ini, efisien menggunakan algoritma TopK berbasis heap dalam query.

Namun, query halaman dalam juga ada dalam skenario bisnis, di mana Anda ingin menampilkan rekaman pada halaman dengan nomor halaman sangat besar, seperti halaman 10.001. Dalam hal ini, K sangat besar, dan memori mungkin tidak cukup untuk menyimpan cache heap berukuran K. Oleh karena itu, hasil query tidak dapat diperoleh menggunakan algoritma TopK berbasis heap. Bahkan jika memori cukup, efisiensi algoritma TopK berbasis heap menurun ketika ukuran heap sangat besar karena akses memori acak selama pemeliharaan heap, dan performa akhirnya tidak memuaskan.

Awalnya, fitur IMCI dari PolarDB for MySQL menggunakan metode sebelumnya untuk mengimplementasikan query berhalaman. Jika memori tidak cukup untuk menyimpan cache heap berukuran K, sistem mengurutkan semua rekaman dalam tabel dan menyimpan cache rekaman dalam rentang yang ditentukan. Akibatnya, performa IMCI dalam query halaman dalam tidak sebaik yang diharapkan. Untuk mengatasi masalah ini, PolarDB for MySQL merancang ulang Operator Sort/TopK IMCI berdasarkan analisis karakteristik skenario halaman dalam dan masalah solusi tradisional. Dalam skenario uji, Operator Sort/TopK yang dirancang ulang secara signifikan meningkatkan performa IMCI dalam skenario halaman dalam.

Solusi yang ada untuk query TopK

Cara mengimplementasikan query TopK adalah masalah klasik di industri. Banyak solusi tersedia untuk mengimplementasikan query TopK secara efisien. Inti dari solusi-solusi ini adalah untuk mengurangi operasi pada data non-set hasil. Berikut tiga solusi utama dalam praktik.

Algoritma TopK berbasis antrian prioritas

Untuk informasi lebih lanjut, lihat bagian Informasi Latar Belakang dari topik ini.

Pemotongan berdasarkan offset dan batas selama penggabungan sortir

Jika memori tidak cukup untuk menyimpan cache antrian prioritas berukuran K, beberapa database, seperti PolarDB, ClickHouse, SQL Server, dan DuckDB, menggunakan penggabungan sortir untuk menangani masalah ini. Tujuan dari algoritma TopK hanya untuk menemukan rekaman dalam rentang [offset, offset + limit). Oleh karena itu, sistem tidak perlu mengurutkan semua data selama setiap penggabungan sortir. Sistem hanya perlu menghasilkan run baru yang diurutkan dengan panjang offset + limit. Pemotongan selama penggabungan dapat memastikan akurasi hasil dan mengurangi operasi pada data non-set hasil.

Filter input penguatan diri

Solusi ini pertama kali diusulkan dalam makalah Goetz Graefe. ApsaraDB for ClickHouse mengadopsi solusi ini. Selama query TopK yang didasarkan pada solusi ini, sistem mempertahankan nilai cutoff dan mengecualikan rekaman yang lebih besar dari nilai cutoff dari set hasil query TopK. Untuk menghasilkan run baru yang diurutkan, sistem menggunakan nilai cutoff saat ini untuk menyaring data. Setelah run baru yang diurutkan dihasilkan, jika K kurang dari panjang run baru yang diurutkan, nilai cutoff saat ini diganti dengan rekaman ke-K dalam run baru yang diurutkan. Data dalam run baru yang diurutkan disaring menggunakan nilai cutoff lama. Oleh karena itu, nilai cutoff baru selalu kurang dari atau sama dengan nilai cutoff lama. Dengan cara ini, nilai cutoff terus-menerus diperkuat sendiri. Pada akhirnya, sistem hanya perlu menggabungkan run yang diurutkan dan disaring untuk mendapatkan set hasil.

Contoh berikut mengilustrasikan algoritma sebelumnya: Dalam query TopK saat ini, nilai K adalah 3. Setelah batch data pertama dibaca, run pertama yang diurutkan adalah (1, 2, 10, 15, 21), dan nilai cutoff diperbarui menjadi 10. Selanjutnya, nilai cutoff 10 digunakan untuk menyaring batch data kedua. Run kedua yang diurutkan adalah (2, 3, 5, 6, 8), dan nilai cutoff diperbarui menjadi 5. Kemudian, nilai cutoff 5 digunakan untuk menyaring batch data ketiga. Run ketiga yang diurutkan adalah (1, 2, 3, 3, 3), dan nilai cutoff diperbarui menjadi 3. Run yang diurutkan dan nilai cutoff berikutnya diperoleh dengan cara yang sama. Nilai cutoff yang terus diperkuat digunakan untuk menyaring lebih banyak data.

Jika K lebih besar dari panjang run yang diurutkan, sistem mengumpulkan cukup run yang diurutkan dengan lebih dari K rekaman dan melakukan pra-penggabungan run yang diurutkan yang terakumulasi untuk mendapatkan nilai cutoff. Selanjutnya, sistem menggunakan nilai cutoff untuk menyaring data dan mengumpulkan cukup run yang diurutkan. Lalu, sistem melakukan pra-penggabungan run yang diurutkan ini untuk mendapatkan nilai cutoff yang lebih kecil, dan seterusnya. Seluruh proses serupa dengan kasus di mana K kurang dari panjang run yang diurutkan. Perbedaannya terletak pada bahwa cukup run yang diurutkan digabungkan untuk mendapatkan nilai cutoff.

Analisis masalah

Query halaman dalam adalah query TopK khusus. Dalam query halaman dalam, K sangat besar, tetapi set hasil aktualnya kecil. Sebagai contoh, dalam pernyataan ORDER BY column LIMIT 1000000, 100, K adalah 1.000.100, tetapi set hasil aktual hanya berisi 100 rekaman. Ini membawa tantangan berikut untuk solusi yang dijelaskan di bagian sebelumnya:

• Jika memori cukup dan sistem menggunakan algoritma TopK berbasis antrian prioritas, antrian prioritas berukuran sangat besar perlu dipertahankan. Akses memori acak dari operasi antrian menurunkan efisiensi akses memori, yang memperburuk performa aktual algoritma.

• Jika memori tidak cukup dan sistem melakukan pemotongan berdasarkan offset dan batas dalam penggabungan sortir, pemotongan mungkin tidak dapat dilakukan selama tahap awal penggabungan sortir karena panjang run yang diurutkan mungkin kurang dari offset + limit. Akibatnya, semua data diurutkan dan efek pemotongan terpengaruh.

Selain itu, dari sudut pandang desain sistem, item berikut harus dipertimbangkan ketika Anda merancang solusi untuk halaman dalam:

• Apakah solusi yang berbeda diperlukan untuk mengimplementasikan query dalam skenario halaman dalam dan halaman dangkal? Jika solusi yang berbeda digunakan dalam dua skenario, bagaimana sistem menentukan batas antara halaman dalam dan halaman dangkal?

• Bagaimana sistem secara adaptif memilih algoritma memori atau disk berdasarkan ukuran memori?

Desain solusi

Desain keseluruhan

Menggabungkan penelitian dan analisis yang dijelaskan dalam bagian sebelumnya, PolarDB for MySQL merancang ulang Operator Sort/TopK IMCI untuk menyelesaikan masalah halaman dalam berdasarkan solusi yang ada.

• Jika memori cukup, algoritma memori berikut digunakan:

  • Solusi filter input penguatan diri diadopsi untuk mencegah masalah efisiensi akses memori rendah.

  • Di atas dasar ini, instruksi single instruction multiple data (SIMD) digunakan untuk meningkatkan efisiensi penyaringan.

  • Algoritma ini digunakan baik dalam skenario halaman dalam maupun halaman dangkal tanpa perlu menentukan batas antara halaman dalam dan halaman dangkal.

• Jika memori tidak cukup, algoritma disk berikut digunakan:

  • Pemotongan dilakukan berdasarkan offset dan batas selama penggabungan sortir.

  • Di atas dasar ini, ZoneMap digunakan pada tahap awal penggabungan sortir untuk pemangkasan. Ini mengurangi operasi pada data non-set hasil sebanyak mungkin.

• Algoritma memori atau disk dipilih secara dinamis. Alih-alih bergantung pada ambang tetap, algoritma dipilih secara dinamis selama eksekusi berdasarkan jumlah memori yang tersedia.

Solusi filter input penguatan diri dan pemotongan berdasarkan offset dan batas selama penggabungan sortir telah dijelaskan dalam bagian sebelumnya. Bagian berikutnya menjelaskan mengapa dua solusi tersebut dipilih. Selain itu, bagian berikutnya menjelaskan bagaimana instruksi SIMD digunakan untuk meningkatkan efisiensi penyaringan data, bagaimana ZoneMap digunakan untuk pemangkasan, dan bagaimana algoritma memori atau disk dipilih secara dinamis.

Filter input penguatan diri yang dipercepat SIMD

Jika memori cukup, solusi filter input penguatan diri langsung digunakan untuk dua alasan utama:

• Dalam solusi filter input penguatan diri, tidak peduli apakah sistem menggunakan nilai cutoff untuk menyaring data atau pra-penggabungan run yang diurutkan, akses memori bersifat berurutan. Ini mencegah efisiensi akses memori rendah dari antrian prioritas.

• Solusi ini memberikan kinerja query yang sangat baik baik dalam skenario halaman dalam maupun halaman dangkal. Anda tidak perlu mempertimbangkan batas antara halaman dalam dan halaman dangkal.

Faktanya, solusi filter input penguatan diri mirip dengan algoritma berbasis antrian prioritas sampai batas tertentu. Nilai cutoff mirip dengan elemen teratas dalam heap, keduanya digunakan untuk menyaring data yang dibaca. Perbedaannya adalah bahwa algoritma berbasis antrian prioritas memperbarui elemen teratas dalam heap secara real-time, sedangkan solusi filter input penguatan diri mengakumulasi data dalam run yang diurutkan dan memperbarui nilai cutoff menggunakan batch data.

Menggunakan nilai cutoff untuk menyaring data adalah proses penting dalam solusi filter input penguatan diri. Perbandingan data terlibat dalam proses ini, di mana operasinya sederhana dan repetitif tetapi sering dilakukan. Oleh karena itu, instruksi SIMD digunakan untuk mempercepat proses ini. Filter nilai cutoff mirip dengan filter predikat yang digunakan dalam pemindaian tabel. Oleh karena itu, ekspresi yang memproses predikat dapat digunakan kembali secara langsung untuk meningkatkan efisiensi penyaringan dan mengurangi waktu perhitungan TopK.

Pemangkasan berbasis ZoneMap

Jika memori tidak cukup, penggabungan sortir digunakan dan pemotongan dilakukan berdasarkan offset dan batas karena alasan berikut:

• Jika sistem terus menggunakan solusi filter input penguatan diri ketika memori tidak cukup, sistem perlu menyimpan run yang diurutkan yang terakumulasi ke disk, dan menggunakan algoritma sortir eksternal selama pra-penggabungan, yang mengarah pada sejumlah besar operasi baca dan tulis disk. Dibandingkan dengan solusi filter input penguatan diri yang digunakan dalam skenario di mana memori cukup, ini menyebabkan overhead tambahan. Jika K sangat besar, sortir eksternal yang digunakan selama pra-penggabungan mungkin melibatkan sejumlah besar data non-set hasil. Hal ini karena query TopK hanya perlu mendapatkan rekaman dalam rentang [offset, offset + limit) dan rekaman dalam rentang [0, offset) tidak relevan.

• Dalam hal ini, penggabungan sortir dapat digunakan. Ketika run yang diurutkan dihasilkan, sistem hanya menyimpan run yang diurutkan ke disk dan kemudian menggunakan statistik untuk pemangkasan. Ini mencegah operasi baca dan tulis disk yang tidak perlu dan juga mengurangi operasi pada data non-set hasil sebanyak mungkin.

Gambar berikut menunjukkan bagaimana statistik digunakan untuk pemangkasan. Dalam gambar, panah menunjukkan sumbu angka dan persegi panjang menunjukkan run yang diurutkan. Posisi kiri dan kanan persegi panjang pada sumbu menunjukkan nilai minimum dan maksimum dari run yang diurutkan. Penghalang menunjukkan ambang batas untuk pemangkasan. ARRIER

• Penghalang dapat membagi semua run yang diurutkan menjadi tiga jenis:

  • Tipe A: run yang diurutkan yang nilai minimum dan maksimumnya keduanya kurang dari penghalang. Contoh: Run1 dan Run2.

  • Tipe B: run yang diurutkan yang nilai minimumnya kurang dari penghalang tetapi nilai maksimumnya lebih besar dari penghalang. Contoh: Run 3.

  • Tipe C: run yang diurutkan yang nilai minimum dan maksimumnya keduanya lebih besar dari penghalang. Contoh: Run4 dan Run5.

• Untuk penghalang, jika jumlah total rekaman dalam semua run yang diurutkan Tipe A dan Tipe B kurang dari nilai offset query TopK, rekaman dalam run yang diurutkan Tipe A pasti berada dalam rentang [0, offset). Dalam hal ini, run yang diurutkan Tipe A dapat dikecualikan dari penggabungan berikutnya.

• Untuk penghalang, jika jumlah total rekaman dalam semua run yang diurutkan Tipe A lebih besar dari jumlah offset + limit query TopK, rekaman dalam run yang diurutkan Tipe C pasti berada dalam rentang [offset + limit, N). Dalam hal ini, run yang diurutkan Tipe C dapat dikecualikan dari penggabungan berikutnya.

Berdasarkan aturan sebelumnya, statistik digunakan untuk pemangkasan dalam proses berikut:

1. Bangun ZoneMap yang berisi nilai minimum dan maksimum run yang diurutkan.

2. Dalam ZoneMap, temukan Barrier 1 yang sebesar mungkin dan memenuhi kondisi berikut: Jumlah rekaman dalam run yang diurutkan Tipe A dan Tipe B kurang dari offset query TopK.

3. Dalam ZoneMap, temukan Barrier 2 yang sekecil mungkin dan memenuhi kondisi berikut: Jumlah rekaman dalam run yang diurutkan Tipe A lebih besar dari jumlah offset + limit query TopK.

4. Gunakan Barrier1 dan Barrier2 untuk memangkas run yang diurutkan terkait.

Pemilihan algoritma memori atau disk dinamis

Algoritma memori berbeda dari algoritma disk. Anda mungkin ingin menggunakan ambang tertentu sebagai dasar untuk memilih algoritma memori atau disk. Sebagai contoh, Anda dapat memilih algoritma memori jika K kurang dari ambang dan sebaliknya memilih algoritma disk. Dalam hal ini, jika ukuran memori berubah, Anda harus menentukan ambang lain. Ini menyebabkan overhead intervensi manual.

Untuk mengatasi masalah ini, PolarDB for MySQL menggunakan mekanisme fallback sederhana untuk secara dinamis memilih algoritma yang akan digunakan berdasarkan ukuran memori yang tersedia selama eksekusi. Algoritma dipilih berdasarkan proses berikut:

• Tidak peduli berapa banyak memori yang tersedia, coba gunakan algoritma memori untuk perhitungan TopK terlebih dahulu.

• Selama eksekusi algoritma memori, gunakan algoritma memori untuk menyelesaikan seluruh perhitungan jika memori selalu cukup.

• Selama eksekusi algoritma memori, jalankan mekanisme fallback jika memori tidak cukup. Sebagai contoh, memori yang tersedia mungkin tidak cukup untuk menyimpan cache run yang diurutkan yang cukup mengandung lebih dari K rekaman, atau memori yang tersedia tidak cukup untuk menyelesaikan pra-penggabungan.

• Mekanisme fallback: Kumpulkan nilai minimum dan maksimum run yang diurutkan yang terakumulasi dalam memori sehingga ZoneMap dapat digunakan untuk memangkas run yang diurutkan, dan kemudian simpan run yang diurutkan ini ke disk. Run yang diurutkan ini digunakan dalam eksekusi algoritma disk.

• Setelah mekanisme fallback dijalankan, gunakan algoritma disk untuk menyelesaikan seluruh perhitungan.

Struktur data yang sama digunakan dalam algoritma memori dan disk. Oleh karena itu, mekanisme fallback tidak perlu mengatur ulang data. Overheadnya kecil. Selain itu, algoritma memori hanya menyaring data non-set hasil. Tidak ada masalah akurasi jika run yang diurutkan yang terakumulasi dalam algoritma memori digunakan secara langsung dalam eksekusi algoritma disk.

Lainnya

Materialisasi terlambat

Materialisasi terlambat adalah optimasi dalam implementasi teknik. Ketika run yang diurutkan dihasilkan, hanya ID baris dan ekspresi atau kolom yang terkait dengan ORDER BY yang dimaterialisasi. Setelah set hasil query TopK dihitung, kolom keluaran diperoleh dari penyimpanan berdasarkan ID baris dalam set hasil. Dibandingkan dengan materialisasi kolom keluaran ketika run yang diurutkan dihasilkan, materialisasi terlambat memiliki dua manfaat berikut:

• ID baris yang dimaterialisasi menempati ruang lebih sedikit. Jika memori yang tersedia sama, Anda dapat menggunakan algoritma memori untuk memproses lebih banyak data.

• Urutan data perlu disesuaikan selama perhitungan TopK, yang melibatkan operasi Copy dan Swap pada data. Jika semua kolom keluaran dimaterialisasi ketika run yang diurutkan dihasilkan, operasi Copy atau Swap untuk setiap rekaman harus dilakukan pada setiap kolom, yang menyebabkan overhead besar. Namun, jika hanya ID baris yang dimaterialisasi, biaya operasi Copy dan Swap dapat dikurangi.

Kerugian dari materialisasi terlambat adalah bahwa beberapa operasi I/O acak mungkin diperlukan untuk mendapatkan kolom keluaran dari penyimpanan berdasarkan ID baris. Namun, analisis menunjukkan bahwa dalam skenario halaman dalam, meskipun K sangat besar, set hasil aktualnya kecil. Oleh karena itu, overhead dari operasi I/O acak yang disebabkan oleh materialisasi terlambat kecil.

Penurunan komputasi

Selama eksekusi algoritma filter input penguatan diri, sistem mendorong nilai cutoff yang terus diperbarui ke operator pemindaian tabel. Nilai cutoff dapat berfungsi sebagai predikat baru dalam pernyataan SQL. Ketika operator pemindaian tabel mendapatkan data, operator dapat menggunakan pruner kembali untuk menyaring data dalam paket atau grup baris berdasarkan predikat baru.

Penurunan komputasi dapat meningkatkan kinerja query TopK dalam dua cara:

• Mengurangi operasi I/O: Selama pemindaian tabel, sistem tidak membaca paket atau grup baris yang hanya berisi data non-set hasil.

• Mengurangi komputasi: Data dalam paket atau grup baris yang difilter tidak lagi digunakan untuk komputasi berikutnya dari operator lapisan atas.

Hasil uji

Verifikasi sederhana dari solusi dilakukan pada dataset TPC-H berukuran 100 GB.

select
    l_orderkey,
    sum(l_quantity)
from
    lineitem
group by
    l_orderkey
order by
    sum(l_quantity) desc
limit
    1000000, 100;

Tabel berikut menggambarkan hasil uji.