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); 
 Verifique o conteúdo de T1:
 
 SELECT keycol, val, SUBSTRING(othercols, 1, 1) AS othercols FROM dbo.T1 ORDER BY val, keycol;
 
 Este código gera a seguinte saída:
 
 keycol val othercols ----------- ----------- --------- 1 1 0xAA 2 1 0xAA 3 3 0xAA 4 3 0xAA 5 5 0xAA 6 8 0xAA 7 13 0xAA 8 16 0xAA 9 18 0xAA 10 20 0xAA 11 21 0xAA
 
 Verifique o conteúdo do T2:
 
 SELECT keycol, val, SUBSTRING(othercols, 1, 1) AS othercols FROM dbo.T2 ORDER BY val, keycol;
 
 Este código gera a seguinte saída:
 
 keycol val othercols ----------- ----------- --------- 1 2 0xBB 2 2 0xBB 4 3 0xBB 5 3 0xBB 3 7 0xBB 6 11 0xBB 7 11 0xBB 8 13 0xBB 9 17 0xBB 10 19 0xBB
 
 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
 
 Antes de começar a trabalhar no desafio, examine o resultado desejado e certifique-se de entender a lógica de correspondência, incluindo a lógica de desempate. Por exemplo, considere a linha em T1 em que keycol é 5 e val é 5. Essa linha tem várias correspondências mais próximas em T2:
 
 keycol val othercols ----------- ----------- --------- 4 3 0xBB 5 3 0xBB 3 7 0xBB
 
 Em todas essas linhas, a diferença absoluta entre T2.val e T1.val (5) é 2. Usando a lógica de desempate baseada na ordem val ascendente, keycol ascendente na linha mais alta aqui é aquela em que val é 3 e keycol é 4. 
 
 Você usará os pequenos conjuntos de dados de amostra para verificar a validade de suas soluções. Para verificar o desempenho, você precisa de conjuntos maiores. Use o código a seguir para criar uma função auxiliar chamada GetNums, que gera uma sequência de inteiros em um intervalo solicitado:
 
 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
 
 Use o código a seguir para preencher T1 e T2 com grandes conjuntos de dados de amostra:
 
 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;
 
 As variáveis ​​@numrowsT1 e @numrowsT2 controlam o número de linhas com as quais você deseja que as tabelas sejam preenchidas. As variáveis ​​@maxvalT1 e @maxvalT2 controlam o intervalo de valores distintos na coluna val e, portanto, afetam a densidade da coluna. O código acima preenche as tabelas com 1.000.000 de linhas cada e usa o intervalo de 1 a 10.000.000 para a coluna val em ambas as tabelas. Isso resulta em baixa densidade na coluna (grande número de valores distintos, com um pequeno número de duplicatas). O uso de valores máximos mais baixos resultará em densidade mais alta (número menor de valores distintos e, portanto, mais duplicatas). 
 
