Estimativa de cardinalidade para um predicado em uma expressão COUNT

SELECT A.City FROM Person.[Address] COMO GRUPO POR A.City HAVING COUNT_BIG(*) =1;

-- Derivado tableSELECT SQ1.CityFROM( SELECT A.City, Expr1001 =COUNT_BIG(*) FROM Person.[Address] AS A GROUP BY A.City) AS SQ1WHERE SQ1.Expr1001 =1; -- CTEWITH Grouped AS( SELECT A.City, Expr1001 =COUNT_BIG(*) FROM Person.[Address] AS A GROUP BY A.City)SELECT G.CityFROM Grouped AS GWHERE G.Expr1001 =1;

DBCC SHOW_STATISTICS ([Person.Address], Cidade) WITH DENSITY_VECTOR;

O problema

DBCC SHOW_STATISTICS ([Person.Address], Cidade) COM HISTOGRAMA;

SELECT A.City, NumRows =COUNT_BIG(*)FROM Person.[Address] AS A WHERE A.City> N'Abingdon' AND A.City  
  
 
 Existem 29 linhas com 19 valores distintos, assim como o histograma disse. Ainda assim, está claro que não temos base para avaliar a seletividade de um predicado na coluna de contagem nessa consulta. Por exemplo, HAVING COUNT_BIG(*) = 2 retornaria 5 linhas (para Alexandria, Altadena, Atlanta, Augsburg e Austin), mas não temos como determinar isso a partir do histograma. 
 
Uma suposição educada
 
 A abordagem do SQL Server é assumir que cada grupo é mais provável para conter a média geral (média) do número de linhas. Isso é simplesmente a cardinalidade dividida pelo número de valores únicos. Por exemplo, para 1.000 linhas com 20 valores exclusivos, o SQL Server assumiria que (1000/20) =50 linhas por grupo é o valor mais provável. 
 
 Voltando ao nosso exemplo original, isso significa que a coluna de contagem computada é "mais provável" de conter um valor em torno de (19614 / 575) ~=34.1113 . Desde a densidade é o recíproco do número de valores únicos, também podemos expressar isso como cardinalidade * densidade =(19614 * 0,00173913), dando um resultado muito semelhante. 
 
Distribuição
 
 Dizer que o valor médio é provavelmente só nos leva até certo ponto. Também precisamos estabelecer exatamente a probabilidade disso; e como a probabilidade muda à medida que nos afastamos do valor médio. Assumir que todos os grupos têm exatamente 34.113 linhas em nosso exemplo não seria um palpite muito "educado"! 
 
 O SQL Server lida com isso assumindo uma distribuição normal. Isso tem a forma de sino característica com a qual você já deve estar familiarizado (imagem da entrada vinculada da Wikipedia):
 
  
 
 A forma exata da distribuição normal depende de dois parâmetros :a média (µ ) e o desvio padrão (σ ). A média determina a localização do pico. O desvio padrão especifica quão "achatada" é a curva do sino. Quanto mais plana a curva, mais baixo é o pico e mais a densidade de probabilidade é distribuída sobre outros valores. 
 
 O SQL Server pode derivar a média das informações estatísticas, conforme já observado. O desvio padrão dos valores da coluna de contagem calculados é desconhecido. SQL Server estima como a raiz quadrada da média (com um pequeno ajuste detalhado mais adiante). Em nosso exemplo, isso significa que os dois parâmetros da distribuição normal são aproximadamente 34,1113 e 5,84 (a raiz quadrada). 
 
 O padrão distribuição normal (a curva vermelha no diagrama acima) é um caso especial digno de nota. Isso ocorre quando a média é zero e o desvio padrão é 1. Qualquer distribuição normal pode ser transformada na distribuição normal padrão subtraindo a média e dividindo pelo desvio padrão. 
 
