Latar Belakang
Dalam mode baris tradisional rencana eksekusi, SQL Server dapat memperkenalkan operator Bitmap sebagai bagian dari melakukan pengurangan semi-gabungan awal sebelum hash paralel atau gabung gabung. Bitmap dibangun dari input build, dan digunakan untuk memfilter baris pada input probe sebelum mencapai join. Saya telah menulis tentang mode baris bitmap sebelumnya dan juga tercakup dalam dokumentasi.
Artikel ini tentang mode batch bitmap, yang memiliki implementasi yang sangat berbeda. Ada peningkatan besar sejak penampilan pertama mesin eksekusi mode batch di SQL Server 2012. Detail yang diberikan di sini berlaku untuk SQL Server 2017 — versi terbaru yang dirilis pada saat penulisan. Fitur khusus untuk versi sebelumnya akan disebutkan sebaris seiring berjalannya waktu.
Pengoptimal Kueri
Satu-satunya operator join yang dapat berjalan dalam mode batch adalah hash join. Pengoptimal kueri memutuskan apakah gabungan hash mode batch (serial atau paralel) harus memiliki bitmap atau tidak. Pengoptimal menilai potensi kegunaan bitmap dengan menghitung selektivitas dari semi join hipotetis dari input hash join pada kunci join.
Semi join masuk akal, karena fungsi penyaringan bitmap adalah untuk menghapus baris dari sisi probe yang tidak ada di sisi build. Jika estimasi selektivitas dari semi join adalah 0,75 atau kurang, pengoptimal menganggapnya bermanfaat menggunakan filter bitmap mode batch. Dengan kata lain, bitmap ditentukan jika perhitungan semi join menunjukkan bahwa 25% atau lebih dari baris sisi probe akan dihilangkan oleh bitmap.
Selektivitas semi join yang tepat hanya digunakan untuk menentukan apakah hash join harus memiliki bitmap atau tidak. Perkiraan selektivitas sisi probe (terlihat sebagai efek pada perkiraan kardinalitas) dimodifikasi untuk mencerminkan fakta bahwa bitmap umumnya tidak sempurna dalam menghapus baris yang tidak memenuhi syarat. Hal ini terutama terjadi ketika bitmap diimplementasikan menggunakan filter Bloom, yang dapat menghasilkan positif palsu (baris sisi-penyelidik yang lolos filter, namun tidak bergabung dengan sisi build).
Pembulatan selektivitas
Pengoptimal memperhitungkan ketidakpastian ini dengan membulatkan selektivitas semi-gabungan menjadi pangkat sepuluh. Ini dilakukan dengan mengambil logaritma basis-10 sebelum pembulatan. Misalnya, selektivitas setengah gabungan sebesar 0,316 memberikan log10 nilai pecahan di bawah -0,5, yang dibulatkan ke bawah menjadi -1. Selektivitas sisi probe yang dihasilkan adalah 10 =0,1. Sebaliknya, selektivitas semi join sebesar 0,317 memberikan log10 nilai tepat di atas -0,5, yang dibulatkan menjadi nol. Oleh karena itu, selektivitas sisi probe adalah 10 =1 (semua baris lulus). Kemungkinan selektivitas bitmap sisi penyelidikan yang dihasilkan dari rangkaian perhitungan ini adalah 1, 0,1, 0,01, 0,001 dan seterusnya. Perhatikan bahwa bitmap masih dapat digunakan saat perkiraan selektivitas dibulatkan ke atas 1 (semua baris lulus predikat).
Estimasi operator dan kardinalitas
Tidak ada Bitmap yang terpisah operator untuk bergabung dengan mode batch. Sebagai gantinya, operator hash join memiliki Pembuat Bitmap properti (diatur ke true), atau properti tidak ada (tidak disetel ke false). Perbedaan antara eksekusi mode baris dan mode batch ini membuat lebih mudah untuk melihat apakah bitmap sedang dibuat, tetapi lebih akurat mencerminkan proses yang mendasarinya:Dalam eksekusi mode baris, Bitmap operator mengisi bitmap saat baris mengalir melaluinya, satu per satu, sebelum mencapai input hash join build. Dengan kata lain, tabel bitmap dan hash dibangun secara bersamaan di bawah eksekusi mode baris. Dalam mode batch, tabel hash dibuat sepenuhnya sebelum bitmap dibuat (lebih lanjut tentang ini segera).
Pengoptimal kueri tidak membuat pilihan berbasis biaya tentang posisi filter bitmap mode batch di sisi pemeriksaan gabungan hash. Ini hanya mengasumsikan bahwa selektivitas bitmap akan berlaku untuk semua operator anak di sisi probe. Pada kenyataannya, bitmap hanya didorong ke bawah sisi probe setelah satu rencana eksekusi akhir telah dipilih oleh pengoptimal. Jika bitmap tidak dapat didorong sepenuhnya ke operator daun, perkiraan kardinalitas akan terlihat agak aneh. Ini adalah pertukaran yang dapat ditingkatkan di masa mendatang.
Mesin Eksekusi
Sementara pengoptimal memutuskan apakah bitmap mode batch gabungan hash harus digunakan atau tidak, mesin eksekusi mode batch memutuskan jenis bitmap untuk digunakan saat runtime. Keputusan ini diinformasikan oleh informasi statistik yang dikumpulkan tentang kunci gabungan sisi build selama pembuatan tabel hash. Seperti yang disebutkan sebelumnya, berbeda dengan eksekusi mode baris, hash mode batch bergabung sepenuhnya untuk membangun tabel hash terlebih dahulu, sebelum melewati tabel hash secara terpisah dilakukan untuk membangun bitmap.
Bitmap Sederhana
Ada dua tipe utama dari batch mode hash join bitmap. sederhana bitmap berisi satu bit untuk masing-masing rentang nilai sisi build yang berdekatan. Misalnya, bitmap sederhana satu byte mampu menunjukkan apakah ada delapan nilai sisi build yang berdekatan atau tidak. Nilai 0 sampai 7 inklusif dapat dikodekan ke dalam bitmap dengan mengatur bit yang sesuai. Nilai 5 akan menetapkan bit 5, yang memiliki nilai posisi 2. Kita dapat mengkodekan himpunan {1, 5, 7} sebagai 2 + 2 + 2 =2 + 32 + 128 =162 =101000102 . Rentang nilai yang tidak dimulai dari nol dapat dikodekan dengan cara yang sama dengan mengimbangi semua nilai dengan nilai minimum yang ada dalam himpunan (yang kita ketahui dari statistik tabel hash).
Bitmap sederhana memiliki keuntungan menyimpan tepat informasi tentang nilai sisi build yang benar-benar ada, dengan biaya yang membutuhkan memori yang sebanding dengan rentang nilai yang ada.
Bitmap Kompleks
Jenis bitmap yang kedua adalah filter Bloom. Ini menetapkan satu atau lebih bit dalam struktur bitmap sesuai dengan hasil penerapan satu atau lebih fungsi hash ke setiap nilai sisi build. Kami menguji kecocokan dengan menerapkan fungsi hash yang sama untuk setiap nilai sisi probe. Jika salah satu fungsi hash mengidentifikasi bit yang tidak disetel, kami dapat yakin bahwa nilai probe saat ini tidak muncul di sisi build.
Karena filter Bloom adalah struktur probabilistik, kami mungkin tidak memfilter beberapa nilai probe yang tidak memiliki kecocokan sisi build (positif palsu), tetapi kami tidak akan pernah memfilter nilai yang ada (negatif palsu). Dengan kata lain, filter Bloom memberi tahu kita "mungkin cocok" atau "pasti tidak cocok". Tingkat positif palsu dapat dikurangi baik dengan menggunakan lebih banyak bit per kunci (bitmap yang lebih besar) atau lebih banyak fungsi hash. Agar jelas, filter Bloom mungkin menghasilkan pemfilteran yang tepat, tetapi mungkin juga tidak.
Filter Bloom menghadirkan alternatif yang hemat ruang dan waktu ketika bitmap sederhana tidak layak karena kebutuhan ruang. Implementasi mode batch SQL Server dari filter Bloom dioptimalkan untuk arsitektur cache CPU modern dan secara internal dikenal sebagai bitmap kompleks . Bitmap kompleks telah mendukung beberapa kolom gabungan dan semua tipe data mode batch sejak SQL Server 2014.
Pilihan Bitmap
Apakah SQL Server memilih sederhana atau kompleks (Filter mekar) bitmap bergantung pada rentang nilai sisi build (dari statistik tabel hash). Ada peringatan penting untuk kata "rentang" di sana, yang akan dijelaskan di bagian selanjutnya. Sementara itu, beginilah cara mesin eksekusi memilih jenis bitmap:
- Sebuah bitmap kecil sederhana digunakan ketika rentang nilai adalah 2 (8.388.608) atau kurang. Ini adalah jumlah bit dalam 1 MB.
- Bila rentang nilai lebih dari 2 tetapi kurang dari atau sama dengan 2 (8MB), mesin eksekusi memilih antara bitmap sederhana yang besar dan bitmap kompleks dengan menghitung memori yang diperlukan untuk setiap opsi dan memilih yang lebih kecil. Bitmap sederhana yang besar dapat berukuran hingga 8 MB. Ukuran bitmap kompleks tergantung pada jumlah bit per kunci yang diperlukan untuk mewakili data secara memadai. Nilai yang lebih berbeda biasanya berarti bitmap kompleks yang lebih besar.
- Jika rentang nilai lebih dari 2 bit, bitmap kompleks digunakan.
Tentang rentang nilai
Rentang nilai yang dirujuk di atas didasarkan pada biner internal representasi datanya. Misalnya, smallint nilai 128 dan 255 dapat direpresentasikan sebagai 0x0080 dan 0x00FF , memberikan rentang 0x7F (127) nilai biner. Rentang ini akan bekerja dengan baik dengan bitmap kecil sederhana.
Sebaliknya, datetime nilai “1900-01-01” dan “1900-01-02” dapat direpresentasikan dalam 8 byte sebagai 0x0000000100000000 dan 0x0000000200000000 (empat byte untuk hari dan empat byte untuk kutu setelah tengah malam). Representasi tersegmentasi ini memberikan rentang biner 0x0100000000 (4.294.967.296) untuk dua nilai contoh tersebut, yang terlalu besar untuk dimasukkan ke dalam bitmap sederhana (bahkan yang besar). Tipe data dengan representasi biner yang kompleks (misalnya pertukaran byte) biasanya tidak akan berfungsi dengan baik dengan bitmap sederhana.
Komplikasi lebih lanjut adalah bahwa data mode batch dinormalisasi — dikonversi ke tata letak biner yang berfungsi baik dengan instruksi vektor — dan selalu berukuran 64 bit. Nilai yang tidak dapat ditampung dalam 64 bit disimpan "di luar baris", dengan pointer 64-bit dalam baris. Layout biner ini tidak sama dengan yang dilaporkan oleh konversi T-SQL ke tipe biner.
Namun demikian, tata letak yang dinormalisasi cukup mirip untuk tipe integer (mis. integer dan bigint ) bahwa bitmap sederhana masih berguna untuk rentang tipe data ini. Jenis lain dengan representasi biner seperti bilangan bulat (mis. money dan date ) juga cocok.
Satu contoh lagi:Satu set integer nilai dalam rentang 1 hingga 8.388.608 akan hanya muat dalam bitmap sederhana kecil 1MB, menggunakan satu bit per kemungkinan nilai integer dalam kisaran. Rentang mungkin memiliki offset tetap, jadi rentang bilangan bulat 10.000.000 hingga 18.388.607 juga cocok (dengan offset sepuluh juta). Perhatikan bahwa nomor nilai yang ada tidak masalah, hanya kisarannya. Dua nilai 0 dan 8.388.607 akan mengisi rentang bitmap sederhana yang kecil serta kumpulan semua nilai yang mungkin di antara kedua ekstrem tersebut.
Tabel Rentang
Saat mesin eksekusi mode batch memutuskan untuk membuat sederhana besar bitmap atau kompleks bitmap untuk hash join, itu juga membangun tabel rentang. Itu tidak buat tabel rentang untuk kecil bitmap sederhana.
Tabel rentang adalah struktur 128KB ukuran tetap yang terdiri dari 8.192 pasang nilai 8-byte yang menentukan rentang nilai (rendah, tinggi) yang ada dalam tabel hash. Tabel rentang dapat dibuat pada tipe data apa pun yang kompatibel dengan eksekusi mode batch. Selama pemindaian tabel hash yang telah selesai, setiap kumpulan data digunakan untuk mengisi bitmap dan tabel jangkauan.
Untuk setiap nilai dalam batch, fungsi hash digunakan untuk menemukan bucket (pasangan nilai rentang) di tabel rentang. Jika bucket saat ini tidak digunakan, nilai disimpan dalam nilai 8 byte rendah dan tinggi. Jika ember sudah digunakan, ember berikutnya akan diisi (dan seterusnya, sampai ember kosong ditemukan).
Jika tabel rentang menjadi sepertiga penuh (2.730 dari 8.192 ember digunakan), entri yang digunakan disalin, rentang ember digandakan, kemudian nilai yang disimpan dimasukkan kembali dengan cara yang sama seperti sebelumnya (meskipun fungsi hash memperhitungkan ukuran ember baru). Setiap ember yang tumpang tindih digabung, dan proses penggandaan berlanjut hingga jumlah ember yang digunakan turun di bawah 2.730. Misalnya, dua ember yang awalnya berisi 'rentang' (1-1) dan (2-2) dapat bergabung menjadi satu ember rentang (1-2) setelah rentang pertama berlipat ganda.
Setelah semua kumpulan data tabel hash telah diproses ke dalam tabel rentang, penggabungan bucket terakhir dilakukan, kemudian quicksort di tempat menempatkan bucket dalam urutan nilai. Hal ini memungkinkan pencarian biner untuk menemukan ember rentang yang diberi nilai minat tertentu.
Hasil bersih dari semua aktivitas ini adalah menghasilkan satu set hingga 2.730 rentang berbeda yang menjelaskan data dalam tabel hash (selain bitmap sederhana atau kompleks yang besar).
Menggunakan Tabel Rentang
Tabel rentang digunakan ketika filter bitmap gabungan hash didorong ke bawah ke operator pemindaian penyimpanan kolom sisi penyelidikan. Setiap segmen columnstore memiliki metadata katalog tentang nilai data minimum dan maksimum yang ada di segmen tersebut. Mesin eksekusi dapat menggunakan informasi ini untuk mencari biner pada tabel rentang bitmap untuk kecocokan. Jika tidak ada kecocokan yang ditemukan, mesin eksekusi dapat melewati segmen sepenuhnya.
Optimalisasi runtime ini juga terjadi untuk read-ahead, sehingga engine bahkan dapat menghindari membaca segmen ke dalam memori yang diketahuinya akan dihilangkan oleh filter tabel rentang. Segmen apa pun yang tidak dihilangkan oleh tabel rentang masih difilter menggunakan bitmap. Kombinasi ini menghasilkan jumlah maksimum baris yang dihilangkan sedini mungkin.
Meskipun tabel rentang tidak dibuat untuk bitmap sederhana yang kecil, struktur itu juga dapat digunakan untuk mencapai eliminasi segmen karena rentang nilai diketahui (termasuk offset apa pun). Ini cukup kecil untuk membuatnya tidak berguna untuk mempartisinya menjadi sub-rentang menggunakan tabel rentang.
Ketika bitmap tidak didorong ke dalam pemindaian columnstore, itu masih dapat dievaluasi sebagai filter mode batch biasa untuk mencapai pengurangan semi-join sebelum hash bergabung. Ini jauh lebih tidak efisien daripada eliminasi segmen atau pemfilteran selama pemindaian columnstore, tetapi masih lebih baik daripada pemfilteran pada hash join itu sendiri.
Bitmap dan Data Terkompresi
Menerapkan bitmap mode batch gabungan hash ke data penyimpanan kolom sebagai bagian dari pemindaian dapat menghasilkan kinerja yang sangat baik, tetapi hal itu membutuhkan data segmen yang tidak murni untuk didekompresi sebelum bitmap dapat diterapkan. Dekompresi ini dapat dilakukan secara efisien menggunakan instruksi SIMD, tetapi ini masih merupakan pekerjaan ekstra.
SQL Server 2016 memperkenalkan kemampuan untuk membuat bitmap untuk predikat umum pada data segmen yang disandikan kamus. Predikat dievaluasi terhadap entri kamus untuk menghasilkan baru bitmap kecil dengan setiap set bit menunjukkan entri kamus yang memenuhi predikat. Menerapkan bitmap ini bisa sangat cepat, terutama jika bitmap cocok dalam satu register SIMD. SQL Server masih dapat menggunakan SIMD jika bitmap tidak cocok, tetapi mengumpulkan bit dari bitmap dalam memori sedikit kurang efisien dibandingkan kasus dalam register.
Pengoptimalan 2016 ini dapat diterapkan ke apa saja predikat didorong ke dalam pemindaian columnstore, termasuk 'predikat' bitmap yang dibuat oleh gabungan hash hulu. Agar jelas, SQL Server mengambil bitmap hash join dan membuat bitmap baru (jauh lebih kecil) menggunakan entri kamus. Bitmap baru ini diterapkan ke data segmen sebelum dekompresi. Pengoptimalan dapat dipantau dengan column_store_expression_filter_bitmap_set peristiwa yang diperluas . Saat bitmap kamus digunakan, anggota acara filter_on_compressed_data_type anggota akan terisi. Biasanya ini akan berisi nilai RAWBITMAP . Ada optimasi lebih lanjut untuk mengonversi bitmap kamus terkompresi ke filter perbandingan jika bitmap kamus mewakili rentang nilai tunggal yang berdekatan. Dalam hal ini Anda akan melihat sesuatu selain RAWBITMAP (mis. LTGT untuk kurang dari/lebih besar dari perbandingan).
Acara yang Diperpanjang dan Tanda Pelacakan
Kemampuan umum untuk mengkompilasi filter push-down (termasuk bitmap yang dihasilkan oleh gabungan hash mode batch) pada pemindaian kolomstore ke dalam bitmap dapat dinonaktifkan dengan tanda pelacakan tingkat sesi 9361. Pengoptimalan bitmap data terkompresi khusus dapat dinonaktifkan dengan sesi -level trace flag 9362. Konversi bitmap kamus dengan satu rentang berdekatan ke filter perbandingan dapat dinonaktifkan dengan trace flag 9363. Sayangnya, tidak ada flag trace build-ritel yang melaporkan pesan informasi tentang bitmap mode batch atau filter push-down kompilasi.
Ada beberapa kejadian tambahan yang menghasilkan informasi tentang bitmap mode gabungan hash. Yang paling berguna adalah:
query_execution_column_store_segment_scan_startedquery_execution_column_store_segment_scan_finishedcolumn_store_expression_filter_bitmap_setcolumn_store_segment_eliminate
Saat bitmap mode batch gabungan hash didorong ke bawah ke pemindaian columnstore, peristiwa "dimulai" melaporkan BITMAP_SIMPLE atau BITMAP_COMPLEX sebagai filter_type . Itu tidak membedakan antara bitmap sederhana kecil dan besar, juga tidak melaporkan apa pun tentang tabel rentang. Metadata peristiwa yang diperluas memang berisi nilai lain untuk column_store_filter_type yang menyertakan BITMAP_SIMPLE_LARGE antara lain, tetapi acara yang diperluas saat ini tidak menghasilkan output ini ketika bitmap sederhana yang besar digunakan. Mungkin ini akan diperbaiki di rilis mendatang.
Bendera jejak global 646 dapat digunakan untuk melaporkan informasi tentang penghapusan segmen yang diaktifkan oleh tabel rentang (atau bitmap kecil sederhana). Ini melaporkan informasi serupa ke segmen menghilangkan acara diperpanjang. Semua tanda jejak yang disebutkan di bagian ini tidak didokumentasikan dan tidak didukung.
Pemikiran Terakhir
Bitmap mode batch bisa sangat efektif jika tipe data yang tepat (maks 64 bit dan seperti bilangan bulat) digunakan dan bitmap dapat ditekan ke pemindaian penyimpanan kolom, terutama jika data segmen menggunakan kompresi RLE (penyimpanan murni), atau jika bitmap dapat dikompilasi menjadi bitmap lain pada data kamus.
Mungkin bagus jika rencana eksekusi melaporkan informasi yang lebih rinci tentang hash join bitmap — setidaknya untuk mengatakan jenis bitmap apa yang dibuat. Karena itu, kami hanya memiliki Pembuat Bitmap properti, dan beberapa acara tambahan untuk dikerjakan. Hal ini membuat analisis rencana terperinci sedikit lebih sulit daripada yang seharusnya, mengingat peningkatan kinerja yang sangat besar yang dapat diwujudkan dengan memanfaatkan semua pengoptimalan cerdas yang dibangun ke dalam mesin eksekusi untuk data penyimpanan kolom dan gabungan hash mode batch.
Demo, ilustrasi, dan diskusi lebih lanjut tentang poin utama yang dibahas dalam artikel ini tersedia di situs pribadi saya di Demo Bitmap Mode Batch.
