Mysterious timeouts in MSSQL 2000

I have a query that has been working fine for ages (2+ years).

All of a sudden it went from taking 3 secs to 30+ to execute. The table indexes have minimal fragmentation, but rebuilding the indexes "fixes" it for about a day.

When I go to check the fragmentation it is around .5 (not bad). The table only sees about 100 inserts and another 100 updates a day.

There are no locks on the table when it happens. Any ideas of what to check?

From serverfault Christopher Kelly

• Check if your Statistics is Out-of-date and update it accordingly.

  gbn : index stats are updated as part of an index rebuild.
  From DaniSQL

• What does the execution plan look like when it is fine, vs when it isn't working correctly?

  Are you rebuilding the indexes or defragging the indexes? How big is the table? When was the last time you updated stats on the table?

  Christopher Kelly : table has a grand total of 4 integer columns and ~20000 rows

  Farseeker : +1 for execution plan

  mrdenny : How much data is changing on the table daily? It is really sounding like the stats are out of date. Can you post the execution plans?
  From mrdenny

• It's probably parameter sniffing (StackOverflow search).

  The index rebuild implicitly rebuilds index statistics which invalidates the cached plan which "fixes" it.

  From gbn