Dynamic parameter set for a stored procedure

Lately I was trying to figure out the best way to pass dynamic number of parameters to a stored procedure. The stored procedure was supposed to do a simple SELECT using parameters provided. The problem was that the set of parameters could change dynamically, depending on app configuration.

There are several ways to achieve that. My first choice was to use a single parameter that would contain all serialized search terms. The terms would be extracted from that param within my stored procedure. Then, I would build the query dynamically using those terms:

(...)
BEGIN
IF @forename IS NOT NULL
BEGIN
 SET @sqlQuery = @ sqlQuery + ' AND forename LIKE ''' + @forename +'%''';
END
END
BEGIN
IF @surname IS NOT NULL
BEGIN
 SET @ sqlQuery = sqlQuery + ' AND surname LIKE ''' + @surname +'%''';
END
END
(...)

The problem with that approach is that building dynamic sql is generally slow. I was advised to try out an alternative solution: pass all possible search terms as separate parameters and use a static query with null checks:

(...)
AND  (@forename IS NULL OR forename LIKE @forename+'%')
AND  (@surname IS NULL OR surname LIKE @surname+'%')
(...)

I wasn't sure which one is better, especially in the case when there are many possible search terms. The first approach uses only specified terms but it takes time to build the query. In second approach the query is static but there are multiple null checks which also takes time (the more possible criteria there is, the worse it gets).

I did some benchmarking using Sql Server 2008 and a table with 1000 records. It came out that the approach with dynamic sql was slightly faster. I ran my tests around 10 times for each params set and then calculated the average duration (not counting values that were far from avg).

Example: Below are the results when 2 params were set. Depending on the param values different results number was returned:

	Dynamic SQL [ms]	Static SQL [ms]
Params returning around 250 results	217	241
Params returning around 15 results	10	24

For other combination of params (e.g. 3 other params returning similar number of results) the duration differences were similar. This shows that from performance perspective dynamic sql is better than the second approach, especially if you have many possible search criteria.

For now i didn't come up with a better approach. Any suggestions?