Pendekatan terbaik untuk median berkelompok

Kembali pada tahun 2012, saya menulis posting blog di sini yang menyoroti pendekatan untuk menghitung median. Dalam posting itu, saya menangani kasus yang sangat sederhana:kami ingin menemukan median kolom di seluruh tabel. Telah disebutkan kepada saya beberapa kali sejak saat itu bahwa persyaratan yang lebih praktis adalah menghitung median yang dipartisi . Seperti halnya kasus dasar, ada beberapa cara untuk menyelesaikannya di berbagai versi SQL Server; tidak mengherankan, beberapa berkinerja jauh lebih baik daripada yang lain.

Pada contoh sebelumnya, kami hanya memiliki id dan val kolom generik. Mari kita buat ini lebih realistis dan katakan kita memiliki tenaga penjualan dan jumlah penjualan yang mereka lakukan dalam beberapa periode. Untuk menguji kueri kita, pertama-tama buat heap sederhana dengan 17 baris, dan verifikasi bahwa semuanya menghasilkan hasil yang kita harapkan (SalesPerson 1 memiliki median 7,5, dan SalesPerson 2 memiliki median 6,0):

BUAT TABEL dbo.Sales(SalesPerson INT, Amount INT);GO INSERT dbo.Sales WITH (TABLOCKX)(SalesPerson, Amount) VALUES(1, 6 ),(1, 11),(1, 4 ),( 1, 4 ),(1, 15),(1, 14),(1, 4 ),(1, 9 ),(2, 6 ),(2, 11),(2, 4 ),(2, 4 ),(2, 15),(2, 14),(2, 4 );

Berikut adalah kueri, yang akan kami uji (dengan lebih banyak data!) terhadap tumpukan di atas, serta dengan indeks pendukung. Saya telah membuang beberapa kueri dari pengujian sebelumnya, yang tidak berskala sama sekali atau tidak memetakan dengan baik ke median yang dipartisi (yaitu, 2000_B, yang menggunakan tabel #temp, dan 2005_A, yang menggunakan baris berlawanan angka). Namun, saya telah menambahkan beberapa ide menarik dari artikel terbaru oleh Dwain Camps (@DwainCSQL), yang dibangun di atas posting saya sebelumnya.

SQL Server 2000+

Satu-satunya metode dari pendekatan sebelumnya yang bekerja cukup baik pada SQL Server 2000 bahkan untuk memasukkannya ke dalam pengujian ini adalah pendekatan "min dari satu setengah, maks dari yang lain":

SELECT DISTINCT s.SalesPerson, Median =( (SELECT MAX(Amount) FROM (PILIH TOP 50 PERCENT Amount FROM dbo.Sales WHERE SalesPerson =s.SalesPerson ORDER BY Amount) AS t) + (SELECT MIN(Amount) FROM (PILIH Jumlah 50 PERSEN TERATAS DARI dbo.Sales WHERE SalesPerson =s.SalesPerson ORDER BY Amount DESC) AS b)) / 2.0FROM dbo.Sales AS s;

Sejujurnya saya mencoba meniru versi tabel #temp yang saya gunakan dalam contoh yang lebih sederhana, tetapi skalanya tidak bagus sama sekali. Pada 20 atau 200 baris itu bekerja dengan baik; pada tahun 2000 butuh waktu hampir satu menit; pada 1.000.000 saya menyerah setelah satu jam. Saya telah menyertakannya di sini untuk anak cucu (klik untuk mengungkapkan).

BUAT TABEL #x( i INT IDENTITY(1,1), SalesPerson INT, Jumlah INT, i2 INT); BUAT INDEKS Kluster v PADA #x(Penjual, Jumlah); INSERT #x(SalesPerson, Amount) SELECT SalesPerson, Amount FROM dbo.Sales ORDER BY Salesperson,Amount OPTION (MAXDOP 1); UPDATE x SET i2 =i-( SELECT COUNT(*) FROM #x WHERE i <=x.i AND Salesperson  
SQL Server 2005+ 1
 

 Ini menggunakan dua fungsi windowing yang berbeda untuk mendapatkan urutan dan jumlah keseluruhan jumlah per staf penjualan.
 
SELECT SalesPerson, Median =AVG(1.0*Amount)FROM( SELECT SalesPerson, Amount, rn =ROW_NUMBER() OVER (PARTITION BY SalesPerson ORDER BY Amount), c =COUNT(*) OVER (PARTITION BY Salesperson) FROM dbo .Penjualan)AS xWHERE rn IN ((c + 1)/2, (c + 2)/2)GROUP BY SalesPerson;
 
SQL Server 2005+ 2
 

 Ini berasal dari artikel Dwain Camps, yang melakukan hal yang sama seperti di atas, dengan cara yang sedikit lebih rumit. Ini pada dasarnya melepaskan baris yang menarik di setiap grup.
 
;DENGAN Hitungan AS( SELECT SalesPerson, c FROM ( SELECT SalesPerson, c1 =(c+1)/2, c2 =CASE c%2 WHEN 0 THEN 1+c/2 ELSE 0 END FROM ( SELECT SalesPerson, c =COUNT(*) FROM dbo.Sales GROUP BY SalesPerson ) a ) a ) CROSS APPLY (VALUES(c1),(c2)) b(c))SELECT a.SalesPerson, Median=AVG(0.+b.Amount)FROM ( SELECT SalesPerson, Amount, rn =ROW_NUMBER() OVER (PARTITION BY SalesPerson ORDER BY Amount) FROM dbo.Sales a) aCROSS APPLY( SELECT Amount FROM Counts b WHERE a.SalesPerson =b.SalesPerson AND a.rn =b.c) bGROUP OLEH a.SalesPerson;
 
