Wrong estimate on a query on partitioned tables

Question

I wonder why SQL Server makes wrong estimations in such a simple case. There is a scenario.

CREATE PARTITION FUNCTION PF_Test (int) AS RANGE RIGHT 
FOR VALUES (20140801, 20140802, 20140803)

CREATE PARTITION SCHEME PS_Test AS PARTITION PF_Test ALL TO ([Primary])

CREATE TABLE A
(
  DateKey int not null,
  Type int not null,
  constraint PK_A primary key (DateKey, Type) on PS_Test(DateKey)
)

INSERT INTO A (DateKey, Type)
SELECT
  DateKey = N1.n  + 20140801,
  Type = N2.n + 1
FROM dbo.Numbers N1
  cross join dbo.Numbers N2
WHERE N1.n BETWEEN 0 AND 2
  and N2.n BETWEEN 0 AND 10000 - 1

UPDATE STATISTICS A (PK_A) WITH FULLSCAN, INCREMENTAL = ON

CREATE TABLE B
(
  DateKey int not null,
  SubType int not null,
  Type int not null,
  constraint PK_B primary key (DateKey, SubType) on PS_Test(DateKey)
)

INSERT INTO B (DateKey, SubType, Type)
SELECT
  DateKey,
  SubType = Type * 10000 + N.n,
  Type
FROM A
  cross join dbo.Numbers N
WHERE N.n BETWEEN 1 AND 10

UPDATE STATISTICS B (PK_B) WITH FULLSCAN, INCREMENTAL = ON

So setup is pretty straightforward, statistics are in place and SQL Server can produce correct estimates when we query one table.

select COUNT(*) from A where DateKey = 20140802
--10000
select COUNT(*) from B where DateKey = 20140802
--100000

But in this simple select estimates are way off, and I see no explanation why.

SELECT a.DateKey, a.Type
FROM A
  JOIN B
    ON b.DateKey = a.DateKey
    AND b.Type = a.Type
WHERE a.DateKey = 20140802

Right after Clustered Index Seek estimation is 57% from actual! Real-world query is even worse, estimate is 2% from actual.

P.S. Numbers table to reproduce setup

DECLARE @UpperBound INT = 1000000;

;WITH cteN(Number) AS
(
  SELECT ROW_NUMBER() OVER (ORDER BY s1.[object_id]) - 1
  FROM sys.all_columns AS s1
  CROSS JOIN sys.all_columns AS s2
)
SELECT n = [Number] INTO dbo.Numbers
FROM cteN WHERE [Number] <= @UpperBound;

CREATE UNIQUE CLUSTERED INDEX CIX_Number ON dbo.Numbers(n)
WITH 
(
  FILLFACTOR = 100,      -- in the event server default has been changed
  DATA_COMPRESSION = ROW -- if Enterprise & table large enough to matter
);

PPS Same scenario but non-partitioned works perfectly.

Answer 1

The estimates (with the new cardinality estimator) are fine for a normal join, but are less accurate when the optimizer considers the option of a colocated join.

A colocated join (aka per-partition join) is available when joining two tables that are partitioned in the same way. The idea is to join one partition at a time, using nested loops apply driven by partition ids provided by a constant scan (in-memory table of values).

Regular join

Since the colocated join involves a nested loops apply, you can force the optimizer to avoid this by specifying OPTION (HASH JOIN) for example:

The two seeks in that plan are:

Seek Keys[1]: Prefix:
    PtnId1000, [dbo].[A].DateKey = Scalar Operator((3)), Scalar Operator((20140802))
Seek Keys[1]: Prefix:
    PtnId1003, [dbo].[B].DateKey = Scalar Operator((3)), Scalar Operator((20140802))

The optimizer has applied static partition elimination in both cases, giving accurate estimates for both seeks, and the following join.

Colocated join

When the optimizer considers a colocated join (as shown in the question), the seeks are:

Seek Keys[1]: Prefix:
    PtnId1000, [dbo].[A].DateKey = Scalar Operator([Expr1006]), Scalar Operator((20140802))
Seek Keys[1]: Prefix:
    PtnId1003, [dbo].[B].DateKey = Scalar Operator([Expr1006]), Scalar Operator((20140802))

...where [Expr1006] is the value returned by the Constant Scan operator.

The cardinality estimator now cannot see that the DateKey value and the partition id are interdependent, as it could when literal constants were used. In other words, it is not apparent to the estimator that the value inside [Expr1006] specifies the same partition as DateKey = 20140802.

As a consequence, the CE chooses (by default) to estimate the selectivity of the two (apparently independent) predicates using the normal exponential backoff method.

This explains the reduced cardinality estimates feeding the join. The lower apparent cost of this option (due to the misestimate) means the optimizer chooses a colocated join instead of a regular join, even though it is obvious (to humans) that it offers no value.

There are several ways to work around this gap in the logic, including using the query hint USE HINT ('ASSUME_MIN_SELECTIVITY_FOR_FILTER_ESTIMATES'), but this will affect the whole query, not just the problematic colocated join alternative. As Erik notes in his answer, you could also hint the use of the legacy CE.

For more information about colocated joins, see my article Improving Partitioned Table Join Performance

Answer 2

This appears to be due to the new cardinality estimator introduced in SQL Server 2014.

If you instruct the query to use the old one, you get a different plan and correct estimates.

SELECT a.DateKey, a.Type
FROM A AS a
  JOIN B AS b
    ON b.DateKey = a.DateKey
    AND b.Type = a.Type
WHERE a.DateKey = 20140802
OPTION(USE HINT('FORCE_LEGACY_CARDINALITY_ESTIMATION'));

See these links for more information:

• Optimizing Your Query Plans with the SQL Server 2014 Cardinality Estimator
• SQL Server Join Estimation using Histogram Coarse Alignment