Nächstes Spiel, Teil 3

In Closest Match, Part 1, habe ich eine T-SQL-Herausforderung behandelt, die mir von Karen Ly, Jr. Fixed Income Analyst bei RBC, zur Verfügung gestellt wurde. Die Herausforderung umfasste zwei Tabellen – T1 und T2, jede mit einer Schlüsselspalte (keycol), einem Wert (val) und einigen anderen Spalten (dargestellt durch eine Spalte namens othercols). Die Aufgabe bestand darin, jeder Zeile von T1 die Zeile von T2 zuzuordnen, in der T2.val am nächsten zu T1.val liegt (die absolute Differenz ist die niedrigste, niedrigste), wobei der niedrigste T2.keycol-Wert als Tiebreaker verwendet wurde. Ich habe ein paar relationale Lösungen bereitgestellt und ihre Leistungsmerkmale besprochen. Ich habe Sie auch aufgefordert, in Fällen, in denen Sie keine unterstützenden Indizes erstellen dürfen/können, eine vernünftig funktionierende Lösung zu finden. In Teil 2 habe ich gezeigt, wie dies durch iterative Lösungen erreicht werden kann. Ich habe mehrere sehr interessante Reader-Lösungen von Kamil Konsno, Alejandro Mesa und Radek Celuch erhalten, und diese Lösungen stehen im Mittelpunkt des Artikels dieses Monats.

Beispieldaten

Zur Erinnerung:Ich habe sowohl kleine als auch große Beispieldatensätze bereitgestellt, mit denen Sie arbeiten können. Kleine Sätze, um die Gültigkeit Ihrer Lösung zu überprüfen, und große Sätze, um ihre Leistung zu überprüfen. Verwenden Sie den folgenden Code, um die Beispieldatenbank testdb und darin die Beispieltabellen T1 und T2 zu erstellen:

-- Beispiel dbSET NOCOUNT ON; IF DB_ID('testdb') IST NULL CREATE DATABASE testdb;GO USE testdb;GO -- Beispieltabellen T1 und 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));

Verwenden Sie den folgenden Code, um die Tabellen mit kleinen Sätzen von Beispieldaten zu füllen:

-- T1 und T2 mit kleinen Sätzen von Beispieldaten füllen TRUNCATE TABLE dbo.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);

Ich werde die kleinen Sätze von Beispieldaten verwenden, wenn ich die Logik der verschiedenen Lösungen beschreibe, und Zwischenergebnissätze für die Lösungsschritte bereitstellen.

Verwenden Sie den folgenden Code, um die Hilfsfunktion GetNums zu erstellen und um die Tabellen mit großen Sätzen von Beispieldaten zu füllen:

--Hilfsfunktion zum Generieren einer Folge von ganzen Zahlen FUNKTION DROPFEN, WENN VORHANDEN 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 VON L2 ALS CROSS JOIN L2 AS B), L4 AS (SELECT 1 AS c VON L3 ALS CROSS JOIN L3 AS B), L5 AS (SELECT 1 AS c VON L4 ALS 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 und T2 mit großen Sätzen von Beispieldaten füllen DECLARE @numrowsT1 AS INT =1000000, @maxvalT1 AS INT =10000000, @numrowsT2 AS INT =1000000, @maxvalT2 AS INT =10000000; KÜRZE TABELLE dbo.T1; KÜRZE TABELLE 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;

Wenn Sie Ihre Lösung mit unterstützenden Indizes testen möchten, verwenden Sie den folgenden Code, um diese Indizes zu erstellen:

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);

Wenn Sie Ihre Lösung testen möchten, ohne Indizes zu unterstützen, verwenden Sie den folgenden Code, um diese Indizes zu entfernen:

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

Lösung 1 von Kamil Kosno – Verwenden einer temporären Tabelle

Kamil Kosno reichte ein paar ein – zwei mit seinen originellen Ideen und zwei Variationen von Alejandros und Radeks Lösungen. Kamils ​​erste Lösung verwendet eine indizierte temporäre Tabelle. Oft ist es so, dass Sie, auch wenn Sie keine unterstützenden Indizes auf den Originaltabellen erstellen dürfen, mit temporären Tabellen arbeiten dürfen, und mit temporären Tabellen können Sie immer Ihre eigenen Indizes erstellen.

Hier ist der Code der vollständigen Lösung:

