Parametric Query Optimization
Arvind Hulgeri, Ph.D, 04, 146 pp.

Department of Computer Science and Engineering
Indian Institute of Technology Bombay, Powai, Mumbai 400 076.
Supervisor: S. Sudarshan

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.

Second, we propose a solution for the PQO problem for the
case when the cost functions are piecewise-linear in the given
parameters. The solution requires modification to an existing query
optimizer. This solution is general, since arbitrary cost functions
can be approximated to piecewiselinear form.

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.

As the final contrIbution, we show how to make a query optimizer
"memory cognizant". Typical optimizers assume all the memory
to be available to each operator in a plan. But while executing
pipelines, memory has to be divided amongst all the operators running
simultaneously in a pipeline. The cost of an operator generally
depends on the available memory. Thus the choice of execution plan
and memory division are interdependent and, if done separately may
not give the optimal plan. We address the problem of choosing an
optimal, memory-division-aware execution plan for a query, given
the .cost versus memory allocation. function for each operator. We
show how to make a query optimizer .memory cognizant.. We have
implemented our techniques on a query optimizer based on the Volcano
query optimization algorithm.