I have a procedure making a call to a table that normally takes 5-10 seconds to return results. However, lately this has been taking 1-2 min. I have found a fix which is to rebuild an index (0% fragmentation) in the main table that the query uses, then it runs fine.
Reorganizing and/or updating statistics on that index does not help. By comparing the before and after exec plans, I’ve noticed that the Actual/estimated number of rows has changed and a key lookup & index seek changes from parallelism = False, to Parallelism = True - after the index rebuild. Other than that nothing major stands out at me when comparing the plans.
Also noticed that after restarting sql the query goes back to the old non-parallelized plan which is slower. This is occuring on both of my SQL 2005 test and production servers. Any ideas what could be causing this?