Karen Ly, Analis Pendapatan Tetap Jr. di RBC, memberi saya tantangan T-SQL yang melibatkan menemukan kecocokan terdekat, bukan menemukan kecocokan persis. Dalam artikel ini saya membahas bentuk tantangan yang digeneralisasikan dan disederhanakan.

Tantangan

Tantangannya melibatkan pencocokan baris dari dua tabel, T1 dan T2. Gunakan kode berikut untuk membuat database sampel yang disebut testdb, dan di dalamnya ada tabel T1 dan T2:

 SET NOCOUNT AKTIF; JIKA DB_ID('testdb') NULL CREATE DATABASE testdb; PERGI GUNAKAN testdb; DROP TABLE JIKA ADA dbo.T1, dbo.T2; CREATE TABLE dbo.T1 ( keycol INT NOT NULL IDENTITY CONSTRAINT PK_T1 PRIMARY KEY, val INT NOT NULL, othercols BINARY(100) NOT NULL CONSTRAINT DFT_T1_col1 DEFAULT(0xAA) ); CREATE TABLE dbo.T2 ( keycol INT NOT NULL IDENTITY CONSTRAINT PK_T2 PRIMARY KEY, val INT NOT NULL, othercols BINARY(100) NOT NULL CONSTRAINT DFT_T2_col1 DEFAULT(0xBB) );

Seperti yang Anda lihat, baik T1 dan T2 memiliki kolom numerik (tipe INT dalam contoh ini) yang disebut val. Tantangannya adalah untuk mencocokkan setiap baris dari T1 baris dari T2 di mana perbedaan mutlak antara T2.val dan T1.val adalah yang terendah. Dalam kasus ikatan (beberapa baris yang cocok di T2), cocokkan baris atas berdasarkan val ascending, keycol urutan menaik. Yaitu baris dengan nilai terendah pada kolom val, dan jika masih memiliki ikatan, baris dengan nilai keycol terendah. Tiebreaker digunakan untuk menjamin determinisme.

