Fast way to have an inparameter match all values? (COALESCE slow)

[Ola Arwidsson]

I have a number of stored procedures to retrieve data. They have over 10 inparameters like date, customerid, shoe size. The idea is to have one procedure where I can use wild cards for all inparameters go get all of that data.
Example
1. call GetShoe('2015-03-26',4711,42) - Get the shoes for todays date, customerid 4711, size 42.
2. Call GetShoe('2015-03-26',-1,42) - Same, but all customers
3. Call GetShoe('2015-03-26',-1,-1) - Same, but all customers and all sizes.
3. Call GetShoe('',-1,-1) - Same, but all customers and all sizes and dates.

So far I have achieved this ny using WHERE constructs like:
WHERE ShoeSize=COALESCE(inParam_ShoeSize, ShoeSize)
(I also start the procedure with an IF to change -1 to null)

This works, but seems to read through all rows which leads to poor performance when row number increases.

Is there a better way to achieve this wildcard behaviour?