Solução 1, usando uma subconsulta TOP
 
 A solução mais simples e óbvia é provavelmente aquela que consulta T1, e usando o operador CROSS APPLY aplica uma consulta com um filtro TOP(1), ordenando as linhas pela diferença absoluta entre T1.val e T2.val, usando T2.val , T2.keycol como desempate. Segue o código da solução:
 
 SELECT T1.keycol AS keycol1, T1.val AS val1, SUBSTRING(T1.othercols, 1, 1) AS othercols1, A.keycol AS keycol2, A.val AS val2, SUBSTRING(A.othercols, 1, 1 ) AS othercols2 FROM dbo.T1 CROSS APPLY ( SELECT TOP (1) T2.* FROM dbo.T2 ORDER BY ABS(T2.val - T1.val), T2.val, T2.keycol ) AS A;
 
 Lembre-se, existem 1.000.000 de linhas em cada uma das tabelas. E a densidade da coluna val é baixa em ambas as tabelas. Infelizmente, como não há predicado de filtragem na consulta aplicada e a ordenação envolve uma expressão que manipula colunas, não há potencial aqui para criar índices de suporte. Essa consulta gera o plano na Figura 1. 
 
 Figura 1:plano para a solução 1 
 
 A entrada externa do loop varre 1.000.000 linhas de T1. A entrada interna do loop executa uma varredura completa de T2 e uma classificação TopN para cada valor T1.val distinto. Em nosso plano isso acontece 998.657 vezes, pois temos densidade muito baixa. Ele coloca as linhas em um spool de índice, chaveado por T1.val, para que possa reutilizá-las para ocorrências duplicadas de valores T1.val, mas temos muito poucas duplicatas. Este plano tem complexidade quadrática. Entre todas as execuções esperadas do branch interno do loop, espera-se que ele processe cerca de um trilhão de linhas. Ao falar sobre um grande número de linhas para uma consulta processar, quando você começa a mencionar bilhões de linhas, as pessoas já sabem que você está lidando com uma consulta cara. Normalmente, as pessoas não pronunciam termos como trilhões, a menos que estejam discutindo a dívida nacional dos EUA ou quedas no mercado de ações. Você geralmente não lida com esses números no contexto de processamento de consultas. Mas planos com complexidade quadrática podem rapidamente acabar com esses números. A execução da consulta no SSMS com Incluir estatísticas de consulta ao vivo habilitada levou 39,6 segundos para processar apenas 100 linhas de T1 no meu laptop. Isso significa que essa consulta deve levar cerca de 4,5 dias para ser concluída. A questão é:você realmente gosta de ver planos de consulta ao vivo? Poderia ser um recorde interessante do Guinness para tentar estabelecer. 
 
Solução 2, usando duas subconsultas TOP
 
 Supondo que você esteja atrás de uma solução que leve segundos, não dias, para ser concluída, aqui está uma ideia. Na expressão de tabela aplicada, unifique duas consultas TOP (1) internas — uma filtrando uma linha em que T2.val  =T1.val (ordenado por T2.val, T2.keycol). É fácil criar índices para dar suporte a essas consultas habilitando uma busca de linha única. Ainda dentro da expressão de tabela aplicada, use uma consulta TOP (1) externa em relação ao resultado de duas linhas, com base na ordem de ABS(D.val – T1.val), D.val, D.keycol. Haverá uma classificação TopN envolvida, mas será aplicada a duas linhas por vez. 
 
 Aqui estão os índices recomendados para dar suporte a esta solução:
 
 CRIAR ÍNDICE idx_val_key ON dbo.T1(val, keycol) INCLUDE(othercols); CREATE INDEX idx_val_key ON dbo.T2(val, keycol) INCLUDE(othercols); CREATE INDEX idx_valD_key ON dbo.T2(val DESC, keycol) INCLUDE(othercols);
 
 Aqui está o código completo da solução:
 
 SELECT T1.keycol AS keycol1, T1.val AS val1, SUBSTRING(T1.othercols, 1, 1) AS othercols1, A.keycol AS keycol2, A.val AS val2, SUBSTRING(A.othercols, 1, 1 ) AS othercols2 FROM dbo.T1 CROSS APPLY ( SELECT TOP (1) D.* FROM ( SELECT TOP (1) * FROM dbo.T2 WHERE T2.val =T1.val ORDER BY T2.val, T2.keycol ) AS D ORDER BY ABS(D.val - T1.val), D.val, D. keycol ) AS A;
 
 Lembre-se de que temos 1.000.000 de linhas em cada tabela, com a coluna val com valores no intervalo de 1 a 10.000.000 (baixa densidade) e índices ideais no local. 
 
 O plano para esta consulta é mostrado na Figura 2. 
 
 Figura 2:plano para a solução 2 
 
 Observe o uso ótimo dos índices em T2, resultando em um plano com escala linear. Este plano usa um spool de índice da mesma maneira que o plano anterior, ou seja, para evitar a repetição do trabalho na ramificação interna do loop para valores T1.val duplicados. Aqui estão as estatísticas de desempenho que obtive para a execução desta consulta no meu sistema:
 
 Decorrido:27,7 segundos, CPU:27,6 segundos, leituras lógicas:17.304.674
 
