Here's an interesting one that I can't fathom. I have updated a large DB with UPDATE STATISTICS WITH FULLSCAN. However, the queries run much faster if I run a simple UPDATE STATISTICS. The query plans bear this out - one of the queries takes 5 mins after the FULLSCAN but 30 seconds after updating the stats without any options. I've looked at the fragmentation of the indexes and all seems well. So what situations produce this behaviour of a FULLSCAN producing duff query plans?