Pertandingan Terdekat, Bagian 3

Dalam Pertandingan Terdekat, Bagian 1, saya membahas tantangan T-SQL yang diberikan kepada saya oleh Karen Ly, Analis Pendapatan Tetap Jr. di RBC. Tantangannya melibatkan dua tabel — T1 dan T2, masing-masing dengan kolom kunci (keycol), nilai (val), dan beberapa kolom lainnya (diwakili dengan kolom yang disebut othercols). Tugasnya adalah mencocokkan setiap baris dari T1 baris dari T2 di mana T2.val paling dekat dengan T1.val (perbedaan mutlak adalah yang terendah terendah), menggunakan nilai T2.keycol terendah sebagai tiebreaker. Saya memberikan beberapa solusi relasional, dan mendiskusikan karakteristik kinerjanya. Saya juga menantang Anda untuk mencoba dan menemukan solusi yang berkinerja wajar jika Anda tidak diizinkan/mampu membuat indeks pendukung. Di Bagian 2, saya menunjukkan bagaimana ini dapat dicapai dengan menggunakan solusi berulang. Saya mendapatkan beberapa solusi pembaca yang sangat menarik dari Kamil Konsno, Alejandro Mesa dan Radek Celuch, dan solusi tersebut menjadi fokus artikel bulan ini.

Contoh Data

Sebagai pengingat, saya menyediakan kumpulan data sampel kecil dan besar untuk Anda gunakan. Set kecil untuk memeriksa validitas solusi Anda dan set besar untuk memeriksa kinerjanya. Gunakan kode berikut untuk membuat database sampel testdb dan di dalamnya tabel sampel T1 dan T2:

-- Contoh dbSET NOCOUNT ON; IF DB_ID('testdb') IS NULL CREATE DATABASE testdb;GO GUNAKAN testdb;GO -- Contoh tabel T1 dan T2DROP TABLE IF EXISTS 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));

Gunakan kode berikut untuk mengisi tabel dengan kumpulan kecil data sampel:

-- Mengisi T1 dan T2 dengan kumpulan kecil data sampel TRUNCATE TABLE dbo.T1;TRUNCATE TABLE 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); 

 Saya akan menggunakan kumpulan kecil data sampel saat menjelaskan logika solusi yang berbeda dan memberikan kumpulan hasil antara untuk langkah-langkah solusi.
 

 Gunakan kode berikut untuk membuat fungsi pembantu GetNums dan untuk mengisi tabel dengan kumpulan data sampel yang besar:
 