Solução 2, com spool desativado
 
 Você não pode deixar de se perguntar se o carretel de índice é realmente benéfico aqui. O ponto é evitar repetir o trabalho para valores duplicados de T1.val, mas em uma situação como a nossa onde temos densidade muito baixa, há muito poucas duplicatas. Isso significa que muito provavelmente o trabalho envolvido no spool é maior do que apenas repetir o trabalho para duplicatas. Há uma maneira simples de verificar isso - usando o sinalizador de rastreamento 8690, você pode desabilitar o spool no plano, assim:
 
 SELECT T1.keycol AS keycol1, T1.val AS val1, SUBSTRING(T1.othercols, 1, 1) AS othercols1, A.keycol AS keycol2, A.val AS val2, SUBSTRING(A.othercols, 1, 1 ) AS othercols2 FROM dbo.T1 CROSS APPLY ( SELECT TOP (1) D.* FROM ( SELECT TOP (1) * FROM dbo.T2 WHERE T2.val =T1.val ORDER BY T2.val, T2.keycol ) AS D ORDER BY ABS(D.val - T1.val), D.val, D. keycol ) COMO OPÇÃO(QUERYTRACEON 8690);
 
 Eu tenho o plano mostrado na Figura 3 para esta execução:
 
 Figura 3:plano para a solução 2, com spool desativado 
 
 Observe que o carretel de índice desapareceu e, desta vez, a ramificação interna do loop é executada 1.000.000 vezes. Aqui estão as estatísticas de desempenho que obtive para esta execução:
 
 Decorrido:19,18 segundos, CPU:19,17 segundos, leituras lógicas:6.042.148
 
 Isso representa uma redução de 44% no tempo de execução. 
 
