CS262A Reading Summary 23

Access Path Selection in a Relational Database Management System

P. G. Selinger et al.
Summary by Feng Zhou
10/29/2002

1. The paper proposes a automatic optimizer that can potential generate join execution plans that can be compared to hand optimized database queries. This is a big step forward because with it we can make database systems that is much easier to use and is still highly efficient.
2. Statistics are collected and used extensively in the proposed join plan optimizer. This makes it able to adapt to situations where same query having very different optimal plan depending on different relation statistics in real world. The concept of "Selection Factor" is also important because it captures the average behavior of different operations.
3. The optimization process is done by dynamic programming, which is much faster than exhaustive search. Several heuristics are used to further speed up the process. One is delay cartisan product operations to as late as possible. The other is to use "interesting ordering" to group relations into equivalent classes. This better reflects the actual costs of different join plans.

1 flaw:

Only plans that can be represented by left-most trees are considered by the optimizer. So actually it may not find the optimal plan sometimes.