Stored procedure slows down after upgrade from SQL Server 2008 to SQL Server 2016 Post migration from SQL Server 2008 to SQL Server 2016, one of our stored procedure is showing performance degradation. It works fine few days, and then gets slow taking up to 5 minutes. Interestingly, at times SP gets back to working normal again.

On clearing the query cache of stored procedure (DBCC FREEPROCCACHE), it starts to work fine (but only for few days).

We have tried to look into execution plan, and it looks like when the performance is fine – the smaller table join happens first to filter the records, whereas while the stored procedure is slow, the smaller table join happens in the end resulting into slow performance. The clustered index seek shows up "Expected Number of Rows"= 4 and "Actual Number of Rows" ~ 60000000. 

Appreciate any inputs.
Make sure your statistics are getting updated. Also check your index fragmentation and your plan for maintaining indexes.

Since you are on SQL Server 2016, I think you should look into the Query Store feature. You turn it on by running

ALTER DATABASE YOURDATABASE SET  QUERY_STORE = ON;


Once this is turned on, the Query Store will keep the execution plans. There are several searches you can use, one being "Regressed Queries". Once you find your query, you can look at the different execution plans and force the query to use the more efficient plan with the GUI tools.

To force your stored procedure to recompile it's plan the next time it is executed, you can run

 EXEC sp_recompile 'YOURSTOREDPROCEDURE'; 


If you would like SQL Server to recompile the procedure plan each time it is executed, you can run

 EXECUTE YOURSTOREDPROCEDURE WITH RECOMPILE; 


Here are some links for further reading and understanding.

The SQL Server 2016 Query Store: Overview and Architecture

Monitoring Performance By Using the Query Store

Recompile a Stored Procedure