Gunakan kode berikut untuk mengisi T1 dan T2 dengan kumpulan kecil data sampel agar dapat memeriksa kebenaran solusi Anda:

 TRUNCATE TABLE dbo.T1; TRUNCATE TABEL dbo.T2; MASUKKAN KE dbo.T1 (val) NILAI(1),(1),(3),(3),(5),(8),(13),(16),(18),(20),( 21); MASUKKAN KE dbo.T2 (val) NILAI(2),(2),(7),(3),(3),(11),(11),(13),(17),(19); 

 Periksa isi T1:
 
 SELECT keycol, val, SUBSTRING(othercols, 1, 1) AS othercols FROM dbo.T1 ORDER BY val, keycol;
 

 Kode ini menghasilkan output berikut:
 
 keycol val othercols ----------- ----------- --------- 1 1 0xAA 2 1 0xAA 3 3 0xAA 4 3 0xAA 5 5 0xAA 6 8 0xAA 7 13 0xAA 8 16 0xAA 9 18 0xAA 10 20 0xAA 11 21 0xAA
 

 Periksa isi T2:
 
 SELECT keycol, val, SUBSTRING(othercols, 1, 1) AS othercols FROM dbo.T2 ORDER BY val, keycol;
 

 Kode ini menghasilkan output berikut:
 
 keycol val othercols ----------- ----------- --------- 1 2 0xBB 2 2 0xBB 4 3 0xBB 5 3 0xBB 3 7 0xBB 6 11 0xBB 7 11 0xBB 8 13 0xBB 9 17 0xBB 10 19 0xBB
 

 Inilah hasil yang diinginkan untuk data sampel yang diberikan:
 
 keycol1 val1 othercols1 keycol2 val2 othercols2 ----------- ----------- ---------- --------- -- ----------- ---------- 1 1 0xAA 1 2 0xBB 2 1 0xAA 1 2 0xBB 3 3 0xAA 4 3 0xBB 4 3 0xAA 4 3 0xBB 5 5 0xAA 4 3 0xBB 6 8 0xAA 3 7 0xBB 7 13 0xAA 8 13 0xBB 8 16 0xAA 9 17 0xBB 9 18 0xAA 9 17 0xBB 10 20 0xAA 10 19 0xBB 11 21 0xAA 10 19 0xBB
 

 Sebelum Anda mulai mengerjakan tantangan, periksa hasil yang diinginkan dan pastikan Anda memahami logika pencocokan, termasuk logika tiebreak. Misalnya, pertimbangkan baris di T1 di mana keycol adalah 5 dan val adalah 5. Baris ini memiliki beberapa kecocokan terdekat di T2:
 
 keycol val othercols ----------- ----------- --------- 4 3 0xBB 5 3 0xBB 3 7 0xBB
 

 Di semua baris ini, perbedaan mutlak antara T2.val dan T1.val (5) adalah 2. Menggunakan logika tiebreak berdasarkan urutan val menaik, keycol menaik baris paling atas di sini adalah yang di mana val adalah 3 dan keycol adalah 4. 
 

 Anda akan menggunakan kumpulan kecil data sampel untuk memeriksa validitas solusi Anda. Untuk memeriksa kinerja, Anda memerlukan set yang lebih besar. Gunakan kode berikut untuk membuat fungsi pembantu yang disebut GetNums, yang menghasilkan urutan bilangan bulat dalam rentang yang diminta:
 
 DROP FUNCTION JIKA ADA dbo.GetNums; GO CREATE OR ALTER FUNCTION dbo.GetNums(@low AS BIGINT, @high AS BIGINT) MENGEMBALIKAN TABEL SEBAGAI RETURN DENGAN L0 AS (SELECT c FROM (SELECT 1 UNION ALL SELECT 1) AS D(c)), L1 AS (SELECT 1 AS c FROM L0 AS A CROSS JOIN L0 AS B), L2 AS (PILIH 1 AS c FROM L1 AS A CROSS JOIN L1 AS B), L3 AS (PILIH 1 AS c FROM L2 AS A CROSS JOIN L2 AS B), L4 AS (SELECT 1 AS c FROM L3 AS A CROSS JOIN L3 AS B), L5 AS (SELECT 1 AS c FROM L4 AS A CROSS JOIN L4 AS B), Nums AS (SELECT ROW_NUMBER() OVER(ORDER BY (SELECT NULL) ) AS rownum FROM L5) SELECT TOP(@high - @low + 1) @low + rownum - 1 AS n FROM Nums ORDER BY rownum; PERGI
 

 Gunakan kode berikut untuk mengisi T1 dan T2 dengan kumpulan data sampel yang besar:
 
 MENYATAKAN @numrowsT1 SEBAGAI INT =1000000, @maxvalT1 SEBAGAI INT =10000000, @numrowsT2 SEBAGAI INT =1000000, @maxvalT2 SEBAGAI INT =10000000; TRUNCATE TABEL dbo.T1; TRUNCATE TABEL dbo.T2; INSERT INTO dbo.T1 WITH(TABLOCK) (val) SELECT ABS(CHECKSUM(NEWID())) % @maxvalT1 + 1 AS val FROM dbo.GetNums(1, @numrowsT1) AS Nums; INSERT INTO dbo.T2 WITH(TABLOCK) (val) SELECT ABS(CHECKSUM(NEWID())) % @maxvalT2 + 1 AS val FROM dbo.GetNums(1, @numrowsT2) AS Nums;
 

 Variabel @numrowsT1 dan @numrowsT2 mengontrol jumlah baris yang Anda inginkan untuk diisi tabel. Variabel @maxvalT1 dan @maxvalT2 mengontrol rentang nilai yang berbeda di kolom val, dan karenanya memengaruhi kepadatan kolom. Kode di atas mengisi tabel dengan masing-masing 1.000.000 baris, dan menggunakan kisaran 1 – 10.000.000 untuk kolom val di kedua tabel. Ini menghasilkan kepadatan rendah di kolom (sejumlah besar nilai yang berbeda, dengan sejumlah kecil duplikat). Menggunakan nilai maksimum yang lebih rendah akan menghasilkan kepadatan yang lebih tinggi (jumlah nilai yang berbeda lebih sedikit, dan karenanya lebih banyak duplikat).
 
