When the database engine compiles a stored procedure, it may use the actual parameters supplied to prepare an execution plan. If the parameters are atypical, the plan may be slow for typical parameters. For consistent sproc performance eliminate parameter sniffing.

Technet article: Batch Compilation, Recompilation, and Plan Caching Issues in SQL Server 2005

 -- SOLUTION 1 - Remap input parameters to local variables

USE AdventureWorks;
GO
 
CREATE PROC uspSuppliersByLocation
          @pStateProvinceName NVARCHAR(50)
AS
  BEGIN
    /**** REMAP parameter to prevent Parameter Sniffing ****/
    DECLARE  @StateProvinceName NVARCHAR(50)
    SET @StateProvinceName = @pStateProvinceName
    /**** END OF REMAP                                  ****/
    SELECT V.VendorID,
           V.Name  AS Vendor,
           A.AddressLine1,
           A.AddressLine2,
           A.City,
           SP.Name AS State,
           CR.Name AS Country
    FROM     Purchasing.Vendor AS V
             INNER JOIN Purchasing.VendorAddress AS VA
               ON VA.VendorID = V.VendorID
             INNER JOIN Person.Address AS A
               ON A.AddressID = VA.AddressID
             INNER JOIN Person.StateProvince AS SP
               ON SP.StateProvinceID = A.StateProvinceID
             INNER JOIN Person.CountryRegion AS CR
               ON CR.CountryRegionCode = SP.CountryRegionCode
    WHERE    SP.Name = @StateProvinceName
    GROUP BY V.VendorID,
             V.Name,
             A.AddressLine1,
             A.AddressLine2,
             A.City,
             SP.Name,
             CR.Name
    ORDER BY V.VendorID;
  END

GO

-- Execute stored procedure

EXEC uspSuppliersByLocation 'California'

------------

 -- SOLUTION 2 - OPTIMIZE FOR query hint

-- Create stored procedure with OPTIMIZE FOR query hint
-- Washington state is typical based on the distribution of states
CREATE PROC sprocSuppliersByLocation
          @StateProvinceName NVARCHAR(50)
AS
  BEGIN
    SELECT V.VendorID,
           V.Name  AS Vendor,
           A.AddressLine1,
           A.AddressLine2,
           A.City,
           SP.Name AS State,
           CR.Name AS Country
    FROM     Purchasing.Vendor AS V
             INNER JOIN Purchasing.VendorAddress AS VA
               ON VA.VendorID = V.VendorID
             INNER JOIN Person.Address AS A
               ON A.AddressID = VA.AddressID
             INNER JOIN Person.StateProvince AS SP
               ON SP.StateProvinceID = A.StateProvinceID
             INNER JOIN Person.CountryRegion AS CR
               ON CR.CountryRegionCode = SP.CountryRegionCode
    WHERE    SP.Name = @StateProvinceName
    GROUP BY V.VendorID,
             V.Name,
             A.AddressLine1,
             A.AddressLine2,
             A.City,
             SP.Name,
             CR.Name
    ORDER BY V.VendorID
  OPTION (OPTIMIZE FOR(@StateProvinceName = 'Washington')); ;
  END
GO
-- Execute stored procedure
EXEC sprocSuppliersByLocation 'Colorado'
/* Partial results
Vendor                  AddressLine1            City        State
Green Lake Bike Company 2342 Peachwillow        Denver      Colorado

*/

------------