DOP TABLE WENN VORHANDEN #T2; SELECT MIN(keycol) AS keycol, valINTO #T2FROM dbo.T2GROUP BY val; EINZIGARTIGEN INDEX ERSTELLEN 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)  

 In Schritt 1 der Lösung speichern Sie die minimale Schlüsselspalte für jeden eindeutigen Wert in einer temporären Tabelle namens #T2 und erstellen einen unterstützenden Index für (Wert, Schlüsselspalte). Hier ist der Code, der diesen Schritt implementiert:
 
DOP TABLE WENN VORHANDEN #T2; SELECT MIN(keycol) AS keycol, valINTO #T2FROM dbo.T2GROUP BY val; EINZIGARTIGEN INDEX ERSTELLEN idx_nc_val_key ON #T2(val, keycol); SELECT * FROM #T2;
 

 Die temporäre Tabelle wird mit den folgenden Daten gefüllt:
 
keycol val----------- ----------1 24 33 76 118 139 1710 19
 

 In Schritt 2 der Lösung wenden Sie Folgendes an:
 

 Berechnen Sie für jede Zeile in T1 prev- und nxt-Werte aus #T2. Berechnen Sie prev als den maximalen Wert in #T2, der kleiner oder gleich dem Wert in T1 ist. Berechnen Sie nxt als den Mindestwert in #T2, der größer oder gleich dem Wert in T1 ist.
 

 Verwenden Sie einen CASE-Ausdruck, um val2 basierend auf der folgenden Logik zu berechnen:
 
 
 Wenn prev oder nxt null ist, wird die erste Nichtnull der beiden zurückgegeben, oder NULL, wenn beide NULL sind. 
 
 Wenn die absolute Differenz zwischen val und prev kleiner als die absolute Differenz zwischen val und nxt ist, wird prev zurückgegeben. 
 
 Wenn die absolute Differenz zwischen val und nxt kleiner ist als die absolute Differenz zwischen val und prv, gib nxt zurück. 
 
 Andernfalls, wenn nxt kleiner als prev ist, gib nxt zurück, andernfalls gib prev zurück. 
 
 

 Hier ist der Code, der diesen Schritt implementiert:
 
SELECT keycol AS keycol1, val AS val1, othercols AS othercols1, CASE WHEN (prev + nxt IS NULL) THEN COALESCE(prev, nxt) WHEN ABS(val - prev)  

 Dieser Code generiert die folgende Ausgabe:
 
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
 

 In Schritt 3 der Lösung definieren Sie basierend auf der Abfrage aus Schritt 2 einen CTE namens bestvals. Sie verknüpfen dann Bestvals mit #T2, um die Schlüssel zu erhalten, und verknüpfen das Ergebnis mit T2, um den Rest der Daten (othercols) zu erhalten.
 

 Hier ist der Code, der diesen Schritt implementiert:
 
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;
 

 Der Plan für Lösung 1 von Kamil mit unterstützende Indizes sind in Abbildung 1 dargestellt.
 

 Abbildung 1:Plan für Lösung 1 von Kamil mit Indizes 
 

 Der erste Zweig des Plans gruppiert und aggregiert die Daten von T2 und schreibt das Ergebnis in die temporäre Tabelle #T2. Beachten Sie, dass dieser Zweig einen vorgeordneten Stream-Aggregate-Algorithmus verwendet, der auf einem geordneten Scan des Index idx_valD_key auf T2 basiert.
 

 Hier sind die Leistungsstatistiken für diesen Plan:
 
Laufzeit (Sek.):5,55, CPU (Sek.):16,6, logische Lesevorgänge:6.687.172
 

 Der Plan für Lösung 1 von Kamil ohne unterstützende Indizes ist in Abbildung 2 dargestellt.
 

 Abbildung 2:Plan für Lösung 1 von Kamil ohne Indizes 
 

 Der Hauptunterschied zwischen diesem Plan und dem vorherigen besteht darin, dass der erste Zweig des Plans, der den Gruppierungs- und Aggregationsteil in Schritt 1 handhabt, dieses Mal die vorgeordneten Daten nicht aus einem unterstützenden Index abrufen kann, sondern ungeordnet aus dem geclusterten Index auf T2 und verwendet dann einen Hash-Aggregate-Algorithmus.
 

 Hier sind die Leistungsstatistiken für diesen Plan:
 
Laufzeit:6,44, CPU:19,3, logische Lesevorgänge:6.688.277
 