SQL Server 2005+ 3
 

 Ini berdasarkan saran dari Adam Machanic di komentar di postingan saya sebelumnya, dan juga disempurnakan oleh Dwain di artikelnya di atas.
 
;DENGAN Hitungan AS( SELECT SalesPerson, c =COUNT(*) FROM dbo.Sales GROUP BY SalesPerson)SELECT a.SalesPerson, Median =AVG(0.+Amount)FROM Counts aCROSS APPLY( SELECT TOP (((a.c) - 1) / 2) + (1 + (1 - a.c % 2))) b.Amount, r =ROW_NUMBER() OVER (ORDER BY b.Amount) FROM dbo.Sales b WHERE a.SalesPerson =b.SalesPerson ORDER BY b.Amount) pWHERE r ANTARA ((a.c - 1) / 2) + 1 AND (((a.c - 1) / 2) + (1 + (1 - a.c % 2)))GROUP BY a.SalesPerson; 
SQL Server 2005+ 4
 

 Ini mirip dengan "2005+ 1" di atas, tetapi alih-alih menggunakan COUNT(*) OVER() untuk menurunkan jumlah, ia melakukan self-join terhadap agregat terisolasi dalam tabel turunan.
 
SELECT SalesPerson, Median =AVG(1.0 * Amount)FROM( SELECT s.SalesPerson, s.Amount, rn =ROW_NUMBER() OVER (PARTITION BY s.SalesPerson ORDER BY s.Amount), c.c FROM dbo.Sales AS s INNER JOIN ( SELECT SalesPerson, c =COUNT(*) FROM dbo.Sales GROUP BY SalesPerson ) AS c ON s.SalesPerson =c.SalesPerson) AS xWHERE rn IN ((c + 1)/2, (c + 2) /2) KELOMPOK MENURUT Staf Penjualan;
 
SQL Server 2012+ 1
 

 Ini adalah kontribusi yang sangat menarik dari sesama MVP SQL Server Peter "Peso" Larsson (@SwePeso) dalam komentar di artikel Dwain; ia menggunakan CROSS APPLY dan OFFSET / FETCH baru fungsionalitas dengan cara yang lebih menarik dan mengejutkan daripada solusi Itzik untuk penghitungan median yang lebih sederhana.
 
SELECT d.SalesPerson, w.MedianFROM( SELECT SalesPerson, COUNT(*) AS y FROM dbo.Sales GROUP BY SalesPerson) AS dCROSS APPLY( SELECT AVG(0E + Amount) FROM ( SELECT z.Amount FROM dbo.Sales AS z WHERE z.SalesPerson =d.SalesPerson ORDER OLEH z.Amount OFFSET (d.y - 1) / 2 ROWS FETCH NEXT 2 - d.y % 2 ROWS ONLY ) AS f) AS w(Median);
 
