Thanks to both of you for those references. They were both extremely helpful.
Noel, that article is AMAZING. Here's the part that makes the biggest difference:
Not all search routines are as complex our search_orders. Sometimes the dynamic search is confined to alternate keys, of which the user always supplies one. In this case, it is not too painful to use IF statements to handle the three different cases. But maybe the column list in the SELECT statement contains complex expressions that you don't want to repeat. You know already that this won't do:
WHERE (key1 = @key1 OR @key1 IS NULL)
AND (key2 = @key2 OR @key2 IS NULL)
AND (key3 = @key3 OR @key3 IS NULL)
As you have seen this will yield a table scan. But what do you think about this:
WHERE (key1 = @key1 AND @key1 IS NOT NULL)
OR (key2 = @key2 AND @key2 IS NOT NULL)
OR (key3 = @key3 AND @key3 IS NOT NULL)
The logic is here the reverse: give me all rows that matche any of the given conditions. From a performance point of view, this may look like the same thing, but this can in fact perform very well. The odds are very good that SQL Server will generate a plan which seeks the three key indexes and then merges the result either by index concatenation or some other method. Here is the real big scoop: thanks to the condition, @x IS NOT NULL, SQL Server adds a filter with a startup expression to the plan, so if the corresponding variable is NULL, SQL Server will not access that index at all.