Áreas e Intervalos
 
 Estamos interessados ​​em estimar a seletividade, então estamos procurando a probabilidade de que a coluna computada da contagem tenha um determinado valor (x). Essa probabilidade é dada não pelo valor do eixo y acima, mas pela área sob a curva à esquerda de x. 
 
 Para a distribuição normal com média 34,1113 e desvio padrão 5,84, a área sob a curva à esquerda de x =30 é de cerca de 0,2406:
 
  
 
 Isso corresponde à probabilidade de que a coluna de contagem calculada seja menor ou igual a 30 para nossa consulta de exemplo. 
 
 Isso leva à ideia de que, em geral, não estamos procurando a probabilidade de um valor específico, mas um intervalo . Para encontrar a probabilidade de que a contagem seja igual um valor inteiro, precisamos levar em conta o fato de que os inteiros abrangem um intervalo de tamanho 1. Como convertemos um inteiro em um intervalo é um tanto arbitrário. O SQL Server lida com isso adicionando e subtraindo 0,5 para fornecer os limites inferior e superior do intervalo. 
 
 Por exemplo, para encontrar a probabilidade de que o valor da contagem calculada seja igual a 30, precisamos subtrair a área sob a curva de distribuição normal para (x =29,5) da área para (x =30,5). O resultado corresponde à fatia para (29,5  
  
 
 A área da fatia vermelha é de aproximadamente 0,0533 . Para uma boa primeira aproximação, essa é a seletividade de um predicado count =30 em nossa consulta de teste. 
 
A Função de Distribuição Cumulativa
 
 Calcular a área sob uma distribuição normal à esquerda de um determinado valor não é simples. A fórmula geral é dada pela função de distribuição cumulativa (CDF). O problema é que o CDF não pode ser expresso em termos de funções matemáticas elementares, então métodos de aproximação numérica devem ser usados. 
 
 Como todas as distribuições normais podem ser facilmente transformadas na distribuição normal padrão (média =0, desvio padrão =1), todas as aproximações funcionam para estimar a normal padrão. Isso significa que precisamos transformar nossos limites de intervalo da distribuição normal específica apropriada para a consulta, para a distribuição normal padrão. Isso é feito, como mencionado anteriormente, subtraindo a média e dividindo pelo desvio padrão. 
 
 Se você estiver familiarizado com o Excel, talvez conheça as funções NORM.DIST e NORM.S.DIST que podem calcular CDFs (usando métodos de aproximação numérica) para uma distribuição normal específica ou a distribuição normal padrão. 
 
 Não há calculadora CDF integrada ao SQL Server, mas podemos criar uma facilmente. Dado que o CDF para a distribuição normal padrão é:
 
  
 
 …onde erf é a função de erro:
 
  
 
 Uma implementação T-SQL para obter o CDF para a distribuição normal padrão é mostrada abaixo. Ele usa uma aproximação numérica para a função de erro que é muito próximo ao que o SQL Server usa internamente:
 
CREATE PROCEDURE dbo.GetStandardNormalCDF( @x float, @cdf float OUTPUT)ASBEGIN SET NOCOUNT, XACT_ABORT ON; DECLARE @sign float, @erf float; SET @sinal =SINAL(@x); SET @x =ABS(@x) / SQRT(2); SET @erf =1; SET @erf =@erf + (0,0705230784 * @x); SET @erf =@erf + (0,0422820123 * POWER(@x, 2)); SET @erf =@erf + (0,0092705272 * POWER(@x, 3)); SET @erf =@erf + (0,0001520143 * POWER(@x, 4)); SET @erf =@erf + (0,0002765672 * POWER(@x, 5)); SET @erf =@erf + (0,0000430638 * POWER(@x, 6)); SET @erf =POWER(@erf, -16); SET @erf =1 - @erf; SET @erf =@erf * @sign; SET @cdf =0,5 * (1 + @erf);END;
 
 Um exemplo, para calcular o CDF para x =30 usando a distribuição normal para nossa consulta de teste:
 
DECLARE @cdf float;DECLARE @x float;-- HAVING COUNT_BIG(*) =xSET @x =30;-- Normalize 30 subtraindo a média-- e dividindo pelo desvio padrãoSET @x =(@x - 34.1113) / 5.84;EXECUTAR dbo.GetStandardNormalCDF @x =@x, @cdf =@cdf OUTPUT;SELECT CDF =@cdf;
 
 Observe a etapa de normalização para converter para a distribuição normal padrão. O procedimento retorna o valor 0,2407196…, que corresponde ao resultado do Excel correspondente com sete casas decimais. 
 
Detalhes e exemplos finais
 
 O código a seguir modifica nossa consulta de exemplo para produzir uma estimativa maior para o Filtro (a comparação agora é com o valor 32, que está muito mais próximo da média do que antes):
 
SELECT A.CityFROM Person.[Address] AS AGROUP BY A.CityHAVING COUNT_BIG(*) =32;
 
  
 
 A estimativa do otimizador agora é 36,7807 . 
 
 Para calcular a estimativa manualmente, primeiro precisamos abordar alguns detalhes finais:
 
 
A média usada para derivar o desvio padrão (via raiz quadrada) é dimensionada por um fator de ((valores distintos – 1) / (valores distintos) . No exemplo, o número de valores distintos é 575, portanto, o fator de escala é (574 / 575) ~=0,99826. 
Se o limite inferior do intervalo (inteiro) for 1, o SQL Server tratará o intervalo como ilimitado no lado inferior. A seletividade é igual ao CDF do limite superior do intervalo (1,5) sozinho. O limite inferior (que seria 0,5) não é usado. 
O estimador de cardinalidade (CE) legado tem lógica complexa para COUNT(*) = 1 , que não é detalhado aqui. 
Além de COUNT(*) = 1 caso, o CE legado usa a mesma lógica que o novo CE (disponível no SQL Server 2014 em diante).
 
 
 O procedimento a seguir incorpora todos os detalhes deste artigo. Requer o procedimento CDF dado anteriormente:
 
CREATE PROCEDURE dbo.GetCountPredicateEstimate( @From integer, @To integer, @Cardinality float, @Density float, @Selectivity float OUTPUT, @Estimate float OUTPUT)ASBEGIN SET NOCOUNT, XACT_ABORT ON; BEGIN TRY DECLARE @Start float, @End float, @Distinct float, @Mean float, @MeanAdj float, @Stdev float, @NormStart float, @NormEnd float, @CDFStart float, @CDFend float; -- Valida a entrada e aplica os padrões IF ISNULL(@From, 0) =0 SET @From =1; IF @From <1 RAISERROR ('@From deve ser>=1', 16, 1); IF ISNULL(@Cardinalidade, -1) <=0 RAISERROR('@Cardinalidade deve ser positiva', 16, 1); IF ISNULL(@Density, -1) <=0 RAISERROR('@Density deve ser positivo', 16, 1); IF ISNULL(@To, 0) =0 SET @To =CEILING(1 / @Density); IF @To <@From RAISERROR('@To deve ser>=@From', 16, 1); -- Converte o intervalo inteiro em intervalo SET @Start =@From - 0,5; SET @Fim =@Para + 0,5; -- Obtém o número de valores distintos SET @Distinct =1 / @Density; -- Calcula a média SET @Mean =@Cardinality * @Density; -- Ajustar média; SET @MeanAdj =@Mean * ((@Distinct - 1) / @Distinct); -- Obtém o desvio padrão (adivinhação) SET @Stdev =SQRT(@MeanAdj); -- Normaliza o intervalo SET @NormStart =(@Start - @Mean) / @Stdev; SET @NormEnd =(@End - @Mean) / @Stdev; -- Calcula CDFs EXECUTE dbo.GetStandardNormalCDF @x =@NormStart, @cdf =@CDFStart OUTPUT; EXECUTE dbo.GetStandardNormalCDF @x =@NormEnd, @cdf =@CDFEnd SAÍDA; -- Seletividade SET @Seletividade =CASE -- Início ilimitado WHEN @From =1 THEN @CDFEnd -- Fim ilimitado WHEN @To>=@Distinct THEN 1 - @CDFStart -- Intervalo normal ELSE @CDFEnd - @CDFStart END; -- Retorna estimativa de linha SET @Estimate =@Selectivity * @Distinct; END TRY BEGIN CATCH DECLARE @EM nvarchar(4000) =ERROR_MESSAGE(); IF @@TRANCOUNT> 0 TRANSAÇÃO DE ROLLBACK; RAISERROR (@EM, 16, 1); RETORNA; END CATCH;END;
 
 Agora podemos usar este procedimento para gerar uma estimativa para nossa nova consulta de teste:
 
DECLARE @Selectivity float, @Estimate float;EXECUTE dbo.GetCountPredicateEstimate @From =32, @To =32, @Cardinality =19614, @Density =0,00173913, @Selectivity =@Selectivity OUTPUT, @Estimate =@Estimate OUTPUT; SELECT Selectivity =@Selectivity, Estimate =@Estimate, Rounded =ROUND(@Estimate, 4);
 
 A saída é:
 
  
 
 Isso se compara muito bem com a estimativa de cardinalidade do otimizador de 36,7807. 
 
Exemplos de intervalo de desigualdade
 
 O procedimento pode ser usado para outros intervalos de contagem além dos testes de igualdade. Tudo o que é necessário é definir o @From e @To parâmetros para os limites do intervalo inteiro. Para especificar ilimitado, passe zero ou NULL como preferir. 
 
SELECT A.CityFROM Pessoa.[Endereço] COMO AGROUP BY A.CityHAVING COUNT_BIG(*) <50;
 
  
 
 Para usar isso com nosso procedimento, definimos @From = NULL e @To = 49 (porque 50 é excluído por menos de):
 
DECLARE @Selectivity float, @Estimate float;EXECUTE dbo.GetCountPredicateEstimate @From =NULL, @To =49, @Cardinality =19614, @Density =0,00173913, @Selectivity =@Selectivity OUTPUT, @Estimate =@Estimate OUTPUT; SELECT Selectivity =@Selectivity, Estimate =@Estimate, Rounded =ROUND(@Estimate, 4);
 
 O resultado é 572,5964:
 
  
 
 Um último exemplo usando BETWEEN :
 
SELECT A.CityFROM Pessoa.[Endereço] COMO AGROUP BY A.CityHAVING COUNT_BIG(*) ENTRE 25 E 30;
 
 A estimativa do otimizador é 
 
  
 
 Desde BETWEEN é inclusivo, passamos o procedimento @From = 25 e @To = 30 . O resultado é:
 
  
 
 Novamente, isso está de acordo com a estimativa do otimizador.