Partido más cercano, Parte 3

En Closest Match, Parte 1, cubrí un desafío de T-SQL que me proporcionó Karen Ly, una analista junior de renta fija en RBC. El desafío involucraba dos tablas:T1 y T2, cada una con una columna clave (keycol), un valor (val) y algunas otras columnas (representadas con una columna llamada othercols). La tarea era hacer coincidir con cada fila de T1 la fila de T2 donde T2.val es el más cercano a T1.val (la diferencia absoluta es la más baja), usando el valor más bajo de T2.keycol como desempate. Proporcioné un par de soluciones relacionales y analicé sus características de rendimiento. También lo desafié a que trate de encontrar una solución que funcione razonablemente en los casos en los que no tenga permitido/no pueda crear índices de soporte. En la Parte 2, demostré cómo se puede lograr esto mediante el uso de soluciones iterativas. Obtuve varias soluciones de lectura muy interesantes de Kamil Konsno, Alejandro Mesa y Radek Celuch, y esas soluciones son el tema central del artículo de este mes.

Datos de muestra

Como recordatorio, le proporcioné conjuntos pequeños y grandes de datos de muestra para que pueda trabajar. Conjuntos pequeños para comprobar la validez de su solución y conjuntos grandes para comprobar su rendimiento. Use el siguiente código para crear la base de datos de muestra testdb y dentro de ella las tablas de muestra T1 y T2:

-- Muestra dbSET NOCOUNT ON; SI DB_ID('testdb') ES NULO CREAR BASE DE DATOS testdb;IR USE testdb;IR -- Tablas de muestra T1 y T2DROP TABLE IF EXISTS dbo.T1, dbo.T2; CREATE TABLE dbo.T1( keycol INT NOT NULL IDENTITY RESTRICINT PK_T1 PRIMARY KEY, val INT NOT NULL, othercols BINARY(100) NOT NULL RESTRICTION DFT_T1_col1 DEFAULT(0xAA)); CREATE TABLE dbo.T2( keycol INT NOT NULL IDENTITY RESTRICINT PK_T2 PRIMARY KEY, val INT NOT NULL, othercols BINARY(100) NOT NULL RESTRICTION DFT_T2_col1 DEFAULT(0xBB));

Utilice el siguiente código para completar las tablas con pequeños conjuntos de datos de muestra:

-- Complete T1 y T2 con pequeños conjuntos de datos de muestra TRUNCATE TABLE dbo.T1;TRUNCATE TABLE dbo.T2; INSERTAR EN dbo.T1 (val) VALORES (1), (1), (3), (3), (5), (8), (13), (16), (18), (20), ( 21); INSERTAR EN dbo.T2 (val) VALORES (2), (2), (7), (3), (3), (11), (11), (13), (17), (19); 

Usaré los pequeños conjuntos de datos de muestra cuando describa la lógica de las diferentes soluciones y proporcionaré conjuntos de resultados intermedios para los pasos de las soluciones.

Use el siguiente código para crear la función auxiliar GetNums y para llenar las tablas con grandes conjuntos de datos de muestra:

