最も近い試合、パート3

Closest Match、パート1では、RBCのジュニア債券アナリストであるKarenLyから提供されたT-SQLチャレンジについて説明しました。課題には、T1とT2の2つのテーブルが含まれ、それぞれにキー列（keycol）、値（val）、およびその他の列（othercolsと呼ばれる列で表される）があります。タスクは、タイブレーカーとして最小のT2.keycol値を使用して、T1からの各行にT2.valがT1.valに最も近い（絶対差が最小の最小である）T2からの行を照合することでした。いくつかのリレーショナルソリューションを提供し、それらのパフォーマンス特性について説明しました。また、サポートインデックスの作成が許可されていない、または作成できない場合に、合理的に実行できるソリューションを見つけるように挑戦しました。パート2では、反復ソリューションを使用してこれを実現する方法を示しました。 Kamil Konsno、Alejandro Mesa、Radek Celuchからいくつかの非常に興味深いリーダーソリューションを入手しました。これらのソリューションは、今月の記事の焦点です。

サンプルデータ

念のため、サンプルデータの大小両方のセットを提供しました。ソリューションの有効性をチェックするための小さなセットと、そのパフォーマンスをチェックするための大きなセット。次のコードを使用して、サンプルデータベースtestdbを作成し、その中にサンプルテーブルT1およびT2を作成します。

-サンプルdbSETNOCOUNTON; IF DB_ID（'testdb'）IS NULL CREATE DATABASE testdb; GO USEtestdb;GO-サンプルテーブルT1およびT2DROPTABLEIF 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））; 

次のコードを使用して、テーブルにサンプルデータの小さなセットを入力します。

-T1とT2にサンプルデータの小さなセットを入力しますTRUNCATETABLEdbo.T1; TRUNCATE TABLE dbo.T2; INSERT INTO dbo.T1（val）VALUES（1）、（1）、（3）、（3）、（5）、（8）、（13）、（16）、（18）、（20）、（ 21）; INSERT INTO dbo.T2（val）VALUES（2）、（2）、（7）、（3）、（3）、（11）、（11）、（13）、（17）、（19）; 

さまざまなソリューションのロジックを説明するときにサンプルデータの小さなセットを使用し、ソリューションのステップの中間結果セットを提供します。

次のコードを使用して、ヘルパー関数GetNumsを作成します 大量のサンプルデータをテーブルに入力するには：

-整数のシーケンスを生成するヘルパー関数DROPFUNCTIONIF EXISTS dbo.GetNums; GO CREATE OR ALTER FUNCTION dbo.GetNums（@low AS BIGINT、@high AS BIGINT）RETURNS TABLEASRETURN WITH 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（SELECT 1 AS c FROM L1 AS A CROSS JOIN L1 AS B）、L3 AS（SELECT 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; GO --T1とT2に大量のサンプルデータを入力しますDECLARE@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; 

サポートするインデックスを使用してソリューションをテストする場合は、次のコードを使用してこれらのインデックスを作成します。

 CREATE INDEX idx_val_key ON dbo.T1（val、keycol）INCLUDE（othercols）; CREATE INDEX idx_val_key ON dbo.T2（val、keycol）INCLUDE（othercols）; CREATE INDEX idx_valD_key ON dbo.T2（val DESC、keycol） INCLUDE（othercols）; 

インデックスをサポートせずにソリューションをテストする場合は、次のコードを使用してこれらのインデックスを削除します。

 DROP INDEX IF EXISTS idx_val_key ON dbo.T1; DROP INDEX IF EXISTS idx_val_key ON dbo.T2; DROP INDEX IF EXISTS idx_valD_key ON dbo.T2; 

Kamil Kosnoによるソリューション1–一時テーブルの使用

Kamil Kosnoは、いくつかを提出しました。2つは彼のオリジナルのアイデアで、2つはAlejandroとRadekのソリューションのバリエーションです。カミルの最初のソリューションは、インデックス付きの一時テーブルを使用します。多くの場合、元のテーブルにサポートインデックスを作成することが許可されていない場合でも、一時テーブルを操作でき、一時テーブルを使用すると、いつでも独自のインデックスを作成できます。

