The problem is that SQL Server is trying to build ONE execution plan to match all parameters. This means that it does not change it and does not select a different index when you give it different parameters. (The different index is important because the load of reassigning a non-local index can be very high.)
The only way to do this is to create a new execution plan and enable dynamic SQL - exactly what you want to avoid.
Nonetheless; dynamic SQL and SP_EXECUTESQL are not necessarily a bad idea. Since this can also be parameterized, proper use allows reuse of the execution plan and can be exceptionally effective in such problems.
Is there any specific reason why you need to avoid dynamic SQL?
The only realistic job is to repeatedly write a query with a different order and choose which one to use with T-SQL IF blocks. This will allow the optimizer to generate various execution plans.
source share