Exponential Backoff: How SQL Server Estimates Several Filters

Exponential backoff is how SQL Server’s newer estimator combines several filters on one table. It does not multiply every selectivity, which would assume the columns are unrelated. It softens the multiplication, and the result is a model, not a measurement.

Why three filters surprise people

Someone opens a plan and says, “It estimated 89 rows, but 500 came back. Are the statistics broken?” Probably not. Each column may have perfect statistics. The estimate for the combination comes from a rule, and rules can be wrong about your data.

Let me build a small case where you can watch the rule work. The table has 10,000 rows. Columns a and b always hold the same number, and c is a different number. So the columns are strongly related. The demo uses a temp table, so nothing stays behind.

DROP TABLE IF EXISTS #Filters;
CREATE TABLE #Filters (Id int PRIMARY KEY, a int, b int, c int);

INSERT #Filters
SELECT value, value % 10, value % 10, value % 20
FROM GENERATE_SERIES(1, 10000);

CREATE STATISTICS S_a ON #Filters (a) WITH FULLSCAN;
CREATE STATISTICS S_b ON #Filters (b) WITH FULLSCAN;
CREATE STATISTICS S_c ON #Filters (c) WITH FULLSCAN;

One filter at a time

First, ask for the estimate behind each single filter. SET STATISTICS PROFILE shows two numbers for each operator. The Rows column is what really happened. The EstimateRows column is what the optimizer expected. In SSMS you can read the same pair from the actual plan.

Look at the last row of each result, the Clustered Index Scan. Filter a = 1 expects 1000 rows and finds 1000. Filter c = 1 expects 500 and finds 500. With a full-scan statistic, a single filter is spot on.

SET STATISTICS PROFILE ON;

SELECT COUNT(*) AS rows_found FROM #Filters WHERE a = 1 OPTION (RECOMPILE);
SELECT COUNT(*) AS rows_found FROM #Filters WHERE c = 1 OPTION (RECOMPILE);

SET STATISTICS PROFILE OFF;

Now combine them

Next, filter on all three at once. The scan still finds 500 rows. The default estimator expects about 88.9. The legacy estimator, which I ask for with a hint, expects 5. Both are wrong, and the newer one is less wrong.

The hint is only for comparison. Please do not put it into production code to chase one number.

SET STATISTICS PROFILE ON;

SELECT COUNT(*) AS rows_found
FROM #Filters
WHERE a = 1 AND b = 1 AND c = 1
OPTION (RECOMPILE);

SELECT COUNT(*) AS rows_found
FROM #Filters
WHERE a = 1 AND b = 1 AND c = 1
OPTION (USE HINT('FORCE_LEGACY_CARDINALITY_ESTIMATION'), RECOMPILE);

SET STATISTICS PROFILE OFF;

Where 88.9 comes from

The three single-filter selectivities are 0.05 for c and 0.1 for each of a and b. The old rule multiplies all three: 10,000 times 0.05 times 0.1 times 0.1 gives 5.

The backoff rule sorts the selectivities from smallest to largest. The smallest counts in full. The next gets a square root. The third gets a fourth root. That is 10,000 times 0.05 times the square root of 0.1 times the fourth root of 0.1. The answer is 88.91397, which matches the plan.

DECLARE @Rows float = 10000, @s1 float = 0.05, @s2 float = 0.1, @s3 float = 0.1;

SELECT @Rows * @s1 * @s2 * @s3 AS IndependentArithmetic,
       @Rows * @s1 * POWER(@s2, 0.5) * POWER(@s3, 0.25) AS BackoffArithmetic;

Think of it as a polite hedge. The optimizer says, “These columns might be related, so I will not shrink the estimate as hard as independence would.” It guesses a middle path. Here the columns are identical twins, and even the middle path is too small.

Tell the optimizer the truth

The fix is not another hint. It is better information. A statistic on all three columns together records how often the combination occurs. After I create it, the estimate becomes 500, the real number.

That works here because every filter is an equality on a column in the statistic. Test your own case before you copy the idea. And always compare the estimate with the actual rows first. A bad estimate matters because it steers join choices and memory grants. The last block drops the temp table.

CREATE STATISTICS S_abc ON #Filters (a, b, c) WITH FULLSCAN;

SET STATISTICS PROFILE ON;

SELECT COUNT(*) AS rows_found
FROM #Filters
WHERE a = 1 AND b = 1 AND c = 1
OPTION (RECOMPILE);

SET STATISTICS PROFILE OFF;

DROP TABLE IF EXISTS #Filters;

Next time an estimate looks odd, find out which rule produced it before you blame the statistics.

A row estimate is not a measured count, it is a model to check against reality.

Published by Pinal Dave on SQLAuthority. More of my work at pinaldave.com.