Oh, and I almost forgot. You probably have clustered indexes on those tables that follow a natural ascending order (i.e. datetime field or IDENTITY). In this case, when you update the stats on those clustered indexes either by rebuilding it or issuing an UPDATE STATISTICS statement, the samples are created in the physical order of the table. This means any new values will lie outside of the statistics histogram. More than likely you'll have to run UPDATE STATISTICS statements a bit more frequently to be able to sample the new values. AUTO UPDATE STATISTICS doesn't always do a very good job of this, since the formula to update the stats is based on a percentage (500 + 20% of total column changes). 20% of a huge table can be quite a bit, and chances are that the stats won't be flagged to update when you have a "large" insert into the table. Many times the default sampling rate will suffice, but sometimes you'll have to supply a larger scan density.