SQL Server 2016 not using index used in 2012 2016 plan here

2012 plan here

I have almost identical tables with very small difference in row count. One on 2012, and the other on 2016. Indexing is identical. These VMs are in exact same environment with upgraded OS and SQL Server versions.  Same number vcores, same memory, same server settings (max degree of parallelism = 8, cost threshold for parallelism = 30).

This drop dead simple query for single record using a single column for filter and single column return. The column in the where filter is the sole column in the index.

2016 version has 8254356 rows
2012 version has 8254427 rows

They are the same queries.  2016 is missing the index and doing full table scan for no apparent reason.  2012 does a RID lookup (Heap) on the table after the index scan.  

I tried WITH (index = CONTACT_RC_NUI1) on 2016 server and the cost jumped from 991 to 1889. On 2012 the cost was 29.

I tried adding AND 1 = (SELECT 1) and that made no difference.
I tried removing parameter sniffing as a possible problem by using OPTION (RECOMPILE) and that made no difference.

The DBA ran index rebuilds after restoring the database. Both servers had fairly recent index stats updates (we run Ola's index update script).  And to be sure I rebuilt the index on 2016 which had no effect on the 2016 explain plan. 

I added hint below in the query...

select address1_stateorprovince 
from dla.dcrm.CONTACT_RC WITH (index = CONTACT_RC_NUI1)
where wv_partyid = 343083;


This resulted in taking cost from 991 to 1889 even though it shows almost identical to 2012 explain plan (2016 just added parallelism (gather streams)).

What 2016 appears to be doing is costing the index for only 1% but the RID lookup is 99%.  In 2012 this was reversed. It appears 2016 used the index to scan all the entries and then looked up every RID in the table?  Could that be true?  I think 2016 optimizer has been smoking something seriously strong.  


wv_party_id is nvarchar(100)
You see different plans because from SQL Server 2014 there is a new cardinality estimator in SQL Server. And then they added some new features to SQL Server 2016 for the the new CE.

First some test data to reproduce what you see.

create table dbo.T(C1 char(10) default '', C2 varchar(11));

go

insert into dbo.T(C2)
select top(800000) row_number() over(order by (select null))
from sys.columns as c1, sys.columns as c2, sys.columns as c3

go

create index IX_T_C2 on dbo.T(C2)


And the queries that will produce the two different plans for you so you can compare them in the same version of SQL Server.

-- Table scan version
select C1
from dbo.T with (index = 0)
where C2 = 100000
option (maxdop 1);

-- Index Scan version
select C1
from dbo.T with (index = IX_T_C2)
where C2 = 100000
option (maxdop 1);


The table scan version in SQL Server 2012 scans all rows and returns one. No surprise there.

The Index scan version of SQL Server 2012 scans all rows in the index and returns one row. There is something there that needs to be looked on further but for now you should take an extra look at the Estimated Number of Rows for the Index Scan operator.



The Table Scan version of SQL Server 2016 is no different than the version in 2012. It scans all rows returning one row.

The Index Scan version looks the same as in 2012 but the cost is much higher and that is because Estimated Number of Rows is much higher than in 2012



So SQL Server now thinks it has to do 80000 RID Lookup to return 1 row and that is why it chooses the Table Scan in SQL Server 2016 with the new cardinality estimator.

The new estimator sees the predicate where CONVERT_IMPLICIT(int,C2) = 100000 and gives up. It uses the standard guess of 10% selectivity for an equality predicate, where 10% of 800,000 rows = 80,000. The original estimator used more complex logic to produce a non-guess (accurate!) estimate of one row.

Now to the issue with the Index Scan. That is probably not what you want. You want SQL Server to do an Index Seek finding the row you are looking for. Currently SQL Server can't do that because you have a type mismatch in the where clause and you do get warnings about it in the query plan. 
Fix that and you should see a plan with an Index Seek and a RID Lookup in both versions of SQL Server.

Note also that cost percentages in execution plans are always based on optimizer estimates, not real run time information.