Estimates, a huge amount of columns selected and predicate pushdown
The query's estimates are not accounting for the residual predicate on the scan being of a higher cost than the seek + key lookup to get all these extra columns from the clustered index. This results in the clustered index scan + residual predicate being chosen instead of the index seek.
My version is Microsoft SQL Server 2016 (RTM-GDR)
These estimates on predicate pushdown where improved in SQL server 2016 SP1
Update to improve diagnostics for query execution plans that involve residual predicate pushdown in SQL Server 2016
To improve diagnostics for the scenario that's described in the
"Symptoms" section, SQL Server 2016 Service Pack 1 (SP1) introduces a
new showplan XML attribute, Estimated Rows Read. This attribute
provides the estimated count of rows will be read by the operator
before the residual predicate is applied. This update is a complement
to KB 3107397.
This adds the EstimatedRowsRead=""
to the query plan XML, in your case this would be close or matching the residual predicate if the scan is chosen.
This should fix your issue
Residual predicate example


Reading 1.2M rows to return 0
Index scan query Estimated total cost
EstimatedTotalSubtreeCost="0.00449281">
Index seek query Estimated total cost
EstimatedTotalSubtreeCost="0.00672858">
Which is higher than the index scan estimations due to not accounting for the residual predicate, and that is why the lesser performing plan was chosen.
The main solution
The main solution would be upgrading to at least SP1 to add the:
Update to improve diagnostics for query execution plans that involve residual predicate pushdown in SQL Server 2016
You should patch sooner and more often, since SP2 CU6 is out as of March 19, 2019, this would be a far better choice.
Another side note, SP1 for SQL Server 2016 adds many additional features such as In memory OLTP, Compression, Columnstore indexes, ....
Other workarounds that may or may not be worth mentioning
- Selecting less columns if they are not needed
- Adding all these columns to the NC index's included columns
- You could try disabling row goals with
OPTION(QUERYTRACEON 4138)
(maybe)
- Using the
WITH(INDEX))
Hint
Comparison with SQL Server 2016 SP1
when running a query alike yours, forcing the clustered index to be used on a SQL2016 SP1 version:
The estimated subtreecost is much higher.
EstimatedTotalSubtreeCost="93.6951"
Where your estimated subtreecost for the clustered index scan
<RelOp AvgRowSize="4788" EstimateCPU="1.36996" EstimateIO="185.267" EstimateRebinds="0" EstimateRewinds="0" EstimatedExecutionMode="Row" EstimateRows="1" LogicalOp="Clustered Index Scan" NodeId="1" Parallel="false" PhysicalOp="Clustered Index Scan" EstimatedTotalSubtreeCost="0.00448209" TableCardinality="1245280">
Is low
EstimatedTotalSubtreeCost="0.00448209"
With the main difference being
EstimatedRowsRead="1000000"
shown when executing the query on the SQL 2016 with SP1 applied.
And when testing with the NC index specified
CREATE INDEX IX_PARTITION_DATAAREAID_REVRECID
ON dbo.LEDGERJOURNALTRANS(PARTITION,DATAAREAID,REVRECID);
<RelOp AvgRowSize="980" EstimateCPU="0.0001581" EstimateIO="0.003125" EstimateRebinds="0" EstimateRewinds="0" EstimatedExecutionMode="Row" EstimateRows="1" LogicalOp="Clustered Index Seek" NodeId="4" Parallel="false" PhysicalOp="Clustered Index Seek" EstimatedTotalSubtreeCost="0.0032831" TableCardinality="1000000">
the EstimatedTotalSubtreeCost for the index seek (not total for entire plan) is also low:
EstimatedTotalSubtreeCost="0.0032831
and the total estimated subtree cost for my test query is very close to yours
EstimatedTotalSubtreeCost="0.00657048">
declare @P1 bigint=5639064671