-- Función auxiliar para generar una secuencia de números enteros FUNCIÓN DROP SI EXISTE dbo.GetNums;IR A CREAR O ALTERAR FUNCIÓN dbo.GetNums(@low AS BIGINT, @high AS BIGINT) DEVUELVE TABLEASRETURN CON L0 AS (SELECT c FROM (SELECT 1 UNION ALL SELECCIONE 1) COMO D(c)), L1 COMO (SELECCIONE 1 COMO c DE L0 COMO CRUZ ÚNASE L0 COMO B), L2 COMO (SELECCIONE 1 COMO c DE L1 COMO CRUZ ÚNASE L1 COMO B), L3 COMO (SELECCIONE 1 COMO c DE L2 COMO CRUZ ÚNASE L2 COMO B), L4 COMO (SELECCIONE 1 COMO c DE L3 COMO CRUZ ÚNASE L3 COMO B), L5 COMO (SELECCIONE 1 COMO c DE L4 COMO CRUZ ÚNASE L4 COMO B), Nums COMO (SELECCIONE ROW_NUMBER() SOBRE(ORDENAR POR (SELECCIONE NULL)) COMO rownum DE L5) SELECCIONE TOP(@high - @low + 1) @low + rownum - 1 AS n FROM Nums ORDER BY rownum;IR -- Llenar T1 y T2 con grandes conjuntos de datos de muestraDECLARAR @numrowsT1 AS INT =1000000, @maxvalT1 AS INT =10000000, @numrowsT2 AS INT =1000000, @maxvalT2 AS INT =10000000; TRUNCATE TABLE dbo.T1; TRUNCATE TABLE dbo.T2; INSERTAR EN dbo.T1 CON(TABLOCK) (val) SELECCIONAR ABS(CHECKSUM(NEWID())) % @maxvalT1 + 1 AS val FROM dbo.GetNums(1, @numrowsT1) AS Nums; INSERTAR EN dbo.T2 CON(TABLOCK) (val) SELECCIONAR ABS(CHECKSUM(NEWID())) % @maxvalT2 + 1 AS val FROM dbo.GetNums(1, @numrowsT2) AS Nums;

Cuando desee probar su solución con índices compatibles, use el siguiente código para crear esos índices:

CREAR ÍNDICE idx_val_key ON dbo.T1(val, keycol) INCLUDE(otroscols); CREAR ÍNDICE idx_val_key ON dbo.T2(val, keycol) INCLUDE(otroscols);CREAR ÍNDICE idx_valD_key ON dbo.T2(val DESC, keycol) INCLUDE(otrascolumnas);

Cuando desee probar su solución sin índices compatibles, use el siguiente código para eliminar esos índices:

BOTAR EL ÍNDICE SI EXISTE idx_val_key EN dbo.T1;BOTAR EL ÍNDICE SI EXISTE idx_val_key EN dbo.T2;BOTAR EL ÍNDICE SI EXISTE idx_valD_key EN dbo.T2;

Solución 1 de Kamil Kosno:usar una tabla temporal

Kamil Kosno presentó algunas:dos con sus ideas originales y dos variaciones de las soluciones de Alejandro y Radek. La primera solución de Kamil utiliza una tabla temporal indexada. A menudo sucede que incluso si no tiene permitido crear índices de soporte en las tablas originales, puede trabajar con tablas temporales y con las tablas temporales siempre puede crear sus propios índices.

Aquí está el código de la solución completa:

BOTAR TABLA SI EXISTE #T2; SELECCIONE MIN(keycol) COMO keycol, valINTO #T2FROM dbo.T2GROUP BY val; CREAR ÍNDICE ÚNICO idx_nc_val_key ON #T2(val, keycol); CON bestvals AS( SELECT keycol AS keycol1, val AS val1, othercols AS othercols1, CASE CUANDO (prev + nxt ES NULO) ENTONCES COALESCE(prev, nxt) CUANDO ABS(val - prev)  

 En el Paso 1 de la solución, almacena el keycol mínimo para cada valor único en una tabla temporal llamada #T2 y crea un índice de soporte en (val, keycol). Aquí está el código que implementa este paso:
 
BOTAR TABLA SI EXISTE #T2; SELECCIONE MIN(keycol) COMO keycol, valINTO #T2FROM dbo.T2GROUP BY val; CREAR ÍNDICE ÚNICO idx_nc_val_key ON #T2(val, keycol); SELECCIONE * DESDE #T2;
 

 La tabla temporal se completa con los siguientes datos:
 
valor col.clave----------- ----------1 24 33 76 118 139 1710 19
 

 En el Paso 2 de la solución, aplica lo siguiente:
 

 Para cada fila en T1, calcule los valores anterior y siguiente de #T2. Calcule prev como el valor máximo en #T2 que es menor o igual que el valor en T1. Calcule nxt como el valor mínimo en #T2 que es mayor o igual que el valor en T1.
 

 Use una expresión CASE para calcular val2 según la siguiente lógica:
 
 
 Cuando prev o nxt es nulo, devuelve el primer no nulo de los dos, o NULL si ambos son NULL. 
 
 Cuando la diferencia absoluta entre val y prev es menor que la diferencia absoluta entre val y nxt, devuelve prev. 
 
 Cuando si la diferencia absoluta entre val y nxt es menor que la diferencia absoluta entre val y prv, devuelva nxt. 
 
 De lo contrario, si nxt es menor que prev, devuelve nxt; de lo contrario, devuelve prev. 
 
 

 Aquí está el código que implementa este paso:
 
