Title:
Parametric Query Optimization

Abstract:
Database queries are typically specified declaratively, and the database
system has to choose an appropriate execution plan for the query. A
query optimizer in a database system is responsible for transforming an
SQL query into an execution plan. Most modern optimizers are cost-based
in that they decide between alternative execution plans by comparing
their estimated execution costs.

The cost of a query plan depends on many parameters such as predicate
selectivities, available memory, and presence of access paths, whose
values may not be known at optimization time. Parametric Query
Optimization (PQO) optimizes a query into a number of candidate plans,
each optimal for some region of the parameter space. At run time, when
the actual parameter values are known, the candidate plan corresponding
to the actual parameter values is picked and used. In this thesis we
propose solutions for several cases of the PQO problem.

We first propose a solution for the PQO problem for the case when the
cost functions are linear in the given parameters. This solution is
minimally intrusive in the sense that an existing query optimizer can be
used as a subroutine with minor modifications: the solution invokes the
conventional query optimizer multiple times, with different parameter
values. The solution works for an arbitrary number of parameters.

We then propose a heuristic solution for the PQO problem for the case
when the cost functions may be nonlinear in the given parameters. This
solution is minimally intrusive. We have implemented the heuristic and
the results of the tests on the TPCD benchmark indicate that the
heuristic is very effective.