SQL Server 2012+ 2
 

 Akhirnya, kami memiliki PERCENTILE_CONT() baru fungsi diperkenalkan di SQL Server 2012.
 
SELECT SalesPerson, Median =MAX(Median)FROM( SELECT SalesPerson,Median =PERCENTILE_CONT(0.5) WITHIN GROUP (ORDER BY Amount) OVER (PARTITION BY SalesPerson) FROM dbo.Sales) SEBAGAI xGROUP BY SalesPerson;
 
Tes Nyata
 

 Untuk menguji kinerja kueri di atas, kita akan membuat tabel yang jauh lebih substansial. Kami akan memiliki 100 tenaga penjualan unik, dengan 10.000 angka jumlah penjualan masing-masing, dengan total 1.000.000 baris. Kami juga akan menjalankan setiap kueri terhadap heap apa adanya, dengan menambahkan indeks non-clustered pada (SalesPerson, Amount) , dan dengan indeks berkerumun pada kolom yang sama. Berikut adalah pengaturannya:
 
CREATE TABLE dbo.Sales(SalesPerson INT, Amount INT);GO --CREATE CLUSTERED INDEX x ON dbo.Sales(SalesPerson, Amount);--CREATE NONCLUSTERED INDEX x ON dbo.Sales(SalesPerson, Amount);- -DROP INDEX x PADA dbo.sales;;DENGAN x AS ( SELECT TOP (100) number FROM master.dbo.spt_values ​​GROUP BY number)INSERT dbo.Sales WITH (TABLOCKX) (SalesPerson, Amount) SELECT x.number, ABS(CHECKSUM(NEWID())) % 99 FROM x CROSS JOIN x AS x2 CROSS JOIN x AS x3;
 

 Dan berikut adalah hasil dari query di atas, terhadap heap, non-clustered index, dan clustered index:
 

 
Durasi, dalam milidetik, dari berbagai pendekatan median yang dikelompokkan (terhadap tumpukan) 
 

 
Durasi, dalam milidetik, dari berbagai pendekatan median yang dikelompokkan (terhadap tumpukan dengan indeks yang tidak berkerumun) 
 

 
Durasi, dalam milidetik, dari berbagai pendekatan median yang dikelompokkan (terhadap indeks berkerumun) 
 
Bagaimana dengan Hekaton?
 

 Tentu saja, saya ingin tahu apakah fitur baru di SQL Server 2014 ini dapat membantu menjawab pertanyaan-pertanyaan ini. Jadi saya membuat database In-Memory, dua versi In-Memory dari tabel Penjualan (satu dengan indeks hash pada (SalesPerson, Amount) , dan yang lainnya hanya di (SalesPerson) ), dan menjalankan ulang pengujian yang sama:
 
CREATE DATABASE Hekaton;GOALTER DATABASE Hekaton ADD FILEGROUP xtp CONTAINS MEMORY_OPTIMIZED_DATA;GOALTER DATABASE Hekaton ADD FILE (name ='xtp', filename ='c:\temp\hek.mod') TOSNSHOB FILEGROUP_TELESSHOT_DOPTSHOT FILE_TO ON;GO GUNAKAN Hekaton;GO CREATE TABLE dbo.Sales1( ID INT IDENTITY(1,1) PRIMARY KEY NONCLUSTERED, SalesPerson INT NOT NULL, Amount INT NOT NULL, INDEX x NONCLUSTERED HASH (SalesPerson, Amount) WITH (BUCKET_COUNT =256) )DENGAN (MEMORY_OPTIMIZED =ON, DURABILITY =SCHEMA_AND_DATA);GO CREATE TABLE dbo.Sales2( ID INT IDENTITY(1,1) PRIMARY KEY NONCLUSTERED, SalesPerson INT NOT NULL, Amount INT NOT NULL, INDEX x NONCLUSTERED H BUCKET_COUNT =256))DENGAN (MEMORY_OPTIMIZED =ON, DURABILITY =SCHEMA_AND_DATA);GO;WITH x AS ( SELECT TOP (100) number FROM master.dbo.spt_values ​​GROUP BY number)INSERT dbo.Sales1 (SalesPerson, Amount) -- TABLOCK /TABLOCKX tidak diizinkan di sini SELECT x.number, ABS(CHECKSUM(NEWID())) % 99 DARI x SALIB GABUNG x SEBAGAI x2 SALIB GABUNG x SEBAGAI x3; INSERT dbo.Sales2 (SalesPerson, Amount) SELECT SalesPerson, Amount FROM dbo.Sales1;
 

 Hasilnya:
 

 
