SQL Server query performance affected by rebuilding an un-fragmented index I have a query within a stored procedure that the same input will periodically time out ( &gt; 30 seconds)  when it normally runs in milliseconds.
The table has 2077748 rows, 59 columns, and 13 indexes.
We have found that rebuilding one of the indexes takes the performance back to milliseconds.
Here is the fun part.  The percentage fragmentation on this index every time it is rebuilt is &lt; 1%, the last time it was .01%.  I've been playing with the fill factors because I thought it may be an expansion issue, it was 100, then 80, now 60.  This has not effected the frequency of this problem.
When I run the following
select b.name,* 
from sys.dm_db_index_physical_stats(5,1075691080,NULL,NULL,NULL) a
JOIN sys.indexes b ON a.object_id = b.object_id AND a.index_id = b.index_id

I get

index_id  partition_number    index_type_desc alloc_unit_type_desc    index_depth index_level avg_fragmentation_in_percent    fragment_count  avg_fragment_size_in_pages  page_count
66    1   NONCLUSTERED INDEX  IN_ROW_DATA 3   0   0.01    1116    18.9229390681004    21118

Any suggestions on other places to look or sources of this problem?
It sounds like the rebuild of the index is a red herring, especially given it was non-clustered. The rebuild is more likely to be invalidating a bad query plan in cache, and on re-run the good query plan is generated and used again.

Captue the query plan when the performance is bad and then after the rebuild and compare them, I suspect you will see a different plan.

That would be my first step - e.g. demonstrate what changes to the plan due to the index rebuild, or prove there is no change on the plan.