Understand why the query plan was changed We had some performance issues with our ERP system. Somewhere around 06:00 the problem started. Long story short; one of my colleagues executed a DBCC FREEPROCCACHE (I know that this is not a preferred action, but that is not the point here). After that, he restarted the whole ERP application, not the database engine. That didn't seem to help. I looked into the Query Store and saw that the query plan was changed somewhere around 06:05. I tried forcing the older plan and the performance issues were gone. 

I compared the 2 plan XMLs and I saw that both were based on the same statistics (updated date was exactly the same). The number of changes on the indexes was different, but that did not trigger an update statistics, because else the new query plan would have had a new date for the used statistics. I checked all the statistics of the involved tables, but they were not updated since the last maintenance job. The last maintenance job ran this weekend, which was also the update date of the statistics used in both query plans.

The query is a parameterized query, so why the query plan changed suddenly is a little unclear to me. I would think just the opposite, that a query suddenly runs slow, because the same plan is used for different parameters. This did not seem to be the case here, because I forced the old query plan.

The query comes from some bespoke work that retrieves orders. Now, I suspect that someone issued the parameterized query which would have returned a very large dataset and that slowed down the ERP system. Then, my colleague ran a DBCC FREEPROCCACHE and that triggered the re-compile of the query plan, based on the new statistics from this weekend. The current query just kept running and that is were he decided to restart the ERP application. Now with the new query plan all new queries slowed down until I forced the old query plan. 

Could this be the explanation? I am a little skeptical, because SQL Server would trigger a re-compile when statistics have changed, so the plan should already have been re-compiled after the index maintenance job. 

I think I am missing something here, but I am not exactly sure what. It is SQL Server 2016 Standard and is a dedicated server for the ERP system.

Edit 15-4-2020 12:17: Now that I write this... I think the issue is just that after the DBCC FREEPROCCACHE the parameters of the first execution of the parameterized query in question used different parameters, which caused SQL Server to recompile the (bad) plan. Or is there still something I am missing?
Statistics are one input to the query optimizer but not the only one.  As mentioned in the post, the optimizer also sniffs parameter values during compilation and uses those to generate estimates of the number of rows that will come out of various operations such as filters, joins, and group by using the statistics that exist at the time of compilation.  Furthermore, the storage engine provides row counts for each compilation and this can also change without stats changing (though if you change enough rows, the optimizer eventually forces stats to be recomputed).  Any of these things changing could be the cause of the plan changing from one compilation to the next.  The query store actually also tracks other factors that it internally uses to represent to you whether the query is the same or different semantically through a table called sys.context_settings.  So, ansi null on/off would be one such semantic change that could also cause differences in results.  The query store abstracts these from you, but if you were to, for example, create a loop in a stored procedure that changed ansi nulls on/off and then run the same statement over and over in the loop, you'd actually get that to compile over and over (each time the settings are changed from the last time the statement in that part of the sproc is compiled) and this would also give you a chance to have new parameters sniffed on each execution.  These would technically show up as different queries in the query store but to the SQL engine these are holding the same statement slot in the cached query plan for the stored procedure.

SQL 2017+ contains a feature called Automatic Tuning which can auto-force the old plan for you for large regressions.  Azure SQL DB also has this same feature.  In the future, we hope to make parameter sniffing less of a problem for customers, so I hope this gives you insight in the meantime to work around the issue for your scenario.