Correspondência mais próxima, Parte 3

Dados de amostra

-- Exemplo dbSET NOCOUNT ON; IF DB_ID('testdb') IS NULL CREATE DATABASE testdb;GO USE testdb;GO -- Tabelas de amostra T1 e 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));

-- Preencha T1 e T2 com pequenos conjuntos de dados de amostra 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); 
 Usarei os pequenos conjuntos de dados de amostra ao descrever a lógica das diferentes soluções e fornecerei conjuntos de resultados intermediários para as etapas das soluções. 
 
 Use o código a seguir para criar a função auxiliar GetNums e para preencher as tabelas com grandes conjuntos de dados de amostra:
 
-- Função auxiliar para gerar uma sequência de inteirosDROP 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 -- Preencha T1 e T2 com grandes conjuntos de dados de amostraDECLARE @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;
 
 Quando você quiser testar sua solução com índices de suporte, use o seguinte código para criar esses índices:
 
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(outros);
 
 Quando você quiser testar sua solução sem oferecer suporte a índices, use o código a seguir para remover esses índices:
 
DROP INDEX IF EXISTS idx_val_key ON dbo.T1;DROP INDEX IF EXISTS idx_val_key ON dbo.T2;DROP INDEX IF EXISTS idx_valD_key ON dbo.T2;
 
Solução 1 de Kamil Kosno – Usando uma tabela temporária
 
 Kamil Kosno apresentou algumas – duas com suas ideias originais e duas variações das soluções de Alejandro e Radek. A primeira solução de Kamil usa uma tabela temporária indexada. Muitas vezes, mesmo que você não tenha permissão para criar índices de suporte nas tabelas originais, você pode trabalhar com tabelas temporárias e, com tabelas temporárias, você sempre pode criar seus próprios índices. 
 
 Aqui está o código da solução completa:
 
DROP TABLE SE EXISTE #T2; SELECT MIN(coluna chave) AS coluna chave, valINTO #T2FROM dbo.T2GROUP BY val; CRIAR ÍNDICE ÚNICO 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)  
 Na Etapa 1 da solução, você armazena o keycol mínimo para cada val exclusivo em uma tabela temporária chamada #T2 e cria um índice de suporte em (val, keycol). Aqui está o código que implementa esta etapa:
 
DROP TABLE SE EXISTE #T2; SELECT MIN(coluna chave) AS coluna chave, valINTO #T2FROM dbo.T2GROUP BY val; CRIAR ÍNDICE ÚNICO idx_nc_val_key ON #T2(val, keycol); SELECIONE * DE #T2;
 
 A tabela temporária é preenchida com os seguintes dados:
 
keycol val----------- ----------1 24 33 76 118 139 1710 19
 
 Na Etapa 2 da solução, você aplica o seguinte:
 
 Para cada linha em T1, calcule os valores prev e nxt de #T2. Calcular prev como o valor máximo em #T2 que é menor ou igual a val em T1. Calcule nxt como o valor mínimo em #T2 que é maior ou igual a val em T1. 
 
 Use uma expressão CASE para calcular val2 com base na seguinte lógica:
 
 
 Quando prev ou nxt for nulo, retorne o primeiro não nulo dos dois, ou NULL se ambos forem NULL. 
 
 Quando a diferença absoluta entre val e prev for menor que a diferença absoluta entre val e nxt, retorne prev. 
 
 Quando se a diferença absoluta entre val e nxt for menor que a diferença absoluta entre val e prv, retorna nxt. 
 
 Caso contrário, se nxt for menor que prev, retorne nxt, caso contrário, retorne prev. 
 
 
 Aqui está o código que implementa esta etapa:
 
SELECT keycol AS keycol1, val AS val1, othercols AS othercols1, CASE WHEN (prev + nxt IS NULL) THEN COALESCE(prev, nxt) WHEN ABS(val - prev)  
 Este código gera a seguinte saída:
 
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
 
 Na Etapa 3 da solução, você define um CTE chamado bestvals com base na consulta da Etapa 2. Você então junta bestvals com #T2 para obter as chaves e junta o resultado com T2 para obter o restante dos dados (othercols). 
 
 Aqui está o código que implementa esta etapa:
 
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;
 
 O plano para a solução 1 de Kamil com índices de suporte é mostrado na Figura 1. 
 
 Figura 1:Plano para a solução 1 do Kamil com índices 
 
 A primeira ramificação do plano agrupa e agrega os dados de T2 e grava o resultado na tabela temporária #T2. Observe que essa ramificação usa um algoritmo Stream Aggregate pré-ordenado que depende de uma varredura ordenada do índice idx_valD_key em T2. 
 
 Aqui estão as estatísticas de desempenho para este plano:
 
