Resultados de densidade bizarra em estatísticas amostradas

Um índice NC obtém uma distribuição estatística totalmente diferente quando estimada com amostragem vs. o amostrado tendo um vetor de densidade bizarro. Isso resulta em planos de execução ruins.

Eu tenho uma tabela de ~ 27M linhas, com uma coluna FK não nula suportada por um índice não clusterizado. A tabela está agrupada em sua chave primária. Ambas as colunas são varchar.

Uma atualização de estatísticas fullscan para nossa coluna FK fornece um vetor de densidade de aparência normal:

All density Average Length  Columns
6,181983E-08    45,99747    INSTANCEELEMENTID
3,615442E-08    95,26874    INSTANCEELEMENTID, ID

Ou seja, devemos ler cerca de 1,7 linhas para cada distinto com o INSTANCELEMENTIDqual estamos nos unindo.

Uma lixeira típica do histograma se parece com isso:

RANGE_HI_KEY    RANGE_ROWS  EQ_ROWS DISTINCT_RANGE_ROWS AVG_RANGE_ROWS
FOOBAR          133053      10      71366               1,679318

No entanto, se fizermos uma atualização com amostra (usando o número de amostra padrão que é de 230k linhas para esta tabela), as coisas mudam para o bizarro:

4,773657E-06    45,99596    INSTANCEELEMENTID
3,702179E-08    95,30183    INSTANCEELEMENTID, ID

A densidade INSTANCEELEMENTIDagora é duas ordens de magnitude maior. (A densidade para ambas as colunas, no entanto, foi estimada em um valor bastante aceitável).

Uma lixeira típica do histograma agora se parece com isso;

RANGE_HI_KEY    RANGE_ROWS  EQ_ROWS     DISTINCT_RANGE_ROWS AVG_RANGE_ROWS
FOOBAR          143870,4    766,2573    1247                115,3596
ZOTZOT          131560,7    1           969                 135,7092

que é uma distribuição completamente diferente. Observe que o INSTANCEELEMENTIDnúmero mais alto de IDs associado tem 12, o número mais comum é 1. Também é muito estranho que alguns compartimentos obtenham EQ_ROWS = 1, isso acontece com cerca de 10% dos compartimentos.

Não há sorteio de linhas estranhas que possam contribuir para isso.

Estou lendo o histograma corretamente? Não parece que a amostra de alguma forma dimensionou EQ_ROWS, DISTINCT_RANGE_ROWS e AVG_RANGE_ROWS incorretamente?

A mesa é, até onde eu sei, desarrumada. Eu tentei emular o amostrador, estimando-me os valores tablesample. Contar esses resultados de maneira normal fornece resultados que concordam com a versão fullscan, não com o amostrador.

Além disso, não consegui reproduzir esse comportamento em índices agrupados.

Eu reduzi isso para isso para reproduzir:

CREATE TABLE F_VAL (
    id varchar(100) primary key,
    num_l_val int not null
)

set nocount on

declare @rowlimit integer = 20000000;

A tabela deve ser suficientemente grande para que isso seja observado. Eu já vi isso com uniqueidentifere varchar(100)mas não int.

declare @i integer = 1;

declare @r float = rand()

while @i < @rowlimit
begin
set @r = rand()
insert f_val (id,num_l_val)
values (
   cast(@i as varchar(100)) + REPLICATE('f', 40 - len(@i)),
   case when @r > 0.8 then 4 when @r > 0.5 then 3 when @r > 0.4 then 2 else 1 end
)
  set @i = @i + 1

end

create table k_val (
 id int identity primary key,
 f_val varchar(100) not null,
)

insert into k_val(f_val)
select id from F_VAL
union all select id from f_val where num_l_val - 1 = 1
union all select id from f_val where num_l_val - 2 = 1
union all select id from f_val where num_l_val - 3 = 1
order by id

create nonclustered index IX_K_VAL_F_VAL  ON K_VAL (F_VAL)

update statistics K_VAL(IX_K_VAL_F_VAL) 
dbcc show_statistics (k_val,IX_k_VAL_F_VAL)

update statistics K_VAL(IX_K_VAL_F_VAL) WITH FULLSCAN
dbcc show_statistics (k_val,IX_k_VAL_F_VAL)

