Menemukan "ToTime" Dengan Agregat Alih-alih Bergabung
Saya ingin membagikan kueri yang sangat liar yang hanya membutuhkan 1 pemindaian tabel dengan 1 pembacaan logis. Sebagai perbandingan, jawaban terbaik lainnya di halaman, kueri Simon Kingston, membutuhkan 2 pemindaian.
Pada kumpulan data yang sangat besar (17.408 baris input, menghasilkan 8.193 baris hasil) dibutuhkan CPU 574 dan waktu 2645, sedangkan kueri Simon Kingston membutuhkan CPU 63.820 dan waktu 37.108.
Ada kemungkinan bahwa dengan indeks, kueri lain pada halaman dapat bekerja berkali-kali lebih baik, tetapi menarik bagi saya untuk mencapai peningkatan CPU 111x dan peningkatan kecepatan 14x hanya dengan menulis ulang kueri.
(Harap dicatat:Saya sama sekali tidak bermaksud tidak menghormati Simon Kingston atau siapa pun; Saya hanya senang dengan ide saya untuk kueri ini berjalan dengan sangat baik. Permintaannya lebih baik daripada saya karena kinerjanya banyak dan sebenarnya dapat dimengerti dan dipelihara , tidak seperti milik saya.)
Inilah pertanyaan yang mustahil. Sulit untuk dipahami. Sulit untuk menulis. Tapi itu luar biasa. :)
WITH Ranks AS (
SELECT
T = Dense_Rank() OVER (ORDER BY Time, Num),
N = Dense_Rank() OVER (PARTITION BY Name ORDER BY Time, Num),
*
FROM
#Data D
CROSS JOIN (
VALUES (1), (2)
) X (Num)
), Items AS (
SELECT
FromTime = Min(Time),
ToTime = Max(Time),
Name = IsNull(Min(CASE WHEN Num = 2 THEN Name END), Min(Name)),
I = IsNull(Min(CASE WHEN Num = 2 THEN T - N END), Min(T - N)),
MinNum = Min(Num)
FROM
Ranks
GROUP BY
T / 2
)
SELECT
FromTime = Min(FromTime),
ToTime = CASE WHEN MinNum = 2 THEN NULL ELSE Max(ToTime) END,
Name
FROM Items
GROUP BY
I, Name, MinNum
ORDER BY
FromTime
Catatan:Ini membutuhkan SQL 2008 atau lebih tinggi. Untuk membuatnya bekerja di SQL 2005, ubah klausa VALUES menjadi SELECT 1 UNION ALL SELECT 2 .
Kueri yang Diperbarui
Setelah memikirkan ini sedikit, saya menyadari bahwa saya sedang menyelesaikan dua tugas logis yang terpisah pada saat yang sama, dan ini membuat kueri menjadi tidak perlu rumit:1) memangkas baris perantara yang tidak ada hubungannya dengan solusi akhir (baris yang tidak dimulai tugas baru) dan 2) tarik nilai "ToTime" dari baris berikutnya. Dengan melakukan #1 sebelum #2, kueri lebih sederhana dan bekerja dengan sekitar setengah CPU!
Jadi, inilah kueri yang disederhanakan yang pertama, memangkas baris yang tidak kita pedulikan, lalu mendapatkan nilai ToTime menggunakan agregat daripada GABUNG. Ya, itu memang memiliki 3 fungsi windowing, bukan 2, tetapi pada akhirnya karena lebih sedikit baris (setelah memangkas yang tidak kami pedulikan) ia memiliki lebih sedikit pekerjaan yang harus dilakukan:
WITH Ranks AS (
SELECT
Grp =
Row_Number() OVER (ORDER BY Time)
- Row_Number() OVER (PARTITION BY Name ORDER BY Time),
[Time], Name
FROM #Data D
), Ranges AS (
SELECT
Result = Row_Number() OVER (ORDER BY Min(R.[Time]), X.Num) / 2,
[Time] = Min(R.[Time]),
R.Name, X.Num
FROM
Ranks R
CROSS JOIN (VALUES (1), (2)) X (Num)
GROUP BY
R.Name, R.Grp, X.Num
)
SELECT
FromTime = Min([Time]),
ToTime = CASE WHEN Count(*) = 1 THEN NULL ELSE Max([Time]) END,
Name = IsNull(Min(CASE WHEN Num = 2 THEN Name ELSE NULL END), Min(Name))
FROM Ranges R
WHERE Result > 0
GROUP BY Result
ORDER BY FromTime;
Kueri yang diperbarui ini memiliki semua masalah yang sama seperti yang saya sajikan dalam penjelasan saya, namun, mereka lebih mudah dipecahkan karena saya tidak berurusan dengan baris tambahan yang tidak dibutuhkan. Saya juga melihat bahwa Row_Number() / 2 nilai 0 saya harus mengecualikan, dan saya tidak yakin mengapa saya tidak mengecualikannya dari kueri sebelumnya, tetapi bagaimanapun ini bekerja dengan sempurna dan sangat cepat!
Aplikasi Luar Merapikan Semuanya
Terakhir, ini adalah versi yang pada dasarnya identik dengan query Simon Kingston yang menurut saya sintaksnya lebih mudah dipahami.
SELECT
FromTime = Min(D.Time),
X.ToTime,
D.Name
FROM
#Data D
OUTER APPLY (
SELECT TOP 1 ToTime = D2.[Time]
FROM #Data D2
WHERE
D.[Time] < D2.[Time]
AND D.[Name] <> D2.[Name]
ORDER BY D2.[Time]
) X
GROUP BY
X.ToTime,
D.Name
ORDER BY
FromTime;
Berikut skrip penyiapan jika Anda ingin melakukan perbandingan kinerja pada kumpulan data yang lebih besar:
CREATE TABLE #Data (
RecordId int,
[Time] int,
Name varchar(10)
);
INSERT #Data VALUES
(1, 10, 'Running'),
(2, 18, 'Running'),
(3, 21, 'Running'),
(4, 29, 'Walking'),
(5, 33, 'Walking'),
(6, 57, 'Running'),
(7, 66, 'Running'),
(8, 77, 'Running'),
(9, 81, 'Walking'),
(10, 89, 'Running'),
(11, 93, 'Walking'),
(12, 99, 'Running'),
(13, 107, 'Running'),
(14, 113, 'Walking'),
(15, 124, 'Walking'),
(16, 155, 'Walking'),
(17, 178, 'Running');
GO
insert #data select recordid + (select max(recordid) from #data), time + (select max(time) +25 from #data), name from #data
GO 10
Penjelasan
Inilah ide dasar di balik pertanyaan saya.
-
Waktu yang mewakili sakelar harus muncul dalam dua baris yang berdekatan, satu untuk mengakhiri aktivitas sebelumnya, dan satu untuk memulai aktivitas berikutnya. Solusi alami untuk ini adalah bergabung sehingga baris keluaran dapat menarik dari barisnya sendiri (untuk waktu mulai) dan berikutnya diubah baris (untuk akhir waktu).
-
Namun, kueri saya memenuhi kebutuhan untuk membuat waktu berakhir muncul di dua baris berbeda dengan mengulangi baris dua kali, dengan
CROSS JOIN (VALUES (1), (2)). Kami sekarang memiliki semua baris kami diduplikasi. Idenya adalah bahwa alih-alih menggunakan GABUNG untuk melakukan perhitungan di seluruh kolom, kita akan menggunakan beberapa bentuk agregasi untuk menciutkan setiap pasangan baris yang diinginkan menjadi satu. -
Tugas berikutnya adalah membuat setiap baris duplikat terbelah dengan benar sehingga satu instance berjalan dengan pasangan sebelumnya dan satu dengan pasangan berikutnya. Ini dilakukan dengan kolom T, sebuah
ROW_NUMBER()diurutkan berdasarkanTime, dan kemudian dibagi 2 (meskipun saya mengubahnya melakukan DENSE_RANK() untuk simetri karena dalam hal ini mengembalikan nilai yang sama dengan ROW_NUMBER). Untuk efisiensi saya melakukan pembagian pada langkah berikutnya sehingga nomor baris dapat digunakan kembali dalam perhitungan lain (lanjutkan membaca). Sejak nomor baris dimulai pada 1, dan membagi dengan 2 secara implisit dikonversi ke int, ini memiliki efek menghasilkan urutan0 1 1 2 2 3 3 4 4 ...yang memiliki hasil yang diinginkan:dengan mengelompokkan berdasarkan nilai yang dihitung ini, karena kami juga mengurutkan berdasarkanNumdi nomor baris, sekarang kita telah menyelesaikan bahwa semua set setelah yang pertama terdiri dari Num =2 dari baris "sebelumnya", dan Num =1 dari baris "berikutnya". -
Tugas sulit berikutnya adalah mencari cara untuk menghilangkan baris yang tidak kita pedulikan dan entah bagaimana meruntuhkan waktu mulai sebuah blok menjadi baris yang sama dengan waktu akhir sebuah blok. Yang kami inginkan adalah cara agar setiap set Lari atau Jalan diskrit diberi nomornya sendiri sehingga kami dapat mengelompokkannya.
DENSE_RANK()adalah solusi alami, tetapi masalahnya adalah ia memperhatikan setiap nilai dalamORDER BYklausa--kita tidak memiliki sintaks untuk melakukanDENSE_RANK() OVER (PREORDER BY Time ORDER BY Name)sehinggaTimetidak menyebabkanRANKperhitungan berubah kecuali pada setiap perubahanName. Setelah beberapa pemikiran, saya menyadari bahwa saya dapat mengambil sedikit dari logika di balik solusi pulau-pulau yang dikelompokkan Itzik Ben-Gan, dan saya menemukan bahwa peringkat baris yang diurutkan berdasarkanTime, dikurangi dari peringkat baris yang dipartisi denganNamedan diurutkan berdasarkanTime, akan menghasilkan nilai yang sama untuk setiap baris dalam grup yang sama tetapi berbeda dari grup lain. Teknik pengelompokan pulau yang umum adalah membuat dua nilai terhitung yang keduanya naik sejajar dengan baris seperti4 5 6dan1 2 3, yang jika dikurangi akan menghasilkan nilai yang sama (dalam contoh kasus ini3 3 3sebagai hasil dari4 - 1,5 - 2, dan6 - 3). Catatan:Saya awalnya memulai denganROW_NUMBER()untukN. saya perhitungan tetapi tidak berhasil. Jawaban yang benar adalahDENSE_RANK()meskipun saya minta maaf untuk mengatakan saya tidak ingat mengapa saya menyimpulkan ini pada saat itu, dan saya harus menyelam lagi untuk mengetahuinya. Tapi bagaimanapun, itulah yangT-Nmenghitung:angka yang dapat dikelompokkan untuk mengisolasi setiap "pulau" dengan satu status (berlari atau berjalan). -
Tapi ini bukan akhir karena ada beberapa kerutan. Pertama-tama, baris "berikutnya" di setiap grup berisi nilai yang salah untuk
Name,N, danT. Kami menyiasatinya dengan memilih, dari setiap grup, nilai dariNum = 2baris ketika ada (tetapi jika tidak, maka kami menggunakan nilai yang tersisa). Ini menghasilkan ekspresi sepertiCASE WHEN NUM = 2 THEN x END:ini akan membuang nilai baris "berikutnya" yang salah dengan benar. -
Setelah beberapa percobaan, saya menyadari bahwa mengelompokkan berdasarkan
T - N. tidak cukup dengan sendirinya, karena grup Berjalan dan grup Lari dapat memiliki nilai terhitung yang sama (dalam kasus data sampel saya menyediakan hingga 17, ada duaT - Nnilai 6). Tapi cukup mengelompokkan berdasarkanNamejuga memecahkan masalah ini. Tidak ada grup "Berlari" atau "Berjalan" yang akan memiliki jumlah nilai intervensi yang sama dari jenis yang berlawanan. Yaitu, karena grup pertama dimulai dengan "Berlari", dan ada dua baris "Berjalan" yang mengintervensi sebelum grup "Berlari" berikutnya, maka nilai untuk N akan menjadi 2 lebih kecil dari nilai untukTdi grup "Berlari" berikutnya. Saya baru menyadari bahwa salah satu cara untuk memikirkan hal ini adalahT - Nperhitungan menghitung jumlah baris sebelum baris saat ini yang TIDAK termasuk dalam nilai "Berlari" atau "Berjalan" yang sama. Beberapa pemikiran akan menunjukkan bahwa ini benar:jika kita beralih ke kelompok "Berlari" ketiga, itu hanya kelompok ketiga karena memiliki kelompok "Berjalan" yang memisahkan mereka, sehingga memiliki jumlah baris intervensi yang berbeda. sebelumnya, dan karena itu dimulai pada posisi yang lebih tinggi, itu cukup tinggi sehingga nilainya tidak dapat diduplikasi. -
Akhirnya, karena grup terakhir kami hanya terdiri dari satu baris (tidak ada waktu akhir dan kami perlu menampilkan
NULLsebagai gantinya) saya harus memasukkan perhitungan yang dapat digunakan untuk menentukan apakah kami memiliki waktu akhir atau tidak. Ini dilakukan denganMin(Num)ekspresi dan akhirnya mendeteksi bahwa ketika Min(Num) adalah 2 (artinya kami tidak memiliki baris "berikutnya") kemudian menampilkanNULLbukannyaMax(ToTime)nilai.
Saya harap penjelasan ini bermanfaat bagi orang-orang. Saya tidak tahu apakah teknik "penggandaan baris" saya secara umum akan berguna dan berlaku untuk sebagian besar penulis kueri SQL di lingkungan produksi karena kesulitan memahaminya dan dan kesulitan pemeliharaannya pasti akan ditunjukkan kepada orang berikutnya yang mengunjungi kode (reaksinya mungkin "Apa yang dilakukannya!?!" diikuti dengan "Waktunya untuk menulis ulang!").
Jika Anda telah sampai sejauh ini, maka saya berterima kasih atas waktu Anda dan telah memanjakan saya dalam perjalanan kecil saya ke tanah teka-teki-sql yang sangat menyenangkan.
Lihat Sendiri
alias mensimulasikan "PREORDER BY":
Satu catatan terakhir. Untuk melihat bagaimana T - N melakukan pekerjaan--dan mencatat bahwa menggunakan bagian metode saya ini mungkin tidak berlaku secara umum untuk komunitas SQL--jalankan kueri berikut terhadap 17 baris pertama dari data sampel:
WITH Ranks AS (
SELECT
T = Dense_Rank() OVER (ORDER BY Time),
N = Dense_Rank() OVER (PARTITION BY Name ORDER BY Time),
*
FROM
#Data D
)
SELECT
*,
T - N
FROM Ranks
ORDER BY
[Time];
Ini menghasilkan:
RecordId Time Name T N T - N
----------- ---- ---------- ---- ---- -----
1 10 Running 1 1 0
2 18 Running 2 2 0
3 21 Running 3 3 0
4 29 Walking 4 1 3
5 33 Walking 5 2 3
6 57 Running 6 4 2
7 66 Running 7 5 2
8 77 Running 8 6 2
9 81 Walking 9 3 6
10 89 Running 10 7 3
11 93 Walking 11 4 7
12 99 Running 12 8 4
13 107 Running 13 9 4
14 113 Walking 14 5 9
15 124 Walking 15 6 9
16 155 Walking 16 7 9
17 178 Running 17 10 7
Bagian yang penting adalah bahwa setiap kelompok "Berjalan" atau "Berlari" memiliki nilai yang sama untuk T - N yang berbeda dari grup lain dengan nama yang sama.
Kinerja
Saya tidak ingin menjelaskan poin tentang kueri saya yang lebih cepat daripada kueri orang lain. Namun, mengingat betapa mencolok perbedaannya (ketika tidak ada indeks), saya ingin menampilkan angka dalam format tabel. Ini adalah teknik yang baik ketika kinerja tinggi dari korelasi baris-ke-baris semacam ini diperlukan.
Sebelum setiap kueri dijalankan, saya menggunakan DBCC FREEPROCCACHE; DBCC DROPCLEANBUFFERS; . Saya menetapkan MAXDOP ke 1 untuk setiap kueri untuk menghilangkan efek paralelisme yang runtuh waktu. Saya memilih setiap hasil yang ditetapkan ke dalam variabel alih-alih mengembalikannya ke klien sehingga hanya mengukur kinerja dan bukan transmisi data klien. Semua kueri diberi klausa ORDER BY yang sama. Semua pengujian menggunakan 17.408 baris input yang menghasilkan 8.193 baris hasil.
Tidak ada hasil yang ditampilkan untuk orang/alasan berikut:
RichardTheKiwi *Could not test--query needs updating*
ypercube *No SQL 2012 environment yet :)*
Tim S *Did not complete tests within 5 minutes*
Tanpa indeks:
CPU Duration Reads Writes
----------- ----------- ----------- -----------
ErikE 344 344 99 0
Simon Kingston 68672 69582 549203 49
Dengan indeks CREATE UNIQUE CLUSTERED INDEX CI_#Data ON #Data (Time); :
CPU Duration Reads Writes
----------- ----------- ----------- -----------
ErikE 328 336 99 0
Simon Kingston 70391 71291 549203 49 * basically not worse
Dengan indeks CREATE UNIQUE CLUSTERED INDEX CI_#Data ON #Data (Time, Name); :
CPU Duration Reads Writes
----------- ----------- ----------- -----------
ErikE 375 414 359 0 * IO WINNER
Simon Kingston 172 189 38273 0 * CPU WINNER
Jadi pesan moral dari cerita ini adalah:
Indeks yang Sesuai Lebih Penting Daripada Query Wizard
Dengan indeks yang sesuai, versi Simon Kingston menang secara keseluruhan, terutama saat menyertakan kompleksitas/pemeliharaan kueri.
Perhatikan pelajaran ini dengan baik! 38k bacaan tidak terlalu banyak, dan versi Simon Kingston berjalan di separuh waktu seperti milik saya. Peningkatan kecepatan kueri saya sepenuhnya karena tidak ada indeks di atas meja, dan biaya bencana yang menyertainya untuk setiap kueri yang membutuhkan gabungan (yang tidak saya lakukan):pemindaian tabel penuh Hash Match membunuh kinerjanya. Dengan indeks, kuerinya dapat melakukan Loop Bersarang dengan pencarian indeks berkerumun (alias pencarian bookmark) yang membuat segalanya benar-benar cepat.
Sangat menarik bahwa indeks berkerumun di Time saja tidak cukup. Meskipun Waktu itu unik, artinya hanya satu Nama yang muncul setiap kali, Nama tetap diperlukan untuk menjadi bagian dari indeks agar dapat menggunakannya dengan benar.
Menambahkan indeks berkerumun ke tabel saat data penuh membutuhkan waktu kurang dari 1 detik! Jangan abaikan indeks Anda.