SELECCIONE keycol COMO keycol1, val COMO val1, othercols COMO othercols1, CASO CUANDO (prev + nxt ES NULO) ENTONCES COALESCE (anterior, nxt) CUANDO ABS (val - prev)  

 Este código genera el siguiente resultado:
 
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
 

 En el Paso 3 de la solución, define un CTE llamado bestvals basado en la consulta del Paso 2. Luego, une bestvals con #T2 para obtener las claves y une el resultado con T2 para obtener el resto de los datos (otrascolumnas).
 

 Aquí está el código que implementa este paso:
 
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 UNIÓN INTERNA dbo.T2 EN T2.keycol =tempT2.keycol;
 

 El plan para la solución 1 por Kamil con los índices de soporte se muestran en la Figura 1.
 

 Figura 1:Plan para la solución 1 de Kamil con índices 
 

 La primera rama del plan agrupa y agrega los datos de T2 y escribe el resultado en la tabla temporal #T2. Tenga en cuenta que esta rama usa un algoritmo Stream Aggregate preordenado que se basa en un escaneo ordenado del índice idx_valD_key en T2.
 

 Estas son las estadísticas de rendimiento de este plan:
 
tiempo de ejecución (seg.):5,55, CPU (seg.):16,6, lecturas lógicas:6 687 172
 

 El plan para la solución 1 de Kamil sin índices de soporte se muestra en la Figura 2.
 

 Figura 2:Plan para la solución 1 de Kamil sin índices 
 

 La principal diferencia entre este plan y el anterior es que la primera rama del plan, que maneja la parte de agrupación y agregación en el Paso 1, esta vez no puede extraer los datos ordenados previamente de un índice de soporte, por lo que los extrae desordenados del agrupado. index en T2 y luego usa un algoritmo Hash Aggregate.
 

 Estas son las estadísticas de rendimiento de este plan:
 
tiempo de ejecución:6,44, CPU:19,3, lecturas lógicas:6 688 277
 
Solución de Alejandro Mesa – Usando la última técnica no nula
 

 La solución de Alejandro usa la última técnica no nula descrita aquí.
 

 Aquí está el código de la solución completa (proporcionado aquí sin devolver otras columnas):
 
CON 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 FILAS ENTRE PRECEDENTES ILIMITADOS Y 1 PRECEDENTE ) COMO debajo_binstr, MIN( CASO CUANDO tid =0 THEN CAST(val COMO binario(4)) + CAST(keycol COMO binario(4)) FIN ) SOBRE( ORDEN POR val, tid, keycol FILAS ENTRE 1 SIGUIENTE Y SIGUIENTE SIN LÍMITES) COMO arriba_binstr DESDE (SELECCIONE 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) COMO 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) COMO debajo_T2_val, COALESCE(debajo_T2_keycol, arriba_T2_keycol) COMO debajo_T2_keycol, COALESCE(arriba_T2_val, debajo_T2_val) COMO arriba_T2_val, COALESCE(arriba_T2_keycol, debajo_T2_keycol) COMO arriba_T2_keycol DESDE R2) SELECCIONE keycol COMO keycol1, val COMO val1, CASO CUANDO ABS_val_T2(val) ) <=ABS(sobre_T2_val - val) ENTONCES debajo_T2_keycol ELSE encima_T2_keycol TERMINA COMO keycol2, CASO CUANDO ABS(val - debajo_T2_val) <=ABS(sobre_T2_val - val) ENTONCES debajo_T2_val ELSE encima_T2_val TERMINA COMO val2DE R3;
 

 En el Paso 1 de la solución, unifica las filas de T1 (asignando una columna de resultado llamada tid a 1) con las filas de T2 (asignando tid =0) y define una tabla derivada llamada T basada en el resultado. Usando la última técnica no nula, basada en el orden de val, tid, keycol, para cada fila actual, recupera los valores de la última fila tid =0 concatenados en una columna binaria llamada below_binstr. De manera similar, recupera los valores de la siguiente fila tid =0 concatenados en una columna binaria llamada above_binstr.
 

 Aquí está el código que implementa este paso:
 
