SQL Server performance sudden degradation I have a SQL Server 2005 that has become unpredictable of late, and I'm scratching my head as to why. Queries that executed in seconds are changing plans and taking minutes (taking the time in full table scan or index spool). Now the first and most obvious thing is, the statistics are obsolete causing the optimizer to get confused but I am convinced this is not the case - firstly because the underlying data isn't significantly changing (e.g. adding one day's data ontop of a year's data already in a table) and secondly because Auto Create Statistics and Auto Update Statistics are both true. However the optimizer is getting confused; running the SQL in the Tuning Advisor gives me lots of multi-column CREATE STATISTICS statements which do seem to fix it (until the next bit of SQL misbehaves).

Any ideas of a strategy I can use to approach root-causing this? Any why the "normal" statistics aren't sufficient?
From MSDN:

"Insert Operations Occur on Ascending or Descending Key Columns
Statistics on ascending or descending key columns, such as IDENTITY or real-time timestamp columns, might require more frequent statistics updates than the query optimizer performs. Insert operations append new values to ascending or descending columns. The number of rows added might be too small to trigger a statistics update. If statistics are not up-to-date and queries select from the most recently added rows, the current statistics will not have cardinality estimates for these new values. This can result in inaccurate cardinality estimates and slow query performance.

For example, a query that selects from the most recent sales order dates will have inaccurate cardinality estimates if the statistics are not updated to include cardinality estimates for the most recent sales order dates.

After Maintenance Operations
Consider updating statistics after performing maintenance procedures that change the distribution of data, such as truncating a table or performing a bulk insert of a large percentage of the rows. This can avoid future delays in query processing while queries wait for automatic statistics updates."

You might use "EXEC sp_updatestats" from time to time on your system (scheduled some time) or use the function STATS_DATE on all the objects and see when their statistics were actually updated last time and if there was too much time since then, use UPDATE STATISTICS for that particular object. In my experience, even with Automatic statistics enabled we're still forced to update stats from time to time, because of insert operations that didn't trigger automatic update.

To add my personal code (used in a weekly job that builds dynamic statements for stats update):

select distinct
        'update statistics [' + stats.SchemaName + '].[' + stats.TableName + ']'
            + case when stats.RowCnt &gt; 50000 then ' with sample 30 percent;'
            else 
                ';' end
        as UpdateStatement
    from (
        select
            ss.name SchemaName,
            so.name TableName,
            so.id ObjectId,
            st.name AS StatsName, 
            STATS_DATE(st.object_id, st.stats_id) AS LastStatisticsUpdateDate
            , si.RowModCtr
            , (select case si2.RowCnt when 0 then 1 else si2.RowCnt end from sysindexes si2 where si2.id = si.id and si2.indid in (0,1)) RowCnt
        from sys.stats st
            join sysindexes si on st.object_id = si.id and st.stats_id = si.indid
            join sysobjects so on so.id = si.id and so.xtype = 'U' --user table
            join sys.schemas ss on ss.schema_id = so.uid
    ) stats
    where cast(stats.RowModCtr as float)/cast(stats.RowCnt as FLOAT)*100 &gt;= 10 --more than 10% of the rows have changed
    or ( --update statistics that were not updated for more than 3 months (and rows no &gt; 0)
        datediff(month, stats.LastStatisticsUpdateDate, getdate()) &gt;= 3
        and stats.RowCnt &gt; 0
    )


Here I get all objects where didn't have stats updated for more then 3 months or since the last stats update it had more than 10% of the rows changed.