tempo de execução (s):5,55, CPU (s):16,6, leituras lógicas:6.687.172
 
 O plano para a solução 1 da Kamil sem os índices de suporte é mostrado na Figura 2. 
 
 Figura 2:Plano para solução 1 do Kamil sem índices 
 
 A principal diferença entre este plano e o anterior é que a primeira ramificação do plano, que lida com a parte de agrupamento e agregação na Etapa 1, desta vez não pode extrair os dados pré-ordenados de um índice de suporte, então ele os puxa desordenadamente do cluster index em T2 e, em seguida, usa um algoritmo Hash Aggregate. 
 
 Aqui estão as estatísticas de desempenho para este plano:
 
tempo de execução:6,44, CPU:19,3, leituras lógicas:6.688.277
 
Solução de Alejandro Mesa – Usando a última técnica não nula
 
 A solução de Alejandro usa a última técnica não nula descrita aqui. 
 
 Aqui está o código completo da solução (fornecido aqui sem retornar othercols):
 
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 ENTRE UNBOUNDED PRECEDING AND 1 PRECEDING ) AS abaixo_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 E 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(abaixo_binstr, 1, 4) AS int) AS abaixo_T2_val, CAST(SUBSTRING(abaixo_binstr, 5, 4) AS int) AS abaixo_T2_keycol, CAST(SUBSTRING(above_binstr, 1, 4) AS int) AS acima_T2_val, CAST(SUBSTRING(above_binstr, 5, 4) AS int) AS acima_T2_keycol FROM R1 WHERE tid =1),R3 AS( SELECT keycol, val, COALESCE(abaixo_T2_val, above_T2 _val) AS abaixo_T2_val, COALESCE(abaixo_T2_keycol, above_T2_keycol) AS abaixo_T2_keycol, COALESCE(acima_T2_val, abaixo_T2_val) AS acima_T2_val, COALESCE(above_T2_keycol, abaixo_T2_keycol) AS above_T2_keycol FROM R2)SELECT keycol AS keycol_T2_val AS keycol1, val AS val1, CASE WHEN ) <=ABS(acima_T2_val - val) THEN abaixo_T2_keycol ELSE above_T2_keycol END AS keycol2, CASE WHEN ABS(val - abaixo_T2_val) <=ABS(acima_T2_val - val) THEN abaixo_T2_val ELSE above_T2_val END AS val2FROM R3;
 
 Na Etapa 1 da solução, você unifica as linhas de T1 (atribuindo uma coluna de resultado chamada tid a 1) com as linhas de T2 (atribuindo tid =0) e define uma tabela derivada chamada T com base no resultado. Usando a última técnica não nula, com base na ordem de val, tid, keycol, para cada linha atual, você recupera os valores da última linha tid =0 concatenados em uma coluna binária chamada abaixo_binstr. Da mesma forma, você recupera os valores da próxima linha tid =0 concatenados em uma coluna binária chamada above_binstr. 
 
 Aqui está o código que implementa esta etapa:
 
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 abaixo_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 E 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;
 
 Este código gera a seguinte saída:
 
keycol val tid abaixo_binstr acima_binstr----------- ----------- ----------- --------- --------- ------------------ 1 1 1 NULL 0X00000002000000012 1 1 NULL 0X00000002000000011 2 0 NULL 0X00000003000000044 3 0 0X0000000200000001 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
 
 Na Etapa 2 da solução, você define um CTE chamado R1 com base na consulta da Etapa 1. Você consulta R1, filtra apenas as linhas em que tid =1 e extrai os valores individuais das cadeias binárias concatenadas. 
 
 Aqui está o código que implementa esta etapa:
 
SELECT keycol, val, CAST(SUBSTRING(abaixo_binstr, 1, 4) AS int) AS abaixo_T2_val, CAST(SUBSTRING(abaixo_binstr, 5, 4) AS int) AS abaixo_T2_keycol, CAST(SUBSTRING(above_binstr, 1, 4) AS int) AS acima_T2_val, CAST(SUBSTRING(above_binstr, 5, 4) AS int) AS acima_T2_keycolFROM R1WHERE tid =1;
 
 Este código gera a seguinte saída:
 