完全なソリューションのコードは次のとおりです。

 DROP TABLE IF EXISTS＃T2; SELECT MIN（keycol）AS keycol、valINTO＃T2FROM dbo.T2GROUP BY val; CREATE UNIQUE INDEX 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） 

 ソリューションのステップ1では、一意の各valの最小キーコルを＃T2という一時テーブルに格納し、（val、keycol）にサポートインデックスを作成します。この手順を実装するコードは次のとおりです。
 
 DROP TABLE IF EXISTS＃T2; SELECT MIN（keycol）AS keycol、valINTO＃T2FROM dbo.T2GROUP BY val; CREATE UNIQUE INDEX idx_nc_val_key ON＃T2（val、keycol）; SELECT * FROM＃T2; 
 

 一時テーブルには、次のデータが入力されます。
 
 keycol val ----------- ---------- 1 24 33 76118139 1710 19 
 

 ソリューションのステップ2では、以下を適用します。
 

 T1の各行について、＃T2からprev値とnxt値を計算します。 prevを＃T2の最大値として計算します。これはT1の値以下です。 nxtを＃T2の最小値として計算します。これはT1の値以上です。
 

 CASE式を使用して、次のロジックに基づいてval2を計算します。
 
 
 prevまたはnxtがnullの場合、2つのうち最初の非nullを返します。両方がNULLの場合は、NULLを返します。 
 
 valとprevの絶対差がvalとnxtの絶対差よりも小さい場合は、prevを返します。 
 
 valとnxtの絶対差がvalとprvの絶対差よりも小さい場合は、nxtを返します。 
 
それ以外の場合、nxtがprevより小さい場合は、nxtを返します。それ以外の場合は、prevを返します。 
 
 

 この手順を実装するコードは次のとおりです。
 
 SELECT keycol AS keycol1、val AS val1、othercols AS othercols1、CASE WHEN（prev + nxt IS NULL）THEN COALESCE（prev、nxt）WHEN ABS（val-prev） 

 このコードは次の出力を生成します：
 
 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 
 

 ソリューションのステップ3では、ステップ2のクエリに基づいてbestvalsと呼ばれるCTEを定義します。次に、bestvalsを＃T2と結合してキーを取得し、結果をT2と結合して残りのデータ（othercols）を取得します。
 

 この手順を実装するコードは次のとおりです。
 
 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 JOIN dbo.T2 ON T2.keycol =tempT2.keycol; 
 

 カミルによるソリューション1の計画with サポートするインデックスを図1に示します。
 

  図1：インデックスを使用したKamilによるソリューション1の計画 
 

 プランの最初のブランチは、T2からのデータをグループ化して集約し、その結果を一時テーブル＃T2に書き込みます。このブランチは、T2のインデックスidx_valD_keyの順序付けられたスキャンに依存する事前に順序付けられたStreamAggregateアルゴリズムを使用していることに注意してください。
 

 このプランのパフォーマンス統計は次のとおりです。
 
実行時間（秒）：5.55、CPU（秒）：16.6、論理読み取り：6,687,172 
 

 インデックスをサポートしないKamilによるソリューション1の計画を図2に示します。
 

  図2：インデックスなしのKamilによるソリューション1の計画 
 

 このプランと前のプランの主な違いは、ステップ1でグループ化と集計の部分を処理するプランの最初のブランチは、今回はサポートインデックスから事前に順序付けられたデータをプルできないため、クラスター化されたものから順序付けられていないデータをプルすることです。 T2でインデックスを作成し、HashAggregateアルゴリズムを使用します。
 

 このプランのパフォーマンス統計は次のとおりです。
 
