O desafio

 SET NOCOUNT ON; IF DB_ID('testdb') IS NULL CREATE DATABASE testdb; VAI USAR testdb; DROP TABLE SE EXISTE 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) );

 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); 
 Lembre-se que o desafio era combinar para cada linha de T1 a linha de T2 onde a diferença absoluta entre T2.val e T1.val é a menor. Em caso de empate, você deve usar val ascendente, keycol ordem ascendente como desempate. 
 
 Aqui está o resultado desejado para os dados de amostra fornecidos:
 
 keycol1 val1 othercols1 keycol2 val2 othercols2 ----------- ----------- ---------- --------- -- ----------- ---------- 1 1 0xAA 1 2 0xBB 2 1 0xAA 1 2 0xBB 3 3 0xAA 4 3 0xBB 4 3 0xAA 4 3 0xBB 5 5 0xAA 4 3 0xBB 6 8 0xAA 3 7 0xBB 7 13 0xAA 8 13 0xBB 8 16 0xAA 9 17 0xBB 9 18 0xAA 9 17 0xBB 10 20 0xAA 10 19 0xBB 11 21 0xAA 10 19 0xBB
 
 Para verificar o desempenho de suas soluções, você precisa de conjuntos maiores de dados de amostra. Você primeiro cria a função auxiliar GetNums, que gera uma sequência de inteiros em um intervalo solicitado, usando o seguinte código:
 
 DROP FUNÇÃO SE EXISTE dbo.GetNums; GO CREATE OR ALTER FUNCTION dbo.GetNums(@low AS BIGINT, @high AS BIGINT) RETURNS TABLE AS RETURN WITH L0 AS (SELECT c FROM (SELECT 1 UNION ALL SELECT 1) AS D(c)), L1 AS (SELECT 1 AS c DE L0 COMO CROSS JOIN L0 AS B), L2 AS (SELECIONE 1 AS c DE L1 COMO CROSS JOIN L1 AS B), L3 AS (SELECIONE 1 AS c DE L2 COMO 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; IR
 
 Em seguida, você preenche T1 e T2 usando o código a seguir, ajustando os parâmetros que indicam os números de linhas e os valores máximos com base em suas necessidades:
 
 DECLARE @numrowsT1 AS INT =1000000, @maxvalT1 AS INT =10000000, @numrowsT2 AS INT =1000000, @maxvalT2 AS INT =10000000; TRUNCATE TABLE dbo.T1; TRUNCATE TABLE dbo.T2; INSERT INTO dbo.T1 WITH(TABLOCK) (val) SELECT ABS(CHECKSUM(NEWID())) % @maxvalT1 + 1 AS val FROM dbo.GetNums(1, @numrowsT1) AS Nums; INSERT INTO dbo.T2 WITH(TABLOCK) (val) SELECT ABS(CHECKSUM(NEWID())) % @maxvalT2 + 1 AS val FROM dbo.GetNums(1, @numrowsT2) AS Nums;
 
 Neste exemplo, você está preenchendo as tabelas com 1.000.000 linhas cada, com valores no intervalo de 1 a 10.000.000 na coluna val (baixa densidade). 
 
Solução 3, usando um cursor e uma variável de tabela baseada em disco
 
 Uma solução iterativa eficiente para nosso desafio de correspondência mais próxima é baseada em um algoritmo semelhante ao algoritmo Merge join. A ideia é aplicar apenas um passe ordenado em cada tabela usando cursores, avaliando os elementos de ordenação e desempate em cada rodada para decidir de que lado avançar e combinando as linhas ao longo do caminho. 
 
 A passagem ordenada em cada tabela certamente se beneficiará do suporte a índices, mas a implicação de não tê-los é que a classificação explícita ocorrerá. Isso significa que a parte de classificação incorrerá em escala n log n, mas isso é muito menos grave do que a escala quadrática que você obtém da Solução 2 em circunstâncias semelhantes. 
 
 Além disso, o desempenho das soluções 1 e 2 foi afetado pela densidade da coluna val. Com maior densidade, o plano aplicou menos religações. Por outro lado, como as soluções iterativas realizam apenas uma passagem em cada uma das entradas, a densidade da coluna val não é um fator que afeta o desempenho. 
 
 Use o código a seguir para criar índices de suporte:
 
 CRIAR ÍNDICE idx_val_key ON dbo.T1(val, keycol) INCLUDE(othercols); CREATE INDEX idx_val_key ON dbo.T2(val, keycol) INCLUDE(othercols);
 
 Certifique-se de testar as soluções com e sem esses índices. 
 
 Aqui está o código completo para a Solução 3:
 
 SET NOCOUNT ON; INICIAR TRAN; DECLARE @keycol1 AS INT, @val1 AS INT, @othercols1 AS BINARY(100), @keycol2 AS INT, @val2 AS INT, @othercols2 AS BINARY(100), @prevkeycol2 AS INT, @prevval2 AS INT, @prevothercols2 AS BINARY(100), @C1 AS CURSOR, @C2 AS CURSOR, @C1fetch_status AS INT, @C2fetch_status AS INT; DECLARE @Result AS TABLE ( keycol1 INT NOT NULL PRIMARY KEY, val1 INT NOT NULL, othercols1 BINARY(100) NOT NULL, keycol2 INT NULL, val2 INT NULL, othercols2 BINARY(100) NULL ); SET @C1 =CURSOR FORWARD_ONLY STATIC READ_ONLY FOR SELECT keycol, val, othercols FROM dbo.T1 ORDER BY val, keycol; SET @C2 =CURSOR FORWARD_ONLY STATIC READ_ONLY FOR SELECT keycol, val, othercols FROM dbo.T2 ORDER BY val, keycol; ABRIR @C1; ABRIR @C2; FETCH NEXT FROM @C2 INTO @keycol2, @val2, @othercols2; SET @C2fetch_status =@@fetch_status; SELECT @prevkeycol2 =@keycol2, @prevval2 =@val2, @prevothercols2 =@othercols2; FETCH NEXT FROM @C1 INTO @keycol1, @val1, @othercols1; SET @C1fetch_status =@@fetch_status; WHILE @C1fetch_status =0 BEGIN IF @val1 <=@val2 OR @C2fetch_status <> 0 BEGIN IF ABS(@val1 - @val2)  @prevval2 SELECT @prevkeycol2 =@keycol2, @prevval2 =@val2, @prevothercols2 =@othercols2; FETCH NEXT FROM @C2 INTO @keycol2, @val2, @othercols2; SET @C2fetch_status =@@fetch_status; FIM; FIM; SELECT keycol1, val1, SUBSTRING(othercols1, 1, 1) AS othercols1, keycol2, val2, SUBSTRING(othercols2, 1, 1) AS othercols2 FROM @Result; COMMIT TRAN;
 
 O código usa uma variável de tabela chamada @Result para armazenar as correspondências e, eventualmente, as retorna consultando a variável de tabela. Observe que o código executa o trabalho em uma transação para reduzir o log. 
 
 O código usa variáveis ​​de cursor chamadas @C1 e @C2 para percorrer as linhas em T1 e T2, respectivamente, em ambos os casos ordenados por val, keycol. As variáveis ​​locais são usadas para armazenar os valores de linha atuais de cada cursor (@keycol1, @val1 e @othercols1 para @C1 e @keycol2, @val2 e @othercols2 para @C2). Variáveis ​​locais adicionais armazenam os valores de linha anteriores de @C2 (@prevkeycol2, @prevval2 e @prevothercols2). As variáveis ​​@C1fetch_status e @C2fetch_status guardam o status da última busca do respectivo cursor. 
 
 Após declarar e abrir os dois cursores, o código busca uma linha de cada cursor nas respectivas variáveis ​​locais e inicialmente armazena os valores da linha atual de @C2 também nas variáveis ​​de linha anteriores. O código então entra em um loop que continua em execução enquanto a última busca de @C1 foi bem-sucedida (@C1fetch_status =0). O corpo do loop aplica o seguinte pseudocódigo em cada rodada:
 
 Se @val1 <=@val2 ou atingiu o final de @C2 Begin Se a diferença absoluta entre @val1 e @val2 for menor que entre @val1 e @prevval2 Adicionar linha a @Result com valores de linha atuais de @C1 e linha atual valores de @C2 Else Adiciona linha a @Result com valores de linha atuais de @C1 e valores de linha anteriores de @C2 Busca a próxima linha de @C1 End Else se a última busca de @C2 foi bem-sucedida Begin If @val2> @prevval2 Definir variáveis ​​mantendo Valores de linha anteriores de @C2 para valores de variáveis ​​de linha atuais Buscar próxima linha de @C2 End
 
 O código então simplesmente consulta a variável de tabela @Result para retornar todas as correspondências. 
 
 Usando os grandes conjuntos de dados de amostra (1.000.000 de linhas em cada tabela), com a indexação ideal, essa solução levou 38 segundos para ser concluída em meu sistema e executou 28.240 leituras lógicas. Claro, a escala desta solução é então linear. Sem a indexação ideal, levou 40 segundos para ser concluído (apenas 2 segundos extras!) e executou 29.519 leituras lógicas. A parte de classificação nesta solução tem escala n log n. 
 
Solução 4, usando um cursor e uma variável de tabela com otimização de memória
 
 Na tentativa de melhorar o desempenho da abordagem iterativa, uma coisa que você pode tentar é substituir o uso da variável de tabela baseada em disco por uma com otimização de memória. Como a solução envolve gravar 1.000.000 de linhas na variável de tabela, isso pode resultar em uma melhoria não desprezível. 
 
 Primeiro, você precisa habilitar o OLTP na memória no banco de dados criando um grupo de arquivos marcado como CONTAINS MEMORY_OPTIMIZED_DATA e dentro dele um contêiner que aponta para uma pasta no sistema de arquivos. Supondo que você tenha criado antecipadamente uma pasta pai chamada C:\IMOLTP\, use o seguinte código para aplicar essas duas etapas:
 
 ALTER DATABASE testdb ADD FILEGROUP testdb_MO CONTÉM MEMORY_OPTIMIZED_DATA; ALTER DATABASE testdb ADD FILE ( NAME =testdb_dir, FILENAME ='C:\IMOLTP\testdb_dir' ) TO FILEGROUP testdb_MO;
 
 A próxima etapa é criar um tipo de tabela com otimização de memória como modelo para nossa variável de tabela executando o seguinte código:
 
 DROP TYPE SE EXISTE dbo.TYPE_closestmatch; GO CREATE TYPE dbo.TYPE_closestmatch AS TABLE ( keycol1 INT NOT NULL PRIMARY KEY NONCLUSTERED, val1 INT NOT NULL, othercols1 BINARY(100) NOT NULL, keycol2 INT NULL, val2 INT NULL, othercols2 BINARY(100) NULL ) WITH (MEMORY_OPTIMIZED =ON );
 
 Então, em vez da declaração original da variável de tabela @Result, você usaria o seguinte código:
 
 DECLARE @Result AS dbo.TYPE_closestmatch;
 
 Aqui está o código completo da solução:
 
 SET NOCOUNT ON; USE testdb; INICIAR TRAN; DECLARE @keycol1 AS INT, @val1 AS INT, @othercols1 AS BINARY(100), @keycol2 AS INT, @val2 AS INT, @othercols2 AS BINARY(100), @prevkeycol2 AS INT, @prevval2 AS INT, @prevothercols2 AS BINARY(100), @C1 AS CURSOR, @C2 AS CURSOR, @C1fetch_status AS INT, @C2fetch_status AS INT; DECLARE @Result AS dbo.TYPE_closestmatch; SET @C1 =CURSOR FORWARD_ONLY STATIC READ_ONLY FOR SELECT keycol, val, othercols FROM dbo.T1 ORDER BY val, keycol; SET @C2 =CURSOR FORWARD_ONLY STATIC READ_ONLY FOR SELECT keycol, val, othercols FROM dbo.T2 ORDER BY val, keycol; ABRIR @C1; ABRIR @C2; FETCH NEXT FROM @C2 INTO @keycol2, @val2, @othercols2; SET @C2fetch_status =@@fetch_status; SELECT @prevkeycol2 =@keycol2, @prevval2 =@val2, @prevothercols2 =@othercols2; FETCH NEXT FROM @C1 INTO @keycol1, @val1, @othercols1; SET @C1fetch_status =@@fetch_status; WHILE @C1fetch_status =0 BEGIN IF @val1 <=@val2 OR @C2fetch_status <> 0 BEGIN IF ABS(@val1 - @val2)  @prevval2 SELECT @prevkeycol2 =@keycol2, @prevval2 =@val2, @prevothercols2 =@othercols2; FETCH NEXT FROM @C2 INTO @keycol2, @val2, @othercols2; SET @C2fetch_status =@@fetch_status; FIM; FIM; SELECT keycol1, val1, SUBSTRING(othercols1, 1, 1) AS othercols1, keycol2, val2, SUBSTRING(othercols2, 1, 1) AS othercols2 FROM @Result; COMMIT TRAN;
 
 Com a indexação ideal em vigor, essa solução levou 27 segundos para ser concluída na minha máquina (em comparação com 38 segundos com a variável de tabela baseada em disco) e sem a indexação ideal, levou 29 segundos para ser concluída (em comparação com 40 segundos). Isso é cerca de 30% de redução no tempo de execução. 
 
Solução 5, usando SQL CLR
 
 Outra maneira de melhorar ainda mais o desempenho da abordagem iterativa é implementar a solução usando SQL CLR, já que a maior parte da sobrecarga da solução T-SQL se deve às ineficiências da busca do cursor e do loop no T-SQL. 
 
 Aqui está o código completo da solução implementando o mesmo algoritmo que usei nas Soluções 3 e 4 com C#, usando objetos SqlDataReader em vez de cursores T-SQL:
 
 usando Sistema; usando System.Data; usando System.Data.SqlClient; usando System.Data.SqlTypes; usando Microsoft.SqlServer.Server; public parcial class ClosestMatch { [SqlProcedure] public static void GetClosestMatches() { using (SqlConnection conn =new SqlConnection("data source=MyServer\\MyInstance;Database=testdb;Trusted_Connection=True;MultipleActiveResultSets=true;")) { SqlCommand comm1 =new SqlCommand(); SqlCommand comm2 =new SqlCommand(); comm1.Connection =conn; comm2.Connection =conn; comm1.CommandText ="SELECT keycol, val, othercols FROM dbo.T1 ORDER BY val, keycol;"; comm2.CommandText ="SELECT keycol, val, othercols FROM dbo.T2 ORDER BY val, keycol;"; colunas SqlMetaData[] =new SqlMetaData[6]; colunas[0] =new SqlMetaData("keycol1", SqlDbType.Int); colunas[1] =new SqlMetaData("val1", SqlDbType.Int); colunas[2] =new SqlMetaData("othercols1", SqlDbType.Binary, 100); colunas[3] =new SqlMetaData("keycol2", SqlDbType.Int); colunas[4] =new SqlMetaData("val2", SqlDbType.Int); colunas[5] =new SqlMetaData("othercols2", SqlDbType.Binary, 100); registro SqlDataRecord =new SqlDataRecord(colunas); SqlContext.Pipe.SendResultsStart(record); conn.Open(); SqlDataReader leitor1 =comm1.ExecuteReader(); SqlDataReader leitor2 =comm2.ExecuteReader(); SqlInt32 keycol1 =SqlInt32.Null; SqlInt32 val1 =SqlInt32.Null; SqlBinary othercols1 =SqlBinary.Null; SqlInt32 keycol2 =SqlInt32.Null; SqlInt32 val2 =SqlInt32.Null; SqlBinary othercols2 =SqlBinary.Null; SqlInt32 prevkeycol2 =SqlInt32.Null; SqlInt32 prevval2 =SqlInt32.Null; SqlBinary prevothercols2 =SqlBinary.Null; Boolean reader2foundrow =reader2.Read(); if (reader2foundrow) { keycol2 =reader2.GetSqlInt32(0); val2 =leitor2.GetSqlInt32(1); othercols2 =leitor2.GetSqlBinary(2); prevkeycol2 =keycol2; val2 =val2; prevothercols2 =othercols2; } Boolean reader1foundrow =reader1.Read(); if (reader1foundrow) { keycol1 =reader1.GetSqlInt32(0); val1 =leitor1.GetSqlInt32(1); othercols1 =leitor1.GetSqlBinary(2); } while (reader1foundrow) { if (val1 <=val2 || !reader2foundrow) { if (Math.Abs((int)(val1 - val2))  prevval2) { prevkeycol2 =keycol2; val2 =val2; prevothercols2 =othercols2; } reader2foundrow =reader2.Read(); if (reader2foundrow) { keycol2 =reader2.GetSqlInt32(0); val2 =leitor2.GetSqlInt32(1); othercols2 =leitor2.GetSqlBinary(2); } } } SqlContext.Pipe.SendResultsEnd(); } } }
 
 Para se conectar ao banco de dados, você normalmente usaria a opção "context connection=true" em vez de uma string de conexão completa. Infelizmente, essa opção não está disponível quando você precisa trabalhar com vários conjuntos de resultados ativos. Nossa solução emulando trabalho paralelo com dois cursores usando dois objetos SqlDataReader e, portanto, você precisa de uma string de conexão completa, com a opção MultipleActiveResultSets=true. Aqui está a string de conexão completa:
 
 "fonte de dados=MyServer\\MyInstance;Database=testdb;Trusted_Connection=True;MultipleActiveResultSets=true;"
 
 É claro que, no seu caso, você precisaria substituir MyServer\\MyInstance pelos nomes do servidor e da instância (se relevante). 
 
 Além disso, o fato de você não usar "context connection=true" em vez de uma string de conexão explícita significa que o assembly precisa acessar um recurso externo e, portanto, ser confiável. Normalmente, você conseguiria isso assinando-o com um certificado ou uma chave assimétrica que tenha um logon correspondente com a permissão correta ou na lista de permissões usando o procedimento sp_add_trusted_assembly. Para simplificar, definirei a opção de banco de dados TRUSTWORTHY como ON e especificarei o conjunto de permissões EXTERNAL_ACCESS ao criar o assembly. O código a seguir implanta a solução no banco de dados:
 
 EXEC sys.sp_configure 'avançado', 1; RECONFIGURAR; EXEC sys.sp_configure 'clr habilitado', 1; EXEC sys.sp_configure 'clr strict security', 0; RECONFIGURAR; EXEC sys.sp_configure 'avançado', 0; RECONFIGURAR; ALTER DATABASE testdb SET TRUSTWORTHY ON; USE testdb; DROP PROC SE EXISTE dbo.GetClosestMatches; DROP ASSEMBLY SE EXISTE ClosestMatch; CRIAR ASSEMBLY ClosestMatch DE 'C:\ClosestMatch\ClosestMatch\bin\Debug\ClosestMatch.dll' COM PERMISSION_SET =EXTERNAL_ACCESS; GO CREATE PROCEDURE dbo.GetClosestMatches AS EXTERNAL NAME ClosestMatch.ClosestMatch.GetClosestMatches;
 
 O código habilita o CLR na instância, desabilita a opção de segurança restrita do CLR, define a opção de banco de dados TRUSTWORTHY como ON, cria o assembly e cria o procedimento GetClosestMatches. 
 
 Use o código a seguir para testar o procedimento armazenado:
 
 EXEC dbo.GetClosestMatches;
 
 A solução CLR levou 8 segundos para ser concluída no meu sistema com indexação ideal e 9 segundos sem. Essa é uma melhoria de desempenho bastante impressionante em comparação com todas as outras soluções - relacionais e iterativas. 
 
Conclusão
 
 As soluções iterativas são tipicamente desaprovadas na comunidade SQL, pois não seguem o modelo relacional. A realidade, porém, é que às vezes você não consegue criar soluções relacionais de bom desempenho e o desempenho é uma prioridade. Usando uma abordagem iterativa, você não está limitado aos algoritmos aos quais o otimizador do SQL Server tem acesso, mas pode implementar qualquer algoritmo que desejar. Conforme demonstrado neste artigo, usando um algoritmo semelhante a mesclagem, você conseguiu realizar a tarefa com uma única passagem ordenada em cada uma das entradas. Usando cursores T-SQL e uma variável de tabela baseada em disco, você obteve desempenho e dimensionamento razoáveis. Você conseguiu melhorar o desempenho em cerca de 30% alternando para uma variável de tabela com otimização de memória e significativamente mais usando SQL CLR.