Let's say you have the following stored procedure:

SELECT Name FROM Person

WHERE City = @city

If you call this stored procedure for the first time, the value of @city will be used to create an execution plan based on statistics, indexes, etc.

Next time you call the stored procedure, this execution plan will be reused. The value of @city doesn't matter anymore. Have in mind that SQL Server only stores two plans per stored procedure: one for serial execution and one for parallel execution.

To reduce the impact of first time execution, you can use the OPTIMIZE FOR clause, which allows you to specify the parameter values for the generation of the execution plan.

By the way, we had some serious performance problems with a stored procedure after a new software release. We found out that due to changes in our nightly schedule, the rebuild index was executed at a different time. The process that was following the rebuild index now used different parameters. As a result, the stored procedure was significant slower than before.