Compare as duas estatísticas; aquele com amostragem agora representa um vetor de densidade diferente total e os compartimentos do histograma estão desligados. Observe que a tabela não está inclinada.

O uso intcomo tipo de dados não causa isso; o SQL Server não examina todo o ponto de dados ao usar varchar?

Vale ressaltar que o problema parece estar em escala, aumentando a taxa de amostragem.

Eu já vi esse mesmo problema de densidade em alguns dos índices não clusterizados nos maiores bancos de dados aos quais tenho acesso. Primeiro, começarei com algumas observações que fiz sobre histogramas e cálculos de densidade:

• O SQL Server pode usar a chave primária da tabela para inferir algo sobre a densidade de ambas as colunas. Isso significa que a densidade que inclui as colunas PK geralmente será muito precisa.
• O cálculo da densidade para a primeira coluna nas estatísticas é consistente com o histograma. Se o histograma não modelar bem os dados, a densidade poderá estar desativada.
• Para criar o histograma, a StatManfunção faz inferências sobre os dados que estão faltando. O comportamento pode mudar dependendo do tipo de dados da coluna.

Para uma maneira de analisar o problema, suponha que você faça uma amostra de 100 linhas de uma tabela de 10000 linhas e obtenha 100 valores distintos. Um palpite para o que os outros dados da tabela são: existem 10000 valores exclusivos. Outro palpite é que existem 100 valores distintos, mas cada um dos valores é repetido 100 vezes. O segundo palpite pode parecer irracional para você, com o qual vou concordar. No entanto, como você equilibra as duas abordagens quando os dados amostrados retornam desigualmente distribuídos? Existe um conjunto de algoritmos desenvolvidos para isso pela Microsoft contidos na StatManfunção. Os algoritmos podem não funcionar para todas as interrupções de dados e todos os níveis de amostra.

Vamos passar por um exemplo relativamente simples. Vou usar VARCHARcolunas como na sua tabela para ver o mesmo comportamento. No entanto, apenas adicionarei um valor inclinado à tabela. Estou testando no SQL Server 2016 SP1. Comece com 100 mil linhas com 100 mil valores exclusivos para a FKcoluna:

DROP TABLE IF EXISTS X_STATS_SMALL;

CREATE TABLE X_STATS_SMALL (
ID VARCHAR(10) NOT NULL, 
FK VARCHAR(10) NOT NULL,
PADDING VARCHAR(900) NOT NULL,
PRIMARY KEY (ID)
);
-- insert 100k rows
INSERT INTO X_STATS_SMALL WITH (TABLOCK)
SELECT N, N, REPLICATE('Z', 900)
FROM dbo.GetNums(100000);

CREATE INDEX IX_X_STATS_SMALL ON X_STATS_SMALL (FK);

-- get sampled stats
UPDATE STATISTICS X_STATS_SMALL IX_X_STATS_SMALL;

Aqui estão alguns exemplos das estatísticas:

╔═════════════╦════════════════╦═════════╗
║ All density ║ Average Length ║ Columns ║
╠═════════════╬════════════════╬═════════╣
║ 1.00001E-05 ║ 4.888205       ║ FK      ║
║ 1.00001E-05 ║ 9.77641        ║ FK, ID  ║
╚═════════════╩════════════════╩═════════╝

╔══════════════╦════════════╦═════════╦═════════════════════╦════════════════╗
║ RANGE_HI_KEY ║ RANGE_ROWS ║ EQ_ROWS ║ DISTINCT_RANGE_ROWS ║ AVG_RANGE_ROWS ║
╠══════════════╬════════════╬═════════╬═════════════════════╬════════════════╣
║ 1005         ║ 0          ║ 1       ║ 0                   ║ 1              ║
║ 10648        ║ 665.0898   ║ 1       ║ 664                 ║ 1.002173       ║
║ 10968        ║ 431.6008   ║ 1       ║ 432                 ║ 1              ║
║ 11182        ║ 290.0924   ║ 1       ║ 290                 ║ 1              ║
║ 1207         ║ 445.7517   ║ 1       ║ 446                 ║ 1              ║
║ ...          ║ ...        ║ ...     ║ ...                 ║ ...            ║
║ 99989        ║ 318.3941   ║ 1       ║ 318                 ║ 1              ║
╚══════════════╩════════════╩═════════╩═════════════════════╩════════════════╝

