A única dificuldade é decidir como lidar com a(s) etapa(s) do histograma parcialmente coberta (s) pelo intervalo do predicado da consulta. Etapas inteiras do histograma cobertas pelo intervalo de predicados são triviais, conforme observado na pergunta.

Estimador de cardinalidade herdado

F= fração (entre 0 e 1) do intervalo de passos coberto pelo predicado da consulta.

A ideia básica é usar F(interpolação linear) para determinar quantos valores distintos intra-etapa são cobertos pelo predicado. Multiplicar esse resultado pelo número médio de linhas por valor distinto (assumindo uniformidade) e adicionar as linhas iguais de passo fornece a estimativa de cardinalidade:

Cardinalidade = EQ_ROWS + (AVG_RANGE_ROWS * F * DISTINCT_RANGE_ROWS)

A mesma fórmula é usada para >e >=no CE herdado.

Novo estimador de cardinalidade

O novo CE modifica ligeiramente o algoritmo anterior para diferenciar entre >e >=.

Tomando >primeiro, a fórmula é:

Cardinalidade = EQ_ROWS + (AVG_RANGE_ROWS * (F * (DISTINCT_RANGE_ROWS - 1)))

Pois >=é:

Cardinalidade = EQ_ROWS + (AVG_RANGE_ROWS * ((F * (DISTINCT_RANGE_ROWS - 1)) + 1))

O + 1reflete que quando a comparação envolve igualdade, uma correspondência é assumida (a suposição de inclusão).

No exemplo da pergunta, Fpode ser calculado como:

DECLARE 
    @Q datetime = '1999-10-13T10:48:38.550',
    @K1 datetime = '1999-10-13T10:47:38.550',
    @K2 datetime = '1999-10-13T10:51:19.317';

DECLARE
    @QR float = DATEDIFF(MILLISECOND, @Q, @K2), -- predicate range
    @SR float = DATEDIFF(MILLISECOND, @K1, @K2) -- whole step range

SELECT
    F = @QR / @SR;

O resultado é 0,728219019233034 . Conectando isso na fórmula >=com os outros valores conhecidos:

Cardinalidade = EQ_ROWS + (AVG_RANGE_ROWS * ((F * (DISTINCT_RANGE_ROWS - 1)) + 1))
            = 16 + (16,1956 * ((0,728219019233034 * (409 - 1)) + 1))
            = 16 + (16,1956 * ((0,728219019233034 * 408) + 1))
            = 16 + (16.1956 * (297.113359847077872 + 1))
            = 16 + (16.1956 * 298.113359847077872)
            = 16 +4828.1247307393343837632
            = 4844.1247307393343837632
            = 4844.12473073933 (para precisão flutuante)

Este resultado está de acordo com a estimativa de 4844,13 apresentada na questão.

A mesma consulta usando o CE herdado (por exemplo, usando o sinalizador de rastreamento 9481) deve produzir uma estimativa de:

Cardinalidade = EQ_ROWS + (AVG_RANGE_ROWS * F * DISTINCT_RANGE_ROWS)
            = 16 + (16,1956 * 0,728219019233034 * 409)
            = 16 +4823.72307468722
            = 4839.72307468722

Observe que a estimativa seria a mesma para >e >=usando o CE herdado.

A fórmula para estimar linhas fica um pouco complicada quando o filtro é "maior que" ou "menor que", mas é um número que você pode chegar.

Os números

Usando a etapa 193, aqui estão os números relevantes:

RANGE_ROWS = 6624

EQ_ROWS = 16

AVG_RANGE_ROWS = 16.1956

RANGE_HI_KEY da etapa anterior = 13/10/1999 10:47:38.550

RANGE_HI_KEY da etapa atual = 13/10/1999 10:51:19.317

Valor da cláusula WHERE = 13/10/1999 10:48:38.550

A fórmula

1) Encontre o ms entre as duas teclas de intervalo hi

SELECT DATEDIFF (ms, '1999-10-13 10:47:38.550', '1999-10-13 10:51:19.317')

O resultado é 220767 ms.

2) Ajuste o número de linhas

Precisamos encontrar as linhas por milissegundo, mas antes disso, temos que subtrair o AVG_RANGE_ROWS do RANGE_ROWS:

6624 - 16,1956 = 6607,8044 linhas

3) Calcule as linhas por ms com o número de linhas ajustado:

6607,8044 linhas/220767 ms = 0,0299311 linhas por ms

4) Calcule o ms entre o valor da cláusula WHERE e a etapa atual RANGE_HI_KEY

SELECT DATEDIFF (ms, '1999-10-13 10:48:38.550', '1999-10-13 10:51:19.317')

Isso nos dá 160767 ms.

5) Calcule as linhas nesta etapa com base nas linhas por segundo:

0,0299311 linhas/ms * 160767 ms = 4811,9332 linhas

6) Lembra como subtraímos o AVG_RANGE_ROWS anteriormente? Hora de adicioná-los de volta. Agora que terminamos de calcular os números relacionados às linhas por segundo, podemos adicionar com segurança o EQ_ROWS também:

4811.9332 + 16.1956 + 16 = 4844.1288

Arredondado, essa é a nossa estimativa de 4844,13.

Testando a fórmula

Não consegui encontrar nenhum artigo ou postagem de blog sobre por que o AVG_RANGE_ROWS é subtraído antes que as linhas por ms sejam calculadas. Pude confirmar que eles foram contabilizados na estimativa, mas apenas no último milissegundo - literalmente.

Usando o banco de dados WideWorldImporters , fiz alguns testes incrementais e descobri que a diminuição nas estimativas de linha era linear até o final da etapa, onde 1x AVG_RANGE_ROWS é contabilizado repentinamente.

Aqui está minha consulta de exemplo:

SELECT PickingCompletedWhen
FROM Sales.Orders
WHERE PickingCompletedWhen >= '2016-05-24 11:00:01.000000'

Atualizei as estatísticas de PickingCompletedWhen e obtive o histograma:

DBCC SHOW_STATISTICS([sales.orders], '_WA_Sys_0000000E_44CA3770')

Para ver como as linhas estimadas diminuem conforme nos aproximamos de RANGE_HI_KEY, coletei amostras ao longo da etapa. A diminuição é linear, mas se comporta como se um número de linhas igual ao valor de AVG_RANGE_ROWS simplesmente não fizesse parte da tendência... até que você atinja RANGE_HI_KEY e de repente elas caem como uma dívida não cobrada baixada. Você pode ver isso nos dados de amostra, especialmente no gráfico.

Observe o declínio constante nas linhas até atingirmos o RANGE_HI_KEY e, em seguida, BOOM, o último bloco AVG_RANGE_ROWS é repentinamente subtraído. Também é fácil identificar em um gráfico.

Para resumir, o tratamento ímpar de AVG_RANGE_ROWS torna o cálculo das estimativas de linha mais complexo, mas você sempre pode reconciliar o que o CE está fazendo.

E quanto ao recuo exponencial?

Exponential Backoff é o método que o novo (a partir do SQL Server 2014) Cardinality Estimator usa para obter melhores estimativas ao usar várias estatísticas de coluna única. Como essa pergunta era sobre uma estatística de coluna única, ela não envolve a fórmula EB.