Sql-server – Ascending keys getting bad plans in SQL 2016 (new CE), replacement for TF 4139 et al.

The way the cardinality estimation is derived certainly seems counter-intuitive to me. The distinct count calculation (viewable with Extended Events or trace flags 2363 and 3604) is:

Notice the cap. The general logic of this seems very reasonable (there can't be more distinct values), but the cap is applied from sampled multi-column statistics:

DBCC SHOW_STATISTICS 
    (BigFactTable, [PK_BigFactTable])
WITH
    STAT_HEADER, 
    DENSITY_VECTOR;

That shows 2,980,235 rows sampled out of 3,439,431,721 with a density vector at the Col5 level of 3.35544E-07. The reciprocal of that gives a number of distinct values of 2,980,235 rounded using real math to 2,980,240.

Now the question is, given sampled statistics, what assumptions the model should make about the number of distinct values. I would expect it to extrapolate, but that isn't done, and perhaps deliberately.

More intuitively, I would expect that instead of using the multi-column statistics, it would look at the density on Col5 (but it doesn't):

DBCC SHOW_STATISTICS 
    (BigFactTable, [_WA_Sys_00000005_24927208])
WITH
    STAT_HEADER, 
    DENSITY_VECTOR;

Here the density is 9.266754E-10, the reciprocal of which is 1,079,126,528.

One obvious workaround in the meantime is to update the multi-column statistics with full scan. The other is to use the original cardinality estimator.

The Connect item you opened, SQL 2014 sampled multi-column statistics override more accurate single-column statistics for non-leading columns, is marked Fixed for SQL Server 2017.

The question of why one cardinality estimation model produces closer results than the other in this case is actually not that interesting. The original CE estimates that not finding a matching row has a very small probability; the new CE calculates that it is almost certain. Both are 'correct', just based on different modelling assumptions. Fundamentally, multi-column semi joins are tricky to evaluate based on single-column statistical information.

It is much more interesting to think about what the query is trying to do, and how we can write it in a way that is more compatible with the statistical information available to SQL Server.

A key observation is that the query will return row(s) with one value per group. In the case of the original query, that is row(s) with the minimum HistoryId value for each Transactionid. In the repro, it is row(s) with the minimum c1 value for each different value of c2. The NOT EXISTS query is just one way of expressing that requirement.

SQL Server has good statistical information about distinct values (density) so all we need to do is write the query in a way that makes it clear we want one value per group. There are many ways to do this, for example (using your repro):

SELECT * 
FROM dbo.nat AS N
WHERE N.c1 =
(
    SELECT MIN(N2.c1) 
    FROM dbo.nat AS N2
    WHERE N2.c2 = N.c2
);

or, equivalently:

SELECT N.* 
FROM dbo.nat AS N
JOIN
(
    SELECT 
        N.c2,
        MIN(N.c1) AS c1
    FROM dbo.nat AS N
    GROUP BY 
        N.c2
) AS J
    ON J.c2 = N.c2
    AND J.c1 = N.c1;

This produces an exactly correct estimate of 9999 rows in 2008 R2, 2012, and 2014 (both CE models):

With a natural index (which would probably be unique as well):

CREATE INDEX i ON dbo.nat (c2, c1);

The plan is even simpler:

You may not always be able to get this very simple plan form, depending on indexes, and other factors. The point I am making is that using basic grouping and joining operations often gets better results from the optimizer (and its cardinality estimation component) than more complex alternatives.

Final notes to clear some misconceptions in the question: the 'new CE' was introduced in 2014. TF 4199 enables plan-affecting optimizer fixes. TF 9481 specifies the original ('legacy') CE, and is only effective on 2014 and later versions.