I've searched far and wide for information on why sampled statistics are less accurate, and broadly speaking every question has always been explained with the following generalizations:
- sampled are always less accurate than fullscan
- skewed data causes less accurate sampled statistics, compared to evenly distributed data
Well, I'm specifically asking - and hopefully answering based on my own findings - why sampled statistics become consistently less accurate as a table grows, when the extent to which the data is skewed never really changes. The only thing that seems to change over time is that the accuracy of the statistics creeps ever further downwards.
Anyway, the answer - I think there is a missing step in statistics calculation, based on performing that missing step manually and consistently achieving a greatly improved histogram accuracy. I'll include a script at the end of this post which I'm using to display the overall accuracy of DISTINCT_RANGE_ROWS and AVG_RANGE_ROWS compared to the actual data in the tables, along with similar values after the 'correction' is applied, and a second result containing the current histogram to the left and my 'corrected' version to the right of it.
The missing step, I think, is a computation on the DISTINCT_RANGE_ROWS column, which affects a subsequent computation on AVG_RANGE_ROWS. It seems that DISTINCT_RANGE_ROWS is always about as artificially small as AVG_RANGE_ROWS is artificially large. If I copy out all of the EQ_ROWS values, arrange them in ascending order, and compute the difference between each value and the next, then after the first few rows the majority of the histogram increments by the exact same value each time. That value? Almost identical to total rows / rows sampled, but slightly lower. Further, if I divide the EQ_ROWS field by that value then we end up with almost exact integers, which must be the number of occurrences of each RANGE_HI_KEY in the sample of data used. Here's a quick example few rows from an earlier attempt to explain this to some uninterested colleagues...
| EQ_ROWS_VALUE | MULTIPLIER | Number of entries in the sampled 1% of data |
|---|---|---|
| 2084.409 | 94.746 | 21.99996834 |
| 2179.155 | 94.746 | 22.99996834 |
| 2273.901 | 94.746 | 23.99996834 |
| 2368.647 | 94.746 | 24.99996834 |
That multiplier isn't exactly rows / rows_sampled (was 95.1 in that example), and those resulting values aren't exact integers, but they're close enough for me. So SQL Server is doing some wizardry, no doubt to allow for more types of data distribution, but eventually landing on a consistent multiplier value to extrapolate the EQ_ROWS column. So, why isn't the same true for DISTINCT_RANGE_ROWS? In fact, why does it appear that no computation whatsoever has been performed against DISTINCT_RANGE_ROWS?
From here:
If the histogram has been built using a sample rather than fullscan, then the values of
equal_rows,range_rows, anddistinct_range_rowsandaverage_range_rowsare estimated, and therefore they do not need to be whole integers.”
So why is DISTINCT_RANGE_ROWS always integers??. My colleagues and I have been unable to find a single non-integer value in DISTINCT_RANGE_ROWS across dozens of customer systems. This is crucial because as I mentioned before, the extent to which DISTINCT_RANGE_ROWS is too small is roughly the same extent to which AVG_RANGE_ROWS is too large. It seems as if its failing to extrapolate the DISTINCT_RANGE_ROWS by the multiplier it used on EQ_ROWS, and then extrapolating AVG_RANGE_ROWS up to far too high a value to compensate. If the same number of answers are split between only 1/10 as many form sessions then we need ten times as many answers per session for the numbers to add up, right? Who cares if that triggers a cut off point where seeks become scans and systems go down...
If I multiply the total number of DISTINCT_RANGE_ROWS by rows/rows_sampled, and divide AVG_RANGE_ROWS by rows/rows_sampled, then the resulting histogram is much more accurate, on the tables I most often see scans against on the systems I support. NOTE: This is only the case on certain indexes! It has to do with data density, and generally I think the density needs to be small enough that the statistics sample will only ever pick up a small % of the unique IDs. Whatever SQL does to compute these histograms seems fit for purpose on larger data densities.
Here's an example output from the script at the end of this post for a real production table out in the wild. This one is from a form headings table with 36 million rows, with the index on FormID. 10 or fewer entries per FormID on >95% of the table, a few % with 10-100 entries, with a million FormIDs appearing once and TWO entries appearing over 1,000 times. So its pretty evenly distributed data:
| rows | rows_sampled | Modifier | Sample % | Distinct_Values_Accuracy | Row_Estimates_Accuracy | Current DISTINCT_RANGE_ROWS | Actual | Corrected | Current 'Average' AVG_RANGE_ROWS | Actual_ | Corrected_ |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 35979567 | 319861 | 112.49 | 0.89 | 1.02 | 0.91 | 39320 | 3855812 | 4403840 | 1024.09 | 9.33 | 9.14 |
The script I'm using:
declare @tablename varchar(64), @indexname varchar(128), @columnname varchar(128)
, @sql varchar(max)
set @tablename = 'table'
set @indexname = 'index'
select @columnname = c.name
from sysobjects a with(nolock)
join sys.index_columns b with(nolock) on a.id=b.[object_id]
join sys.indexes b2 with(nolock) on a.id=b2.[object_id] and b.index_id=b2.index_id
join sys.columns c with(nolock) on a.id=c.[object_id] and b.column_id=c.column_id
where b.index_column_id = 1
and a.name = @tablename and b2.name = @indexname
-- show table name, index name, column name, and various details
set @sql = 'select a.name Table_Name, b2.name Index_Name, c.name Column_Name
, g.rows, g.rows_sampled
, cast(g.rows as decimal(10,2))/g.rows_sampled Modifier
, (100.0/g.rows)*g.rows_sampled [Sample %]
, (100.0/MAX(f.[count_distinct]))*SUM(d.distinct_range_rows) [Distinct_Values_Accuracy]
, (100.0/AVG(average_range_rows))*max(cast(e.count as float) / cast(f.count_distinct as float)) [Row_Estimates_Accuracy]
, SUM(d.distinct_range_rows) [Current DISTINCT_RANGE_ROWS]
, MAX(f.[count_distinct]) [Actual]
, SUM(d.distinct_range_rows * (g.rows/g.rows_sampled)) [Corrected]
, cast(AVG(average_range_rows) as decimal(10,2)) [Current ''Average'' AVG_RANGE_ROWS]
, cast(max(cast(e.count as float) / cast(f.count_distinct as float)) as decimal(10,2)) [Actual_]
, cast(AVG(average_range_rows / (g.rows/g.rows_sampled)) as decimal(10,2)) [Corrected_]
from sysobjects a with(nolock)
join sys.index_columns b with(nolock) on a.id=b.[object_id]
join sys.indexes b2 with(nolock) on a.id=b2.[object_id] and b.index_id=b2.index_id
join sys.columns c with(nolock) on a.id=c.[object_id] and b.column_id=c.column_id
outer apply sys.dm_db_stats_histogram (a.id, b2.index_id) d
outer apply (select count(*) [count] from ' + @tablename + ') as e
outer apply (select count(distinct ' + @columnname + ' ) [count_distinct] from ' + @tablename + ') as f
outer apply sys.dm_db_stats_properties (a.id, b2.index_id) g
where b.index_column_id = 1
and a.name = ''' + @tablename + ''' and b2.name = ''' + @indexname + '''
group by a.name, b2.name, c.name, g.rows, g.rows_sampled
'
print @sql
exec (@sql)
set @sql = 'select
d.step_number, d.range_high_key, d.range_rows, d.equal_rows, d.distinct_range_rows, d.average_range_rows
, d.step_number, d.range_high_key, d.range_rows, d.equal_rows, d.distinct_range_rows * (g.rows/g.rows_sampled) Modif_distinct, d.average_range_rows / (g.rows/g.rows_sampled) Modif_Avg
from sysobjects a with(nolock)
join sys.index_columns b with(nolock) on a.id=b.[object_id]
join sys.indexes b2 with(nolock) on a.id=b2.[object_id] and b.index_id=b2.index_id
join sys.columns c with(nolock) on a.id=c.[object_id] and b.column_id=c.column_id
outer apply sys.dm_db_stats_histogram (a.id, b2.index_id) d
outer apply (select count(*) [count] from ' + @tablename + ') as e
outer apply (select count(distinct ' + @columnname + ' ) [count_distinct] from ' + @tablename + ') as f
outer apply sys.dm_db_stats_properties (a.id, b2.index_id) g
where b.index_column_id = 1
and a.name = ''' + @tablename + ''' and b2.name = ''' + @indexname + '''
order by d.step_number asc
'
print @sql
exec (@sql)
This appears to be consistent across all of our customer systems from SQL 2012 through to 2019, and I'm sure it was also the case in 2008 back when that version was still supported.
Just to update this, I've been able to raise this question with Microsoft support so, although I doubt many people are keeping track of this post, watch this space! Seems likely that there really is a bug here. How on Earth did none of us notice this before?!