Solução 2, com intervalo de valores e indexação modificados
 
 Desabilitar o spooling faz muito sentido quando você tem baixa densidade nos valores T1.val; no entanto, o spooling pode ser muito benéfico quando você tem alta densidade. Por exemplo, execute o seguinte código para repovoar T1 e T2 com a configuração de dados de amostra @maxvalT1 e @maxvalT2 para 1000 (1.000 valores distintos máximos):
 
 DECLARE @numrowsT1 AS INT =1000000, @maxvalT1 AS INT =1000, @numrowsT2 AS INT =1000000, @maxvalT2 AS INT =1000; 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;
 
 Execute novamente a Solução 2, primeiro sem o sinalizador de rastreamento:
 
 SELECT T1.keycol AS keycol1, T1.val AS val1, SUBSTRING(T1.othercols, 1, 1) AS othercols1, A.keycol AS keycol2, A.val AS val2, SUBSTRING(A.othercols, 1, 1 ) AS othercols2 FROM dbo.T1 CROSS APPLY ( SELECT TOP (1) D.* FROM ( SELECT TOP (1) * FROM dbo.T2 WHERE T2.val =T1.val ORDER BY T2.val, T2.keycol ) AS D ORDER BY ABS(D.val - T1.val), D.val, D. keycol ) AS A;
 
 O plano para esta execução é mostrado na Figura 4:
 
 Figura 4:plano para a solução 2, com intervalo de valores de 1 a 1.000 
 
 O otimizador decidiu usar um plano diferente devido à alta densidade em T1.val. Observe que o índice em T1 é verificado na ordem de chave. Assim, para cada primeira ocorrência de um valor T1.val distinto, a ramificação interna do loop é executada e o resultado é spool em um spool de tabela regular (rebind). Em seguida, para cada ocorrência que não seja a primeira do valor, é aplicado um retrocesso. Com 1.000 valores distintos, o branch interno é executado apenas 1.000 vezes. Isso resulta em excelentes estatísticas de desempenho:
 
 Decorrido:1,16 segundos, CPU:1,14 segundos, leituras lógicas:23.278
 
 Agora tente executar a solução com o spooling desabilitado:
 
 SELECT T1.keycol AS keycol1, T1.val AS val1, SUBSTRING(T1.othercols, 1, 1) AS othercols1, A.keycol AS keycol2, A.val AS val2, SUBSTRING(A.othercols, 1, 1 ) AS othercols2 FROM dbo.T1 CROSS APPLY ( SELECT TOP (1) D.* FROM ( SELECT TOP (1) * FROM dbo.T2 WHERE T2.val =T1.val ORDER BY T2.val, T2.keycol ) AS D ORDER BY ABS(D.val - T1.val), D.val, D. keycol ) COMO OPÇÃO(QUERYTRACEON 8690);
 
 Eu tenho o plano mostrado na Figura 5. 
 
 Figura 5:Plano para a Solução 2, com intervalo de valores 1 – 1.000 e spooling desabilitado  
 
 É essencialmente o mesmo plano mostrado anteriormente na Figura 3. A ramificação interna do loop é executada 1.000.000 vezes. Aqui estão as estatísticas de desempenho que obtive para esta execução:
 
 Decorrido:24,5 segundos, CPU:24,2 segundos, leituras lógicas:8.012.548
 
 Claramente, você deve ter cuidado para não desabilitar o spool quando tiver alta densidade em T1.val. 
 
 A vida é boa quando sua situação é simples o suficiente para que você possa criar índices de suporte. A realidade é que, em alguns casos, na prática, há lógica adicional suficiente na consulta, o que impede a capacidade de criar índices de suporte ideais. Nesses casos, a Solução 2 não funcionará bem. 
 
 Para demonstrar o desempenho da Solução 2 sem índices de suporte, preencha novamente T1 e T2 com a configuração de dados de amostra @maxvalT1 e @maxvalT2 para 10000000 (intervalo de valor 1 – 10M) e também remova os índices de suporte:
 
 DROP INDEX SE EXISTE idx_val_key ON dbo.T1; DROP INDEX SE EXISTE idx_val_key ON dbo.T2; DROP INDEX SE EXISTE idx_valD_key ON dbo.T2; 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;
 
 Execute novamente a Solução 2, com Incluir Estatísticas de Consulta ao Vivo habilitada no SSMS:
 
 SELECT T1.keycol AS keycol1, T1.val AS val1, SUBSTRING(T1.othercols, 1, 1) AS othercols1, A.keycol AS keycol2, A.val AS val2, SUBSTRING(A.othercols, 1, 1 ) AS othercols2 FROM dbo.T1 CROSS APPLY ( SELECT TOP (1) D.* FROM ( SELECT TOP (1) * FROM dbo.T2 WHERE T2.val =T1.val ORDER BY T2.val, T2.keycol ) AS D ORDER BY ABS(D.val - T1.val), D.val, D. keycol ) AS A;
 
 Eu tenho o plano mostrado na Figura 6 para esta consulta:
 
 Figura 6:Plano para a Solução 2, sem indexação, com intervalo de valores de 1 a 1.000.000  
 
 Você pode ver um padrão muito semelhante ao mostrado anteriormente na Figura 1, só que desta vez o plano verifica T2 duas vezes por valor T1.val distinto. Novamente, a complexidade do plano é quadrática. A execução da consulta no SSMS com Incluir estatísticas de consulta ao vivo habilitada levou 49,6 segundos para processar 100 linhas de T1 no meu laptop, o que significa que essa consulta deve levar cerca de 5,7 dias para ser concluída. É claro que isso pode significar boas notícias se você estiver tentando quebrar o recorde mundial do Guinness por assistir a um plano de consulta ao vivo. 
 
Conclusão
 
 Gostaria de agradecer a Karen Ly do RBC por me presentear com este belo desafio de correspondência mais próxima. Fiquei bastante impressionado com o código dela para lidar com isso, que incluía muita lógica extra específica para seu sistema. Neste artigo, mostrei soluções de desempenho razoável quando você pode criar índices de suporte ideais. Mas como você pode ver, nos casos em que isso não é uma opção, obviamente os tempos de execução que você obtém são abismais. Você consegue pensar em soluções que funcionarão bem mesmo sem índices de suporte ideais? Continua…