Estimasi Kardinalitas untuk Predikat pada Ekspresi COUNT

Artikel ini membahas estimasi selektivitas dan kardinalitas untuk predikat pada COUNT(*) ekspresi, seperti yang dapat dilihat di HAVING klausa. Detailnya mudah-mudahan menarik dalam diri mereka. Mereka juga memberikan wawasan tentang beberapa pendekatan umum dan algoritme yang digunakan oleh penduga kardinalitas.

Contoh sederhana menggunakan database sampel AdventureWorks:

PILIH A.City FROM Person.[Address] SEBAGAI GROUP BY A.City HAVING COUNT_BIG(*) =1;

Kami tertarik untuk melihat bagaimana SQL Server memperoleh perkiraan untuk predikat pada ekspresi hitungan di HAVING klausa.

Tentu saja HAVING klausa hanyalah gula sintaksis. Kita bisa sama-sama menulis kueri menggunakan tabel turunan, atau ekspresi tabel umum:

-- Derived tableSELECT SQ1.CityFROM( SELECT A.City, Expr1001 =COUNT_BIG(*) FROM Person.[Address] AS A GROUP BY A.City) AS SQ1WHERE SQ1.Expr1001 =1; -- CTEWITH Dikelompokkan AS( SELECT A.City, Expr1001 =COUNT_BIG(*) FROM Person.[Address] SEBAGAI GROUP BY A.City)SELECT G.CityFROM Dikelompokkan AS GWHERE G.Expr1001 =1;

Ketiga formulir kueri menghasilkan rencana eksekusi yang sama, dengan nilai hash rencana kueri yang identik.

Rencana pasca-eksekusi (aktual) menunjukkan perkiraan yang sempurna untuk agregat; namun, perkiraan untuk HAVING filter klausa (atau yang setara, dalam bentuk kueri lainnya) buruk:

Statistik di City kolom memberikan informasi yang akurat tentang jumlah nilai kota yang berbeda:

DBCC SHOW_STATISTICS ([Person.Address], City) WITH DENSITY_VECTOR;

semua kepadatan angka adalah kebalikan dari jumlah nilai unik. Cukup hitung (1 / 0,00173913) =575 memberikan perkiraan kardinalitas untuk agregat. Pengelompokan berdasarkan kota jelas menghasilkan satu baris untuk setiap nilai yang berbeda.

Perhatikan bahwa semua kepadatan berasal dari vektor kerapatan. Berhati-hatilah agar tidak menggunakan kepadatan . secara tidak sengaja nilai dari output tajuk statistik DBCC SHOW_STATISTICS . Kepadatan header dipertahankan hanya untuk kompatibilitas mundur; itu tidak digunakan oleh pengoptimal selama estimasi kardinalitas hari ini.

Masalahnya

Agregat memperkenalkan kolom terhitung baru ke alur kerja, berlabel Expr1001 dalam rencana eksekusi. Ini berisi nilai COUNT(*) di setiap baris keluaran yang dikelompokkan:

Jelas tidak ada informasi statistik dalam database tentang kolom baru yang dihitung ini. Meskipun pengoptimal mengetahui akan ada 575 baris, pengoptimal tidak mengetahui apa pun tentang distribusi jumlah nilai dalam baris tersebut.

Yah tidak apa-apa:Pengoptimal menyadari bahwa nilai hitungan akan menjadi bilangan bulat positif (1, 2, 3…). Namun, distribusi nilai jumlah bilangan bulat ini di antara 575 baris yang diperlukan untuk memperkirakan secara akurat selektivitas COUNT(*) = 1 predikat.

Orang mungkin berpikir bahwa beberapa jenis informasi distribusi dapat diturunkan dari histogram, tetapi histogram hanya menyediakan informasi jumlah tertentu (dalam EQ_ROWS ) untuk nilai langkah histogram. Di antara langkah-langkah histogram, yang kita miliki hanyalah ringkasan:RANGE_ROWS baris memiliki DISTINCT_RANGE_ROWS nilai-nilai yang berbeda. Untuk tabel yang cukup besar sehingga kami memperhatikan kualitas estimasi selektivitas, kemungkinan besar sebagian besar tabel diwakili oleh ringkasan intra-langkah ini.

