Sql-server – Why does Concatenation operator estimate fewer rows than its inputs

cardinality-estimatesconcatperformancequery-performancesql serversql server 2014

In the following query plan snippet, it seems obvious that the row estimate for the Concatenation operator should be ~4.3 billion rows, or the sum of the row estimates for its two inputs.

However, an estimate of~238 million rows is produced, leading to a sub-optimal Sort / Stream Aggregate strategy that spills hundreds of GB of data to tempdb. A logically consistent estimate in this case would have produced a Hash Aggregate, removed the spill, and dramatically improved query performance.

Is this a bug in SQL Server 2014? Are there any valid circumstances in which an estimate lower than the inputs could be reasonable? What workarounds might be available?

enter image description here

Here is the full query plan (anonymized). I do not have sysadmin access to this server in order to provide outputs from QUERYTRACEON 2363 or similar trace flags, but may be able to get these outputs from an admin if they would be helpful.

The database is in compatibility level 120, and is therefore using the new SQL Server 2014 Cardinality Estimator.

Stats are updated manually every time data is loaded. Given the volume of data, we are currently using the default sampling rate. It's possible that a higher sampling rate (or FULLSCAN) could have an impact.

Best Answer

To quote Campbell Fraser on this Connect item:

These "cardinality inconsistencies" can arise in a number of situations, including when concat is used. They can arise because the estimation of a particular subtree in the final plan may have been perfomed on a differently structured but logically equivalent subtree. Due to the statistical nature of cardinality estimation, estimating on different but logically equivalent trees is not guaranteed to get the same estimate. So overall no guarantees of expected consistency are provided.

To expand on that a little: The way I like to explain it is to say that the initial cardinality estimation (performed before cost-based optimization starts) produces more "consistent" cardinality estimates, since the whole initial tree is processed, with each subsequent estimation depending directly on the preceding one.

During cost-based optimization, parts of the plan tree (one or more operators) may be explored and replaced with alternatives, each of which may require a new cardinality estimate. There is no general way to say which estimate will be generally better than another, so it is quite possible to end up with a final plan that appears "inconsistent". This is simply the result of stitching together "bits of plans" to form the final arrangement.

All that said, there were some detailed changes to the new cardinality estimator (CE) introduced in SQL Server 2014 that makes this somewhat less common than was the case with the original CE.

Aside from upgrading to the latest Cumulative Update and checking that optimizer fixes with 4199 are on, your main options are to try statistics/index changes (noting the warnings for missing indexes) and updates, or expressing the query differently. The goal being to acquire a plan that displays the behaviour you require. This may then be frozen with a plan guide, for example.

The anonymized plan makes it hard to assess the detail, but I would also look carefully at the bitmaps to see if they are of the 'optimized' (Opt_Bitmap) or post-optimization (Bitmap) variety. I am also suspicious of the Filters.

If the row counts are anything like accurate though, this seems like a query that might benefit from columnstore. Quite aside from the usual benefits, you might be able to take advantage of the dynamic memory grant for batch mode operators (trace flag 9389 may be required).

Related Question