Microsoft SQL Server 2016 performance degradation for stored procedure called 1000's of times
In SQL Server 2014 &amp; up, new cardinality estimation logic was introduced.

From BOL :


  The cardinality estimation logic, called the cardinality estimator, is re-designed in SQL Server 2014 to improve the quality of query plans, and therefore to improve query performance. The new cardinality estimator incorporates assumptions and algorithms that work well on modern OLTP and data warehousing workloads. It is based on in-depth cardinality estimation research on modern workloads, and our learnings over the past 15 years of improving the SQL Server cardinality estimator. Feedback from customers shows that while most queries will benefit from the change or remain unchanged, a small number might show regressions compared to the previous cardinality estimator.


Recently, we upgrade from SQL server 2012 to SQL server 2014 and got hit by the new Cardinality estimator short coming - queries were timing out, cpu pegging close to 100%.

After much troubleshooting, updating stats, rebuilding indexes, doing query plan analysis, we figured out that changing compatibility level to sql 2012 works well.

Paul White explains - Cardinality Estimation for Multiple Predicates


  Selectivity computation in SQL Server 2014 behaves the same as previous versions (and trace flag 4137 works as before) if the database compatibility level is set lower than 120, or if trace flag 9481 is active.


So my advise would be 


For small number of queries revealing the problem, use QUERYTRACEON(9481) hint.
If you dont want to gamble, then just have the trace flag TF9481 as a start-up parameter, so it gets persisted during server restarts.


Note: Enabling TF 9481, you dont need to set the compatibility level of the database to a lower level.

From KB2801413 :


  9481   :Use when running SQL Server 2014 with the default database compatibility level 120. Trace flag 9481 forces the query optimizer to use version 70 (the SQL Server 2012 version) of the cardinality estimator when creating the query plan.


As a side note, along with proper testing -  you also want to look into TF4199 (Think of it as a master key to turn on every fix for the query optimizer). TF4199 behavior changes with sql server 2016.. TF4199 helped in my environment at lot and is by default ON for all new installations.

In SQL Server 2016, you dont need to turn on the trace flag 9481 .

SELECT  name, value  
    FROM  sys.database_scoped_configurations  
    WHERE name = 'LEGACY_CARDINALITY_ESTIMATION'; 
-- if above is having value = 0, then set to ON
ALTER DATABASE
    SCOPED CONFIGURATION  
        SET LEGACY_CARDINALITY_ESTIMATION = ON;  
go  


For Trace Flag 4199, you can just do 

ALTER DATABASE
    SCOPED CONFIGURATION  
        SET QUERY_OPTIMIZER_HOTFIXES = ON