SELECT keycol, val, tid, MAX( CASE WHEN tid =0 THEN CAST(val AS binary(4)) + CAST(keycol AS binary(4)) END ) SOBRE( ORDENAR POR val, tid, keycol FILAS ENTRE PRECEDENTE ILIMITADO Y 1 PRECEDENTE ) COMO debajo_binstr, MIN( CASO CUANDO tid =0 ENTONCES CAST(val COMO binario(4)) + CAST(keycol COMO binario(4)) END ) SOBRE( ORDEN POR val, tid, keycol FILAS ENTRE 1 SIGUIENTE Y SIGUIENTE ILIMITADO) COMO above_binstrFROM ( SELECCIONE 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;
 

 Este código genera el siguiente resultado:
 
keycol val tid debajo_binstr encima_binstr----------- ----------- ----------- --------- --------- ---------------------- 1 1 1 NULL 0x00000002000000012 1 1 NULL 0X0000000200000000011 2 0 NULL 0X0000000300000000044 3 0 0X000000020000000101N 0X0000000700000000033 3 1 0X0000000003000004 0x000000070000034 3 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0x000000030000000004 0x00000007000000035 5 1 0x00000003000000000004 0x00000000070000000333 7 0 0x000000000300000004 0x0000000B00000000066 8 1 0x000000070000000000002000 '0.000 197 0.000 0.000' 0.000 000000000000002000000ITOMINOS ALTENCIOS ALTENCIALES UNA 08 0x00000011000000098 16 1 0x0000000d00000008 0x0000000011000000099 17 0 0x0000000D00000008000 0x000000130000000A9 18 1 0x00000010000000009 0x00000013000000000A10 19 0 0x0000001100000009 NULL10 20 1 0x001330000001300013001300130013000 ALTLULLE11132TRES11130000000000000013000 ALTLULLE11 

 En el Paso 2 de la solución, define un CTE llamado R1 basado en la consulta del Paso 1. Consulta R1, filtra solo las filas donde tid =1 y extrae los valores individuales de las cadenas binarias concatenadas.
 

 Aquí está el código que implementa este paso:
 
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;
 

 Este código genera el siguiente resultado:
 
valor keycol debajo_T2_val debajo_T2_keycol above_T2_val above_T2_keycol----------- ----------- ------------ ------- -------- ------------ ---------------1 1 NULO NULO 2 12 1 NULO NULO 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
 

 En el Paso 3 de la solución, define un CTE llamado R2 basado en la consulta del Paso 2. Luego calcula las siguientes columnas de resultados:
 
 
 debajo_T2_val:el primer no nulo entre debajo_T2_val y arriba_T2_val 
 
 debajo_T2_keycol:el primer no nulo entre debajo_T2_keycol y arriba_T2_keycol 
 
 above_T2_val:el primer no nulo entre above_T2_val y below_T2_val 
 
 above_T2_keycol:el primer no nulo entre above_T2_keycol y below_T2_keycol 
 
 

 Aquí está el código que implementa este paso:
 
SELECT keycol, val, COALESCE(debajo_T2_val, above_T2_val) COMO debajo_T2_val, COALESCE(debajo_T2_keycol, above_T2_keycol) COMO debajo_T2_keycol, COALESCE(encima_T2_val, debajo_T2_val) COMO arriba_T2_val, COALESCE(encima_T2_keycol, debajo_T2_keycol) COMO arriba_T2;
keycol> 

 Este código genera el siguiente resultado:
 
valor keycol debajo_T2_val debajo_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
 

 En el Paso 4 de la solución, define un CTE llamado R3 basado en la consulta del Paso 3. Devuelve keycol con alias T1_keycol y val con alias T1_val. Calcule la columna de resultado T2_keycol como:si la diferencia absoluta entre val y under_T2_val es menor o igual que la diferencia absoluta entre above_T2_val y val, devuelva under_T2_keycol, de lo contrario, above_T2_keycol. Calcule la columna de resultado T2_val como:si la diferencia absoluta entre val y under_T2_val es menor o igual que la diferencia absoluta entre above_T2_val y val, devuelva under_T2_val, de lo contrario, above_T2_val.
 

 Aquí está el código que implementa este paso:
 
SELECCIONE keycol COMO keycol1, val COMO val1, CASO CUANDO ABS (valor - debajo_T2_val) <=ABS (arriba_T2_val - val) ENTONCES debajo_T2_keycol ELSE arriba_T2_keycol FIN COMO keycol2, CASO CUANDO ABS (valor - debajo_T2_val) <=ABS (arriba_T2_val - val) ENTONCES debajo_T2_val ELSE encima_T2_val TERMINA COMO val2DE R3;
 

 El plan para la solución de Alejandro con índices de apoyo se muestra en la Figura 3.
 

 Figura 3:Plan de solución de Alejandro con índices 
 

 Estas son las estadísticas de rendimiento de este plan:
 
tiempo de ejecución:7,8, CPU:12,6, lecturas lógicas:35 886
 

 El plan para la solución de Alejandro sin índices de soporte se muestra en la Figura 4.
 

 Figura 4:Plan de solución de Alejandro sin índices 
 

 Estas son las estadísticas de rendimiento de este plan:
 
tiempo de ejecución:8.19, CPU:14.8, lecturas lógicas:37 091
 

 Observe que en las dos primeras ramas del plan de la Figura 4 hay dos tipos antes del operador Merge Join (Concatenación) debido a la falta de índices de soporte. Esas clasificaciones no son necesarias en el plan de la Figura 3, ya que los datos se recuperan ordenados previamente de los índices de soporte.
 
La variación de Kamil sobre la solución de Alejandro
 

 En esta solución, Kamil también se basó en la última técnica no nula. Aquí está el código de la solución completa:
 
CON 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 (ORDEN BY val, filas keycol ENTRE EL ANTERIOR SIN LÍMITES Y EL 1 PRECEDENTE) COMO anterior, MIN (CASO CUANDO keycol ES NULO ENTONCES VAL END) SOBRE (ORDENAR POR val, FILAS keycol ENTRE 1 SIGUIENTE Y SIGUIENTE ILIMITADO) AS nxt FROM all_vals),matched_vals AS( SELECCIONE keycol COMO keycol1, val AS val1, CASO CUANDO ABS (val - prev) <=ISNULL (ABS (val - nxt), prev) ENTONCES prev ELSE nxt FIN COMO val2 DESDE rangos DONDE keycol NO ES NULO) SELECCIONE keycol1, val1, SUBCADENA(T1.otrascols, 1, 1) AS otrascols1, val2, T2.keycol AS keycol2, SUBCADENA(T2.otrascols, 1, 1) AS otrascols2 FROM matched_vals AS M INNER JOIN ( SELECT *, ROW_NUMBER() OVER (PARTITION BY val ORDEN POR keycol) COMO rn DESDE dbo.T2 ) COMO T2 EN T2.val =M.val2 Y rn =1 UNIÓN INTERNA dbo.T1 EN T1.keycol =keycol1;
 

 En el Paso 1 de la solución, define CTE llamados all_vals y ranges, donde usa la última técnica no nula para identificar para cada valor en T1 (donde keycol no es NULL) rangos de valores inferiores (anteriores) y superiores (nxt) de T2 ( donde keycol es nulo).
 

 Aquí está el código que implementa este paso:
 