Durasi, dalam milidetik, untuk berbagai perhitungan median terhadap In-Memory tabel 
 

 Bahkan dengan indeks hash yang tepat, kami tidak benar-benar melihat peningkatan yang signifikan dibandingkan tabel tradisional. Lebih jauh dari itu, mencoba memecahkan masalah median menggunakan prosedur tersimpan yang dikompilasi secara asli tidak akan menjadi tugas yang mudah, karena banyak konstruksi bahasa yang digunakan di atas tidak valid (saya juga terkejut dengan beberapa di antaranya). Mencoba mengkompilasi semua variasi kueri di atas menghasilkan parade kesalahan ini; beberapa terjadi beberapa kali dalam setiap prosedur, dan bahkan setelah menghapus duplikat, ini masih agak lucu:
 Pesan 10794, Level 16, Status 47, Procedure GroupedMedian_2000
Opsi 'DISTINCT' tidak didukung dengan prosedur tersimpan yang dikompilasi secara asli.
Msg 12311, Level 16, State 37, Procedure GroupedMedian_2000
Subqueries ( kueri bersarang di dalam kueri lain) tidak didukung dengan prosedur tersimpan yang dikompilasi secara asli.
Msg 10794, Level 16, Status 48, Procedure GroupedMedian_2000
Opsi 'PERCENT' tidak didukung dengan prosedur tersimpan yang dikompilasi secara asli.

Msg 12311, Level 16, Status 37, Procedure GroupedMedian_2005_1
Subquery (query yang disarangkan di dalam kueri lain) tidak didukung dengan prosedur tersimpan yang dikompilasi secara asli.
Msg 10794, Level 16, State 91 , Procedure GroupedMedian_2005_1
Fungsi agregat 'ROW_NUMBER' tidak didukung dengan prosedur tersimpan yang dikompilasi secara asli.
Msg 10794, Level 16, State 56, Procedure GroupedMedian_2005_1
Operator 'IN' tidak didukung dengan prosedur tersimpan yang dikompilasi secara asli.

Msg 12310, Level 16, Status 36, Procedure GroupedMedian_2005_2
Common Table Expressions (CTE) tidak didukung dengan prosedur tersimpan yang dikompilasi secara asli.
Msg 12309, Level 16, State 35, Procedure GroupedMedian_2005_2
Pernyataan formulir INSERT…VALUES… yang menyisipkan beberapa baris tidak didukung dengan prosedur tersimpan yang dikompilasi secara asli.
Msg 10794, Level 16, State 53, Procedure GroupedMedian_2005_2
Operator 'APPLY' tidak didukung dengan prosedur tersimpan yang dikompilasi secara asli. 
Msg 12311, Level 16, Status 37, Procedure GroupedMedian_2005_2
Subquery (query bersarang di dalam kueri lain) tidak didukung dengan prosedur tersimpan yang dikompilasi secara asli.
Msg 10794, Level 16, State 91, Procedure GroupedMedian_2005_2
Fungsi agregat 'ROW_NUMBER' tidak didukung dengan prosedur tersimpan yang dikompilasi secara asli.

Msg 12310, Level 16, State 36, Procedure GroupedMedian_2005_3
Common Table Expressions (CTE) adalah tidak didukung dengan penyimpanan yang dikompilasi secara asli prosedur.
Msg 12311, Level 16, Status 37, Procedure GroupedMedian_2005_3
Subquery (query bersarang di dalam kueri lain) tidak didukung dengan prosedur tersimpan yang dikompilasi secara asli.
Msg 10794, Level 16, State 91 , Procedure GroupedMedian_2005_3
Fungsi agregat 'ROW_NUMBER' tidak didukung dengan prosedur tersimpan yang dikompilasi secara asli.
Msg 10794, Level 16, State 53, Procedure GroupedMedian_2005_3
Operator 'APPLY' tidak didukung dengan prosedur tersimpan yang dikompilasi secara native.

