Match le plus proche, partie 3

Dans Closest Match, partie 1, j'ai couvert un défi T-SQL qui m'a été proposé par Karen Ly, analyste junior des titres à revenu fixe chez RBC. Le défi impliquait deux tables - T1 et T2, chacune avec une colonne clé (keycol), une valeur (val) et quelques autres colonnes (représentées par une colonne appelée othercols). La tâche consistait à faire correspondre à chaque ligne de T1 la ligne de T2 où T2.val est la plus proche de T1.val (la différence absolue est la plus basse la plus basse), en utilisant la valeur T2.keycol la plus basse comme condition de départage. J'ai fourni quelques solutions relationnelles et discuté de leurs caractéristiques de performance. Je vous ai également mis au défi d'essayer de trouver une solution raisonnablement performante dans les cas où vous n'êtes pas autorisé/capable de créer des index de support. Dans la partie 2, j'ai montré comment cela peut être réalisé en utilisant des solutions itératives. J'ai reçu plusieurs solutions de lecture très intéressantes de Kamil Konsno, Alejandro Mesa et Radek Celuch, et ces solutions sont au centre de l'article de ce mois-ci.

Exemple de données

Pour rappel, j'ai fourni à la fois de petits et de grands ensembles d'exemples de données avec lesquels vous pouvez travailler. De petits ensembles pour vérifier la validité de votre solution et de grands ensembles pour vérifier ses performances. Utilisez le code suivant pour créer l'exemple de base de données testdb et les exemples de tables T1 et T2 :

-- Exemple dbSET NOCOUNT ON ; IF DB_ID('testdb') IS NULL CREATE DATABASE testdb;GO USE testdb;GO -- Exemples de tables T1 et 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));

Utilisez le code suivant pour remplir les tableaux avec de petits ensembles d'exemples de données :

-- Remplir T1 et T2 avec de petits ensembles d'exemples de données TRUNCATE TABLE dbo.T1;TRUNCATE TABLE dbo.T2; INSÉRER DANS dbo.T1 (val) VALEURS(1),(1),(3),(3),(5),(8),(13),(16),(18),(20),( 21); INSÉRER DANS dbo.T2 (val) VALEURS(2),(2),(7),(3),(3),(11),(11),(13),(17),(19); 

 J'utiliserai les petits ensembles d'exemples de données pour décrire la logique des différentes solutions et fournirai des ensembles de résultats intermédiaires pour les étapes des solutions.
 

 Utilisez le code suivant pour créer la fonction d'assistance GetNums et pour remplir les tableaux avec de grands ensembles d'exemples de données :
 
-- Fonction d'assistance pour générer une séquence d'entiersDROP FUNCTION IF 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 -- Remplir T1 et T2 avec de grands ensembles d'échantillons de donnéesDECLARE @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 ;
 

 Lorsque vous souhaitez tester votre solution avec des index de prise en charge, utilisez le code suivant pour créer ces index :
 
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(autrescols);
 

 Lorsque vous souhaitez tester votre solution sans prendre en charge les index, utilisez le code suivant pour supprimer ces index :
 
SUPPRIMER L'INDEX SI EXISTE idx_val_key SUR dbo.T1 ;SUPPRIMER L'INDEX SI EXISTE idx_val_key SUR dbo.T2 ;SUPPRIMER L'INDEX SI EXISTE idx_valD_key SUR dbo.T2 ;
 
Solution 1 par Kamil Kosno – Utiliser une table temporaire
 

 Kamil Kosno en a soumis quelques-unes – deux avec ses idées originales et deux variantes des solutions d'Alejandro et de Radek. La première solution de Kamil utilise une table temporaire indexée. Il arrive souvent que même si vous n'êtes pas autorisé à créer des index de support sur les tables d'origine, vous êtes autorisé à travailler avec des tables temporaires, et avec des tables temporaires, vous pouvez toujours créer vos propres index.
 

 Voici le code complet de la solution :
 
SUPPRIMER TABLE SI EXISTE #T2 ; SELECT MIN(keycol) AS keycol, valINTO #T2FROM dbo.T2GROUP BY val ; CRÉER UN INDEX UNIQUE 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)  

 À l'étape 1 de la solution, vous stockez le keycol minimum pour chaque val unique dans une table temporaire appelée #T2 et créez un index de support sur (val, keycol). Voici le code implémentant cette étape :
 
SUPPRIMER TABLE SI EXISTE #T2 ; SELECT MIN(keycol) AS keycol, valINTO #T2FROM dbo.T2GROUP BY val ; CRÉER UN INDEX UNIQUE idx_nc_val_key ON #T2(val, keycol); SÉLECTIONNER * À PARTIR DE #T2 ;
 

 La table temporaire est remplie avec les données suivantes :
 