CON 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 (ORDEN POR val, filas keycol ENTRE EL PRECEDENTE ILIMITADO Y EL 1 PRECEDENTE) COMO anterior, MIN(CASO CUANDO keycol ES NULO ENTONCES VAL END) SOBRE (ORDENAR POR val, FILAS keycol ENTRE 1 SIGUIENTE Y SIGUIENTE ILIMITADO) AS nxt FROM all_vals) SELECCIONAR * DESDE rangos;
 

 Este código genera el siguiente resultado:
 
keycol val prev nxt----------- ----------- ----------- ---------- -1 1 NULO 22 1 NULO 2NULO 2 NULO 3NULO 3 2 73 3 3 74 3 3 75 5 3 7NULO 7 3 116 8 7 11NULO 11 7 13NULO 13 11 177 13 13 178 16 13 17NULO 17 13 199 19 18 NULO 20 19 NULO11 21 19 NULO
 

 En el Paso 2 de la solución, consulta los rangos de CTE y filtra solo las filas donde keycol no es nulo. Devuelve las columnas keycol y val de T1 como keycol1 y val1, respectivamente. Luego, entre prev y nxt, devuelves el más cercano a val1 como val2.
 

 Aquí está el código que implementa este paso:
 
SELECCIONE keycol COMO keycol1, val COMO val1, CASO CUANDO ABS(val - prev) <=ISNULL(ABS(val - nxt), prev) ENTONCES prev ELSE nxt END AS val2FROM rangesWHERE keycol NO ES NULO;
 

 Este código genera el siguiente resultado:
 
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
 

 En el Paso 3 de la solución, define un CTE llamado matched_vals basado en la consulta del Paso 2. También define una tabla derivada llamada T2 donde, usando números de fila particionados, maneja la lógica de desempate para las filas de dbo.T2. Luego, une matched_vals, el CTE T2 y la tabla T1 para manejar la lógica de coincidencia final.
 

 Aquí está el código que implementa este paso:
 
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 ( SELECCIONAR * , ROW_NUMBER() SOBRE (PARTICIÓN POR val ORDEN POR keycol) COMO rn DESDE dbo.T2 ) COMO T2 EN T2.val =M.val2 Y rn =1 UNIÓN INTERNA dbo.T1 EN T1.keycol =keycol1;
 

 El plan para la variación de Kamil en la solución de Alejandro con índices de apoyo se muestra en la Figura 5.
 

 Figura 5:Plan para la variación de Kamil en la solución de Alejandro con índices 
 

 Estas son las estadísticas de rendimiento de este plan:
 
