Hail bailout agregat

10

Sebuah pertanyaan yang muncul dalam diskusi obrolan:

Saya tahu hash bergabung dengan bailout switch secara internal ke semacam loop hal bersarang.

Apa yang SQL Server lakukan untuk bailout agregat hash (jika itu bisa terjadi sama sekali)?

Paul White 9
sumber

Jawaban:

11

Hash join dan hash agregat keduanya menggunakan kode operator yang sama secara internal, meskipun agregat hash hanya menggunakan satu input (build). Operasi dasar dari hash agregat yang dijelaskan oleh Craig Freedman :

Seperti halnya hash join, agregat hash membutuhkan memori. Sebelum menjalankan kueri dengan agregat hash, SQL Server menggunakan perkiraan kardinalitas untuk memperkirakan berapa banyak memori yang kita butuhkan untuk menjalankan kueri. Dengan hash join, kami menyimpan setiap baris build, sehingga total kebutuhan memori sebanding dengan jumlah dan ukuran baris build. Jumlah baris yang bergabung dan kardinalitas output dari gabungan tidak berpengaruh pada persyaratan memori gabungan. Dengan agregat hash, kami menyimpan satu baris untuk setiap grup, sehingga total kebutuhan memori sebenarnya sebanding dengan jumlah dan ukuran grup atau baris output. Jika kami memiliki lebih sedikit nilai unik grup berdasarkan kolom dan grup lebih sedikit, kami membutuhkan lebih sedikit memori. Jika kami memiliki nilai yang lebih unik dari grup dengan kolom dan lebih banyak grup, kami membutuhkan lebih banyak memori.

Dia kemudian berbicara tentang rekursi hash:

Jadi, apa yang terjadi jika kita kehabisan memori? Sekali lagi, seperti hash bergabung, jika kita kehabisan memori, kita harus mulai menumpahkan baris ke tempdb. Kami menumpahkan satu atau lebih ember atau partisi termasuk setiap hasil teragregasi bersama dengan setiap baris baru tambahan yang hash ke ember atau partisi tumpah. Meskipun kami tidak berusaha untuk mengumpulkan baris baru yang tumpah, kami melakukan hash dan membaginya menjadi beberapa ember atau partisi. Setelah kami selesai memproses semua kelompok input, kami mengeluarkan kelompok dalam memori yang selesai dan mengulang algoritma dengan membaca kembali dan menggabungkan satu partisi yang tumpah sekaligus. Dengan membagi baris yang tumpah menjadi beberapa partisi, kami mengurangi ukuran setiap partisi dan, dengan demikian, mengurangi risiko bahwa algoritma perlu mengulangi berkali-kali.

Bailout

Hash bailout didokumentasikan dengan ringan, tetapi disebutkan oleh Nacho Alonso Portillo di Apa tingkat maksimum rekursi untuk iterator hash sebelum memaksa bail-out?

Nilai adalah konstanta, kode keras dalam produk, dan nilainya lima (5). Ini berarti bahwa sebelum operator hash memindai resor ke algoritma berbasis semacam untuk setiap subpartisi yang diberikan yang tidak sesuai dengan memori yang diberikan dari ruang kerja, lima upaya sebelumnya untuk membagi partisi asli ke dalam partisi yang lebih kecil harus terjadi.

"Operator pemindai hash" menyebutkan ada referensi ke kelas internal CQScanHashdi sqlmin.dll. Kelas ini mengepalai implementasi operator hash (dalam semua bentuknya, termasuk agregat parsial dan aliran berbeda) yang kita lihat dalam rencana eksekusi.

Algoritme bailout

Ini membawa kami pada inti pertanyaan Anda - apa tepatnya yang dilakukan algoritma bailout? Apakah "berdasarkan jenis" atau berdasarkan "semacam hal yang bersarang"?

Ini bisa dibilang keduanya, tergantung pada sudut pandang Anda. Ketika rekursi hash mencapai level 5, partisi hash di dalam memori berubah dari menjadi tabel hash menjadi indeks b-tree yang awalnya kosong pada nilai hash. Setiap baris dari partisi hash tunggal yang sebelumnya tumpah dilihat dalam indeks b-tree dan dimasukkan (grup baru) atau diperbarui (mempertahankan agregat) yang sesuai.

Rangkaian sisipan yang tidak berurutan ke b-tree dapat juga dilihat sebagai jenis penyisipan atau sebagai pencarian loop berindeks yang diindeks.

Bagaimanapun, algoritma fallback ini dijamin akan selesai pada akhirnya tanpa mengalokasikan lebih banyak memori. Mungkin diperlukan beberapa lintasan jika ruang yang tersedia untuk b-tree tidak cukup untuk menampung semua kunci pengelompokan dan agregat dari partisi overflow.

Setelah memori yang tersedia untuk menahan indeks b-tree habis, setiap baris lebih lanjut (dari partisi yang tumpah saat ini) dikirim ke satu partisi tempdb baru (yang dijamin lebih kecil) dan proses ini diulangi seperlunya. Level tumpahan tetap di 5 karena rekursi hash telah berakhir. Beberapa detail pemrosesan dapat diamati dengan flag jejak 7357 yang tidak berdokumen.

Paul White 9
sumber