When you run a stored procedure,, the first step is to see if the stored procedure is in the plan cache. Since stored procedures typically have variables passed to them, the entity that is stored does not reflect the specific query run last time since it does not include the parameter. A hash of the new query is compared to the stored query to see if there is match, and if found, the cached plan is used. If not, the Query Optimizer finds a good enough plan and that is used and cached.
Apparently, the hash used to look at the stored procedure and the actual cache are different – the cache does have the values passed to it. therefore a new run of the cache was really different parameters might be ‘no so good’. This might be caused by uneven data distribution. parameter sniffing
The actual execution plan which you can get from SSMS will have the “parameter compiled value” and the “parameter runtime value” values listed. Presumably, you would NOT have the same value all the time, however if the data skew of the parameter is very different for different values of the same parameter, this will lead to bad queries.
Solutions would be to recompile, compile the stored procedure for a specific value, create the sp with the recompile option, use a plan guide or create a stored procedure that will look at the distribution, then call one of a number of sps with better stored variables.