keycol val----------- ----------1 24 33 76 118 139 1710 19
 

 À l'étape 2 de la solution, vous appliquez les éléments suivants :
 

 Pour chaque ligne de T1, calculez les valeurs prev et nxt de #T2. Calcule prev comme valeur maximale dans #T2 qui est inférieure ou égale à val dans T1. Calculez nxt comme la valeur minimale dans #T2 qui est supérieure ou égale à val dans T1.
 

 Utilisez une expression CASE pour calculer val2 selon la logique suivante :
 
 
 Lorsque prev ou nxt est nul, renvoie le premier non nul des deux, ou NULL si les deux sont NULL. 
 
 Lorsque la différence absolue entre val et prev est inférieure à la différence absolue entre val et nxt, renvoie prev. 
 
 Lorsque si la différence absolue entre val et nxt est inférieure à la différence absolue entre val et prv, renvoie nxt. 
 
 Sinon, si nxt est inférieur à prev, renvoie nxt, sinon renvoie prev. 
 
 

 Voici le code implémentant cette étape :
 
SELECT keycol AS keycol1, val AS val1, othercols AS othercols1, CASE WHEN (prev + nxt IS NULL) THEN COALESCE(prev, nxt) WHEN ABS(val - prev)  

 Ce code génère la sortie suivante :
 
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
 

 À l'étape 3 de la solution, vous définissez un CTE appelé bestvals en fonction de la requête de l'étape 2. Vous joignez ensuite bestvals avec #T2 pour obtenir les clés, et joignez le résultat avec T2 pour obtenir le reste des données (othercols).
 

 Voici le code implémentant cette étape :
 
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;
 

 Le plan pour la solution 1 par Kamil avec les index de prise en charge sont illustrés à la figure 1.
 

 Figure 1 :Plan de la solution 1 par Kamil avec index 
 

 La première branche du plan regroupe et agrège les données de T2 et écrit le résultat dans la table temporaire #T2. Notez que cette branche utilise un algorithme Stream Aggregate préordonné qui repose sur une analyse ordonnée de l'index idx_valD_key sur T2.
 

 Voici les statistiques de performances de ce plan :
 
temps d'exécution (sec) :5,55, CPU (sec) :16,6, lectures logiques :6 687 172
 

 Le plan de la solution 1 de Kamil sans index de prise en charge est illustré à la figure 2.
 

 Figure 2 :Plan pour la solution 1 par Kamil sans index 
 

 La principale différence entre ce plan et le précédent est que la première branche du plan, qui gère la partie regroupement et agrégation à l'étape 1, ne peut cette fois pas extraire les données préordonnées d'un index de support, elle les extrait donc de manière désordonnée du cluster index sur T2, puis utilise un algorithme Hash Aggregate.
 

 Voici les statistiques de performances de ce plan :
 
durée d'exécution :6,44, CPU :19,3, lectures logiques :6 688 277
 
