One of the common challenges that arises in many applications is around how to optimize the SQL Server performance of dynamic search queries. For example, we've all seen applications with screens like this:
Often, there will be many, many more fields to be searched. What I often hear from developers is that there is no way to optimize the query because you don't know in advance which options the user will choose. While this is partly true, it assumes that human behaviour is much more random than it really is. Let me explain:
A few years back, I was doing performance tuning work at a company that books flights. They had a stored procedure that took a single parameter of a BookingNumber, and returned details of a customer's booking. It took around ½ second to execute.
Eventually, one of the users said "I'd love to be able to look up the booking by LastName". So they changed the procedure to have an optional parameter to allow for that. Later another user asked for EmailAddress. And so on, and so on. When I arrived, they had a 4000 line procedure that allowed 14 optional parameters. Unfortunately, it now took 90 seconds to execute every time.
What was truly sad, was that in a week of testing, I never saw any value passed except the BookingNumber. So they had created a situation where all the users all day long were experiencing glacial response times, for a situation that almost never occurred.
I see this sort of scenario played out time and again. When confronted with a screen that allows the users to pick and choose search criteria, developers always seem to assume that people will choose a wide variety of options. Yet that isn't what happens. Generally, there will be a small set of options that they will choose again and again, and only rarely will they make other choices.
Knowing that, you realise that even though you can't optimize for every possible code path, it's critical that the common paths are optimized. If necessary, provide alternate code paths for the high volume query types.
Finally, for the atypical choices made by users, what do you do? A Swedish friend of mine (and fellow SQL Server MVP) Erland Sommarskog has some awesome articles at his web site www.sommarskog.se. One in particular is on Dynamic Search Conditions. I recommend reading it if you have never done so.
I've run into the same situation numerous times. The solution is easy even with search boxes with thousands of param combinations.
Create one stored proc for the most common search code paths. Ensure you don't suffer from parameter sniffing/bad plan side-effects and you have good response times. Then create an additional stored proc (OPTION RECOMPILE) for the less common search combinations where you know you can't index properly/use sargable params/will suffer from sniffing/cached plan issues. Use a few of these if needed. Try your best to hide those known-flaky search combinations by using UX/UI tricks like making those options available only when someone clicks on the "advanced search" button.
Now have your developers actually do some work and code the form submission to determine which search options the user selected and then pick the right proc to execute. Developers hate to do this, but it works.
The worst thing is being lazy and ordinally passing the search conditions to a single monolithic proc. Like you noted, that's when you can guarantee nothing will perform.
The only complaint with this is you essentially have the same code copied and pasted into multiple procedures with only slight variants for the differing parameters (thanks to SQL Server not supporting macros). For the purist this is heresy. For the pragmatist this is solved with some simple code comments and grok.