実行時間：6.44、CPU：19.3、論理読み取り：6,688,277 
 
 Alejandro Mesaによる解決策–最後の非ヌル手法を使用
 

 Alejandroのソリューションは、ここで説明する最後のnull以外の手法を使用しています。
 

 完全なソリューションのコードは次のとおりです（他の列を返さずにここで提供されます）：
 
 WITH 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 ROWS BETWEEN UNBOUNDED PRECEDING AND 1 PRECEDING）ASbelow_binstr、MIN（CASE WHEN tid =0 THEN CAST（val AS binary（4））+ CAST（keycol AS binary（4））END）OVER（ORDER BY val、tid、 keycol ROWS BETWEEN 1 FOLLOWING AND UNBOUNDED FOLLOWING）AS above_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（below_binstr、1、4）AS int）ASbelow_T2_val、CAST（SUBSTRING（below_binstr、5、4）AS int）ASbelow_T2_keycol、CAST（SUBSTRING（above_binstr、1、 4）AS int）AS above_T2_val、CAST（SUBSTRING（above_binstr、5、4）AS int）AS above_T2_keycol FROM R1 WHERE tid =1）、R3 AS（SELECT keycol、val、COALESCE（below_T2_val、above_T2 _val）ASbelow_T2_val、COALESCE（below_T2_keycol、above_T2_keycol）ASbelow_T2_keycol、COALESCE（above_T2_val、below_T2_val）ASabove_T2_val、COALESCE（above_T2_keycol、below_T2_keycol）ASabove_T2 ）<=ABS（above_T2_val --val）THENbelow_T2_keycol ELSE above_T2_keycol END AS keycol2、CASE WHEN ABS（val--below_T2_val）<=ABS（above_T2_val--val）THENbelow_T2_val ELSEabove_T2_val END AS val2FROM; 

 ソリューションのステップ1では、T1の行（tidという結果列を1に割り当てる）とT2の行（tid =0を割り当てる）を統合し、結果に基づいてTという派生テーブルを定義します。現在の各行のval、tid、keycolの順序に基づいて、最後の非null手法を使用して、below_binstrというバイナリ列に連結された最後のtid=0行の値を取得します。同様に、above_binstrというバイナリ列に連結された次のtid=0行の値を取得します。
 

 この手順を実装するコードは次のとおりです。
 
 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 ROWS BETWEEN UNBOUNDED PRECEDING AND 1 PRECEDING）ASbelow_binstr、MIN（CASE WHEN tid =0 THEN CAST（val AS binary（4））+ CAST（keycol AS binary（4））END）OVER（ORDER BY val、tid、keycol ROWS BETWEEN 1 FOLLOWING AND 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; 
 

 このコードは次の出力を生成します：
 
 keycol val tidbelow_binstrabove_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 0x0000000B00000006 0x00000011000000097 13 1 0x0000000D000000 08 0x00000011000000098 16 1 0x0000000D00000008 0x00000011000000099 17 0 0x0000000D00000008 0x000000130000000A9 18 1 0x0000001100000009 0x000000130000000A10 19 0 0x0000001100000009 NULL10 20 1 0x000000130000000A NULL11 21 1 0x000000130000000A NULL 
 

 ソリューションのステップ2では、ステップ1のクエリに基づいてR1というCTEを定義します。R1にクエリを実行し、tid =1の行のみをフィルタリングし、連結されたバイナリ文字列から個々の値を抽出します。
 

 この手順を実装するコードは次のとおりです。
 
 SELECT keycol、val、CAST（SUBSTRING（below_binstr、1、4）AS int）ASbelow_T2_val、CAST（SUBSTRING（below_binstr、5、4）AS int）ASbelow_T2_keycol、CAST（SUBSTRING（above_binstr、1、4） AS int）AS above_T2_val、CAST（SUBSTRING（above_binstr、5、4）AS int）AS above_T2_keycolFROM R1WHERE tid =1; 
 

 このコードは次の出力を生成します：
 
 keycol valbelow_T2_valbelow_T2_keycolabove_T2_valabove_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 
 

 ソリューションのステップ3では、ステップ2のクエリに基づいてR2というCTEを定義します。次に、次の結果列を計算します。
 
 
below_T2_val：below_T2_valとabove_T2_valの間の最初の非ヌル
 
