Estimativa de cardinalidade fora do histograma

14

Configuração

Estou tendo problemas para entender uma estimativa de cardinalidade. Aqui está a minha configuração de teste:

  • a versão 2010 do banco de dados Stack Overflow
  • SQL Server 2017 CU15 + GDR (KB4505225) - 14.0.3192.2
  • o novo CE (nível de compatibilidade 140)

Eu tenho este proc:

USE StackOverflow2010;
GO

CREATE OR ALTER PROCEDURE #sp_PostsByCommentCount
    @CommentCount int
AS
BEGIN
    SELECT * 
    FROM dbo.Posts p
    WHERE 
        p.CommentCount = @CommentCount
    OPTION (RECOMPILE); 
END;
GO

Não há índices ou estatísticas não clusterizados na dbo.Poststabela (existe um índice clusterizado Id).

Ao solicitar um plano estimado para isso, as "linhas estimadas" dbo.Postssão 1.934,99:

EXEC #sp_PostsByCommentCount @CommentCount = 51;

O seguinte objeto estatístico foi criado automaticamente quando solicitei o plano estimado:

DBCC SHOW_STATISTICS('dbo.Posts', [_WA_Sys_00000006_0519C6AF]);

captura de tela da saída de estatísticas no SSMS

Os destaques são:

  • As estatísticas têm uma taxa de amostragem bastante baixa de 1,81% (67.796 / 3.744.192)
  • Apenas 31 etapas do histograma foram usadas
  • O valor "Toda a densidade" é 0.03030303(33 valores distintos foram amostrados)
  • O último RANGE_HI_KEYno histograma é 50, com EQ_ROWS1

Questão

Passar qualquer valor acima de 50 (até 2.147.483.647) incluindo os resultados na estimativa de linha de 1.934,99. Qual cálculo ou valor é usado para produzir essa estimativa? O estimador de cardinalidade herdado produz uma estimativa de 1 linha, a propósito.

O que eu tentei

Aqui estão algumas teorias que eu tinha, coisas que tentei ou informações adicionais que consegui descobrir ao analisar isso.

Vetor de densidade

Inicialmente, pensei que seria o vetor de densidade, o mesmo que se eu tivesse usado OPTION (OPTIMIZE FOR UNKNOWN). Mas o vetor de densidade para esse objeto de estatísticas é 3.744.192 * 0,03030303 = 113.460, então não é isso.

Eventos estendidos

Tentei executar uma sessão de evento estendido que coletou o query_optimizer_estimate_cardinalityevento (sobre o qual aprendi na postagem do blog de Paul White sobre Cardinality Estimation: Combining Density Statistics ) e recebi esses tipos de petiscos interessantes:

<CalculatorList>
  <FilterCalculator CalculatorName="CSelCalcColumnInInterval" Selectivity="-1.000" 
                    CalculatorFailed="true" TableName="[p]" ColumnName="CommentCount" />

  <FilterCalculator CalculatorName="CSelCalcAscendingKeyFilter" Selectivity="0.001" 
                    TableName="[p]" ColumnName="CommentCount" UseAverageFrequency="true" 
                    StatId="4" />
</CalculatorList>

Parece que a CSelCalcAscendingKeyFiltercalculadora foi usada (a outra diz que falhou, o que quer que isso signifique). Esta coluna não é uma chave, é única ou necessariamente é ascendente, mas é o que for.

Ao pesquisar no Google, esse termo me levou a algumas postagens no blog:

Esses posts indicam que o novo CE baseia essas estimativas fora do histograma em uma combinação do vetor de densidade e do contador de modificações do stat. Infelizmente, eu já descartei o vetor de densidade (eu acho ?!), e o contador de modificações é zero (de sys.dm_db_stats_propertiesqualquer maneira).

Sinalizadores de rastreamento

Forrest sugeriu que eu ative o TF 2363 para obter mais informações sobre o processo de estimativa. Eu acho que a coisa mais relevante nessa saída é esta:

Plan for computation:

  CSelCalcAscendingKeyFilter(avg. freq., QCOL: [p].CommentCount)

Selectivity: 0.000516798

Esta é uma descoberta (obrigado, Forrest!): Esse 0.000516798número (que parece ter sido arredondado sem ajuda no Selectivity="0.001"atributo XE acima) multiplicado pelo número de linhas da tabela é a estimativa que eu estou procurando (1.934,99).

Provavelmente estou perdendo algo óbvio, mas não consegui fazer engenharia reversa de como esse valor de seletividade é produzido dentro da CSelCalcAscendingKeyFiltercalculadora.

Josh Darnell
fonte

Respostas:

13

Com base nos meus testes, a estimativa de cardinalidade fora dos limites é simplesmente a raiz quadrada da contagem de linhas, delimitada abaixo pelo número de linhas adicionadas desde a última atualização das estatísticas e delimitada acima pela média de linhas por valor.

No seu caso, 1.934,99 = SQRT (3744192)

Testando a configuração abaixo:

--setup
USE TestDB
ALTER DATABASE [TestDB] SET AUTO_UPDATE_STATISTICS OFF
GO

DROP TABLE IF EXISTS dbo.Hist

CREATE TABLE dbo.Hist (
ID int identity primary key,
Num int
)

INSERT dbo.Hist
SELECT TOP 300
(ROW_NUMBER() OVER(ORDER BY(SELECT 1/0)))%3
FROM master..spt_values a
CROSS JOIN master..spt_values b
--Get estimated plan
--don't forget to run right after setup to auto-create stats
SELECT *
FROM dbo.Hist
WHERE Num = 1000
--gradually add rows, then rerun estimate above
INSERT dbo.Hist
SELECT TOP 100
-1
FROM master..spt_values a
--I sure hope you weren't testing this in prod (cleanup)
ALTER DATABASE [TestDB] SET AUTO_UPDATE_STATISTICS ON
GO

Surpreendentemente, estimativas de linha foram geradas a partir dessa abordagem: 20 em 400 linhas no total, 30 em 900, 40 em 1600 etc.

Depois de 10000, porém, a estimativa de linha atinge o máximo de 100, que é o número de linhas por valor nas estatísticas existentes. A adição de apenas 10 linhas definirá a estimativa para 10, pois sqrt (300)> 10.

Assim, as estimativas podem ser expressas usando esta fórmula:

Estimate = MIN(SQRT(AC), MIN(AR, MC))

Observe que se as estatísticas forem amostradas, o MC não será considerado. Então a fórmula se torna:

Estimate = MIN(SQRT(AC), AR))

Onde

  • MC é a "contagem de modificações" (número de modificações desde que as estatísticas foram criadas)
  • AC é a "cardinalidade ajustada" (número de linhas das estatísticas mais MC),
  • AR é a média de linhas por valor (número de linhas das estatísticas divididas por valores distintos na coluna)

As fórmulas para essas estimativas e outros detalhes sobre a calculadora podem ser encontradas nesta postagem do blog: Analisando estimativas da calculadora CSelCalcAscendingKeyFilter

Forrest
fonte