Why does Concatenation operator estimate fewer rows than its inputs?

Question

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?

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.

Answer 1

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).

Answer 2

Building an admittedly rather simple test bed on SQL Server 2012 (11.0.6020) allows me to recreate a plan with two hash matched queries being concatenated via a UNION ALL. My test-bed does not display the incorrect estimate you see. Perhaps this is a SQL Server 2014 CE problem.

I get an estimate of 133.785 rows for a query that actually returns 280 rows, however that is to be expected as we'll see further on down:

IF OBJECT_ID('dbo.Union1') IS NOT NULL
DROP TABLE dbo.Union1;
CREATE TABLE dbo.Union1
(
    Union1_ID INT NOT NULL
        CONSTRAINT PK_Union1
        PRIMARY KEY CLUSTERED
        IDENTITY(1,1)
    , Union1_Text VARCHAR(255) NOT NULL
    , Union1_ObjectID INT NOT NULL
);

IF OBJECT_ID('dbo.Union2') IS NOT NULL
DROP TABLE dbo.Union2;
CREATE TABLE dbo.Union2
(
    Union2_ID INT NOT NULL
        CONSTRAINT PK_Union2
        PRIMARY KEY CLUSTERED
        IDENTITY(2,2)
    , Union2_Text VARCHAR(255) NOT NULL
    , Union2_ObjectID INT NOT NULL
);

INSERT INTO dbo.Union1 (Union1_Text, Union1_ObjectID)
SELECT o.name, o.object_id
FROM sys.objects o;

INSERT INTO dbo.Union2 (Union2_Text, Union2_ObjectID)
SELECT o.name, o.object_id
FROM sys.objects o;
GO

SELECT *
FROM dbo.Union1 u1
    INNER HASH JOIN sys.objects o ON u1.Union1_ObjectID = o.object_id
UNION ALL
SELECT *
FROM dbo.Union2 u2
    INNER HASH JOIN sys.objects o ON u2.Union2_ObjectID = o.object_id;

I think the reason is around the lack of statistics for the two resulting joins that are UNIONed. SQL Server needs to make educated guesses in most cases around the selectivity of columns when faced with the lack of statistics.

Joe Sack has an interesting read on that here.

For a UNION ALL, it's safe to say we'll see exactly the total number of rows returned by each component of the union, however since SQL Server is using row estimates for the two components of the UNION ALL, we see it adds the total estimated rows from both queries to come up with the estimate for the concatenation operator.

In my example above, the estimated number of rows for each portion of the UNION ALL is 66.8927, which when summed equals 133.785, which we see for the estimated number of rows for the concatenation operator.

The actual execution plan for the union query above looks like:

You can see the "estimated" vs "actual" number of rows. In my case, adding the "estimated" number of rows returned by the two hash match operators exactly equals the amount shown by the concatenation operator.

I would try to get output from trace 2363 etc as recommended in Paul White's post you show in your question. Alternately, you might try using OPTION (QUERYTRACEON 9481) in the query to revert back to the version 70 CE to see if that "fixes" the issue.