below_T2_keycol：below_T2_keycolとabove_T2_keycolの間の最初の非ヌル
 
 above_T2_val：above_T2_valとbelow_T2_valの間の最初の非ヌル
 
 above_T2_keycol：above_T2_keycolとbelow_T2_keycolの間の最初の非ヌル
 
 

 この手順を実装するコードは次のとおりです。
 
 SELECT keycol、val、COALESCE（below_T2_val、above_T2_val）ASbelow_T2_val、COALESCE（below_T2_keycol、above_T2_keycol）ASbelow_T2_keycol、COALESCE（above_T2_val、below_T2_val）ASabove_T2_val）ASabove_T2_val、COA 

 このコードは次の出力を生成します：
 
 keycol valbelow_T2_valbelow_T2_keycolabove_T2_valabove_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 
 

 ソリューションのステップ4では、ステップ3のクエリに基づいてR3というCTEを定義します。T1_keycolとしてエイリアスされたkeycolとT1_valとしてエイリアスされたvalを返します。結果列T2_keycolを次のように計算します。valとbelow_T2_valの絶対差がabove_T2_valとvalの絶対差以下の場合は、below_T2_keycolを返し、それ以外の場合はabove_T2_keycolを返します。結果列T2_valを次のように計算します。valとbelow_T2_valの絶対差がabove_T2_valとvalの絶対差以下の場合は、below_T2_valを返し、それ以外の場合はabove_T2_valを返します。
 

 この手順を実装するコードは次のとおりです。
 
 SELECT keycol AS keycol1、val AS val1、CASE WHEN ABS（val-below_T2_val）<=ABS（above_T2_val --val）THENbelow_T2_keycol ELSE above_T2_keycol END AS keycol2、CASE WHEN ABS（val-below_T2_val）<=ABS（above_T2_val val）THENbelow_T2_val ELSEabove_T2_val END AS val2FROM R3; 
 

 インデックスをサポートするAlejandroのソリューションの計画を図3に示します。
 

  図3：インデックスを使用したAlejandroによるソリューションの計画 
 

 このプランのパフォーマンス統計は次のとおりです。
 
実行時間：7.8、CPU：12.6、論理読み取り：35,886 
 

 インデックスをサポートしないAlejandroのソリューションの計画を図4に示します。
 

  図4：インデックスなしのAlejandroによるソリューションの計画 
 

 このプランのパフォーマンス統計は次のとおりです。
 
実行時間：8.19、CPU：14.8、論理読み取り：37,091 
 

 図4のプランの最初の2つのブランチには、サポートするインデックスがないため、マージ結合（連結）演算子の前に2つのソートがあることに注意してください。図3の計画では、サポートするインデックスからデータが事前に並べ替えられて取得されるため、これらの並べ替えは必要ありません。
 
