On a somewhat related note...
We've moved to MSSQL due to several reasons including customer demand.
We're experiencing the MSSQL query planner occasionally generating terrible plans for core queries which then gets cached, leading to support calls.
Workaround for now has been to have our query geneator append a fixed-value column which and have it change the value every 10 minutes, as a cache defeat.
Still, surprised the engine doesn't figure this out itself, like try regenerating plans frequently if they contain non-trivial table scans say.
Or just expire cache entries every 15 minutes or so, so a bad plan doesn't stick around for too long.
It’s one of RDBMS peculiarities that you just need to learn about. Any half decent MSSQL course or book will tell you about the plan cache and the occasional gotcha exactly like yours. Time wasted debugging this issue by the unaware is probably in kilo man years by now.
…but MSSQL is still a fantastic database, if you can afford it. Postgres and mysql come with their own set of gotchas, some of which need an actually decent book to be explained. (Note all the RDBMS manuals are decent books and everyone without exception should read at least the TOC of the db they’re using, which IME is still a rarity.)
To add to sibling comment. This sounds like a parameter sniffing. Read it up. It should help you understand the problem. It is a known issue with SQL Server. Or rather a tradeoff. You don't want to compile a new execution plan for every query. This would eat up CPU by itself.