keycol val abaixo_T2_val abaixo_T2_keycol acima_T2_val acima_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
 
 Na Etapa 3 da solução, você define um CTE chamado R2 com base na consulta da Etapa 2. Em seguida, calcula as seguintes colunas de resultado:
 
 
 below_T2_val:o primeiro não nulo entre below_T2_val e above_T2_val 
 
 below_T2_keycol:o primeiro não nulo entre below_T2_keycol e above_T2_keycol 
 
 above_T2_val:o primeiro não nulo entre above_T2_val e below_T2_val 
 
 above_T2_keycol:o primeiro não nulo entre above_T2_keycol e below_T2_keycol 
 
 
 Aqui está o código que implementa esta etapa:
 
SELECT keycol, val, COALESCE(abaixo_T2_val, above_T2_val) AS abaixo_T2_val, COALESCE(abaixo_T2_keycol, above_T2_keycol) AS abaixo_T2_keycol, COALESCE(above_T2_val, below_T2_val) AS above_T2_val, COALESCE(above_T2_keycol, below_T2_keycol) AS above_T2_keycol) 
 Este código gera a seguinte saída:
 
keycol val abaixo_T2_val abaixo_T2_keycol acima_T2_val acima_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
 
 Na Etapa 4 da solução, você define um CTE chamado R3 com base na consulta da Etapa 3. Você retorna keycol como T1_keycol e val como T1_val. Calcule a coluna de resultado T2_keycol como:se a diferença absoluta entre val e below_T2_val for menor ou igual à diferença absoluta entre above_T2_val e val, retorne abaixo_T2_keycol, caso contrário, above_T2_keycol. Calcule a coluna de resultado T2_val como:se a diferença absoluta entre val e below_T2_val for menor ou igual à diferença absoluta entre above_T2_val e val, retorne abaixo_T2_val, caso contrário, above_T2_val. 
 
 Aqui está o código que implementa esta etapa:
 
SELECT keycol AS keycol1, val AS val1, CASE WHEN ABS(val - abaixo_T2_val) <=ABS(acima_T2_val - val) THEN below_T2_keycol ELSE above_T2_keycol END AS keycol2, CASE WHEN ABS(val - abaixo_T2_val) <=ABS(acima_T2_val - val) ENTÃO abaixo_T2_val ELSE acima_T2_val END AS val2FROM R3;
 
 O plano para a solução de Alejandro com índices de suporte é mostrado na Figura 3. 
 
 Figura 3:Plano para solução de Alejandro com índices 
 
 Aqui estão as estatísticas de desempenho para este plano:
 
tempo de execução:7,8, CPU:12,6, leituras lógicas:35.886
 
 O plano para a solução de Alejandro sem índices de suporte é mostrado na Figura 4. 
 
 Figura 4:Plano para solução de Alejandro sem índices 
 
 Aqui estão as estatísticas de desempenho para este plano:
 
tempo de execução:8,19, CPU:14,8, leituras lógicas:37.091
 
 Observe que nas duas primeiras ramificações do plano na Figura 4 há duas classificações antes do operador Merge Join (Concatenação) devido à falta de índices de suporte. Essas classificações não são necessárias no plano da Figura 3, pois os dados são recuperados pré-ordenados dos índices de suporte. 
 
Variação de Kamil na solução de Alejandro
 
 Nesta solução, Kamil também contou com a última técnica não nula. Aqui está o código da solução completa:
 
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 ENTRE 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;
 
 Na Etapa 1 da solução, você define CTEs chamados all_vals e intervalos, onde você usa a última técnica não nula para identificar para cada valor em T1 (onde keycol não é NULL) intervalos de valores abaixo (anterior) e acima (nxt) de T2 ( onde keycol é nulo). 
 
 Aqui está o código que implementa esta etapa:
 
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 ENTRE 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;
 
 Este código gera a seguinte saída:
 
keycol val anterior 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 17NULLNULL7 191 199 18 20 19 NULL11 21 19 NULL
 
 Na Etapa 2 da solução, você consulta os intervalos de CTE e filtra apenas as linhas em que keycol não é nulo. Você retorna as colunas keycol e val de T1 como keycol1 e val1, respectivamente. Então, entre prev e nxt, você retorna o mais próximo de val1 como val2. 
 
 Aqui está o código que implementa esta etapa:
 
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;
 
 Este código gera a seguinte saída:
 
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
 
 Na Etapa 3 da solução, você define um CTE chamado matched_vals com base na consulta da Etapa 2. Você também define uma tabela derivada chamada T2, na qual, usando números de linha particionados, você manipula a lógica de desempate para as linhas de dbo.T2. Você então junta matched_vals, o CTE T2 e a tabela T1 para lidar com a lógica de correspondência final. 
 
 Aqui está o código que implementa esta etapa:
 
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;
 
 O plano para a variação de Kamil na solução de Alejandro com índices de suporte é mostrado na Figura 5. 
 
 Figura 5:Planeje a variação de Kamil na solução de Alejandro com índices 
 
 Aqui estão as estatísticas de desempenho para este plano:
 