tiempo de ejecución:11,5, CPU:18,3, lecturas lógicas:59 218
 

 El plan para la variación de Kamil en la solución de Alejandro sin índices de apoyo se muestra en la Figura 6.
 

 Figura 6:Plan para la variación de Kamil en la solución de Alejandro sin índices 
 

 Estas son las estadísticas de rendimiento de este plan:
 
tiempo de ejecución:12,6, CPU:23,5, lecturas lógicas:61 432
 

 Similar a los planes para la solución de Alejandro, también en este caso el plan en la Figura 5 no requiere ordenaciones explícitas antes de aplicar el operador Merge Join (concatenación) ya que los datos se recuperan ordenados previamente de los índices de soporte, y el plan en la Figura 6 no requieren ordenaciones explícitas ya que no hay índices de soporte.
 
Solución de Radek Celuch:uso de intervalos
 

 A Radek se le ocurrió una idea simple y hermosa. Para cada valor distinto en T2.val, calcula un intervalo que representa el rango de valores de T1.val que coincidiría con el T2.val actual. 
 

 Aquí está el código de la solución completa:
 
CON 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( ORDENAR POR val) COMO anterior, LEAD(val) SOBRE(ORDENAR POR val) COMO siguiente DESDE Pre1 DONDE 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.alta;
 

 En el Paso 1 de la solución, consulta T2 y calcula los números de fila (llame a la columna rn), particionada por val y ordenada por keycol. Defina un CTE llamado Pre1 basado en esta consulta. Luego consulta Pre1 y filtra solo las filas donde rn =1. En la misma consulta, usando LAG y LEAD, devuelve para cada fila el valor de la columna val de la fila anterior (llámela prev) y de la fila siguiente ( llámalo a continuación).
 

 Aquí está el código que implementa este paso:
 
