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.
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.