Statistics and Cardinality Estimation: Histograms, Density and the Cost of a Wrong Estimate

Version note: The T-SQL (Transact-SQL, Microsoft's dialect of SQL (Structured Query Language)) examples in this post were run on SQL Server 2025 CU10 (17.0.5035.5, compatibility level 170); no separate .NET code was needed, because every query here arrives the same way from Entity Framework Core (EF Core) or Dapper.

Guess First

In Bookstore, customer 1 (a university library) has 200,000 orders. We write the same query in two ways: first with the value directly, then with a variable:

SET STATISTICS PROFILE ON;

SELECT COUNT(*) FROM dbo.Orders WHERE CustomerId = 1 OPTION (RECOMPILE);

DECLARE @c int = 1;
SELECT COUNT(*) FROM dbo.Orders WHERE CustomerId = @c;

Both queries count 200,000. How many rows did the optimizer expect for each one while building the plan? For the first one, "200,000" is easy. And the second?

    Rows EstimateRows
  200000     200000.0   |--Index Seek(OBJECT:([Orders].[IX_Orders_CustomerId]), SEEK:([Orders].[CustomerId]=(1)) ORDERED FORWARD)
  200000    10.223904   |--Index Seek(OBJECT:([Orders].[IX_Orders_CustomerId]), SEEK:([Orders].[CustomerId]=[@c]) ORDERED FORWARD)

10.22 rows. One twenty-thousandth of the real value. Because the variable's value was unknown at compile time, the optimizer assumed "an average customer". In a COUNT(*) this estimate costs nothing; but when the same estimate feeds a join, a sort or a memory grant calculation, the whole plan is built wrong. In this post we examine where the optimizer gets these numbers: the statistics object, the histogram, the density vector, when statistics are created and updated, the ascending key problem, correlated columns and the real price of a wrong estimate.

The Statistics Object: Header, Density Vector and Histogram

Every index comes with a statistics object for its key columns. Let's look at the statistics of IX_Orders_CustomerId:

DBCC SHOW_STATISTICS ('dbo.Orders', 'IX_Orders_CustomerId') WITH STAT_HEADER, NO_INFOMSGS;
DBCC SHOW_STATISTICS ('dbo.Orders', 'IX_Orders_CustomerId') WITH DENSITY_VECTOR, NO_INFOMSGS;

Name                 Updated             Rows    Rows Sampled Steps Density    Average key length
-------------------- ------------------- ------- ------------ ----- ---------- ------------------
IX_Orders_CustomerId Nov  8 2026 12:00PM 1000000 1000000      96    0.12805143 8.0

All density  Average Length Columns
------------ -------------- --------------------
1.0223904E-5 4.0            CustomerId
0.000001     8.0            CustomerId, OrderId

There are three parts. The header tells you when it was built, over how many rows and by sampling how many; since the index is created in SCHEMA.sql after the data is loaded, all 1,000,000 rows were read (FULLSCAN). The density vector is 1 / (number of distinct values) for each column prefix: 1.0224e-5 for 97,810 distinct customers. It answers the question "if the value is unknown, how many rows does an average value return", and the opening estimate came exactly from here: 1,000,000 × 1.0224e-5 = 10.22. The CustomerId, OrderId line is more proof that the clustering key is appended to every nonclustered index.

The third part is the histogram. It is kept only for the first key column and has at most 200 steps; ours has 96. It can be read through the documented DMV (Dynamic Management View) sys.dm_db_stats_histogram:

SELECT TOP (8) step_number, range_high_key, range_rows, equal_rows, distinct_range_rows, average_range_rows
FROM sys.dm_db_stats_histogram(OBJECT_ID('dbo.Orders'),
     INDEXPROPERTY(OBJECT_ID('dbo.Orders'), 'IX_Orders_CustomerId', 'IndexID'))
ORDER BY step_number;

step_number range_high_key range_rows equal_rows distinct_range_rows avg_range_rows
----------- -------------- ---------- ---------- ------------------- --------------
1           1              0          200000     0                   1.00
2           2              0          17359      0                   1.00
3           3              0          4458       0                   1.00
4           5              3030       2504       1                   3030.00
5           8              3919       1610       2                   1959.50
6           10             1456       1347       1                   1456.00
7           13             2376       1133       2                   1188.00
8           19             4785       860        5                   957.00

Each step ends at a range_high_key. equal_rows is the number of rows exactly equal to that value, range_rows the rows between the previous step and this value, distinct_range_rows the number of distinct values in that range and avg_range_rows the ratio of the two. SQL Server put the skewed values in their own steps: customers 1, 2 and 3 are one step each. The long tail is gathered in wide steps; for example step 73 reduces the 3,245 customers between 15,167 and 18,412 to a single average.

How Is the Estimate Calculated?

For an equality condition the optimizer looks at where the value falls in the histogram. Four examples:

SELECT COUNT(*) FROM dbo.Orders WHERE CustomerId = 1 OPTION (RECOMPILE);
SELECT COUNT(*) FROM dbo.Orders WHERE CustomerId = 15000 OPTION (RECOMPILE);
SELECT COUNT(*) FROM dbo.Orders WHERE CustomerId = 6 OPTION (RECOMPILE);
SELECT COUNT(*) FROM dbo.Orders WHERE CustomerId BETWEEN 1 AND 3 OPTION (RECOMPILE);

    Rows EstimateRows
  200000     200000.0   SEEK:([Orders].[CustomerId]=(1))
      16    9.5975103   SEEK:([Orders].[CustomerId]=(15000))
    2070       1959.5   SEEK:([Orders].[CustomerId]=(6))
  221817     221817.0   SEEK:([Orders].[CustomerId] >= (1) AND [Orders].[CustomerId] <= (3))

Customer 1 is a range_high_key; the estimate is equal_rows directly, so it is perfect. Customer 15,000 falls inside a step; the optimizer used that step's avg_range_rows (9.60), and the actual is 16. Customer 6 is inside step 5 as well: estimate 1,959.5, actual 2,070. You remember this number from the tipping point table in the previous post; this very average made the optimizer's decision between the index and the scan. For a range condition, the steps are summed, and for the 1–3 range the result is again perfect.

A variable, the OPTIMIZE FOR UNKNOWN hint, or any case where the value is unknown at compile time falls back to the density vector. With stored procedure and sp_executesql parameters, however, the optimizer "sniffs" the value of the first execution (parameter sniffing) and uses the histogram with that value. We will cover the good and bad sides of this separately in post seven.

When Are Statistics Created and Updated?

When a column without an index is filtered and AUTO_CREATE_STATISTICS is on (the default), SQL Server creates automatic statistics for that column. There is no index on Status; one query was enough:

SELECT COUNT(*) AS pending FROM dbo.Orders WHERE Status = 'Pending';

SELECT s.name, s.auto_created, sp.rows, sp.rows_sampled, sp.steps, sp.modification_counter
FROM sys.stats AS s
CROSS APPLY sys.dm_db_stats_properties(s.object_id, s.stats_id) AS sp
WHERE s.object_id = OBJECT_ID('dbo.Orders');

name                      auto_created rows    rows_sampled sample_pct steps modification_counter
------------------------- ------------ ------- ------------ ---------- ----- --------------------
PK_Orders                 0            1000000 168134       16.81      184   0
_WA_Sys_00000004_4E88ABD4 1            1000000 168134       16.81      5     0
UX_Orders_OrderNumber     0            1000000 1000000      100.00     180   0
IX_Orders_CustomerId      0            1000000 1000000      100.00     96    0

The object named _WA_Sys_... is the automatically created statistics; it sampled only 16.81% of the rows. Its histogram says 4,680 rows for Pending, while the actual is 4,800; sampling introduced a small deviation. PK_Orders is sampled too: it was created while the table was empty, so its statistics were built later by an automatic update, again with sampling. Creating an index after loading the data means FULLSCAN.

For automatic updates, SQL Server counts changes to the key columns of each statistics object in modification_counter. At compatibility level 130 and above the threshold is MIN(500 + 0.20 × n, √(1000 × n)); for a million rows, √1,000,000,000 ≈ 31,623 changes. I tested this directly:

WITH x AS (SELECT TOP (31000) Status FROM dbo.Orders WHERE Status = 'Delivered' ORDER BY OrderId)
UPDATE x SET Status = 'Cancelled';
SELECT COUNT(*) AS cancelled FROM dbo.Orders WHERE Status = 'Cancelled';  /* a query that uses the statistics */
/* then 1,000 more rows and the same query */

31,000 changes stayed below the threshold and the statistics were not considered stale. At 32,000 the threshold was crossed; the update was triggered not by the change itself but by the compile of the next query that used the statistics, and the counter was reset. The default update is synchronous: that query waits until the statistics are updated. With AUTO_UPDATE_STATISTICS_ASYNC on, the query continues immediately with the old statistics and the update happens in the background.

The Ascending Key Problem

The 31,623-change threshold leaves an annoying gap on large tables. In tables with an ever-increasing column, like an orders table, the newest rows are always beyond the last histogram step. I created an index on CreatedAt (with FULLSCAN statistics), then added 20,000 new orders. Since the change count stayed below the threshold, the histogram still ends on October 20, 2026. Now the query that fetches only the latest days' orders with customer emails:

SELECT o.OrderId, o.CreatedAt, c.Email
FROM dbo.Orders AS o
JOIN dbo.Customers AS c ON c.CustomerId = o.CustomerId
WHERE o.CreatedAt >= '2026-10-21'
OPTION (RECOMPILE);

The CE (cardinality estimation) model, the default since SQL Server 2014, estimated exactly 6,000 rows for this range beyond the histogram, which equals 30% of the modification counter of 20,000. With this estimate it chose a parallel plan with hash joins. I ran the same query with the legacy CE model of compatibility level 110 and earlier (USE HINT('FORCE_LEGACY_CARDINALITY_ESTIMATION')); if you carry the LEGACY_CARDINALITY_ESTIMATION = ON setting in an old database, this is your default:

/* Legacy CE: estimate 1 row */
Table 'Customers'. Scan count 0, logical reads 60000
Table 'Orders'. Scan count 1, logical reads 60044
   20000     1   1.0  |--Nested Loops(Inner Join, OUTER REFERENCES:([o].[CustomerId]))
   20000     1   1.0       |--Nested Loops(Inner Join, OUTER REFERENCES:([o].[OrderId]))
   20000     1   1.0       |    |--Index Seek(OBJECT:([Orders].[IX_Orders_CreatedAt] AS [o]), SEEK:([o].[CreatedAt] >= '2026-10-21 00:00:00'))
   20000 20000   1.0       |    |--Clustered Index Seek(OBJECT:([Orders].[PK_Orders] AS [o]), ... LOOKUP ORDERED FORWARD)
   20000 20000   1.0       |--Clustered Index Seek(OBJECT:([Customers].[PK_Customers] AS [c]), ...)

/* Default CE: estimate 6,000 rows */
Table 'Orders'. Scan count 22, logical reads 3070
Table 'Customers'. Scan count 11, logical reads 1954
   20000    10   6000.0  |--Hash Match(Inner Join, HASH:([o].[CustomerId])=([c].[CustomerId]))

The legacy model assumed there are no rows beyond the histogram, estimated 1 row and built "the cheapest plan for one row": two nested loops, a key lookup and a customer seek for every row. When 20,000 rows arrived, this plan cost 120,044 logical reads; the hash join plan cost 5,024. Same query, same data, a factor of 24. After UPDATE STATISTICS dbo.Orders IX_Orders_CreatedAt, even the legacy CE estimated 17,772 rows and switched to a hash join.

Correlated Columns and CE Models

Histograms cover a single column. With multiple conditions, the optimizer has to make an assumption to combine selectivities, and in real life columns are not independent of each other. In the Customers table, the city depends on the country: everyone in Istanbul is in TR. Of 100,000 customers, 59,788 are in TR and 41,755 in Istanbul; 41,755 satisfy both. I created FULLSCAN statistics on each column and ran the same query under different model assumptions:

SELECT COUNT(*) FROM dbo.Customers WHERE Country = 'TR' AND City = N'Istanbul' OPTION (RECOMPILE);
/* the same query with USE HINT('FORCE_LEGACY_CARDINALITY_ESTIMATION'), 'ASSUME_FULL_INDEPENDENCE_FOR_FILTER_ESTIMATES'
   and 'ASSUME_MIN_SELECTIVITY_FOR_FILTER_ESTIMATES' */

The math is straightforward: full independence multiplies the two selectivities (0.5979 × 0.4176 = 0.2496). The default model takes the most selective condition fully and multiplies by the square root of the second (0.4176 × √0.5979 = 0.3229). Full correlation takes only the most selective condition and gives a perfect result on this data. But no assumption is right for every data set: Country = 'DE' AND City = N'Istanbul' returns zero rows while the default model expected 9,885. Creating multi-column statistics on (Country, City) did not fix it either; that object only keeps the average density of the combination, not a histogram of value pairs, and in our test the default model's estimate dropped to 24,964.

There are two automatic correction mechanisms for these errors of the default model. CE feedback, introduced with SQL Server 2022 (compatibility level 160), sees a large gap between estimate and actual in repeating queries, tries a new plan that changes the correlation, join containment or row goal assumption, and if it helps, makes it permanent as a Query Store hint. Query Store must be on and in READ_WRITE mode, and according to the edition table this feature is in Enterprise. SQL Server 2025 (level 170) extended it with CE feedback for expressions: a learned model choice can now apply not just to one query but to the same expressions across different queries.

How SQL Server 2019/2022 differ: the histogram, density vector, automatic update threshold and the CE 120+ model have been the same since 2019. CE feedback came with 2022 (level 160); 2019 lacks it. CE feedback for expressions exists only in 2025 at level 170. sys.dm_db_stats_histogram has been available since 2016 SP1 (Service Pack 1) CU2 (Cumulative Update 2).

In Production

Separate statistics maintenance from index maintenance. Microsoft's index maintenance guide also says the speed-up seen after a rebuild often comes from the FULLSCAN statistics update. Running UPDATE STATISTICS in a nightly job is far cheaper than a rebuild.

Do not wait for the automatic threshold on large, constantly growing tables. In tables like orders, logs or events, new rows pile up beyond the histogram. Updating the relevant statistics by hand after a load, or setting up a more frequent job for critical statistics, shrinks the ascending key problem.

Choose sampling deliberately. On skewed columns, default sampling can miss important values. With UPDATE STATISTICS ... WITH FULLSCAN or WITH SAMPLE 50 PERCENT, PERSIST_SAMPLE_PERCENT = ON you can set a rate and keep it for automatic updates as well.

Common Pitfalls

Saying "the index doesn't work" without looking at the estimate. Put actual and estimated row counts side by side in the plan; if they differ by more than 10x, check statistics first. Forcing the index is often the wrong fix.

Disabling the histogram by using a variable in the query. In T-SQL scripts and some reports, DECLAREd variables leave the optimizer only the average; in the opening example, 200,000 rows were taken for 10.

Turning on legacy CE database-wide "because of a post-upgrade regression" and forgetting about it. If the problem is in a single query, fixing that query with USE HINT or a Query Store hint is better than condemning the whole database to the old model.

Believing single-column statistics know about correlation. No histogram keeps the combined selectivity of two conditions. If you see a wrong estimate in a critical query, filtered statistics, a hint or rewriting the query is your job, because you are the one who knows the data.

A Small Experiment

★☆☆ Find the step in the IX_Orders_CustomerId histogram where customer 20,000 falls and compute the estimate on paper. Then compare it with SET STATISTICS PROFILE ON.

★★☆ Update the automatic statistics on Status with UPDATE STATISTICS dbo.Orders _WA_Sys_... WITH FULLSCAN. What did the Pending estimate change from 4,680 to? Try pinning the sampling rate with PERSIST_SAMPLE_PERCENT.

★★★ Can you get the right estimate for WHERE Country = 'TR' AND City = N'Istanbul' without hints, using filtered statistics (CREATE STATISTICS ... WHERE Country = 'TR')? Explain the result and its limits.

We saw where the estimates come from and where they go wrong. In the next post we look at where those estimates end up: reading execution plans, the difference between estimated and actual plans, operators and the three join algorithms.