Research Projects

Query Optimization Techniques for Partitioned Tables

Table partitioning splits a table into smaller parts that can be accessed, stored, and maintained independent of one another. From their original use to improve query performance, partitioning strategies have evolved into powerful mechanisms to improve database system manageability. Partitioning simplifies administrative tasks like data loading, removal, backup, statistics maintenance, and storage provisioning. SQL extensions and MapReduce frameworks now enable applications and user queries to specify how their results should be partitioned for further use.

However, query optimization techniques have not kept pace with the rapid advances in usage and user control of table partitioning. We address this gap by developing new techniques to generate efficient plans for SQL queries involving multiway joins over partitioned tables. Our techniques are designed for easy incorporation into bottom-up query optimizers that are in wide use today. We have prototyped these techniques in the PostgreSQL optimizer and demonstrated through an extensive evaluation that our partition-aware optimization techniques, with low optimization overhead, generate plans that can be an order of magnitude better than plans produced by current optimizers.

Example query execution plans
P1 is a plan generated by current optimizers.
P2 is a plan generated by our partition-aware optimizer.

Publications