I know that Paul and I recommended that you subscribe to Conor's blog... but have you? He's posted some great details on Partitioning (Part 1 and Part 2) as well as statistics and it always reminds me of how much I can learn from other people's perspectives!

And, just to dove-tail on some of his statistics comments... I, too, have found that as tables get significantly larger AND have non-standard distributions of more than 200 distinct values (and un-even distribution between those values as well), that the optimizer just cannot possibly do a perfect job. The only way an optimizer can be good is when it can "find a good plan fast" (which I first heard from Nigel Ellis (former Development Manager of the Query Processor team) - back when he delivered a Pacific Northwest SQL Server User Group meeting many moons ago). The most important thing to realize is that it's just not possible to waste time to find the absolutely best plan... mathematically analyzing all permutations would be prohibitive - you'd have to take a vacation between query executions (wait, that's not a bad idea... I digress :).

The point:

1. Make sure that statistics are up-to-date (either through the database option: auto update stats OR by manually updating statistics)
2. Consider re-evaluating statistics over large tables (and, when poor performance occurs - look at the estimated rows v. the actual rows - if the estimate/actual are off by a fact of 10, then it could be the statistics). I'd try updating stats first and then if that doesn't work, updating with a fullscan. If neither of those work, I'd also re-evaluate other possible indexes (there are some distributions between tables being joined that just can't show a correct correlation between the values when in multiple indexes... sometimes the best index is a multi-column (ie. composite index)). 
3. Consider breaking very large tables down into smaller chunks (not just table index partitioning but possibly Partitioned Tables AND Partitioned Views) as this can give the optimizer additional details about partiticularly interesting data sets. Even in SQL Server 2008, statistics are still table-level (filtered indexes can provide some, but not complete, relief... I'll give more details in a later post) but I'd often argue that some of the best table designs are not just for a single table. Consider the statistical, locking, and indexing implications for mixed workloads against a single table (and the tremendous amount of blocking that could occur in addition to varying access patterns). And, even while 2008 will offer Partition-level lock escalation, well-designed tables may not need it! I know I've mentioned this before but different perspectives on statistics, optimizers and the fact that a good optimizer has to be efficient in-and-of itself, remind me of some of the most basic things that are also the most common problems contributing to poor query performance.

Returning to the basics and optimizing a system from the ground up always leads to better scalability!

Enjoy!
kt

Actually, I can't even begin to tell you how great it is that Paul loves blogging so much... he does an amazing job filling in everyone (even our family :)) with our travels through his "personal" posts on his blog (and, he always researches the sites/details as well). And, so, with our mostly business event to China over the past couple of weeks, Paul posted a few links on our side travels (which consisted of about 2.5 total days over our 2 week trip). I have to admit that we were originally going to try and stay for Chinese New Year (New Year's Day is Feb 7) and spend even more time tatting about but ended up cutting the trip short for more work (isn't that always the case :). But, having said that, we made every moment count by squeezing in as much site seeing as possible (we had 1 spare day in Shanghai and 1.5 spare days in Beijing). It really was an amazing trip and we hope to get back to China someday and spend even more time there.

So, if you're interested in hearing a bit more about the trip - and don't already read Paul's blog (which is surprising because he really blogs a lot and he's had some great/technical and deep posts on all sorts of stuff!!!), check out these posts on our travels:

In Shanghai the first week: http://www.sqlskills.com/blogs/paul/2008/01/21/PersonalFirstTripOfTheYearChina.aspx
In Beijing the second week: http://www.sqlskills.com/blogs/paul/2008/01/27/PersonalAndOnToBeijingAndTheGreatWall.aspx and http://www.sqlskills.com/blogs/paul/2008/02/03/PersonalFinalDayInBeijingSightseeingLotsOfPhotos.aspx

I hope your year is going well and Xie Xie (thank you!) to all of the folks that made our trip in China really special! I hope that everyone has a Happy Chinese New Year (and can travel safely through the holidays - especially given the terrible weather conditions that are happening all over China right now).

Kimberly