Para dados distribuídos uniformemente com um valor único por linha, obtemos uma densidade precisa, mesmo com uma VARCHARcoluna de histograma e um tamanho de amostra de 14294 linhas.

Agora vamos adicionar um valor distorcido e atualizar as estatísticas novamente:

-- add 70k rows with a FK value of '35000'
INSERT INTO X_STATS_SMALL WITH (TABLOCK)
SELECT N + 100000 , '35000',  REPLICATE('Z', 900)
FROM dbo.GetNums(70000);

UPDATE STATISTICS X_STATS_SMALL IX_X_STATS_SMALL;

Com um tamanho de amostra de 17010 linhas, a densidade da primeira coluna é menor do que deveria ser:

╔══════════════╦════════════════╦═════════╗
║ All density  ║ Average Length ║ Columns ║
╠══════════════╬════════════════╬═════════╣
║ 6.811061E-05 ║ 4.935802       ║ FK      ║
║ 5.882353E-06 ║ 10.28007       ║ FK, ID  ║
╚══════════════╩════════════════╩═════════╝

╔══════════════╦════════════╦══════════╦═════════════════════╦════════════════╗
║ RANGE_HI_KEY ║ RANGE_ROWS ║ EQ_ROWS  ║ DISTINCT_RANGE_ROWS ║ AVG_RANGE_ROWS ║
╠══════════════╬════════════╬══════════╬═════════════════════╬════════════════╣
║ 10039        ║ 0          ║ 1        ║ 0                   ║ 1              ║
║ 10978        ║ 956.9945   ║ 1        ║ 138                 ║ 6.954391       ║
║ 11472        ║ 621.0283   ║ 1        ║ 89                  ║ 6.941863       ║
║ 1179         ║ 315.6046   ║ 1        ║ 46                  ║ 6.907561       ║
║ 11909        ║ 91.62713   ║ 1        ║ 14                  ║ 6.74198        ║
║ ...          ║ ...        ║ ...      ║ ...                 ║ ...            ║
║ 35000        ║ 376.6893   ║ 69195.05 ║ 54                  ║ 6.918834       ║
║ ...          ║ ...        ║ ...      ║ ...                 ║ ...            ║
║ 99966        ║ 325.7854   ║ 1        ║ 47                  ║ 6.909731       ║
╚══════════════╩════════════╩══════════╩═════════════════════╩════════════════╝

É surpreendente que AVG_RANGE_ROWSseja bastante uniforme para todas as etapas em torno de 6,9, mesmo para baldes de chaves para os quais a amostra não pôde encontrar valores duplicados. Não sei por que isso é. A explicação mais provável é que o algoritmo usado para adivinhar as páginas ausentes não se dá bem com essa distribuição de dados e tamanho da amostra.

Como afirmado anteriormente, é possível calcular a densidade da coluna FK usando o histograma. A soma dos DISTINCT_RANGE_ROWSvalores de todas as etapas é 14497. Existem 179 etapas do histograma, portanto a densidade deve ser de cerca de 1 / (179 + 14497) = 0,00006813845, o que é bastante próximo do valor relatado.

Testar com uma tabela maior pode mostrar como o problema pode piorar à medida que a tabela aumenta. Desta vez, começaremos com 1 milhão de linhas:

DROP TABLE IF EXISTS X_STATS_LARGE;

CREATE TABLE X_STATS_LARGE (
ID VARCHAR(10) NOT NULL,
FK VARCHAR(10) NOT NULL,
PADDING VARCHAR(900) NOT NULL,
PRIMARY KEY (ID));

INSERT INTO X_STATS_LARGE WITH (TABLOCK)
SELECT N, N, REPLICATE('Z', 900)
FROM dbo.Getnums(1000000);

CREATE INDEX IX_X_STATS_LARGE ON X_STATS_LARGE (FK);

-- get sampled stats
UPDATE STATISTICS X_STATS_LARGE IX_X_STATS_LARGE;