Alejandroのソリューションに対するKamilのバリエーション
 

 このソリューションでは、Kamilも最後の非ヌル手法に依存していました。完全なソリューションのコードは次のとおりです。
 
 WITH all_vals AS（SELECT keycol、val FROM dbo.T1 UNION ALL SELECT DISTINCT NULL、val FROM dbo.T2）、ranges AS（SELECT keycol、val、MAX（CASE WHEN keycol IS NULL THEN val END）OVER（ORDER BY val、keycol ROWS BETWEEN UNBOUNDED PRECEDING AND 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）AS nxt FROM all_vals）、matched_vals AS 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 matches_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; 
 

 ソリューションのステップ1では、all_valsおよびrangesと呼ばれるCTEを定義します。ここでは、最後の非null手法を使用して、T2（prev）およびabove（nxt）の値のT1（keycolがNULLではない）範囲の各値を識別します。ここで、keycolはnullです。
 

 この手順を実装するコードは次のとおりです。
 
 WITH all_vals AS（SELECT keycol、val FROM dbo.T1 UNION ALL SELECT DISTINCT NULL、val FROM dbo.T2）、ranges AS（SELECT keycol、val、MAX（CASE WHEN keycol IS NULL THEN val END）OVER（ORDER BY val、keycol ROWS BETWEEN UNBOUNDED PRECEDING AND 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）AS nxt FROM all_vals）SELECT * FROM range; 
 

 このコードは次の出力を生成します：
 
 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 3116 8 7 11NULL 11 7 13NULL 13 11177 13 13178 16 13 17NULL 17 13199 18 17 19NULL 19 17 NULL10 20 19 NULL11 21 19 NULL 
 

 ソリューションのステップ2では、CTE範囲を照会し、keycolがnullでない行のみをフィルター処理します。 T1からkeycol列とval列をそれぞれkeycol1とval1として返します。次に、prevとnxtの間に、val1に最も近いものをval2として返します。
 

 この手順を実装するコードは次のとおりです。
 
 SELECT keycol AS keycol1、val AS val1、CASE WHEN ABS（val --prev）<=ISNULL（ABS（val --nxt）、prev）THEN prev ELSE nxt END AS val2FROM rangeWHERE keycol IS NOT NULL; 
 

 このコードは次の出力を生成します：
 
 keycol1 val1 val2 ----------- ----------- -----------1 1 22 1 23 3 34 3 35 5 36 8 77 13138 16179 18 1710 20 1911 21 19 
 

 ソリューションのステップ3では、ステップ2のクエリに基づいてmatched_valsというCTEを定義します。また、T2という派生テーブルを定義します。ここで、パーティション化された行番号を使用して、dbo.T2からの行のタイブレークロジックを処理します。次に、matched_vals、CTE T2、およびテーブルT1を結合して、最終的なマッチングロジックを処理します。
 

 この手順を実装するコードは次のとおりです。
 
 SELECT keycol1、val1、SUBSTRING（T1.othercols、1、1）AS othercols1、val2、T2.keycol AS keycol2、SUBSTRING（T2.othercols、1、1）AS othercols2 FROM matches_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; 
 

 インデックスをサポートするAlejandroのソリューションに対するKamilのバリエーションの計画を図5に示します。
 

  図5：インデックスを使用したAlejandroのソリューションでのKamilのバリエーションの計画 
 

 このプランのパフォーマンス統計は次のとおりです。
 
実行時間：11.5、CPU：18.3、論理読み取り：59,218 
 

 インデックスをサポートしないAlejandroのソリューションに対するKamilのバリエーションの計画を図6に示します。
 

  図6：インデックスなしのAlejandroのソリューションでのKamilのバリエーションの計画 
 

 このプランのパフォーマンス統計は次のとおりです。
 