Solution par Alejandro Mesa - Utilisation de la dernière technique non nulle
 

 La solution d'Alejandro utilise la dernière technique non nulle décrite ici.
 

 Voici le code complet de la solution (fourni ici sans renvoyer d'autres cols) :
 
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 LIGNES ENTRE 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(above_T2_keycol, below_T2_keycol) AS above_T2_keycol FROM R2)SELECT keycol AS keycol1, val AS val1, CASE WHENT ABS(val - below_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 ;
 

 À l'étape 1 de la solution, vous unifiez les lignes de T1 (attribuant une colonne de résultat appelée tid à 1) avec les lignes de T2 (attribuant tid =0) et définissez une table dérivée appelée T basée sur le résultat. En utilisant la dernière technique non nulle, basée sur l'ordre de val, tid, keycol, pour chaque ligne actuelle, vous récupérez les valeurs de la dernière ligne tid =0 concaténées dans une colonne binaire appelée below_binstr. De même, vous récupérez les valeurs de la ligne suivante tid =0 concaténées dans une colonne binaire appelée above_binstr.
 

 Voici le code implémentant cette étape :
 
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;
 

 Ce code génère la sortie suivante :
 
keycol val tid below_binstr above_binstr----------- ----------- ----------- --------- --------- ------------------ 1 1 1 1 null 0x00000002000000012 1 1 null 0x00000002000000011 2 0 null 0x00000003000000044 3 0 0x0000000200000001 0x000000000000000333 3 1 0x0000000400004 0x0000000000000034 3 1 1 0x00000000040004000000000000034 3 1 1 1 0x00000000040004000000000000034 3 1 1 1 0x0000000004. 0x0000000300000004 0x00000007000000035 5 1 0x0000000300000004 0x00000007000000033 7 0 0x0000000300000004 0x0000000b000000066 8 1 0x0000000000000000303 0x000000000000000000000000000000000000008 08 0x00000011000000098 16 1 0x0000000d00000008 0x00000011000000099 17 0 0x0000000d00000008 0x000000130000000a9 18 1 0x0000001100000009 NULL102 

 À l'étape 2 de la solution, vous définissez un CTE appelé R1 en fonction de la requête de l'étape 1. Vous interrogez R1, filtrez uniquement les lignes où tid =1 et extrayez les valeurs individuelles des chaînes binaires concaténées.
 

 Voici le code implémentant cette étape :
 
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 ;
 

 Ce code génère la sortie suivante :
 
keycol val ci-dessous_T2_val ci-dessous_T2_keycol au-dessus_T2_val ci-dessus_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
 

 À l'étape 3 de la solution, vous définissez un CTE appelé R2 basé sur la requête de l'étape 2. Vous calculez ensuite les colonnes de résultats suivantes :
 
 
 below_T2_val :le premier non nul entre below_T2_val et above_T2_val 
 
 below_T2_keycol :le premier non nul entre below_T2_keycol et above_T2_keycol 
 
 above_T2_val :le premier non nul entre above_T2_val et below_T2_val 
 
 above_T2_keycol :le premier non nul entre above_T2_keycol et below_T2_keycol 
 
 

 Voici le code implémentant cette étape :
 
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(above_T2_keycol, below_T2_keycol) AS above_T2_keycolFROM> R2;
 Ce code génère la sortie suivante :
 
keycol val ci-dessous_T2_val ci-dessous_T2_keycol au-dessus_T2_val ci-dessus_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
 

 À l'étape 4 de la solution, vous définissez un CTE appelé R3 en fonction de la requête de l'étape 3. Vous renvoyez keycol alias T1_keycol et val alias T1_val. Calculez la colonne de résultat T2_keycol comme :si la différence absolue entre val et below_T2_val est inférieure ou égale à la différence absolue entre above_T2_val et val, renvoyez below_T2_keycol, sinon above_T2_keycol. Calculez la colonne de résultat T2_val comme suit :si la différence absolue entre val et below_T2_val est inférieure ou égale à la différence absolue entre above_T2_val et val, renvoie below_T2_val, sinon above_T2_val.
 

 Voici le code implémentant cette étape :
 
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) ALORS en dessous de_T2_val SINON au-dessus de_T2_val END AS val2FROM R3 ;
 

 Le plan de la solution d'Alejandro avec les index de prise en charge est illustré à la figure 3.
 

 Figure 3 :Plan de solution par Alejandro avec index 
 

 Voici les statistiques de performances de ce plan :
 
durée d'exécution :7,8, CPU :12,6, lectures logiques :35 886
 

 Le plan de la solution d'Alejandro sans prise en charge des index est illustré à la figure 4.
 

 Figure 4 :Plan de solution par Alejandro sans index 
 

 Voici les statistiques de performances de ce plan :
 
durée d'exécution :8.19, CPU :14.8, lectures logiques :37 091
 

 Notez que dans les deux premières branches du plan de la figure 4, il existe deux tris avant l'opérateur Merge Join (Concaténation) en raison du manque d'index de prise en charge. Ces tris ne sont pas nécessaires dans le plan de la figure 3 puisque les données sont récupérées pré-ordonnées à partir des index de prise en charge.
 