Solusi 1, menggunakan satu subquery TOP
 

 Solusi paling sederhana dan paling jelas mungkin adalah yang menanyakan T1, dan menggunakan operator CROSS APPLY menerapkan kueri dengan filter TOP (1), mengurutkan baris dengan perbedaan mutlak antara T1.val dan T2.val, menggunakan T2.val , T2.keycol sebagai pemutus. Berikut kode solusinya:
 
 PILIH T1.keycol AS keycol1, T1.val AS val1, SUBSTRING(T1.othercols, 1, 1) AS othercols1, A.keycol AS keycol2, A.val AS val2, SUBSTRING(A.othercols, 1, 1 ) AS othercols2 FROM dbo.T1 CROSS APPLY ( SELECT TOP (1) T2.* FROM dbo.T2 ORDER BY ABS(T2.val - T1.val), T2.val, T2.keycol ) AS A;
 

 Ingat, ada 1.000.000 baris di setiap tabel. Dan kepadatan kolom val rendah di kedua tabel. Sayangnya, karena tidak ada predikat pemfilteran dalam kueri yang diterapkan, dan pengurutan melibatkan ekspresi yang memanipulasi kolom, tidak ada potensi di sini untuk membuat indeks pendukung. Kueri ini menghasilkan rencana pada Gambar 1. 
 

 Gambar 1:Rencanakan Solusi 1 
 

 Input luar loop memindai 1.000.000 baris dari T1. Input bagian dalam loop melakukan pemindaian penuh T2 dan pengurutan TopN untuk setiap nilai T1.val yang berbeda. Dalam rencana kami, ini terjadi 998.657 kali karena kepadatan kami sangat rendah. Ini menempatkan baris dalam gulungan indeks, dikunci oleh T1.val, sehingga dapat digunakan kembali untuk kejadian duplikat dari nilai T1.val, tetapi kami memiliki sangat sedikit duplikat. Rencana ini memiliki kompleksitas kuadrat. Di antara semua eksekusi yang diharapkan dari cabang bagian dalam loop, diperkirakan akan memproses hampir satu triliun baris. Saat berbicara tentang sejumlah besar baris untuk diproses kueri, setelah Anda mulai menyebutkan miliaran baris, orang-orang sudah tahu bahwa Anda berurusan dengan kueri yang mahal. Biasanya, orang tidak mengucapkan istilah seperti triliunan, kecuali jika mereka membahas utang nasional AS, atau ambruknya pasar saham. Anda biasanya tidak berurusan dengan angka-angka seperti itu dalam konteks pemrosesan kueri. Tetapi rencana dengan kompleksitas kuadrat dapat dengan cepat berakhir dengan angka seperti itu. Menjalankan kueri di SSMS dengan Sertakan Statistik Kueri Langsung diaktifkan membutuhkan waktu 39,6 detik untuk memproses hanya 100 baris dari T1 di laptop saya. Ini berarti bahwa kueri ini akan membutuhkan waktu sekitar 4,5 hari untuk diselesaikan. Pertanyaannya adalah, apakah Anda benar-benar menyukai rencana permintaan langsung menonton pesta? Bisa menjadi rekor Guinness yang menarik untuk dicoba dan dibuat.
 