実行時間：12.6、CPU：23.5、論理読み取り：61,432 
 

 Alejandroのソリューションの計画と同様に、この場合も、データはサポートインデックスから事前に順序付けられて取得されるため、図5の計画では、マージ結合（連結）演算子を適用する前に明示的な並べ替えは必要ありません。図6の計画ではサポートするインデックスがないため、明示的な並べ替えが必要です。
 
 Radek Celuchによるソリューション–間隔を使用
 

 Radekはシンプルで美しいアイデアを思いつきました。 T2.valの個別の値ごとに、現在のT2.valと一致するT1.valからの値の範囲を表す間隔を計算します。 
 

 完全なソリューションのコードは次のとおりです。
 
 WITH 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 --prev）％2）、0）AS low、ISNULL（val +（next --val）/ 2、2147483647）AS high FROM Pre2）SELECT 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 ON T1.val BETWEEN T2.low AND T2.high; 
 

 ソリューションのステップ1では、T2にクエリを実行し、行番号（列rnと呼びます）を計算し、valで分割し、keycolで並べ替えます。このクエリに基づいて、Pre1というCTEを定義します。次に、Pre1にクエリを実行し、rn =1の行のみをフィルタリングします。同じクエリで、LAGとLEADを使用して、各行について、前の行（prevと呼びます）と次の行（prevと呼びます）のval列の値を返します。次にそれを呼び出します。
 

 この手順を実装するコードは次のとおりです。
 
 WITH 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; 
 

 このコードは次の出力を生成します：
 
 keycol val othercols prev next ------- ---- ---------- ----------- ---------- -1 2 0xBB NULL 34 3 0xBB 2 73 7 0xBB 3116 11 0xBB 7138 13 0xBB 11179 17 0xBB 13 1910 19 0xBB 17 NULL 
 

 ソリューションのステップ2では、ステップ1のクエリに基づいてPre2というCTEを定義します。Pre2にクエリを実行し、各行について、T1からのvalが含まれる間隔[low、high]を計算します。高：
 
 
 low =ISNULL（val –（val – prev）/ 2 +（1 –（val – prev）％2）、0）
 
 high =ISNULL（val +（next – val）/ 2、2147483647）
 
 

 下限の計算に関するmod2チェックは、下限のT2.val要件を満たすために使用され、行番号フィルターは、下限のT2.keycol要件を満たすために使用されます。値0と2147483647は、極端な下限と上限として使用されます。
 

 この手順を実装するコードは次のとおりです。
 
 SELECT keycol、val、othercols、ISNULL（val-（val --prev）/ 2 +（1-（val --prev）％2）、0）AS low、ISNULL（val +（next --val）/ 2 、2147483647）AS highFROM Pre2; 
 

 このコードは次の出力を生成します：
 
 keycol val othercols low high ------- ---- ---------- ---- -----------1 2 0xBB 0 24 3 0xBB 3 53 7 0xBB 6 96 11 0xBB 10128 13 0xBB 13159 17 0xBB 16 1810 19 0xBB 19 2147483647 
 

 ソリューションのステップ3では、ステップ2のクエリに基づいてT2というCTEを定義します。次に、テーブルT1を、T2の間隔[low、high]内にあるT1からのvalに基づくCTET2一致行と結合します。
 

 この手順を実装するコードは次のとおりです。
 
 SELECT 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 ON T1.val BETWEENT2.low AND T2.high; 
 

 インデックスをサポートするRadekのソリューションの計画を図7に示します。
 

  図7：インデックスを使用したRadekによるソリューションの計画 
 

 このプランのパフォーマンス統計は次のとおりです。
 
実行時間：10.6、CPU：7.63、論理読み取り：3,193,125 
 

 インデックスをサポートしないRadekのソリューションの計画を図8に示します。
 

  図8：インデックスなしのRadekによるソリューションの計画 
 

 このプランのパフォーマンス統計は次のとおりです。
 
実行時間：18.1、CPU：27.4、論理読み取り：5,827,360 
 

 ここでは、2つのプランのパフォーマンスの違いはかなりのものです。図8の計画では、行番号を計算する前に予備的な並べ替えが必要ですが、図7の計画では必要ありません。さらに重要なことに、各間隔をT1のそれぞれの行と一致させるために、図8のプランは、欠落しているインデックスの代替として基本的にインデックススプールを作成しますが、図7のプランは、T1の既存のインデックスidx_val_keyを使用します。これが、すべてのパフォーマンス測定値に大きな違いがある主な理由です。それでも、インデックスをサポートしない場合のパフォーマンスは妥当です。
 
Radekのソリューションに対するKamilのバリエーション
 

 カミルは、ラデクのソリューションのバリエーションを考え出しました。完全なソリューションのコードは次のとおりです。
 
 WITH T2_collapsed AS（SELECT keycol AS keycol2、val AS val2、ROW_NUMBER（）OVER（PARTITION BY val ORDER BY keycol）AS rn FROM dbo.T2）、ranges 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  

 Here’s Kamil’s own description of this solution:
 

 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. Here’s the complete solution’s code:
 
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 
 
 

 Here’s the code implementing this step:
 
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;
 

 This code generates the following output:
 
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.
 

 Here’s the code implementing this step:
 
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;
 

 This code generates the following output:
 
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.
 

 Here’s the code implementing this step:
 
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;
 

 This code generates the following output:
 
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.
 

 Here’s the code implementing this step:
 
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;
 

 This code generates the following output:
 
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.
 

 Here’s the code implementing this step:
 
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.
 
結論
 

 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!