SQL Server 2014: any explanation for inconsistent self join cardinality estimate?

Consider the following query plan in SQL Server 2014:

In the query plan, a self-join ar.fId = ar.fId yields an estimate of 1 row. However, this is a logically inconsistent estimate: ar has 20,608 rows and just one distinct value of fId (accurately reflected in the statistics). Therefore, this join produces the full cross product of rows (~424MM rows), causing the query to run for several hours.

I am having a hard time understanding why SQL Server would come up with an estimate that can be so easily proven to be inconsistent with the statistics. Any ideas?

Initial investigation and additional detail

Based on Paul's answer here, it seems like both the SQL 2012 and SQL 2014 heuristics for estimating join cardinality should easily handle a situation where two identical histograms need to be compared.

I started with output from trace flag 2363, but was not able to understand that easily. Does the following snippet mean that SQL Server is comparing histograms for fId and bId in order to estimate the selectivity of a join that uses only fId? If so, that would obviously not be correct. Or am I misreading the trace flag output?

Plan for computation:
  CSelCalcExpressionComparedToExpression( QCOL: [ar].fId x_cmpEq QCOL: [ar].fId )
Loaded histogram for column QCOL: [ar].bId from stats with id 3
Loaded histogram for column QCOL: [ar].fId from stats with id 1
Selectivity: 0

Note that I have come up with several workarounds, which are include in the full repro script and bring this query down to milliseconds. This question is focused on understanding the behavior, how to avoid it in future queries, and determining whether it is a bug that should be filed with Microsoft.

Here is a full repro script, here is the full output from trace flag 2363, and here is the query and table definitions in case you want to quickly look at them without opening the full script:

```
WITH cte AS (
SELECT ar.fId,
ar.bId,
MIN(CONVERT(INT, ar.isT)) A

I am having a hard time understanding why SQL Server would come up with an estimate that can be so easily proven to be inconsistent with the statistics.

Consistency

There is no general guarantee of consistency. Estimates may be calculated on different (but logically equivalent) subtrees at different times, using different statistical methods.

There is nothing wrong with the logic that says joining those two identical subtrees ought to produce a cross product, but there is equally nothing to say that choice of reasoning is more sound than any other.
Initial estimation

In your specific case, the initial cardinality estimation for the join is not performed on two identical subtrees. The tree shape at that time is:

LogOp_Join
LogOp_GbAgg
LogOp_LeftOuterJoin
LogOp_Get TBL: ar
LogOp_Select
LogOp_Get TBL: tcr
ScaOp_Comp x_cmpEq
ScaOp_Identifier [tcr].rId
ScaOp_Const Value=508
ScaOp_Logical x_lopAnd
ScaOp_Comp x_cmpEq
ScaOp_Identifier [ar].fId
ScaOp_Identifier [tcr].fId
ScaOp_Comp x_cmpEq
ScaOp_Identifier [ar].bId
ScaOp_Identifier [tcr].bId
AncOp_PrjList
AncOp_PrjEl Expr1003
ScaOp_AggFunc stopMax
ScaOp_Convert int
ScaOp_Identifier [tcr].isS
LogOp_Select
LogOp_GbAgg
LogOp_LeftOuterJoin
LogOp_Get TBL: ar
LogOp_Select
LogOp_Get TBL: tcr
ScaOp_Comp x_cmpEq
ScaOp_Identifier [tcr].rId
ScaOp_Const Value=508
ScaOp_Logical x_lopAnd
ScaOp_Comp x_cmpEq
ScaOp_Identifier [ar].fId
ScaOp_Identifier [tcr].fId
ScaOp_Comp x_cmpEq
ScaOp_Identifier [ar].bId
ScaOp_Identifier [tcr].bId
AncOp_PrjList
AncOp_PrjEl Expr1006
ScaOp_AggFunc stopMin
ScaOp_Convert int
ScaOp_Identifier [ar].isT
AncOp_PrjEl Expr1007
ScaOp_AggFunc stopMax
ScaOp_Convert int
ScaOp_Identifier [tcr].isS
ScaOp_Comp x_cmpEq
ScaOp_Identifier Expr1006
ScaOp_Const Value=1
ScaOp_Comp x_cmpEq
ScaOp_Identifier QCOL: [ar].fId
ScaOp_Identifier QCOL: [ar].fId

The first join input has had an unprojected aggregate simplified away, and the second join input has the predicate t.isT = 1 pushed below it, where t.isT is MIN(CONVERT(INT, ar.isT)). Despite this, the selectivity calculation for the isT predicate is able to use CSelCalcColumnInInterval on a histogram:

CSelCalcColumnInInterval
Column: COL: Expr1006

Loaded histogram for column QCOL: [ar].isT from stats with id 3

Selectivity: 4.85248e-005

Stats collection generated:
CStCollFilter(ID=11, CARD=1)
CStCollGroupBy(ID=10, CARD=20608)
CStCollOuterJoin(ID=9, CARD=20608 x_jtLeftOuter)
CStCollBaseTable(ID=3, CARD=20608 TBL: ar)
CStCollFilter(ID=8, CARD=1)
CStCollBaseTable(ID=4, CARD=28 TBL: tcr)

The (correct) expectation is for 20,608 rows to be reduced to 1 row by this predicate.
Join estimation

The question now becomes how the 20,608 rows from the other join input will match up with this one row:

LogOp_Join
CStCollGroupBy(ID=7, CARD=20608)
CStCollOuterJoin(ID=6, CARD=20608 x_jtLeftOuter)
...

CStCollFilter(ID=11, CARD=1)
CStCollGroupBy(ID=10, CARD=20608)
...

ScaOp_Comp x_cmpEq
ScaOp_Identifier QCOL: [ar].fId
ScaOp_Identifier QCOL: [ar].fId

There are several different ways to estimate the join in general. We could, for example:

• Derive new histograms at each plan operator in each subtree, align them at the join (interpolating step values as necessary), and see how they match up; or

• Perform a simpler 'coarse' alignment of the histograms (using minimum and maximum values, not step-by-step); or

• Compute separate selectivities for the join columns alone (from the base table, and without any filtering), then add in the selectivity effect of the non-join predicate(s).

• ...

Depending on the cardinality estimator in use, and some heuristics, any of those (or a variation) could be used. See the Microsoft White Paper Optimizing Your Query Plans with the SQL Server 2014 Cardinality Estimator for more.
Bug?

Now, as noted in the question, in this case the 'simple' single-column join (on fId) uses the CSelCalcExpressionComparedToExpression calculator:

Plan for computation:

CSelCalcExpressionComparedToExpression [ar].fId x_cmpEq [ar].fId

Loaded histogram for column QCOL: [ar].bId from stats with id 2
Loaded histogra

StackExchange Database Administrators Q#141220, answer score: 24