I'd be curious why the plans are choosing to do scans. Assuming the distribution of the data hasn't changed, just having more data doesn't generally affect the statistics that much. Partitioning is not really a mechanism for improving performance. It can, but it's primarily a means of making data management of large data sets easier. Many people see poorer performance from partitioning, so I'd be cautious about that. From the sounds of things, I'd focus on general query tuning, ensuring the indexes are good, etc., and probably look to throw more disks at the problem. For a system that size it sounds like the hardware might not be optimal (and I'm not the guy who normally argues for hardware solutions).