tempo de execução:11,5, CPU:18,3, leituras lógicas:59.218
 
 O plano para a variação de Kamil na solução de Alejandro sem índices de suporte é mostrado na Figura 6. 
 
 Figura 6:Planeje a variação de Kamil na solução de Alejandro sem índices 
 
 Aqui estão as estatísticas de desempenho para este plano:
 
tempo de execução:12,6, CPU:23,5, leituras lógicas:61.432
 
 Semelhante aos planos para a solução de Alejandro, também neste caso o plano na Figura 5 não requer classificações explícitas antes de aplicar o operador Merge Join (concatenação), pois os dados são recuperados pré-ordenados dos índices de suporte, e o plano na Figura 6 não exigem classificações explícitas, pois não há índices de suporte. 
 
Solução de Radek Celuch – Usando intervalos
 
 Radek teve uma ideia simples e bonita. Para cada valor distinto em T2.val, você calcula um intervalo que representa o intervalo de valores de T1.val que corresponderia ao T2.val atual. 
 
 Aqui está o código da solução completa:
 
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 - anterior) % 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.alto;
 
 Na Etapa 1 da solução, você consulta T2 e calcula números de linha (chame a coluna rn), particionado por val e ordenado por keycol. Você define um CTE chamado Pre1 com base nessa consulta. Você então consulta Pre1 e filtra apenas as linhas onde rn =1. Na mesma consulta, usando LAG e LEAD, você retorna para cada linha o valor da coluna val da linha anterior (chame-a de prev) e da próxima linha ( chame-o em seguida). 
 
 Aqui está o código que implementa esta etapa:
 
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;
 
 Este código gera a seguinte saída:
 
keycol val othercols anterior próximo ------- ---- ---------- ----------- ---------- -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
 
 Na Etapa 2 da solução, você define um CTE chamado Pre2 com base na consulta da Etapa 1. Você consulta Pre2 e calcula para cada linha um intervalo [baixo, alto] em que val de T1 cairia. Aqui estão os cálculos para baixo e Alto:
 
 
 baixo =ISNULL(val – (val – anterior) / 2 + (1 – (val – anterior) % 2), 0) 
 
 alto =ISNULL(val + (próximo – valor) / 2, 2147483647) 
 
 
 A verificação mod 2 no cálculo do limite inferior é usada para atender ao requisito T2.val inferior, e o filtro de número de linha é usado para atender ao requisito T2.keycol inferior. Os valores 0 e 2147483647 são usados ​​como os limites inferior e superior extremos. 
 
 Aqui está o código que implementa esta etapa:
 
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;
 
 Este código gera a seguinte saída:
 
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
 
 Na Etapa 3 da solução, você define um CTE chamado T2 com base na consulta da Etapa 2. Em seguida, une a tabela T1 com as linhas correspondentes CTE T2 com base em val de T1 dentro do intervalo [baixo, alto] em T2. 
 
 Aqui está o código que implementa esta etapa:
 
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 ENTRE T2.low AND T2.high;
 
 O plano para a solução da Radek com índices de suporte é mostrado na Figura 7. 
 
 Figura 7:plano para solução do Radek com índices 
 
 Aqui estão as estatísticas de desempenho para este plano:
 
tempo de execução:10,6, CPU:7,63, leituras lógicas:3.193.125
 
 O plano para a solução da Radek sem índices de suporte é mostrado na Figura 8. 
 
 Figura 8:Plano para solução do Radek sem índices 
 
 Aqui estão as estatísticas de desempenho para este plano:
 
tempo de execução:18.1, CPU:27.4, leituras lógicas:5.827.360
 
 Aqui a diferença de desempenho entre os dois planos é bastante substancial. O plano da Figura 8 requer uma classificação preliminar antes do cálculo dos números das linhas, o que o plano da Figura 7 não faz. Mais importante, para corresponder cada intervalo com as respectivas linhas de T1, o plano na Figura 8 cria um Spool de Índice essencialmente como uma alternativa ao índice ausente, enquanto o plano na Figura 7 simplesmente usa o índice existente idx_val_key em T1. Essa é a principal razão para as grandes diferenças em todas as medidas de desempenho. Ainda assim, o desempenho sem índices de suporte é razoável. 
 
Variação de Kamil na solução de Radek
 
 Kamil apresentou uma variação da solução de Radek. Aqui está o código da solução completa:
 
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. 
 
Conclusão
 
 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!