Misalnya, dua baris pertama dari City histogram kolom adalah:

DBCC SHOW_STATISTICS ([Person.Address], Kota) DENGAN HISTOGRAM;

Ini memberitahu kita bahwa ada tepat satu baris untuk "Abingdon", dan 29 baris lainnya setelah "Abingdon" tetapi sebelum "Ballard", dengan 19 nilai berbeda dalam rentang 29 baris tersebut. Kueri berikut menunjukkan distribusi aktual baris di antara nilai unik dalam rentang intra-langkah 29 baris tersebut:

SELECT A.City, NumRows =COUNT_BIG(*)FROM Person.[Address] AS A WHERE A.City> N'Abingdon' AND A.City  

 
 

 Ada 29 baris dengan 19 nilai berbeda, seperti yang dikatakan histogram. Namun, jelas kami tidak memiliki dasar untuk mengevaluasi selektivitas predikat pada kolom hitung dalam kueri itu. Misalnya, HAVING COUNT_BIG(*) = 2 akan mengembalikan 5 baris (untuk Alexandria, Altadena, Atlanta, Augsburg, dan Austin) tetapi kami tidak memiliki cara untuk menentukannya dari histogram.
 
Tebakan Terdidik
 

 Pendekatan yang diambil SQL Server adalah dengan mengasumsikan bahwa setiap grup kemungkinan besar berisi jumlah rata-rata (rata-rata) baris secara keseluruhan. Ini hanyalah kardinalitas dibagi dengan jumlah nilai unik. Misalnya, untuk 1000 baris dengan 20 nilai unik, SQL Server akan mengasumsikan bahwa (1000 / 20) =50 baris per grup adalah nilai yang paling mungkin.
 

 Kembali ke contoh awal kita, ini berarti kolom hitungan yang dihitung "kemungkinan besar" berisi nilai sekitar (19614/575) ~=34.1113 . Sejak kepadatan adalah kebalikan dari jumlah nilai unik, kita juga dapat menyatakannya sebagai kardinalitas * kerapatan =(19614 * 0,00173913), memberikan hasil yang sangat mirip.
 
Distribusi
 

 Mengatakan bahwa nilai rata-rata kemungkinan besar hanya membawa kita sejauh ini. Kita juga perlu menetapkan dengan tepat seberapa besar kemungkinannya; dan bagaimana kemungkinan berubah saat kita menjauh dari nilai rata-rata. Dengan asumsi bahwa semua grup memiliki tepat 34.113 baris dalam contoh kita bukanlah tebakan yang sangat "berpendidikan"!
 

 SQL Server menangani ini dengan mengasumsikan distribusi normal. Ini memiliki karakteristik bentuk lonceng yang mungkin sudah Anda kenal (gambar dari entri Wikipedia yang ditautkan):
 

 
 

 Bentuk pasti dari distribusi normal bergantung pada dua parameter :rata-rata (µ ) dan simpangan baku (σ ). Mean menentukan lokasi puncak. Standar deviasi menentukan seberapa "rata" kurva lonceng. Semakin datar kurvanya, semakin rendah puncaknya, dan semakin banyak kepadatan probabilitas yang terdistribusi pada nilai-nilai lain.
 

 SQL Server dapat memperoleh mean dari informasi statistik seperti yang telah dicatat. Standar deviasi dari nilai kolom hitungan yang dihitung tidak diketahui. SQL Server memperkirakannya sebagai akar kuadrat dari rata-rata (dengan sedikit penyesuaian yang dirinci nanti). Dalam contoh kita, ini berarti dua parameter dari distribusi normal kira-kira adalah 34,1113 dan 5,84 (akar kuadrat).
 

 Standar distribusi normal (kurva merah pada diagram di atas) adalah kasus khusus yang patut diperhatikan. Hal ini terjadi ketika meannya nol, dan simpangan bakunya adalah 1. Distribusi normal apa pun dapat ditransformasikan ke distribusi normal standar dengan mengurangkan mean dan membaginya dengan simpangan baku.
 
