Azure SQL database query performance degradation
After discussion, the issue here is that the optimizer in SQL Server/SQL Azure currently &quot;sniffs&quot; current parameter values when compiling the query.  The query plan is then cached and used on future executions of the query.  The plan that is generated may be more optimal for the originally sniffed value, but if other values are more commonly used at execution time (or, more broadly, if the impact on the rest of the query is different statistically such as one value being uncommon when sniffed vs. more common cases being sniffed), then this can be a source of runtime variance in a data application.  There are a few knobs to control this at different scopes, but using the option OPTIMIZE FOR UNKNOWN query hint will cause the optimizer to not sniff.  This will generate a query plan that is more generic (but still usually reasonably fast).
The original question suggested that clearing out the query store &quot;fixed&quot; the problem, but this was not actually the real cause.  It so happens that clearing the query store will force recompiles for all the query plans it was tracking on the next execution of each query.  That just allowed the optimizer to sniff a different value and, at least for the customer's experience, it happened to be better in that experiment.  Anything that forces a recompile would lead to a similar result.  You could do DBCC FREEPROCCACHE (empties the plan cache), reboot your server, force/unforce the plan for the query in query store, any metadata change to the database or tables involved in the query, etc.