T-SQL: Recompiling an SP Causes Bad Plan

Stored Procedure generates bad plan after re-compile?

Friday at work I encountered an interesting situation.  I had a stored procedure which did a bunch of things, and I noticed that when executing it with the same parameters, same data-set, etc. I would get varied performance.  Digging a little deeper I noticed that there were two different plans that it was generating.  The big difference between the two plans was essentially the order of execution.  In the good plan, it was scanning a small table first, filter the result-set to about a dozen records, before continuing on and working with these records.  In the bad plan, it was joining a very large table first, doing much processing with a few million records, before finally filtering it at the end to the dozen or so records I needed.

Now, at first you think this has something to do with parameter-sniffing, and that sort of problem, where the engine caches a plan based on the first execution which is a bad plan for subsequent executions.  However, while the stored procedure does have some IF/ELSE logic embedded, this still doesn't make any sense.  When I was executing the stored procedure, I was using the same parameters, and the same underlying data.  With every execution it was going down the same path, and adding a WITH RECOMPILE didn't solve the problem.

In fact, it's the exact opposite.  What I found out was that working with the indexes used by the plans caused the good plan, but recompiling the stored procedure led to a bad plan on the next execution.  What am I talking about?  Here is the essential order of events, using pseudo-code:

1) EXECUTE usp_TheStoredProcedure -> It is executed with the good plan, runs in 2 seconds or less.
2) RECOMPILE usp_TheStoredProcedure
3) EXECUTE usp_TheStoredProcedure -> It is executed with the bad plan, takes 45+ seconds to run.
4) CREATE INDEX AnyIndexUsedBySP.
5) EXECUTE usp_TheStoredProcedure -> It is executed with the good plan, runs in 2 seconds or less.
6) EXECUTE usp_TheStoredProcedure -> It is executed with the good plan, runs in 2 seconds or less.
7) RECOMPILE usp_TheStoredProcedure
8) EXECUTE usp_TheStoredProcedure -> It is executed with the bad plan, takes 45+ seconds to run.
7) DROP INDEX AnyIndexUsedBySP.
8) EXECUTE usp_TheStoredProcedure -> It is executed with the good plan, runs in 2 seconds or less.

In other words, simply affecting any index attached to any table queried by the SP would allow subsequent executions of the SP to use the good plan, UNTIL I recompiled the SP, then it would go back to using the terrible plan.  What I did with the Index made no difference, in fact the work around I have found is that I can create and drop some random index on a small table WITHIN the stored procedure itself, and it then generates a good plan for every execution! In other words:

ALTER usp_TheStoredProcedure AS BEGIN

CREATE INDEX idx_SomeIndex ON SomeSmallTable(SomeColumn);
DROP INDEX idx_SomeIndex;

/* Continue the normal SP logic */

END

This solved the problem! What is going on here? Are the statistics going bad every single time I recompile the SP, and affecting the Indexes refreshes them?

If anyone out there can explain this phenomenon, please comment below or Tweet me at @RyanJLind