Solusi 2, menggunakan dua subkueri TOP
 

 Dengan asumsi Anda mencari solusi yang membutuhkan waktu beberapa detik, bukan hari, untuk diselesaikan, inilah idenya. Dalam ekspresi tabel yang diterapkan, satukan dua kueri TOP (1) bagian dalam—satu memfilter baris di mana T2.val  =T1.val (dipesan oleh T2.val, T2.keycol). Sangat mudah untuk membuat indeks untuk mendukung kueri semacam itu dengan mengaktifkan pencarian satu baris. Masih dalam ekspresi tabel yang diterapkan, gunakan kueri TOP (1) luar terhadap hasil dua baris, berdasarkan urutan ABS(D.val – T1.val), D.val, D.keycol. Akan ada pengurutan TopN yang terlibat, tetapi akan diterapkan ke dua baris sekaligus.
 

 Berikut adalah indeks yang direkomendasikan untuk mendukung solusi ini:
 
 BUAT INDEKS idx_val_key PADA dbo.T1(val, keycol) INCLUDE(othercols); BUAT INDEKS idx_val_key PADA dbo.T2(val, keycol) INCLUDE(othercols); BUAT INDEKS idx_valD_key PADA dbo.T2(val DESC, keycol) INCLUDE(othercols);
 

 Berikut kode solusi lengkapnya:
 
 PILIH T1.keycol AS keycol1, T1.val AS val1, SUBSTRING(T1.othercols, 1, 1) AS othercols1, A.keycol AS keycol2, A.val AS val2, SUBSTRING(A.othercols, 1, 1 ) AS othercols2 FROM dbo.T1 CROSS APPLY ( SELECT TOP (1) D.* FROM ( SELECT TOP (1) * FROM dbo.T2 WHERE T2.val =T1.val ORDER BY T2.val, T2.keycol ) AS D ORDER BY ABS(D.val - T1.val), D.val, D. keycol ) SEBAGAI A;
 

 Ingat bahwa kita memiliki 1.000.000 baris di setiap tabel, dengan kolom val memiliki nilai dalam kisaran 1 – 10.000.000 (kepadatan rendah), dan indeks optimal sudah ada. 
 

 Rencana untuk kueri ini ditunjukkan pada Gambar 2.
 

 Gambar 2:Rencana Solusi 2 
 

 Amati penggunaan indeks yang optimal pada T2, menghasilkan rencana dengan penskalaan linier. Rencana ini menggunakan spool indeks dengan cara yang sama seperti rencana sebelumnya, yaitu, untuk menghindari pengulangan pekerjaan di cabang dalam loop untuk nilai T1.val duplikat. Berikut adalah statistik kinerja yang saya dapatkan untuk eksekusi kueri ini di sistem saya:
 
 Berlalu:27,7 detik, CPU:27,6 detik, pembacaan logis:17.304.674
 
Solusi 2, dengan spooling dinonaktifkan
 

 Mau tidak mau Anda bertanya-tanya apakah spool indeks benar-benar bermanfaat di sini. Intinya adalah untuk menghindari pekerjaan berulang untuk nilai T1.val duplikat, tetapi dalam situasi seperti kita di mana kita memiliki kepadatan yang sangat rendah, ada sangat sedikit duplikat. Ini berarti bahwa kemungkinan besar pekerjaan yang terlibat dalam spooling lebih besar daripada hanya mengulangi pekerjaan untuk duplikat. Ada cara sederhana untuk memverifikasi ini—menggunakan trace flag 8690 Anda dapat menonaktifkan spooling dalam paket, seperti:
 
 PILIH T1.keycol AS keycol1, T1.val AS val1, SUBSTRING(T1.othercols, 1, 1) AS othercols1, A.keycol AS keycol2, A.val AS val2, SUBSTRING(A.othercols, 1, 1 ) AS othercols2 FROM dbo.T1 CROSS APPLY ( SELECT TOP (1) D.* FROM ( SELECT TOP (1) * FROM dbo.T2 WHERE T2.val =T1.val ORDER BY T2.val, T2.keycol ) AS D ORDER BY ABS(D.val - T1.val), D.val, D. keycol ) SEBAGAI OPSI(QUERYTRACEON 8690);
 

 Saya mendapatkan rencana yang ditunjukkan pada Gambar 3 untuk eksekusi ini:
 

 Gambar 3:Rencana Solusi 2, dengan spooling dinonaktifkan 
 

 Amati bahwa spool indeks menghilang, dan kali ini cabang dalam loop dieksekusi 1.000.000 kali. Berikut adalah statistik kinerja yang saya dapatkan untuk eksekusi ini:
 
 Berlalu:19,18 detik, CPU:19,17 detik, pembacaan logis:6.042.148
 

 Itu pengurangan 44 persen dalam waktu eksekusi. 
 