Lösung von Alejandro Mesa – Verwendung der letzten Nicht-Null-Technik
 

 Alejandros Lösung verwendet die letzte hier beschriebene Nicht-Null-Technik.
 

 Hier ist der Code der vollständigen Lösung (hier bereitgestellt, ohne andere Cols zurückzugeben):
 
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 ) AS below_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) AS below_T2_val, CAST(SUBSTRING(below_binstr, 5, 4) AS int) AS below_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) AS below_T2_val, COALESCE(below_T2_keycol, above_T2_keycol) AS below_T2_keycol, COALESCE(above_T2_val, below_T2_val) AS above_T2_val, COALESCE(obove_T2_keycol, below_T2_keycol) AS above_T2_keycol FROM R2)SELECT keycol AS keycol1, val AS val1, val ABS_T2 CASE WENN ) <=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_val END AS val2FROM R3;
 

 In Schritt 1 der Lösung vereinheitlichen Sie die Zeilen aus T1 (Zuweisung einer Ergebnisspalte namens tid zu 1) mit den Zeilen aus T2 (Zuweisung von tid =0) und definieren basierend auf dem Ergebnis eine abgeleitete Tabelle namens T. Unter Verwendung der letzten Nicht-Null-Technik, basierend auf der Reihenfolge von val, tid, keycol, rufen Sie für jede aktuelle Zeile die Werte der letzten tid =0-Zeile ab, die in einer binären Spalte namens below_binstr verkettet sind. Auf ähnliche Weise rufen Sie die Werte der nächsten tid =0-Zeile ab, die zu einer binären Spalte namens above_binstr.
 verkettet sind 

 Hier ist der Code, der diesen Schritt implementiert:
 
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 ) AS below_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;
 

 Dieser Code generiert die folgende Ausgabe:
 
keycol val tid below_binstr above_binstr----------- ----------- ----------- --------- ---------- ---------------------- 1 1 1 NULL 0x00000002000000012 1 1 NULL 0x000000020000011 2 0 NULL 0X000000030000044 3 0 0X0000000200000001 0x000000070000033 3 1 0x0000030000040004 0x000007000000034 3 1 0x000003000004000400040007000000034 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
 

 In Schritt 2 der Lösung definieren Sie einen CTE namens R1 basierend auf der Abfrage aus Schritt 1. Sie fragen R1 ab, filtern nur Zeilen mit tid =1 und extrahieren die einzelnen Werte aus den verketteten Binärzeichenfolgen.
 

 Hier ist der Code, der diesen Schritt implementiert:
 
SELECT keycol, val, CAST(SUBSTRING(below_binstr, 1, 4) AS int) AS below_T2_val, CAST(SUBSTRING(below_binstr, 5, 4) AS int) AS below_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;
 

 Dieser Code generiert die folgende Ausgabe:
 
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
 

 In Schritt 3 der Lösung definieren Sie basierend auf der Abfrage aus Schritt 2 einen CTE namens R2. Anschließend berechnen Sie die folgenden Ergebnisspalten:
 
 
 below_T2_val:die erste Nichtnull zwischen below_T2_val und above_T2_val 
 
 below_T2_keycol:die erste Nichtnull zwischen below_T2_keycol und above_T2_keycol 
 
 above_T2_val:die erste Nichtnull zwischen above_T2_val und below_T2_val 
 
 above_T2_keycol:die erste Nichtnull zwischen above_T2_keycol und below_T2_keycol 
 
 

 Hier ist der Code, der diesen Schritt implementiert:
 
SELECT keycol, val, COALESCE(below_T2_val, above_T2_val) AS below_T2_val, COALESCE(below_T2_keycol, above_T2_keycol) AS below_T2_keycol, COALESCE(obove_T2_val, below_T2_val) AS above_T2_val, COALESCE(above_T2_keycol, below_T2_keycol;Taste R2_keycol) AS above_T2_val 

 Dieser Code generiert die folgende Ausgabe:
 
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
 

 In Schritt 4 der Lösung definieren Sie basierend auf der Abfrage aus Schritt 3 einen CTE namens R3. Sie geben keycol mit dem Alias ​​T1_keycol und val mit dem Alias ​​T1_val zurück. Berechnen Sie die Ergebnisspalte T2_keycol wie folgt:Wenn die absolute Differenz zwischen val und below_T2_val kleiner oder gleich der absoluten Differenz zwischen above_T2_val und val ist, geben Sie below_T2_keycol zurück, andernfalls above_T2_keycol. Berechnen Sie die Ergebnisspalte T2_val wie folgt:Wenn die absolute Differenz zwischen val und below_T2_val kleiner oder gleich der absoluten Differenz zwischen above_T2_val und val ist, geben Sie below_T2_val zurück, andernfalls above_T2_val.
 

 Hier ist der Code, der diesen Schritt implementiert:
 
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(above_T2_val - val) THEN below_T2_val ELSE above_T2_val END AS val2FROM R3;
 

 Der Plan für Alejandros Lösung mit unterstützenden Indizes ist in Abbildung 3 dargestellt.
 

 Abbildung 3:Lösungsplan von Alejandro mit Indizes 
 

 Hier sind die Leistungsstatistiken für diesen Plan:
 