O objeto de estatísticas ainda não é interessante. A densidade de FKé 1.025289E-06, que é quase exata (1.0E-06).

Agora vamos adicionar um valor distorcido e atualizar as estatísticas novamente:

INSERT INTO X_STATS_LARGE WITH (TABLOCK)
SELECT N + 1000000 , '350000',  REPLICATE('Z', 900)
FROM dbo.Getnums(700000);

UPDATE STATISTICS X_STATS_LARGE IX_X_STATS_LARGE;

Com um tamanho de amostra de 45627 linhas, a densidade da primeira coluna é pior do que antes:

╔══════════════╦════════════════╦═════════╗
║ All density  ║ Average Length ║ Columns ║
╠══════════════╬════════════════╬═════════╣
║ 2.60051E-05  ║ 5.93563        ║ FK      ║
║ 5.932542E-07 ║ 12.28485       ║ FK, ID  ║
╚══════════════╩════════════════╩═════════╝

╔══════════════╦════════════╦═════════╦═════════════════════╦════════════════╗
║ RANGE_HI_KEY ║ RANGE_ROWS ║ EQ_ROWS ║ DISTINCT_RANGE_ROWS ║ AVG_RANGE_ROWS ║
╠══════════════╬════════════╬═════════╬═════════════════════╬════════════════╣
║ 100023       ║ 0          ║ 1       ║ 0                   ║ 1              ║
║ 107142       ║ 8008.354   ║ 1       ║ 306                 ║ 26.17787       ║
║ 110529       ║ 4361.357   ║ 1       ║ 168                 ║ 26.02392       ║
║ 114558       ║ 3722.193   ║ 1       ║ 143                 ║ 26.01217       ║
║ 116696       ║ 2556.658   ║ 1       ║ 98                  ║ 25.97568       ║
║ ...          ║ ...        ║ ...     ║ ...                 ║ ...            ║
║ 350000       ║ 5000.522   ║ 700435  ║ 192                 ║ 26.03268       ║
║ ...          ║ ...        ║ ...     ║ ...                 ║ ...            ║
║ 999956       ║ 2406.266   ║ 1       ║ 93                  ║ 25.96841       ║
╚══════════════╩════════════╩═════════╩═════════════════════╩════════════════╝

AVG_RANGE_ROWSé até 26. Curiosamente, se eu alterar o tamanho da amostra para 170100 linhas (10X na outra tabela), o valor médio de AVG_RANGE_ROWSserá novamente 6,9. À medida que sua tabela aumenta, o SQL Server seleciona um tamanho de amostra menor, o que significa que ele precisa fazer palpites sobre uma porcentagem maior de páginas na tabela. Isso pode exagerar os problemas estatísticos para certos tipos de distorção de dados.

Em conclusão, é importante lembrar que o SQL Server não calcula a densidade assim:

SELECT COUNT(DISTINCT FK) * 1700000. / COUNT(*) -- 1071198.9 distinct values for one run
FROM X_STATS_LARGE TABLESAMPLE (45627 ROWS);

O que para algumas distribuições de dados será muito preciso. Em vez disso, usa algoritmos não documentados . Na sua pergunta, você disse que seus dados não estavam distorcidos, mas o INSTANCEELEMENTIDvalor com o maior número de IDs associados tem 12 e o número mais comum é 1. Para os fins dos algoritmos usados ​​por eles, Statmanesses dados podem ser distorcidos.

Nesse ponto, não há nada que você possa fazer, exceto reunir estatísticas com uma taxa de amostragem mais alta. Uma estratégia comum é reunir estatísticas com FULLSCANe NORECOMPUTE. Você pode atualizar as estatísticas com um trabalho em qualquer intervalo que faça sentido para a sua taxa de alteração de dados. Na minha experiência, uma FULLSCANatualização não é tão ruim quanto a maioria das pessoas pensa, especialmente em relação a um índice. O SQL Server pode apenas verificar o índice inteiro em vez da tabela inteira (como faria em uma tabela de armazenamento de linhas em uma coluna não indexada). Além disso, no SQL Serer 2014, apenas as FULLSCANatualizações de estatísticas são feitas em paralelo, para que uma FULLSCANatualização possa terminar mais rapidamente do que algumas atualizações de amostra.