Solusi 2, dengan rentang nilai dan pengindeksan yang dimodifikasi
 

 Menonaktifkan spooling sangat masuk akal ketika Anda memiliki kepadatan rendah dalam nilai T1.val; Namun, spooling bisa sangat bermanfaat bila Anda memiliki kepadatan tinggi. Misalnya, jalankan kode berikut untuk mengisi ulang T1 dan T2 dengan pengaturan data sampel @maxvalT1 dan @maxvalT2 hingga 1000 (1.000 nilai berbeda maksimum):
 
 MENYATAKAN @numrowsT1 SEBAGAI INT =1000000, @maxvalT1 SEBAGAI INT =1000, @numrowsT2 SEBAGAI INT =1000000, @maxvalT2 SEBAGAI INT =1000; TRUNCATE TABEL dbo.T1; TRUNCATE TABEL dbo.T2; INSERT INTO dbo.T1 WITH(TABLOCK) (val) SELECT ABS(CHECKSUM(NEWID())) % @maxvalT1 + 1 AS val FROM dbo.GetNums(1, @numrowsT1) AS Nums; INSERT INTO dbo.T2 WITH(TABLOCK) (val) SELECT ABS(CHECKSUM(NEWID())) % @maxvalT2 + 1 AS val FROM dbo.GetNums(1, @numrowsT2) AS Nums;
 

 Jalankan kembali Solusi 2, pertama tanpa tanda jejak:
 
 PILIH T1.keycol AS keycol1, T1.val AS val1, SUBSTRING(T1.othercols, 1, 1) AS othercols1, A.keycol AS keycol2, A.val AS val2, SUBSTRING(A.othercols, 1, 1 ) AS othercols2 FROM dbo.T1 CROSS APPLY ( SELECT TOP (1) D.* FROM ( SELECT TOP (1) * FROM dbo.T2 WHERE T2.val =T1.val ORDER BY T2.val, T2.keycol ) AS D ORDER BY ABS(D.val - T1.val), D.val, D. keycol ) SEBAGAI A;
 

 Rencana eksekusi ini ditunjukkan pada Gambar 4:
 

 Gambar 4:Rencana Solusi 2, dengan rentang nilai 1 – 1000 
 

 Pengoptimal memutuskan untuk menggunakan paket yang berbeda karena kepadatan tinggi di T1.val. Perhatikan bahwa indeks pada T1 dipindai dalam urutan kunci. Jadi, untuk setiap kemunculan pertama dari nilai T1.val yang berbeda, cabang bagian dalam loop dieksekusi, dan hasilnya digulung dalam gulungan tabel biasa (rebind). Kemudian, untuk setiap kemunculan nilai yang bukan pertama, rewind diterapkan. Dengan 1.000 nilai yang berbeda, cabang dalam dieksekusi hanya 1.000 kali. Ini menghasilkan statistik kinerja yang sangat baik:
 
 Berlalu:1,16 detik, CPU:1,14 detik, pembacaan logis:23.278
 

 Sekarang coba jalankan solusi dengan spooling dinonaktifkan:
 
 PILIH T1.keycol AS keycol1, T1.val AS val1, SUBSTRING(T1.othercols, 1, 1) AS othercols1, A.keycol AS keycol2, A.val AS val2, SUBSTRING(A.othercols, 1, 1 ) AS othercols2 FROM dbo.T1 CROSS APPLY ( SELECT TOP (1) D.* FROM ( SELECT TOP (1) * FROM dbo.T2 WHERE T2.val =T1.val ORDER BY T2.val, T2.keycol ) AS D ORDER BY ABS(D.val - T1.val), D.val, D. keycol ) SEBAGAI OPSI(QUERYTRACEON 8690);
 

 Saya mendapatkan rencana yang ditunjukkan pada Gambar 5.
 

 Gambar 5:Rencana Solusi 2, dengan rentang nilai 1 – 1.000 dan spooling dinonaktifkan  
 

 Ini pada dasarnya adalah rencana yang sama yang ditunjukkan sebelumnya pada Gambar 3. Cabang bagian dalam dari loop dieksekusi 1.000.000 kali. Berikut adalah statistik kinerja yang saya dapatkan untuk eksekusi ini:
 
 Berlalu:24,5 detik, CPU:24,2 detik, pembacaan logis:8.012.548
 

 Jelas, Anda ingin berhati-hati untuk tidak menonaktifkan spooling saat Anda memiliki kepadatan tinggi di T1.val.
 

 Hidup itu baik ketika situasi Anda cukup sederhana sehingga Anda dapat membuat indeks pendukung. Kenyataannya adalah bahwa dalam beberapa kasus dalam praktiknya, ada cukup logika tambahan dalam kueri, yang menghalangi kemampuan untuk membuat indeks pendukung yang optimal. Dalam kasus seperti itu, Solusi 2 tidak akan berjalan dengan baik.
 

 Untuk mendemonstrasikan kinerja Solusi 2 tanpa indeks pendukung, isi ulang T1 dan T2 kembali dengan pengaturan data sampel @maxvalT1 dan @maxvalT2 hingga 10000000 (rentang nilai 1 – 10M), dan juga hapus indeks pendukung:
 
 JATUH INDEKS JIKA ADA idx_val_key PADA dbo.T1; JATUHKAN INDEKS JIKA ADA idx_val_key PADA dbo.T2; JATUHKAN INDEKS JIKA ADA idx_valD_key PADA dbo.T2; MENYATAKAN @numrowsT1 SEBAGAI INT =1000000, @maxvalT1 SEBAGAI INT =10000000, @numrowsT2 SEBAGAI INT =1000000, @maxvalT2 SEBAGAI INT =10000000; TRUNCATE TABEL dbo.T1; TRUNCATE TABEL dbo.T2; INSERT INTO dbo.T1 WITH(TABLOCK) (val) SELECT ABS(CHECKSUM(NEWID())) % @maxvalT1 + 1 AS val FROM dbo.GetNums(1, @numrowsT1) AS Nums; INSERT INTO dbo.T2 WITH(TABLOCK) (val) SELECT ABS(CHECKSUM(NEWID())) % @maxvalT2 + 1 AS val FROM dbo.GetNums(1, @numrowsT2) AS Nums;
 

 Jalankan kembali Solusi 2, dengan Sertakan Statistik Kueri Langsung diaktifkan di SSMS:
 
 PILIH T1.keycol AS keycol1, T1.val AS val1, SUBSTRING(T1.othercols, 1, 1) AS othercols1, A.keycol AS keycol2, A.val AS val2, SUBSTRING(A.othercols, 1, 1 ) AS othercols2 FROM dbo.T1 CROSS APPLY ( SELECT TOP (1) D.* FROM ( SELECT TOP (1) * FROM dbo.T2 WHERE T2.val =T1.val ORDER BY T2.val, T2.keycol ) AS D ORDER BY ABS(D.val - T1.val), D.val, D. keycol ) SEBAGAI A;
 

 Saya mendapatkan paket yang ditunjukkan pada Gambar 6 untuk kueri ini:
 

 Gambar 6:Rencana Solusi 2, tanpa pengindeksan, dengan rentang nilai 1 – 1.000.000  
 

 Anda dapat melihat pola yang sangat mirip dengan yang ditunjukkan sebelumnya pada Gambar 1, hanya saja kali ini rencana memindai T2 dua kali per nilai T1.val yang berbeda. Sekali lagi, kompleksitas rencana menjadi kuadrat. Menjalankan kueri di SSMS dengan Sertakan Statistik Kueri Langsung diaktifkan membutuhkan waktu 49,6 detik untuk memproses 100 baris dari T1 di laptop saya, artinya kueri ini akan membutuhkan waktu sekitar 5,7 hari untuk diselesaikan. Ini tentu saja bisa berarti kabar baik jika Anda mencoba memecahkan rekor dunia Guinness untuk menonton pesta rencana kueri langsung.
 
Kesimpulan
 

 Saya ingin berterima kasih kepada Karen Ly dari RBC karena telah memberi saya tantangan pertandingan terdekat yang bagus ini. Saya cukup terkesan dengan kodenya untuk menanganinya, yang mencakup banyak logika tambahan yang khusus untuk sistemnya. Dalam artikel ini saya menunjukkan solusi yang berkinerja wajar ketika Anda dapat membuat indeks pendukung yang optimal. Tetapi seperti yang Anda lihat, dalam kasus di mana ini bukan pilihan, jelas waktu eksekusi yang Anda dapatkan sangat buruk. Dapatkah Anda memikirkan solusi yang akan bekerja dengan baik bahkan tanpa indeks pendukung yang optimal? Bersambung…