Laufzeit:7,8, CPU:12,6, logische Lesevorgänge:35.886
 

 Der Plan für Alejandros Lösung ohne unterstützende Indizes ist in Abbildung 4 dargestellt.
 

 Abbildung 4:Lösungsplan von Alejandro ohne Indizes 
 

 Hier sind die Leistungsstatistiken für diesen Plan:
 
Laufzeit:8,19, CPU:14,8, logische Lesevorgänge:37.091
 

 Beachten Sie, dass es in den ersten beiden Zweigen des Plans in Abbildung 4 zwei Sortierungen vor dem Merge Join (Concatenation)-Operator gibt, da keine unterstützenden Indizes vorhanden sind. Diese Sortierungen werden im Plan in Abbildung 3 nicht benötigt, da die Daten vorgeordnet aus den unterstützenden Indizes abgerufen werden.
 
Kamils ​​Variation von Alejandros Lösung
 

 Bei dieser Lösung stützte sich Kamil auch auf die letzte Nicht-Null-Technik. Hier ist der Code der vollständigen Lösung:
 
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 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;
 

 In Schritt 1 der Lösung definieren Sie CTEs namens all_vals und ranges, wobei Sie die letzte Nicht-Null-Technik verwenden, um für jeden Wert in T1 (wobei keycol nicht NULL ist) Bereiche von Werten unter (prev) und über (nxt) von T2 zu identifizieren ( wobei keycol null ist).
 

 Hier ist der Code, der diesen Schritt implementiert:
 
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 IST NULL THEN val END) OVER (ORDER BY val, keycol ROWS BETWEEN 1 FOLLOWING AND UNBOUNDED FOLLOWING) AS nxt FROM all_vals)SELECT * FROM ranges;
 

 Dieser Code generiert die folgende Ausgabe:
 
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 20 19 NULL11 21 19 NULL
 

 In Schritt 2 der Lösung fragen Sie die CTE-Bereiche ab und filtern nur Zeilen, in denen keycol nicht null ist. Sie geben die Spalten keycol und val von T1 als keycol1 bzw. val1 zurück. Dann geben Sie zwischen prev und nxt den Wert zurück, der val1 am nächsten kommt, als val2.
 

 Hier ist der Code, der diesen Schritt implementiert:
 
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;
 

 Dieser Code generiert die folgende Ausgabe:
 
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
 

 In Schritt 3 der Lösung definieren Sie einen CTE namens matched_vals basierend auf der Abfrage aus Schritt 2. Sie definieren auch eine abgeleitete Tabelle namens T2, in der Sie mithilfe partitionierter Zeilennummern die Tiebreak-Logik für die Zeilen aus dbo.T2 handhaben. Sie verbinden dann matched_vals, den CTE T2 und die Tabelle T1, um die endgültige Matching-Logik zu handhaben.
 

 Hier ist der Code, der diesen Schritt implementiert:
 
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;
 

 Der Plan für Kamils ​​Variation von Alejandros Lösung mit unterstützenden Indizes ist in Abbildung 5 dargestellt.
 

 Abbildung 5:Plan für Kamils ​​Variante von Alejandros Lösung mit Indizes 
 

 Hier sind die Leistungsstatistiken für diesen Plan:
 
Laufzeit:11,5, CPU:18,3, logische Lesevorgänge:59.218
 

 Der Plan für Kamils ​​Variation von Alejandros Lösung ohne unterstützende Indizes ist in Abbildung 6 dargestellt.
 

 Abbildung 6:Plan für Kamils ​​Variante von Alejandros Lösung ohne Indizes 
 

 Hier sind die Leistungsstatistiken für diesen Plan:
 
Laufzeit:12,6, CPU:23,5, logische Lesevorgänge:61.432
 

 Ähnlich wie bei den Plänen für die Lösung von Alejandro erfordert auch in diesem Fall der Plan in Abbildung 5 keine expliziten Sortierungen vor der Anwendung des Operators Merge Join (Verkettung), da die Daten vorgeordnet aus unterstützenden Indizes abgerufen werden, was beim Plan in Abbildung 6 der Fall ist erfordern explizite Sortierungen, da es keine unterstützenden Indizes gibt.
 
