Sql-server – Clustered index scan appears to be costed too low with row count spool

I've never posted one of these before so let me know if any information is missing.

I have a relatively simple query that performs pretty poorly with the default sample size on a few key columns. The costing of a clustered index scan used by a row count spool appears to be impossibly low. I will go through the technical details that I can share about the problem. Unfortunately, I cannot share statistics or provide a data set. What I am looking for is an explanation of the root cause and additional workarounds to the problem.

This is the SQL Server version that I'm testing on:
Microsoft SQL Server 2014 – 12.0.4100.1 (X64)
Apr 20 2015 17:29:27
Copyright (c) Microsoft Corporation
Developer Edition (64-bit) on Windows NT 6.3 (Build 9600: ) (Hypervisor)

Trace flags 4199 and 9481 are enabled. Trace flags 4134, 2390, and 2371 are also enabled but I don't expect those to have any effect for this query.

The query itself only has two tables.

CREATE TABLE X_JRO_TABLE_1 (
PK_COLUMN NUMERIC(18,0) NOT NULL,
JOIN_COLUMN NUMERIC(18,0) NULL,
PRIMARY KEY (PK_COLUMN)
)
WITH (DATA_COMPRESSION = PAGE);

CREATE TABLE X_JRO_TABLE_2 (
PK_COLUMN NUMERIC(18,0) NOT NULL,
JOIN_COLUMN NUMERIC(18,0) NULL,
DATA_TO_PAD_PAGES VARCHAR(500) NULL
PRIMARY KEY (PK_COLUMN)
)
WITH (DATA_COMPRESSION = PAGE);

-- insert data query here

CREATE STATISTICS X_JRO_TABLE_1__JOIN_COLUMN ON X_JRO_TABLE_1 (JOIN_COLUMN) 
WITH NORECOMPUTE;

CREATE STATISTICS X_JRO_TABLE_2__JOIN_COLUMN ON X_JRO_TABLE_2 (JOIN_COLUMN) 
WITH NORECOMPUTE;

Information that I can share on the statistics for JOIN_COLUMN in X_JRO_TABLE_1:
Rows: about 63500000
Rows sampled: 1056952
Steps: 200
All density: 4.741809E-05

6.168829E+07 EQ_ROWS for the step with a NULL RANGE_HI_KEY.
Rest of the histogram is hard to describe.

Information that I can share on the statistics for JOIN_COLUMN in X_JRO_TABLE_2:
Rows: about 23400000
Rows sampled: 182929
Steps: 188
All density: 0.0003521127

About 170 steps in the histogram with 1 EQ_ROWS, 0 DISTINCT_RANGE_ROWS, and 1 AVG_RANGE_ROWS.
2.295549E+07 EQ_ROWS for the step with a NULL RANGE_HI_KEY.
The other steps mostly have 170.4468 AVG_RANGE_ROWS and a few hundred DISTINCT_RANGE_ROWS.

Here is the query text:

SELECT t1.JOIN_COLUMN
FROM X_JRO_TABLE_1 t1 
WHERE NOT EXISTS
(
    SELECT 1
    FROM X_JRO_TABLE_2 t2
    WHERE t1.JOIN_COLUMN = t2.JOIN_COLUMN
)
AND t1.JOIN_COLUMN > A
AND t1.JOIN_COLUMN <= B;

The difference between A and B is 104173. These are both integers.

Here is a screenshot of the estimated query plan:

Here is a screenshot of the key operator:

By request here is the anonymized estimated execution plan: http://pastebin.com/h47Lzs0L

Here is my interpretation of what is happening in this query. The query optimizer does a clustered index scan on X_JRO_TABLE_1. It then sorts the data by JOIN_COLUMN. It expects there to only be 1268 distinct values for the JOIN_COLUMN column. For each unique value, the row count spool needs to do a clustered index scan on X_JRO_TABLE_2. So with this plan we are looking at 1268 full scans on X_JRO_TABLE_2. When I let this query run, it did indeed do hundreds of clustered index scans on X_JRO_TABLE_2 and racked up a billion logical reads before I cancelled the query execution.

Why did the query optimizer pick this plan? Well, the subtree cost of the clustered index scan on X_JRO_TABLE_2 appears to be artificially low. It is only 153 magic optimizer units. I would expect it to be larger than 1148 magic optimizer units because that's what a single clustered index scan costs in the following query:

SELECT DISTINCT t2.JOIN_COLUMN
FROM X_JRO_TABLE_2 t2
WHERE 
t2.JOIN_COLUMN > A
AND t2.JOIN_COLUMN <= B;

Here is a screenshot of the clustered index scan operator for that query:

So if the SQL Server query optimizer is deciding between different plans and one of the plans has an artificially low cost for a required step then it seems unlikely that I will get a different plan, even if that plan seems absurd to me personally.

If I increase the sample size of the stats on JOIN_COLUMN for X_JRO_TABLE_1 or X_JRO_TABLE_2 then the cost of the full scan on X_JRO_TABLE_2 goes up. With a large enough sample size I believe that we hit a tipping point that makes the row count spool plan inferior to other plan choices including just a regular table spool. Here is a screenshot of the query plan after I gathered stats in full:

I tried to get a query plan with a row count spool after increasing the sample size and could not do so, even after disabling the following optimizer rules:

dbcc ruleoff('RASJNtoHS')
dbcc ruleoff('LASJNtoHS')
dbcc ruleoff('RASJNtoSM')
dbcc ruleoff('LASJNtoSM')
dbcc ruleoff('SelToIndexOnTheFly')
dbcc ruleoff('GbAggToHS')
dbcc ruleoff('GbAggToSort')
dbcc ruleoff('GbAggToStrm')

The following plan was the end result of that endeavor. This isn't a great query plan but it is certainly better than the row count spool one.

It seems odd to me that increasing the sample size of JOIN_COLUMN of X_JRO_TABLE_2 affects the operator cost. I get why the operator cost increases as I increase the sample size of JOIN_COLUMN of X_JRO_TABLE_1. The estimated number of executions increases. However, the rows returned and the estimated number of executions does not change with a statistics changes for X_JRO_TABLE_2. Here is a screenshot of the full scan operator:

As far as I can tell the only thing that is different is the estimated subtree cost. That doesn't make sense to me.

I know of a few workarounds but I do not like them for reasons that I don't need to get into here.

• Update statistics with FULLSCAN for JOIN_COLUMN in X_JRO_TABLE_1 or X_JRO_TABLE_2.
• Use the 2014 CE.
• In SQL Server 2016 use the NO_PERFORMANCE_SPOOL query hint.
• Use QUERYTRACEON 8690.
• Create a nonclustered index on JOIN_COLUMN in X_JRO_TABLE_2.
• Put the rows that I need from X_JRO_TABLE_2 into a temp table with an index on it and join to that instead of X_JRO_TABLE_2.
• Instead of WHERE NOT EXISTS, use LEFT OUTER JOIN X_JRO_TABLE_2 t2 … WHERE t2.PK_COLUMN IS NULL
• Replace the join clause with something like this: WHERE t1.JOIN_COLUMN = CASE WHEN t1.JOIN_COLUMN IS NOT NULL THEN t2.JOIN_COLUMN ELSE NULL END

If you made it to the end thank you for reading. As I said earlier, I am looking for the root cause of this behavior and am interested in any other workarounds that the community can provide.