WITH Pre1 AS( SELECCIONE 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) COMO anterior, LEAD(val) SOBRE(ORDENAR POR val) COMO nextFROM Pre1WHERE rn =1;
 

 Este código genera el siguiente resultado:
 
keycol val othercols prev next------- ---- ---------- ----------- ---------- -1 2 0xBB NULO 34 3 0xBB 2 73 7 0xBB 3 116 11 0xBB 7 138 13 0xBB 11 179 17 0xBB 13 1910 19 0xBB 17 NULO
 

 En el Paso 2 de la solución, define un CTE llamado Pre2 basado en la consulta del Paso 1. Consulta Pre2 y calcula para cada fila un intervalo [bajo, alto] donde val de T1 caería. Aquí están los cálculos para bajo y alto:
 
 
 bajo =ESNULL(val – (val – anterior) / 2 + (1 – (val – anterior) % 2), 0) 
 
 alto =ISNULL(val + (siguiente – val) / 2, 2147483647) 
 
 

 La verificación mod 2 en el cálculo del límite inferior se usa para cumplir con el requisito de T2.val más bajo, y el filtro de número de fila se usa para cumplir con el requisito de T2.keycol más bajo. Los valores 0 y 2147483647 se utilizan como límites superior e inferior extremos.
 

 Aquí está el código que implementa este paso:
 
SELECT keycol, val, othercols, ISNULL(val - (val - prev) / 2 + (1 - (val - prev) % 2), 0) AS low, ISNULL(val + (next - val) / 2 , 2147483647) COMO alto DESDE Pre2;
 

 Este código genera el siguiente resultado:
 
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
 

 En el Paso 3 de la solución, define un CTE llamado T2 basado en la consulta del Paso 2. Luego, une la tabla T1 con las filas coincidentes de CTE T2 según el valor de T1 que se encuentra dentro del intervalo [bajo, alto] en T2.
 

 Aquí está el código que implementa este paso:
 
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 ) COMO othercols2FROM dbo.T1 INNER JOIN T2 ON T1.val ENTRE T2.low Y T2.high;
 

 El plan para la solución de Radek con índices de apoyo se muestra en la Figura 7. 
 

 Figura 7:Plan de solución de Radek con índices 
 

 Estas son las estadísticas de rendimiento de este plan:
 
tiempo de ejecución:10,6, CPU:7,63, lecturas lógicas:3 193 125
 

 El plan para la solución de Radek sin índices de soporte se muestra en la Figura 8. 
 

 Figura 8:Plan de solución de Radek sin índices 
 

 Estas son las estadísticas de rendimiento de este plan:
 
tiempo de ejecución:18,1, CPU:27,4, lecturas lógicas:5 827 360
 

 Aquí la diferencia de rendimiento entre los dos planes es bastante sustancial. El plan de la Figura 8 requiere una ordenación preliminar antes del cálculo de los números de fila, lo que no ocurre con el plan de la Figura 7. Más importante aún, para hacer coincidir cada intervalo con las filas respectivas de T1, el plan de la Figura 8 crea un Index Spool esencialmente como una alternativa al índice faltante, mientras que el plan de la Figura 7 simplemente usa el índice existente idx_val_key en T1. Esa es la razón principal de las grandes diferencias entre todas las medidas de rendimiento. Aun así, el rendimiento sin índices de soporte es razonable.
 
Variación de Kamil sobre la solución de Radek
 

 A Kamil se le ocurrió una variación de la solución de Radek. Aquí está el código de la solución completa:
 
CON T2_collapsed AS( SELECT keycol AS keycol2, val AS val2 , ROW_NUMBER() SOBRE (PARTICIÓN POR val ORDEN POR keycol) COMO rn DESDE dbo.T2), rangos AS( SELECT keycol2 AS prevkey, val2 AS prevval, LEAD( keycol2) SOBRE (ORDENAR POR val2) COMO nxtkey, LEAD(val2) SOBRE (ORDENAR POR val2) COMO nxtval FROM T2_collapsed WHERE rn =1),mejores coincidencias AS( SELECCIONE T1.keycol COMO keycol1, T1.val COMO val1, SUBCADENA(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.
 
Conclusión
 

 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!