Msg 12311, Level 16, State 37, Procedure GroupedMedian_2005_4
Subquery (query yang disarangkan di dalam kueri lain) tidak didukung dengan prosedur tersimpan yang dikompilasi secara native.
Msg 10794, Level 16, Status 91, Procedure GroupedMedian_2005_4
Fungsi agregat 'ROW_NUMBER' tidak didukung dengan prosedur tersimpan yang dikompilasi secara asli.
Msg 10794, Level 16, State 56, Procedure GroupedMedian_2005_4
Operator 'IN' tidak didukung dengan penyimpanan yang dikompilasi secara asli ed procedure.

Msg 12311, Level 16, State 37, Procedure GroupedMedian_2012_1
Subquery (query bersarang di dalam query lain) tidak didukung dengan prosedur tersimpan yang dikompilasi secara asli.
Msg 10794, Level 16, Status 38, Procedure GroupedMedian_2012_1
Operator 'OFFSET' tidak didukung dengan prosedur tersimpan yang dikompilasi secara asli.
Msg 10794, Level 16, State 53, Procedure GroupedMedian_2012_1
Operator 'APPLY' tidak didukung dengan prosedur tersimpan yang dikompilasi secara asli.

Msg 12311, Level 16, Status 37, Procedure GroupedMedian_2012_2
Subkueri (kueri yang disarangkan di dalam kueri lain) tidak didukung dengan prosedur tersimpan yang dikompilasi secara asli.
Msg 10794, Level 16, Status 90, Procedure GroupedMedian_2012_2
Fungsi agregat 'PERCENTILE_CONT' tidak didukung dengan prosedur tersimpan yang dikompilasi secara asli. 

 Seperti yang ditulis saat ini, tidak satu pun dari kueri ini yang dapat di-porting ke prosedur tersimpan yang dikompilasi secara native. Mungkin ada sesuatu yang perlu diperhatikan untuk posting tindak lanjut lainnya.
 
Kesimpulan
 

 Membuang hasil Hekaton, dan ketika ada indeks pendukung, kueri Peter Larsson ("2012+ 1") menggunakan OFFSET/FETCH keluar sebagai pemenang jauh-jauh dalam tes ini. Meskipun sedikit lebih kompleks daripada kueri yang setara dalam pengujian yang tidak dipartisi, ini cocok dengan hasil yang saya amati terakhir kali. 
 

 Dalam kasus yang sama, 2000 MIN/MAX pendekatan dan PERCENTILE_CONT() tahun 2012 keluar sebagai anjing sungguhan; lagi, seperti pengujian saya sebelumnya terhadap kasus yang lebih sederhana.
 

 Jika Anda belum menggunakan SQL Server 2012, maka opsi terbaik Anda berikutnya adalah "2005+ 3" (jika Anda memiliki indeks pendukung) atau "2005+ 2" jika Anda berurusan dengan heap. Maaf saya harus membuat skema penamaan baru untuk ini, sebagian besar untuk menghindari kebingungan dengan metode di posting saya sebelumnya.
 

 Tentu saja, ini adalah hasil saya terhadap skema dan kumpulan data yang sangat spesifik – seperti halnya semua rekomendasi, Anda harus menguji pendekatan ini terhadap skema dan data Anda, karena faktor lain dapat memengaruhi hasil yang berbeda.
 
Satu catatan lagi
 

 Selain menjadi berkinerja buruk, dan tidak didukung dalam prosedur tersimpan yang dikompilasi secara asli, satu titik masalah lain dari PERCENTILE_CONT() adalah bahwa itu tidak dapat digunakan dalam mode kompatibilitas yang lebih lama. Jika Anda mencoba, Anda mendapatkan kesalahan ini:
 Pesan 10762, Level 15, Status 1
Fungsi PERCENTILE_CONT tidak diizinkan dalam mode kompatibilitas saat ini. Ini hanya diperbolehkan dalam mode 110 atau lebih tinggi.