-- Fungsi pembantu untuk menghasilkan urutan bilangan bulatDROP FUNCTION JIKA ADA dbo.GetNums;GO CREATE OR ALTER FUNCTION dbo.GetNums(@low AS BIGINT, @high AS BIGINT) RETURNS TABLEASRETURN WITH L0 AS (SELECT c FROM (SELECT c FROM) 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 (SELECT 1 AS c FROM L1 AS A CROSS JOIN L1 AS B), L3 AS (PILIH 1 AS c DARI L2 SEBAGAI LINTAS GABUNG L2 AS B), L4 AS (PILIH 1 AS c DARI L3 SEBAGAI LINTAS GABUNG L3 AS B), L5 AS (PILIH 1 AS c DARI L4 SEBAGAI LINTAS GABUNG 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;GO -- Mengisi T1 dan T2 dengan kumpulan data sampel yang besarDECLARE @numrowsT1 AS INT =1000000, @maxvalT1 AS INT =10000000, @numrowsT2 AS INT =1000000, @maxvalT2 AS INT =10000000; TRUNCATE TABLE dbo.T1;TRUNCATE TABLE 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;
 

 Saat Anda ingin menguji solusi Anda dengan indeks pendukung, gunakan kode berikut untuk membuat indeks tersebut:
 
BUAT INDEX idx_val_key PADA dbo.T1(val, keycol) INCLUDE(othercols);BUAT INDEX idx_val_key PADA dbo.T2(val, keycol) INCLUDE(othercols);BUAT INDEX idx_valD_key ON val dbo.T2 INCLUDE(othercols);
 

 Saat Anda ingin menguji solusi Anda tanpa mendukung indeks, gunakan kode berikut untuk menghapus indeks tersebut:
 
LEPAS INDEKS JIKA ADA idx_val_key PADA dbo.T1;LEPASKAN INDEKS JIKA ADA idx_val_key PADA dbo.T2;TURUN INDEKS JIKA ADA idx_valD_key PADA dbo.T2;
 
Solusi 1 oleh Kamil Kosno – Menggunakan tabel sementara
 

 Kamil Kosno mengajukan beberapa — dua dengan ide orisinalnya, dan dua variasi pada solusi Alejandro dan Radek. Solusi pertama Kamil menggunakan tabel sementara yang diindeks. Seringkali terjadi bahwa meskipun Anda tidak diizinkan untuk membuat indeks pendukung pada tabel asli, Anda diizinkan untuk bekerja dengan tabel sementara, dan dengan tabel sementara Anda selalu dapat membuat indeks sendiri.
 

 Berikut kode solusi lengkapnya:
 
DROP TABLE JIKA ADA #T2; PILIH MIN(keycol) AS keycol, valINTO #T2FROM dbo.T2GROUP BY val; BUAT INDEKS UNIK idx_nc_val_key ON #T2(val, keycol); WITH bestvals AS( SELECT keycol AS keycol1, val AS val1, othercols AS othercols1, CASE WHEN (prev + nxt IS NULL) THEN COALESCE(prev, nxt) WHEN ABS(val - prev)  

 Pada Langkah 1 dari solusi Anda menyimpan keycol minimum untuk setiap val unik dalam tabel sementara yang disebut #T2, dan membuat indeks pendukung pada (val, keycol). Berikut kode yang mengimplementasikan langkah ini:
 
DROP TABLE JIKA ADA #T2; PILIH MIN(keycol) AS keycol, valINTO #T2FROM dbo.T2GROUP BY val; BUAT INDEKS UNIK idx_nc_val_key ON #T2(val, keycol); PILIH * DARI #T2;
 

 Tabel sementara diisi dengan data berikut:
 
keycol val----------- ----------1 24 33 76 118 139 1710 19
 

 Pada Langkah 2 dari solusi Anda menerapkan yang berikut:
 

 Untuk setiap baris di T1 hitung nilai prev dan nxt dari #T2. Hitung prev sebagai val maksimum di #T2 yang kurang dari atau sama dengan val di T1. Hitung nxt sebagai val minimum di #T2 yang lebih besar dari atau sama dengan val di T1.
 

 Gunakan ekspresi CASE untuk menghitung val2 berdasarkan logika berikut:
 
 
 Ketika prev atau nxt adalah null, kembalikan nonnull pertama dari keduanya, atau NULL jika keduanya NULL. 
 
 Ketika perbedaan absolut antara val dan prev kurang dari perbedaan absolut antara val dan nxt, kembalikan prev. 
 
 Jika selisih mutlak antara val dan nxt lebih kecil dari selisih mutlak antara val dan prv, kembalikan nxt. 
 
 Lain, jika nxt kurang dari sebelumnya, kembalikan nxt, jika tidak kembalikan sebelumnya. 
 
 

 Berikut kode yang mengimplementasikan langkah ini:
 
SELECT keycol AS keycol1, val AS val1, othercols AS othercols1, CASE WHEN (prev + nxt IS NULL) THEN COALESCE(prev, nxt) WHEN ABS(val - prev)  

 Kode ini menghasilkan output berikut:
 
keycol1 val1 othercols1 val2-------- ----- ----------- -----1 1 0xAA 22 1 0xAA 23 3 0xAA 34 3 0xAA 35 5 0xAA 36 8 0xAA 77 13 0xAA 138 16 0xAA 179 18 0xAA 1710 20 0xAA 1911 21 0xAA 19
 

 Di Langkah 3 solusi, Anda menentukan CTE yang disebut bestvals berdasarkan kueri dari Langkah2. Kemudian gabungkan bestval dengan #T2 untuk mendapatkan kunci, dan gabungkan hasilnya dengan T2 untuk mendapatkan data lainnya (kolom lain).
 

 Berikut kode yang mengimplementasikan langkah ini:
 
SELECT keycol1, val1, SUBSTRING(othercols1, 1, 1) AS othercols1, tempT2.keycol AS keycol2, val2, SUBSTRING(T2.othercols, 1, 1) AS othercols2FROM bestvals AS B INNER JOIN #T2 AS tempT2 ON tempT2 .val =B.val2 INNER GABUNG dbo.T2 DI T2.keycol =tempT2.keycol;
 

 Rencana solusi 1 oleh Kamil dengan indeks pendukung ditunjukkan pada Gambar 1.
 

 Gambar 1:Rencanakan solusi 1 oleh Kamil dengan indeks 
 

 Cabang pertama dari rencana mengelompokkan dan menggabungkan data dari T2 dan menulis hasilnya ke tabel sementara #T2. Perhatikan bahwa cabang ini menggunakan algoritme Stream Aggregate yang telah dipesan sebelumnya yang bergantung pada pemindaian berurutan indeks idx_valD_key pada T2.
 

 Berikut adalah statistik kinerja untuk rencana ini:
 
run time (sec):5,55, CPU (sec):16.6, pembacaan logis:6.687.172
 

 Rencana solusi 1 oleh Kamil tanpa indeks pendukung ditunjukkan pada Gambar 2.
 

 Gambar 2:Rencanakan solusi 1 oleh Kamil tanpa indeks 
 

 Perbedaan utama antara rencana ini dan yang sebelumnya adalah bahwa cabang pertama dari rencana tersebut, yang menangani bagian pengelompokan dan agregasi pada Langkah 1, kali ini tidak dapat menarik data yang telah dipesan sebelumnya dari indeks pendukung, sehingga menariknya tidak berurutan dari clustered indeks pada T2 dan kemudian menggunakan algoritma Hash Aggregate.
 

 Berikut adalah statistik kinerja untuk rencana ini:
 
waktu berjalan:6,44, CPU:19,3, pembacaan logis:6.688.277
 
Solusi oleh Alejandro Mesa – Menggunakan teknik nonnull terakhir
 

 Solusi Alejandro menggunakan teknik nonnull terakhir yang dijelaskan di sini.
 

 Berikut kode solusi lengkapnya (disediakan di sini tanpa mengembalikan kode lain):
 
DENGAN R1 AS( SELECT keycol, val, tid, MAX( CASE WHEN tid =0 THEN CAST(val AS binary(4)) + CAST(keycol AS binary(4)) END ) OVER( ORDER BY val, tid , keycol BARIS ANTARA UNBOUNDED PRECEDING DAN 1 PRECEDING ) SEPERTI berikut_binstr, MIN( CASE WHEN tid =0 THEN CAST(val AS binary(4)) + CAST(keycol AS binary(4)) END ) OVER( ORDER BY val, tid, keycol BARIS ANTARA 1 FOLLOWING DAN UNBOUNDED FOLLOWING ) SEPERTI atas_binstr FROM ( SELECT keycol, val, 1 AS tid FROM dbo.T1 UNION ALL SELECT MIN(keycol) AS keycol, val, 0 AS tid FROM dbo.T2 GROUP BY val ) AS T ),R2 AS( SELECT keycol, val, CAST(SUBSTRING(di bawah_binstr, 1, 4) AS int) AS di bawah_T2_val, CAST(SUBSTRING(dibawah_binstr, 5, 4) AS int) AS di bawah_T2_keycol, CAST(SUBSTRING(di atas_binstr, 1, 4) AS int) AS di atas_T2_val, CAST(SUBSTRING(di atas_binstr, 5, 4) AS int) AS di atas_T2_keycol FROM R1 WHERE tid =1),R3 AS( SELECT keycol, val, COALESCE(di bawah_T2_val, di atas_T2 _val) AS di bawah_T2_val, COALESCE(di bawah_T2_keycol, di atas_T2_keycol) AS di bawah_T2_keycol, COALESCE(di atas_T2_val, di bawah_T2_val) AS di atas_T2_val, COALESCE(di atas_T2_keycol, di bawah_T2_keycol AScol_AS_T2_val) AS col ) <=ABS(above_T2_val - val) THEN below_T2_keycol ELSE above_T2_keycol END AS keycol2, CASE WHEN ABS(val - below_T2_val) <=ABS(above_T2_val - val) THEN below_T2_val ELSE above_T2_VROM END AS; 

 Pada Langkah 1 dari solusi, Anda menyatukan baris dari T1 (menetapkan kolom hasil yang disebut tid ke 1) dengan baris dari T2 (menetapkan tid =0), dan mendefinisikan tabel turunan yang disebut T berdasarkan hasil. Menggunakan teknik nonnull terakhir, berdasarkan urutan val, tid, keycol, untuk setiap baris saat ini, Anda mengambil nilai baris tid =0 terakhir yang digabungkan menjadi kolom biner yang disebut below_binstr. Demikian pula, Anda mengambil nilai tid =0 baris berikutnya yang digabungkan menjadi kolom biner yang disebut above_binstr.
 

 Berikut kode yang mengimplementasikan langkah ini:
 
SELECT keycol, val, tid, MAX( CASE WHEN tid =0 THEN CAST(val AS binary(4)) + CAST(keycol AS binary(4)) END ) OVER( ORDER BY val, tid, keycol BARIS ANTARA UNBOUNDED PRECEDING DAN 1 PRECEDING ) AS below_binstr, MIN( CASE WHEN WHEN =0 THEN CAST(val AS binary(4)) + CAST(keycol AS binary(4)) END ) OVER( ORDER BY val, tid, keycol BARIS ANTARA 1 FOLLOWING DAN UNBOUNDED FOLLOWING ) AS above_binstrFROM ( SELECT keycol, val, 1 AS tid FROM dbo.T1 UNION ALL SELECT MIN(keycol) AS keycol, val, 0 AS tid FROM dbo.T2 GROUP BY val ) AS T;
 

 Kode ini menghasilkan output berikut:
 
keycol val tid below_binstr above_binstr----------- ----------- ----------- --------- --------- ------------------1 1 1 NULL 0x00000002000000012 1 1 NULL 0x00000002000000011 2 0 NULL 0x00000003000000044 3 0 0x0000000200000001 0x00000007000000033 3 1 0x0000000300000004 0x00000007000000034 3 1 0x0000000300000004 0x00000007000000035 5 1 0x0000000300000004 0x00000007000000033 7 0 0x0000000300000004 0x0000000B000000066 8 1 0x0000000700000003 0x0000000B000000066 11 0 0x0000000700000003 0x0000000D000000088 13 0 0x0000000B000000097 0x00000100000000 08 0x00000011000000098 16 1 0x0000000D00000008 0x00000011000000099 17 0 0x0000000D00000008 0x000000130000000A9 18 1 0x0000001100000009 0x000000130000000A10 19 0 0x0000001100000009 NULL10 20 1 0x000000130000000A NULL11 21 1 0x0000001
 Pada Langkah 2 dari solusi, Anda mendefinisikan CTE yang disebut R1 berdasarkan kueri dari Langkah 1. Anda meminta R1, memfilter hanya baris di mana tid =1, dan mengekstrak nilai individual dari string biner gabungan.
 

 Berikut kode yang mengimplementasikan langkah ini:
 
SELECT keycol, val, CAST(SUBSTRING(di bawah_binstr, 1, 4) AS int) AS di bawah_T2_val, CAST(SUBSTRING(dibawah_binstr, 5, 4) AS int) AS di bawah_T2_keycol, CAST(SUBSTRING(di atas_binstr, 1, 4) AS int) AS di atas_T2_val, CAST(SUBSTRING(di atas_binstr, 5, 4) AS int) AS di atas_T2_keycolFROM R1WHERE tid =1;
 

 Kode ini menghasilkan output berikut:
 
keycol val below_T2_val below_T2_keycol above_T2_val above_T2_keycol----------- ----------- ------------ ------- -------- ------------ ---------------1 1 NULL NULL 2 12 1 NULL NULL 2 13 3 3 4 7 34 3 3 4 7 35 5 3 4 7 36 8 7 3 11 67 13 13 8 17 98 16 13 8 17 99 18 17 9 19 1010 20 19 10 NULL NULL11 21 19 10 NULL NULL
 

 Pada Langkah 3 dari solusi Anda mendefinisikan CTE yang disebut R2 berdasarkan kueri dari Langkah 2. Anda kemudian menghitung kolom hasil berikut:
 
 
 below_T2_val:nonnull pertama antara below_T2_val dan above_T2_val 
 
 below_T2_keycol:nonnull pertama antara below_T2_keycol dan above_T2_keycol 
 
 atas_T2_val:nonnull pertama antara atas_T2_val dan di bawah_T2_val 
 
 above_T2_keycol:nonnull pertama antara above_T2_keycol dan below_T2_keycol 
 
 

 Berikut kode yang mengimplementasikan langkah ini:
 SELECT keycol, val, COALESCE(di bawah_T2_val, di atas_T2_val) AS di bawah_T2_val, COALESCE(di bawah_T2_keycol, di atas_T2_keycol) AS di bawah_T2_keycol, COALESCE(di atas_T2_val, di bawah_T2_val) AS di atas kunci_kolom_T2_AS di atas_kolom_T2_Kol_T2_T2_kunci_di atas COALESCE_tekan_kunci 

 Kode ini menghasilkan output berikut:
 
keycol val below_T2_val below_T2_keycol above_T2_val above_T2_keycol----------- ----------- ------------ ------- -------- ------------ --------------- 1 1 2 1 2 12 1 2 1 2 13 3 3 4 7 34 3 3 4 7 35 5 3 4 7 36 8 7 3 11 67 13 13 8 17 98 16 13 8 17 99 18 17 9 19 1010 20 19 10 19 1011 21 19 10 19 10
 

 Pada Langkah 4 dari solusi Anda mendefinisikan CTE yang disebut R3 berdasarkan kueri dari Langkah 3. Anda mengembalikan keycol alias sebagai T1_keycol dan val alias sebagai T1_val. Hitung kolom hasil T2_keycol sebagai:jika perbedaan absolut antara val dan below_T2_val kurang dari atau sama dengan perbedaan absolut antara above_T2_val dan val, kembalikan below_T2_keycol, jika tidak di atas_T2_keycol. Hitung kolom hasil T2_val sebagai:jika perbedaan absolut antara val dan below_T2_val kurang dari atau sama dengan perbedaan absolut antara above_T2_val dan val, kembalikan ke below_T2_val, jika tidak di atas_T2_val.
 

 Berikut kode yang mengimplementasikan langkah ini:
 
SELECT keycol AS keycol1, val AS val1, CASE WHEN ABS(val - below_T2_val) <=ABS(above_T2_val - val) THEN below_T2_keycol ELSE above_T2_keycol END AS keycol2, CASE WHEN ABS(val - below_T2_val) <=ABS_val - val) LALU di bawah_T2_val LAIN di atas_T2_val AKHIR SEBAGAI val2FROM R3;
 

 Rencana solusi Alejandro dengan indeks pendukung ditunjukkan pada Gambar 3.
 

 Gambar 3:Rencana solusi oleh Alejandro dengan indeks 
 

 Berikut adalah statistik kinerja untuk rencana ini:
 
waktu berjalan:7.8, CPU:12.6, pembacaan logis:35.886
 

 Rencana solusi Alejandro tanpa indeks pendukung ditunjukkan pada Gambar 4.
 

 Gambar 4:Rencanakan solusi oleh Alejandro tanpa indeks 
 

 Berikut adalah statistik kinerja untuk rencana ini:
 
waktu berjalan:8,19, CPU:14.8, pembacaan logis:37.091
 

 Perhatikan bahwa dalam dua cabang pertama dari rencana pada Gambar 4 ada dua jenis sebelum operator Merge Join (Concatenation) karena kurangnya indeks pendukung. Jenis-jenis tersebut tidak diperlukan dalam rencana pada Gambar 3 karena data diambil dari indeks pendukung.
 
Variasi Kamil pada solusi Alejandro
 

 Dalam solusi ini, Kamil juga mengandalkan teknik nonnull terakhir. Berikut kode solusi lengkapnya:
 
DENGAN all_vals AS( SELECT keycol, val FROM dbo.T1 UNION ALL SELECT DISTINCT NULL, val FROM dbo.T2),rentang AS( SELECT keycol, val, MAX(CASE WHEN keycol IS NULL THEN val END) OVER (ORDER OLEH val, keycol ROWS ANTARA UNBOUNDED PRECEDING DAN 1 PRECEDING) AS prev, MIN(CASE WHEN keycol IS NULL THEN val END) OVER (ORDER BY val, keycol ROWS BETWEEN 1 FOLLOWING AND UNBOUNDED FOLLOWING) SEBAGAI nxt,FROM all_vals SELECT keycol AS keycol1, val AS val1, CASE WHEN ABS(val - prev) <=ISNULL(ABS(val - nxt), prev) THEN prev ELSE nxt END AS val2 FROM ranges WHERE keycol IS NOT NULL)SELECT keycol1, val1, SUBSTRING(T1.othercols, 1, 1) AS othercols1, val2, T2.keycol AS keycol2, SUBSTRING(T2.othercols, 1, 1) AS othercols2 FROM matched_vals AS M INNER JOIN ( SELECT *, ROW_NUMBER() OVER (PARTITION BY val ORDER BY keycol) AS rn FROM dbo.T2 ) AS T2 PADA T2.val =M.val2 AND rn =1 INNER JOIN dbo.T1 PADA T1.keycol =keycol1;
 

 Pada Langkah 1 dari solusi Anda mendefinisikan CTE yang disebut all_vals and ranges, di mana Anda menggunakan teknik nonnull terakhir untuk mengidentifikasi setiap nilai di T1 (di mana keycol bukan NULL) rentang di bawah (sebelumnya) dan di atas (nxt) nilai dari T2 ( di mana keycol adalah null).
 

 Berikut kode yang mengimplementasikan langkah ini:
 
DENGAN all_vals AS( SELECT keycol, val FROM dbo.T1 UNION ALL SELECT DISTINCT NULL, val FROM dbo.T2),rentang AS( SELECT keycol, val, MAX(CASE WHEN keycol IS NULL THEN val END) OVER (ORDER OLEH val, keycol BARIS ANTARA UNBOUNDED PRECEDING DAN 1 PRECEDING) SEBAGAI prev, MIN(CASE WHEN keycol IS NULL THEN val END) OVER (ORDER BY val, keycol BARIS ANTARA 1 FOLLOWING DAN UNBOUNDED FOLLOWING) SEBAGAI nxt FROM all_vals;
 

 Kode ini menghasilkan output berikut:
 
keycol val prev nxt----------- ----------- ----------- ---------- -1 1 NULL 22 1 NULL 2NULL 2 NULL 3NULL 3 2 73 3 3 74 3 3 75 5 3 7NULL 7 3 116 8 7 11NULL 11 7 13NULL 13 11 177 13 13 178 16 13 17NULL 17 13 199 18 17 19NULL 19 17 NULL10 20 19 NULL11 21 19 NULL
 

 Pada Langkah 2 dari solusi Anda menanyakan rentang CTE dan memfilter hanya baris di mana keycol tidak nol. Anda mengembalikan kolom keycol dan val dari T1 sebagai keycol1 dan val1, masing-masing. Kemudian, antara prev dan nxt, Anda mengembalikan yang paling dekat ke val1 sebagai val2.
 

 Berikut kode yang mengimplementasikan langkah ini:
 
SELECT keycol AS keycol1, val AS val1, CASE WHEN ABS(val - prev) <=ISNULL(ABS(val - nxt), prev) THEN prev ELSE nxt END AS val2FROM rangesWHERE keycol IS NOT NULL;
 

 Kode ini menghasilkan output berikut:
 
keycol1 val1 val2----------- ----------- -----------1 1 22 1 23 3 34 3 35 5 36 8 77 13 138 16 179 18 1710 20 1911 21 19
 

 Pada Langkah 3 dari solusi Anda mendefinisikan CTE yang disebut matched_vals berdasarkan kueri dari Langkah 2. Anda juga mendefinisikan tabel turunan yang disebut T2 di mana menggunakan nomor baris yang dipartisi Anda menangani logika tiebreak untuk baris dari dbo.T2. Anda kemudian bergabung dengan matched_vals, CTE T2 dan tabel T1 untuk menangani logika pencocokan akhir.
 

 Berikut kode yang mengimplementasikan langkah ini:
 
SELECT keycol1, val1, SUBSTRING(T1.othercols, 1, 1) AS othercols1, val2, T2.keycol AS keycol2, SUBSTRING(T2.othercols, 1, 1) AS othercols2 FROM matched_vals AS M INNER JOIN ( SELECT * , ROW_NUMBER() OVER (PARTITION BY val ORDER BY keycol) AS rn FROM dbo.T2 ) AS T2 ON T2.val =M.val2 AND rn =1 INNER JOIN dbo.T1 ON T1.keycol =keycol1;
 

 Rencana variasi Kamil pada solusi Alejandro dengan indeks pendukung ditunjukkan pada Gambar 5.
 

 Gambar 5:Rencanakan variasi Kamil pada solusi Alejandro dengan indeks 
 

 Berikut adalah statistik kinerja untuk rencana ini:
 
waktu berjalan:11.5, CPU:18.3, pembacaan logis:59.218
 

 Rencana variasi Kamil pada solusi Alejandro tanpa indeks pendukung ditunjukkan pada Gambar 6.
 

 Gambar 6:Rencanakan variasi Kamil pada solusi Alejandro tanpa indeks 
 

 Berikut adalah statistik kinerja untuk rencana ini:
 
waktu berjalan:12,6, CPU:23.5, pembacaan logis:61.432
 

 Mirip dengan rencana untuk solusi Alejandro, juga dalam hal ini rencana pada Gambar 5 tidak memerlukan pengurutan eksplisit sebelum menerapkan operator Merge Join (penggabungan) karena data diambil secara preorder dari indeks pendukung, dan rencana pada Gambar 6 tidak. memerlukan pengurutan eksplisit karena tidak ada indeks pendukung.
 
Solusi oleh Radek Celuch – Menggunakan interval
 

 Radek datang dengan ide yang sederhana dan indah. Untuk setiap nilai yang berbeda di T2.val Anda menghitung interval yang mewakili rentang nilai dari T1.val yang akan cocok dengan T2.val saat ini. 
 

 Berikut kode solusi lengkapnya:
 
DENGAN Pre1 AS( SELECT keycol, val, othercols, ROW_NUMBER() OVER(PARTITION BY val ORDER BY keycol) AS rn FROM dbo.T2),Pre2 AS( SELECT keycol, val, othercols, LAG(val) OVER( ORDER BY val) AS prev, LEAD(val) OVER(ORDER BY val) AS next FROM Pre1 WHERE rn =1),T2 AS( SELECT keycol, val, othercols, ISNULL(val - (val - prev) / 2 + ( 1 - (val - sebelumnya) % 2), 0) AS rendah, ISNULL(val + (berikutnya - val) / 2, 2147483647) AS tinggi FROM Pre2)PILIH T1.keycol AS keycol1, T1.val AS val1, SUBSTRING( T1.othercols, 1, 1) AS othercols1, T2.keycol AS keycol2, T2.val AS val2, SUBSTRING(T2.othercols, 1, 1) AS othercols2FROM dbo.T1 INNER JOIN T2 PADA T1.val ANTARA T2.low DAN T2.tinggi;
 

 Pada Langkah 1 dari solusi Anda meminta T2 dan menghitung nomor baris (panggil kolom rn), dipartisi oleh val dan diurutkan oleh keycol. Anda mendefinisikan CTE yang disebut Pre1 berdasarkan kueri ini. Anda kemudian menanyakan Pre1 dan memfilter hanya baris di mana rn =1. Dalam kueri yang sama, menggunakan LAG dan LEAD, Anda mengembalikan nilai kolom val untuk setiap baris dari baris sebelumnya (sebut saja sebelumnya) dan dari baris berikutnya ( panggil berikutnya).
 

 Berikut kode yang mengimplementasikan langkah ini:
 
DENGAN Pre1 AS( SELECT keycol, val, othercols, ROW_NUMBER() OVER(PARTITION BY val ORDER BY keycol) AS rn FROM dbo.T2)SELECT keycol, val, othercols, LAG(val) OVER(ORDER BY val) AS prev, LEAD(val) OVER(ORDER BY val) AS nextFROM Pre1WHERE rn =1;
 

 Kode ini menghasilkan output berikut:
 
keycol val othercols prev next------- ---- ---------- ----------- ---------- -1 2 0xBB NULL 34 3 0xBB 2 73 7 0xBB 3 116 11 0xBB 7 138 13 0xBB 11 179 17 0xBB 13 1910 19 0xBB 17 NULL
 

 Pada Langkah 2 dari solusi Anda mendefinisikan CTE yang disebut Pre2 berdasarkan kueri dari Langkah 1. Anda meminta Pre2 dan menghitung untuk setiap baris interval [rendah, tinggi] di mana val dari T1 akan masuk. Berikut adalah perhitungan untuk rendah dan tinggi:
 
 
 rendah =ISNULL(val – (val – sebelumnya) / 2 + (1 – (val – sebelumnya) % 2), 0) 
 
 tinggi =ISNULL(val + (berikutnya – val) / 2, 2147483647) 
 
 

 Pemeriksaan mod 2 pada penghitungan batas rendah digunakan untuk memenuhi persyaratan T2.val yang lebih rendah, dan filter nomor baris digunakan untuk memenuhi persyaratan T2.keycol yang lebih rendah. Nilai 0 dan 2147483647 digunakan sebagai batas bawah dan atas yang ekstrim.
 

 Berikut kode yang mengimplementasikan langkah ini:
 
SELECT keycol, val, othercols, ISNULL(val - (val - sebelumnya) / 2 + (1 - (val - sebelumnya) % 2), 0) AS rendah, ISNULL(val + (berikutnya - val) / 2 , 2147483647) AS highFROM Pre2;
 

 Kode ini menghasilkan output berikut:
 
keycol val othercols low high------- ---- ---------- ---- -----------1 2 0xBB 0 24 3 0xBB 3 53 7 0xBB 6 96 11 0xBB 10 128 13 0xBB 13 159 17 0xBB 16 1810 19 0xBB 19 2147483647
 

 Pada Langkah 3 dari solusi Anda mendefinisikan CTE yang disebut T2 berdasarkan kueri dari Langkah 2. Anda Kemudian bergabung dengan tabel T1 dengan baris pencocokan CTE T2 berdasarkan val dari T1 berada dalam interval [rendah, tinggi] di T2.
 

 Berikut kode yang mengimplementasikan langkah ini:
 
PILIH T1.keycol AS keycol1, T1.val AS val1, SUBSTRING(T1.othercols, 1, 1) AS othercols1, T2.keycol AS keycol2, T2.val AS val2, SUBSTRING(T2.othercols, 1, 1 ) AS othercols2FROM dbo.T1 INNER JOIN T2 PADA T1.val ANTARA T2.low DAN T2.high;
 

 Rencana solusi Radek dengan indeks pendukung ditunjukkan pada Gambar 7. 
 

 Gambar 7:Rencanakan solusi oleh Radek dengan indeks 
 

 Berikut adalah statistik kinerja untuk rencana ini:
 
waktu berjalan:10.6, CPU:7.63, pembacaan logis:3.193.125
 

 Rencana solusi Radek tanpa indeks pendukung ditunjukkan pada Gambar 8. 
 

 Gambar 8:Rencanakan solusi oleh Radek tanpa indeks 
 

 Berikut adalah statistik kinerja untuk rencana ini:
 
waktu berjalan:18.1, CPU:27,4, pembacaan logis:5.827.360
 

 Di sini perbedaan kinerja antara kedua rencana tersebut cukup besar. Denah pada Gambar 8 memerlukan penyortiran pendahuluan sebelum penghitungan nomor baris, yang tidak dilakukan pada denah pada Gambar 7. Lebih penting lagi, untuk mencocokkan setiap interval dengan masing-masing baris dari T1, rencana pada Gambar 8 membuat Spool Indeks pada dasarnya sebagai alternatif dari indeks yang hilang, sedangkan rencana pada Gambar 7 hanya menggunakan indeks idx_val_key yang ada di T1. Itulah alasan utama perbedaan besar di semua ukuran kinerja. Namun, kinerja tanpa indeks pendukung adalah wajar.
 
Variasi Kamil pada solusi Radek
 

 Kamil datang dengan variasi pada solusi Radek. Berikut kode solusi lengkapnya:
 
DENGAN T2_collapsed AS( SELECT keycol AS keycol2, val AS val2 , ROW_NUMBER() OVER (PARTITION BY val ORDER BY keycol) AS rn FROM dbo.T2),rentang AS( SELECT keycol2 AS prevkey, val2 AS prevval, LEAD( keycol2) OVER (ORDER BY val2) AS nxtkey, LEAD(val2) OVER (ORDER BY val2) AS nxtval FROM T2_collapsed WHERE rn =1),bestmatches AS( SELECT T1.keycol AS keycol1, T1.val AS val1, SUBSTRING(T1 .othercols, 1, 1) AS othercols1, CASE WHEN ABS(T1.val - prevval) <=ABS(T1.val - nxtval) THEN prevkey ELSE nxtkey END AS keycol2, CASE WHEN ABS(T1.val - prevval) <=ABS(T1.val - nxtval) THEN prevval ELSE nxtval END AS val2 FROM ranges INNER JOIN dbo.T1 ON prevval <=T1.val AND T1.val  

 Berikut deskripsi Kamil sendiri tentang solusi ini:
 

 This solution is close to Radek's idea of checking against low and high range, although the ranges are based purely on actual T2 values. We get each row and the lead values only for each row in collapsed T2 (first step always gets rid of duplicate keys if found, by using row number or min(keycol) grouped by val on t2). The key concepts are how to check low and high range not to get duplicates – lower range inclusive, higher range exclusive, as well as handling the outliers (if present) by creating a separate set looking at the lowest and max values in T2 (UNION ALL bit). The check against the max value is done with inclusive range to complement the case of T1 vals being equal to the top T2 vals.
 

 The plan for Kamil’s variation on Radek’s solution with supporting indexes is shown in Figure 9.
 

 Figure 9:Plan for Kamil’s variation on Radek’s solution with indexes 
 

 Here are the performance stats for this plan:
 
run time:8.59, CPU:8.5, logical reads:3,206,849
 

 The plan for Kamil’s variation on Radek’s solution without supporting indexes is shown in Figure 10.
 

 Figure 10:Plan for Kamil’s variation on Radek’s solution without indexes 
 

 Here are the performance stats for this plan:
 
run time:14, CPU:24.5, logical reads:5,870,596
 

 The plan in Figure 9 is serial and most of the calculations are done based on preordered data obtained from the supporting indexes. The plan in Figure 10 is parallel, plus there are a few sorts, and even an index spool activity. The performance measures of the latter plan are substantially higher than the former plan, but the performance in both cases is reasonable.
 
Solution 2 by Kamil Kosno – Using ranking, offset and aggregate window functions
 

 Kamil came up with another original approach that is based on a combination of ranking, offset and aggregate window functions. Berikut kode solusi lengkapnya:
 
WITH A AS( SELECT 1 AS t, keycol,val, DENSE_RANK() OVER(ORDER BY val) AS rnk FROM dbo.T1 UNION ALL SELECT NULL, MIN(keycol), val, 0 FROM dbo.T2 GROUP BY val),B AS( SELECT t, keycol, val, CASE WHEN t =1 THEN DENSE_RANK() OVER (ORDER BY val, t) - rnk ELSE 0 END AS grp, LAG(CASE WHEN t IS NULL THEN val END) OVER(ORDER BY val, t) AS prev, LAG(CASE WHEN t IS NULL THEN keycol END) OVER(ORDER BY val, t) AS prevkey, LEAD(CASE WHEN t IS NULL THEN val END) OVER(ORDER BY val, t) AS nxt, LEAD(CASE WHEN t IS NULL THEN keycol END) OVER(ORDER BY val, t) AS nxtkey FROM A),C AS( SELECT keycol AS keycol1, val AS val1, MAX (prev) OVER(PARTITION BY grp ORDER BY prev DESC ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW) AS mxprev, MAX (prevkey) OVER(PARTITION BY grp ORDER BY prev DESC ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW) AS mxprevkey, MAX (nxt) OVER(PARTITION BY grp ORDER BY nxt ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING) AS mxnxt, MAX (nxtkey) OVER(PARTITION BY grp ORDER BY nxt ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING) AS mxnxtkey FROM B WHERE t =1),D AS( SELECT keycol1, val1, CASE WHEN ABS(val1 - mxprev) <=ISNULL(ABS(val1 - mxnxt), mxprev) THEN mxprevkey ELSE mxnxtkey END AS keycol2, CASE WHEN ABS(val1 - mxprev) <=ISNULL(ABS(val1 - mxnxt), mxprev) THEN mxprev ELSE mxnxt END AS val2 FROM C)SELECT D.keycol1, D.val1, D.keycol2, D.val2, SUBSTRING(T1.othercols, 1, 1) AS othercols1, SUBSTRING(T2.othercols, 1, 1) AS othercols2FROM D INNER JOIN dbo.T1 ON T1.keycol =D.keycol1 INNER JOIN dbo.T2 ON T2.keycol =D.keycol2;
 

 In Step 1 of the solution you unify the following result sets:
 
 
 Rows from T1 with a result column called t assigned with the constant 1 and column rnk representing dense rank values ordered by val 
 
 Group rows from T2 by val and return val and min keycol for each group, with the result column t assigned with NULL and rnk with 0 
 
 

 Berikut kode yang mengimplementasikan langkah ini:
 
SELECT 1 AS t, keycol,val, DENSE_RANK() OVER(ORDER BY val) AS rnkFROM dbo.T1UNION ALLSELECT NULL, MIN(keycol), val, 0FROM dbo.T2GROUP BY val;
 

 Kode ini menghasilkan output berikut:
 
t keycol val rnk----------- ----------- ----------- --------------------1 1 1 11 2 1 11 3 3 21 4 3 21 5 5 31 6 8 41 7 13 51 8 16 61 9 18 71 10 20 81 11 21 9NULL 1 2 0NULL 4 3 0NULL 3 7 0NULL 6 11 0NULL 8 13 0NULL 9 17 0NULL 10 19 0
 

 In Step 2 of the solution you define a CTE called A based on the query from Step 1. You query A and compute group identifiers (grp) for T1 values that fall between ranges of distinct T2 values. This is done using an islands technique where you subtract rnk (dense ranks for only T1 values) from rnk2 (dense ranks for unified T1 values and distinct T2 values).
 

 Using the LAG and LEAD functions, you compute for each T1 row the prev/next val and keycol values from T2, if present, and NULL otherwise. These calculations return values for the first and last rows in each group, if present, but NULLs for intermediate rows in groups.
 

 Berikut kode yang mengimplementasikan langkah ini:
 
SELECT t, keycol, val, rnk, DENSE_RANK() OVER (ORDER BY val) AS rnk2, CASE WHEN t =1 THEN DENSE_RANK() OVER (ORDER BY val, t) - rnk ELSE 0 END AS grp, LAG(CASE WHEN t IS NULL THEN val END) OVER(ORDER BY val, t) AS prev, LAG(CASE WHEN t IS NULL THEN keycol END) OVER(ORDER BY val, t) AS prevkey, LEAD(CASE WHEN t IS NULL THEN val END) OVER(ORDER BY val, t) AS nxt, LEAD(CASE WHEN t IS NULL THEN keycol END) OVER(ORDER BY val, t) AS nxtkeyFROM A;
 

 Kode ini menghasilkan output berikut:
 
t keycol val rnk rnk2 grp prev prevkey nxt nxtkey----- ------ --- --- ---- --- ----- ------- ----- -------1 1 1 1 1 0 NULL NULL NULL NULL1 2 1 1 1 0 NULL NULL 2 1NULL 1 2 0 2 0 NULL NULL 3 4NULL 4 3 0 3 0 2 1 NULL NULL1 3 3 2 3 2 3 4 NULL NULL1 4 3 2 3 2 NULL NULL NULL NULL1 5 5 3 4 2 NULL NULL 7 3NULL 3 7 0 5 0 NULL NULL NULL NULL1 6 8 4 6 3 7 3 11 6NULL 6 11 0 7 0 NULL NULL 13 8NULL 8 13 0 8 0 11 6 NULL NULL1 7 13 5 8 5 13 8 NULL NULL1 8 16 6 9 5 NULL NULL 17 9NULL 9 17 0 10 0 NULL NULL NULL NULL1 9 18 7 11 6 17 9 19 10NULL 10 19 0 12 0 NULL NULL NULL NULL1 10 20 8 13 7 19 10 NULL NULL1 11 21 9 14 7 NULL NULL NULL NULL
 

 In Step 3 you define a CTE called B based on the query from Step 2. You Query B and filter only original T1 rows (where t =1). In each group, you return the first row's prev and prevkey values, and last row's nxt and nxtkey values. Instead of just using a window partition clause, a window frame specification is used to define the minimal frame with the desired row to reduce I/O against the spool.
 

 Berikut kode yang mengimplementasikan langkah ini:
 
SELECT keycol AS keycol1, val AS val1, MAX (prev) OVER(PARTITION BY grp ORDER BY prev DESC ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW) AS mxprev, MAX (prevkey) OVER(PARTITION BY grp ORDER BY prev DESC ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW) AS mxprevkey, MAX (nxt) OVER(PARTITION BY grp ORDER BY nxt ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING) AS mxnxt, MAX (nxtkey) OVER(PARTITION BY grp ORDER BY nxt ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING) AS mxnxtkeyFROM BWHERE t =1;
 

 Kode ini menghasilkan output berikut:
 
keycol1 val1 mxprev mxprevkey mxnxt mxnxtkey----------- ----------- ----------- ----------- ----------- -----------2 1 NULL NULL 2 11 1 NULL NULL 2 15 5 3 4 7 33 3 3 4 7 34 3 3 4 7 36 8 7 3 11 68 16 13 8 17 97 13 13 8 17 99 18 17 9 19 1010 20 19 10 NULL NULL11 21 19 10 NULL NULL
 

 In Step 4 you define a CTE called C based on the query from Step 3. You query C to compute keycol2 and val2 based on the closest match.
 

 Berikut kode yang mengimplementasikan langkah ini:
 
SELECT keycol1, val1, CASE WHEN ABS(val1 - mxprev) <=ISNULL(ABS(val1 - mxnxt), mxprev) THEN mxprevkey ELSE mxnxtkey END AS keycol2, CASE WHEN ABS(val1 - mxprev) <=ISNULL(ABS(val1 - mxnxt), mxprev) THEN mxprev ELSE mxnxt END AS val2FROM C;
 

 Kode ini menghasilkan output berikut:
 
keycol1 val1 keycol2 val2----------- ----------- ----------- -----------2 1 1 21 1 1 25 5 4 33 3 4 34 3 4 36 8 3 78 16 9 177 13 8 139 18 9 1710 20 10 1911 21 10 19
 

 In Step 5 you define a CTE called D based on the query from Step 4. You then join D with T1 and T2 to get the other needed columns.
 

 Berikut kode yang mengimplementasikan langkah ini:
 
SELECT D.keycol1, D.val1, D.keycol2, D.val2, SUBSTRING(T1.othercols, 1, 1) AS othercols1, SUBSTRING(T2.othercols, 1, 1) AS othercols2FROM D INNER JOIN dbo.T1 ON T1.keycol =D.keycol1 INNER JOIN dbo.T2 ON T2.keycol =D.keycol2;
 

 The plan for solution 2 by Kamil with supporting indexes is shown in Figure 11.
 

 Figure 11:Plan for solution 2 by Kamil with indexes 
 

 Here are the performance stats for this plan:
 
run time:18.1, CPU:34.4, logical reads:56,736
 

 The plan for solution 2 by Kamil without supporting indexes is shown in Figure 12.
 

 Figure 12:Plan for solution 2 by Kamil without indexes 
 

 Here are the performance stats for this plan:
 
run time:20.3, CPU:38.9, logical reads:59,012
 

 As you can see, the Plan in Figure 12 involves a couple of extra sorts compared to the plan in Figure 1 to order the data for the two queries in the CTE A—one to support the dense rank calculation and the other to support the grouped query. Other than that, the rest of the work is similar in both. In the grand scheme of things, there’s a bit of extra CPU work and consequentially time penalty, but still both queries perform fairly reasonably.
 
Kesimpulan
 

 This article concludes the series on the closest match challenge. It’s great to see the different creative ideas that Kamil, Alejandro and Radek came up with. Thanks to all of you for sending your solutions!