Area dan Interval
 

 Kami tertarik untuk mengestimasi selektivitas, jadi kami mencari probabilitas bahwa kolom yang dihitung memiliki nilai tertentu (x). Probabilitas ini tidak diberikan oleh nilai sumbu y di atas, tetapi oleh area di bawah kurva di sebelah kiri x.
 

 Untuk distribusi normal dengan mean 34,1113 dan simpangan baku 5,84, luas daerah di bawah kurva di sebelah kiri x =30 adalah sekitar 0,2406:
 

 
 

 Ini sesuai dengan probabilitas bahwa kolom hitungan yang dihitung kurang dari atau sama dengan 30 untuk contoh kueri kami.
 

 Ini mengarah dengan baik pada gagasan bahwa secara umum, kami tidak mencari probabilitas nilai tertentu, tetapi untuk interval . Untuk menemukan kemungkinan bahwa hitungan sama dengan nilai integer, kita perlu memperhitungkan fakta bahwa bilangan bulat menjangkau interval ukuran 1. Bagaimana kita mengubah bilangan bulat ke interval agak sewenang-wenang. SQL Server menangani ini dengan menambahkan dan mengurangi 0,5 untuk memberikan batas bawah dan atas interval.
 

 Misalnya, untuk menemukan probabilitas bahwa nilai hitungan yang dihitung sama dengan 30, kita perlu mengurangi luas di bawah kurva distribusi normal untuk (x =29,5) dari luas untuk (x =30,5). Hasilnya sesuai dengan irisan untuk (29,5  

 
 

 Luas irisan merah adalah sekitar 0,0533 . Untuk perkiraan pertama yang baik, ini adalah selektivitas predikat count =30 dalam kueri pengujian kami.
 
Fungsi Distribusi Kumulatif
 

 Menghitung luas di bawah distribusi normal di sebelah kiri nilai yang diberikan tidak mudah. Rumus umum diberikan oleh fungsi distribusi kumulatif (CDF). Masalahnya adalah CDF tidak dapat dinyatakan dalam fungsi matematika dasar, sehingga metode aproksimasi numerik harus digunakan sebagai gantinya.
 

 Karena semua distribusi normal dapat dengan mudah diubah menjadi distribusi normal standar (rata-rata =0, simpangan baku =1), semua aproksimasi bekerja untuk mengestimasi normal standar. Ini berarti kita perlu mengubah batas interval kami dari distribusi normal tertentu yang sesuai dengan kueri, hingga distribusi normal standar. Ini dilakukan, seperti yang disebutkan sebelumnya, dengan mengurangkan mean dan membaginya dengan standar deviasi.
 

 Jika Anda terbiasa dengan Excel, Anda mungkin mengetahui fungsi NORM.DIST dan NORM.S.DIST yang dapat menghitung CDF (menggunakan metode perkiraan numerik) untuk distribusi normal tertentu atau distribusi normal standar.
 

 Tidak ada kalkulator CDF yang ada di dalam SQL Server, tetapi kita dapat dengan mudah membuatnya. Diketahui CDF untuk distribusi normal standar adalah:
 

 
 

 …di mana erf adalah fungsi kesalahan:
 

 
 

 Implementasi T-SQL untuk mendapatkan CDF untuk distribusi normal standar ditunjukkan di bawah ini. Ini menggunakan perkiraan numerik untuk fungsi kesalahan yang sangat dekat dengan yang digunakan SQL Server secara internal:
 
BUAT PROSEDUR dbo.GetStandardNormalCDF( @x float, @cdf float OUTPUT)ASBEGIN SET NOCOUNT, XACT_ABORT ON; MENYATAKAN @tanda float, @erf float; SET @tanda =TANDA(@x); SET @x =ABS(@x) / SQRT(2); SET @erf =1; SET @erf =@erf + (0.0705230784 * @x); SET @erf =@erf + (0.0422820123 * POWER(@x, 2)); SET @erf =@erf + (0,0092705272 * POWER(@x, 3)); SET @erf =@erf + (0,0001520143 * POWER(@x, 4)); SET @erf =@erf + (0,0002765672 * POWER(@x, 5)); SET @erf =@erf + (0,0000430638 * POWER(@x, 6)); SET @erf =POWER(@erf, -16); SET @erf =1 - @erf; SET @erf =@erf * @tanda; SET @cdf =0.5 * (1 + @erf);END;
 

 Contoh, untuk menghitung CDF untuk x =30 menggunakan distribusi normal untuk kueri pengujian kami:
 
DECLARE @cdf float;DECLARE @x float;-- HAVING COUNT_BIG(*) =xSET @x =30;-- Normalisasikan 30 dengan mengurangi mean-- dan membaginya dengan standar deviasiSET @x =(@x - 34.1113) / 5.84;JALANKAN dbo.GetStandardNormalCDF @x =@x, @cdf =@cdf OUTPUT;PILIH CDF =@cdf;
 

 Perhatikan langkah normalisasi untuk mengkonversi ke distribusi normal standar. Prosedur mengembalikan nilai 0.2407196…, yang cocok dengan hasil Excel yang sesuai hingga tujuh tempat desimal.
 
Rincian Akhir dan Contoh
 

 Kode berikut memodifikasi kueri contoh kami untuk menghasilkan perkiraan yang lebih besar untuk Filter (perbandingannya sekarang dengan nilai 32, yang jauh lebih dekat dengan rata-rata daripada sebelumnya):
 
SELECT A.CityFROM Person.[Address] AS AGROUP BY A.CityHAVING COUNT_BIG(*) =32;
 

 
 

 Taksiran dari pengoptimal sekarang 36,7807 .
 

 Untuk menghitung perkiraan secara manual, pertama-tama kita perlu membahas beberapa detail akhir:
 
 
Rata-rata yang digunakan untuk menurunkan simpangan baku (melalui akar kuadrat) diskalakan dengan faktor ((nilai berbeda – 1) / (nilai berbeda) . Dalam contoh, jumlah nilai yang berbeda adalah 575, jadi faktor penskalaannya adalah (574/575) ~=0,99826. 
Jika batas bawah interval (bilangan bulat) adalah 1, SQL Server memperlakukan interval sebagai tak terbatas di sisi bawah. Selektivitas sama dengan CDF dari batas atas interval (1.5) saja. Batas bawah (yang akan menjadi 0,5) tidak digunakan. 
Penaksir kardinalitas lama (CE) memiliki logika kompleks untuk COUNT(*) = 1 , yang tidak dijelaskan di sini. 
Selain dari COUNT(*) = 1 kasus, CE lama menggunakan logika yang sama dengan CE baru (tersedia di SQL Server 2014 dan seterusnya).
 
 

 Prosedur berikut menggabungkan semua detail dalam artikel ini. Ini membutuhkan prosedur CDF yang diberikan sebelumnya:
 
BUAT PROSEDUR dbo.GetCountPredicateEstimate( @From integer, @To integer, @Cardinality float, @Density float, @Selectivity float OUTPUT, @Estimate float OUTPUT)ASBEGIN SET NOCOUNT, XACT_ABORT ON; MULAI COBA MENYATAKAN @Start float, @End float, @Distinct float, @Mean float, @MeanAdj float, @Stdev float, @NormStart float, @NormEnd float, @CDFStart float, @CDFEnd float; -- Validasi input dan terapkan default IF ISNULL(@From, 0) =0 SET @From =1; JIKA @Dari <1 RAISERROR ('@Dari harus>=1', 16, 1); IF ISNULL(@Kardinalitas, -1) <=0 RAISERROR('@Kardinalitas harus positif', 16, 1); IF ISNULL(@Kepadatan, -1) <=0 RAISERROR('@Kepadatan harus positif', 16, 1); JIKA ISNULL(@Ke, 0) =0 SET @Ke =CEILING(1 / @Kepadatan); JIKA @Ke <@Dari RAISERROR('@Ke harus>=@Dari', 16, 1); -- Konversi rentang bilangan bulat ke interval SET @Mulai =@Dari - 0,5; SET @Akhir =@Ke + 0.5; -- Dapatkan jumlah nilai yang berbeda SET @Distinct =1 / @Density; -- Hitung mean SET @Mean =@Cardinality * @Density; -- Sesuaikan rata-rata; SET @MeanAdj =@Mean * ((@Distinct - 1) / @Distinct); -- Dapatkan simpangan baku (tebak) SET @Stdev =SQRT(@MeanAdj); -- Normalisasi interval SET @NormStart =(@Start - @Mean) / @Stdev; SET @NormEnd =(@End - @Mean) / @Stdev; -- Hitung CDF EXECUTE dbo.GetStandardNormalCDF @x =@NormStart, @cdf =@CDFStart OUTPUT; EXECUTE dbo.GetStandardNormalCDF @x =@NormEnd, @cdf =@CDFEnd OUTPUT; -- Selektivitas SET @Selectivity =KASUS -- Awal tak terbatas KETIKA @Dari =1 KEMUDIAN @CDFEnd -- Akhir tak terbatas KETIKA @Ke>=@Berbeda KEMUDIAN 1 - @CDFStart -- Interval normal ELSE @CDFEnd - @CDFStart AKHIR; -- Kembalikan estimasi baris SET @Estimate =@Selectivity * @Distinct; AKHIR COBA MULAI CATCH DECLARE @EM nvarchar(4000) =ERROR_MESSAGE(); JIKA @@TRANSAKSI> 0 TRANSAKSI ROLLBACK; RAISERROR (@EM, 16, 1); KEMBALI; AKHIR TANGKAP;AKHIR;
 

 Kami sekarang dapat menggunakan prosedur ini untuk menghasilkan perkiraan untuk kueri pengujian baru kami:
 
DECLARE @Selectivity float, @Estimate float;EXECUTE dbo.GetCountPredicateEstimate @From =32, @To =32, @Cardinality =19614, @Density =0.00173913, @Selectivity =@Selectivity OUTPUT, @Estimate =@Estimate OUTPUT; SELECT Selektivitas =@Selektivitas, Perkiraan =@Perkiraan, Pembulatan =ROUND(@Perkiraan, 4);
 

 Outputnya adalah:
 

 
 

 Ini sangat cocok dengan perkiraan kardinalitas pengoptimal 36,7807. 
 
Contoh interval ketidaksetaraan
 

 Prosedur ini dapat digunakan untuk interval hitungan lain selain dari tes kesetaraan. Yang diperlukan hanyalah mengatur @From dan @To parameter ke batas interval bilangan bulat. Untuk menentukan tak terbatas, berikan nol atau NULL seperti yang Anda inginkan.
 
SELECT A.CityFROM Person.[Address] AS AGROUP BY A.CityHAVING COUNT_BIG(*) <50;
 

 
 

 Untuk menggunakan ini dengan prosedur kami, kami menetapkan @From = NULL dan @To = 49 (karena 50 dikecualikan dengan kurang dari):
 
DECLARE @Selectivity float, @Estimate float;EXECUTE dbo.GetCountPredicateEstimate @From =NULL, @To =49, @Cardinality =19614, @Density =0.00173913, @Selectivity =@Selectivity OUTPUT, @Estimate =@Estimate OUTPUT; SELECT Selektivitas =@Selektivitas, Perkiraan =@Perkiraan, Pembulatan =ROUND(@Perkiraan, 4);
 

 Hasilnya adalah 572.5964:
 

 
 

 Satu contoh terakhir menggunakan BETWEEN :
 
SELECT A.CityFROM Person.[Address] AS AGROUP BY A.CityHAVING COUNT_BIG(*) BETWEEN 25 AND 30;
 

 Estimasi pengoptimal adalah 
 

 
 

 Sejak BETWEEN inklusif, kami melewati prosedur @From = 25 dan @To = 30 . Hasilnya adalah:
 

 
 

 Sekali lagi, ini sesuai dengan perkiraan pengoptimal.