La variation de Kamil sur la solution d'Alejandro
 

 Dans cette solution, Kamil s'est également appuyé sur la dernière technique non nulle. Voici le code complet de la solution :
 
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;
 

 À l'étape 1 de la solution, vous définissez des CTE appelés all_vals et plages, où vous utilisez la dernière technique non nulle pour identifier pour chaque valeur dans T1 (où keycol n'est pas NULL) les plages de valeurs inférieures (prev) et supérieures (nxt) de T2 ( où keycol est nul).
 

 Voici le code implémentant cette étape :
 
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 ranges;
 

 Ce code génère la sortie suivante :
 
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 1NULL 19 18 20 19 NULL11 21 19 NULL
 

 À l'étape 2 de la solution, vous interrogez les plages CTE et filtrez uniquement les lignes où keycol n'est pas null. Vous renvoyez les colonnes keycol et val de T1 en tant que keycol1 et val1, respectivement. Ensuite, entre prev et nxt, vous retournez le plus proche de val1 en tant que val2.
 

 Voici le code implémentant cette étape :
 
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;
 

 Ce code génère la sortie suivante :
 
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
 

 À l'étape 3 de la solution, vous définissez un CTE appelé matched_vals basé sur la requête de l'étape 2. Vous définissez également une table dérivée appelée T2 dans laquelle, à l'aide de numéros de lignes partitionnées, vous gérez la logique de départage pour les lignes de dbo.T2. Vous joignez ensuite matched_vals, le CTE T2 et la table T1 pour gérer la logique de correspondance finale.
 

 Voici le code implémentant cette étape :
 
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() SUR (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;
 

 Le plan de la variation de Kamil sur la solution d'Alejandro avec les index de support est illustré à la figure 5.
 

 Figure 5 :Plan pour la variation de Kamil sur la solution d'Alejandro avec index 
 

 Voici les statistiques de performances de ce plan :
 
temps d'exécution :11,5, CPU :18,3, lectures logiques :59 218
 

 Le plan de la variation de Kamil sur la solution d'Alejandro sans index de prise en charge est illustré à la figure 6.
 

 Figure 6 :Plan pour la variation de Kamil sur la solution d'Alejandro sans index 
 

 Voici les statistiques de performances de ce plan :
 
durée d'exécution :12,6, CPU :23,5, lectures logiques :61 432
 

 Semblable aux plans de la solution d'Alejandro, dans ce cas également, le plan de la figure 5 ne nécessite pas de tris explicites avant d'appliquer l'opérateur Merge Join (concaténation) puisque les données sont récupérées pré-ordonnées à partir des index de prise en charge, et le plan de la figure 6 ne nécessitent des tris explicites car il n'y a pas d'index de support.
 
Solution de Radek Celuch – Utilisation d'intervalles
 

 Radek a eu une idée simple et belle. Pour chaque valeur distincte dans T2.val, vous calculez un intervalle représentant la plage de valeurs de T1.val qui correspondrait au T2.val actuel. 
 

 Voici le code complet de la solution :
 
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.élevé ;
 

 À l'étape 1 de la solution, vous interrogez T2 et calculez les numéros de ligne (appelez la colonne rn), partitionnés par val et classés par keycol. Vous définissez un CTE appelé Pre1 en fonction de cette requête. Vous interrogez ensuite Pre1 et filtrez uniquement les lignes où rn =1. Dans la même requête, en utilisant LAG et LEAD, vous renvoyez pour chaque ligne la valeur de la colonne val de la ligne précédente (appelez-la prev) et de la ligne suivante ( appelez-le ensuite).
 

 Voici le code implémentant cette étape :
 
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;
 

 Ce code génère la sortie suivante :
 
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
 

 À l'étape 2 de la solution, vous définissez un CTE appelé Pre2 basé sur la requête de l'étape 1. Vous interrogez Pre2 et calculez pour chaque ligne un intervalle [faible, élevé] dans lequel val de T1 tomberait. Voici les calculs pour faible et élevé :
 
 
 bas =ISNULL(val – (val – prev) / 2 + (1 – (val – prev) % 2), 0) 
 
 haut =ISNULL(val + (suivant – val) / 2, 2147483647) 
 
 

 Le contrôle mod 2 sur le calcul de la limite inférieure est utilisé pour répondre à l'exigence T2.val inférieure, et le filtre de numéro de ligne est utilisé pour répondre à l'exigence T2.keycol inférieure. Les valeurs 0 et 2147483647 sont utilisées comme limites inférieure et supérieure extrêmes.
 

 Voici le code implémentant cette étape :
 
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 ;
 

 Ce code génère la sortie suivante :
 
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
 

 À l'étape 3 de la solution, vous définissez un CTE appelé T2 basé sur la requête de l'étape 2. Vous joignez ensuite la table T1 avec les lignes correspondantes CTE T2 basées sur la valeur de T1 se trouvant dans l'intervalle [faible, élevé] dans T2.
 

 Voici le code implémentant cette étape :
 
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 ;
 

 Le plan de la solution de Radek avec les index de prise en charge est illustré à la figure 7. 
 

 Figure 7 :Plan de solution par Radek avec index 
 

 Voici les statistiques de performances de ce plan :
 
temps d'exécution :10.6, CPU :7.63, lectures logiques :3 193 125
 

 Le plan de la solution de Radek sans prise en charge des index est illustré à la figure 8. 
 

 Figure 8 :Plan de solution par Radek sans index 
 

 Voici les statistiques de performances pour ce plan :
 
temps d'exécution :18,1, CPU :27,4, lectures logiques :5 827 360
 

 Ici, la différence de performances entre les deux plans est assez importante. Le plan de la figure 8 nécessite un tri préliminaire avant le calcul des numéros de ligne, ce que le plan de la figure 7 ne fait pas. Plus important encore, pour faire correspondre chaque intervalle avec les lignes respectives de T1, le plan de la figure 8 crée un spool d'index essentiellement comme alternative à l'index manquant, tandis que le plan de la figure 7 utilise simplement l'index existant idx_val_key sur T1. C'est la principale raison des grandes différences entre toutes les mesures de performance. Néanmoins, les performances sans index de prise en charge sont raisonnables.
 
La variation de Kamil sur la solution de Radek
 

 Kamil a proposé une variante de la solution de Radek. Voici le code complet de la solution :
 
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), plages 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),meilleures correspondances 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.
 
Conclusion
 

 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!