Lösung von Radek Celuch – Verwendung von Intervallen
 

 Radek hatte eine einfache und schöne Idee. Für jeden unterschiedlichen Wert in T2.val berechnen Sie ein Intervall, das den Wertebereich von T1.val darstellt, der mit dem aktuellen T2.val übereinstimmen würde. 
 

 Hier ist der Code der vollständigen Lösung:
 
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.hoch;
 

 In Schritt 1 der Lösung fragen Sie T2 ab und berechnen Zeilennummern (nennen Sie die Spalte rn), partitioniert nach val und geordnet nach keycol. Basierend auf dieser Abfrage definieren Sie einen CTE namens Pre1. Sie fragen dann Pre1 ab und filtern nur die Zeilen, in denen rn =1 ist. In derselben Abfrage geben Sie mit LAG und LEAD für jede Zeile den Wert der val-Spalte aus der vorherigen Zeile (nennen Sie sie prev) und aus der nächsten Zeile ( nenne es als nächstes).
 

 Hier ist der Code, der diesen Schritt implementiert:
 
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;
 

 Dieser Code generiert die folgende Ausgabe:
 
keycol val othercols zurück weiter------- ---- ---------- ----------- ---------- -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
 

 In Schritt 2 der Lösung definieren Sie einen CTE namens Pre2 basierend auf der Abfrage aus Schritt 1. Sie fragen Pre2 ab und berechnen für jede Zeile ein Intervall [niedrig, hoch], in das val von T1 fallen würde. Hier sind die Berechnungen für niedrig und hoch:
 
 
 niedrig =ISNULL(val – (val – prev) / 2 + (1 – (val – prev) % 2), 0) 
 
 hoch =ISNULL(val + (next – val) / 2, 2147483647) 
 
 

 Die Mod-2-Prüfung beim Berechnen der unteren Grenze wird verwendet, um die untere T2.val-Anforderung zu erfüllen, und der Zeilennummernfilter wird verwendet, um die untere T2.keycol-Anforderung zu erfüllen. Als untere und obere Grenze werden die Werte 0 und 2147483647 verwendet.
 

 Hier ist der Code, der diesen Schritt implementiert:
 
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;
 

 Dieser Code generiert die folgende Ausgabe:
 
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
 

 In Schritt 3 der Lösung definieren Sie einen CTE namens T2 basierend auf der Abfrage aus Schritt 2. Sie verbinden dann die Tabelle T1 mit den CTE T2 übereinstimmenden Zeilen, basierend darauf, dass val von T1 innerhalb des Intervalls [niedrig, hoch] in T2. 

 Hier ist der Code, der diesen Schritt implementiert:
 
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;
 

 Der Plan für Radeks Lösung mit unterstützenden Indizes ist in Abbildung 7 dargestellt. 
 

 Abbildung 7:Lösungsplan von Radek mit Indizes 
 

 Hier sind die Leistungsstatistiken für diesen Plan:
 
Laufzeit:10.6, CPU:7.63, logische Lesevorgänge:3.193.125
 

 Der Plan für Radeks Lösung ohne unterstützende Indizes ist in Abbildung 8 dargestellt. 
 

 Abbildung 8:Lösungsplan von Radek ohne Indizes 
 

 Hier sind die Leistungsstatistiken für diesen Plan:
 
Laufzeit:18,1, CPU:27,4, logische Lesevorgänge:5.827.360
 

 Hier ist der Leistungsunterschied zwischen den beiden Plänen ziemlich groß. Der Plan in Abbildung 8 erfordert eine vorläufige Sortierung vor der Berechnung der Zeilennummern, was der Plan in Abbildung 7 nicht tut. Noch wichtiger ist, dass der Plan in Abbildung 8 einen Index-Spool erstellt, um jedes Intervall mit den entsprechenden Zeilen von T1 abzugleichen, im Wesentlichen als Alternative zum fehlenden Index, während der Plan in Abbildung 7 einfach den vorhandenen Index idx_val_key auf T1 verwendet. Das ist der Hauptgrund für die großen Unterschiede über alle Leistungsmaße hinweg. Dennoch ist die Leistung ohne unterstützende Indizes angemessen.
 
Kamils ​​Variante von Radeks Lösung
 

 Kamil entwickelte eine Variation von Radeks Lösung. Hier ist der Code der vollständigen Lösung:
 
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.
 
Schlussfolgerung
 

 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!