Design and Analysis of Parametric Query Optimization Algorithms
Šumit Ganguly · 1998
Query optimizers normally compile queries into one optimal plan by assuming complete knowledge of all cost parameters such as selec-tivity and resource availability. The execution of such plans could be sub-optimal when cost parameters are either unknown at compile time or change significantly between compile time and runtime [Loh89, GrW89]. Paramet-ric query optimization [INS+92, CG94, GK94] optimizes a query into a number of candidate plans, each optimal for some region of the pa-rameter space. In this paper, we present para-metric query optimization algorithms. Our approach is based on the property that for linear cost functions, each parametric optimal plan is optimal in a convex polyhedral region of the parameter space. This property is used to optimize linear and non-linear cost func-tions. We also analyze the expected sizes of the parametric optimal set of plans and the number of plans produced by the Cole and Graefe algorithm [CG94]. 1