6. RELATED WORK
Figure 6 shows how MPQ optimization relates to prior query
optimization variants. The figure shows for each variant the
type of cost function c, that is, associated with each query
plan. Arrows point from a more restricted to a more general
query optimization variant. Multi-objective query optimization1, 7, 11, 16, 17 and parametric query optimization3, 4, 6, 8, 10, 13
both generalize the traditional query optimization model.
Multi-objective parametric query optimization generalizes
both of the aforementioned variants.
The algorithm that we propose in this paper allows to
solve query optimization problems that prior algorithms
cannot solve. Algorithms for parametric query optimization
are not applicable to MPQ since they cannot handle multiple
cost metrics. Algorithms for multi-objective query optimization are not applicable to MPQ since they cannot handle
parameters. Note that parameters and cost metrics have
a different semantic such that it is not possible to model
parameters as cost metrics or vice versa. Intuitively, we want
to “cover” the entire parameter space (by finding plans for
each possible parameter value combination) while we do not
want to cover the entire cost space (plans with higher cost
values than necessary are not part of the result plan set).
The algorithm that we describe in this article is based
on dynamic programming. It calculates optimal plans for
a query by combining optimal plans for its subqueries.
Many query optimization algorithms for traditional query
14 multi-objective query optimization,
16, 17 and
parametric query optimization8 use the same dynamic programming scheme. The difference between our algorithm
and all prior algorithms lies in the implementation of the
pruning function. We use linear programming in the pruning function. Our algorithm shares this property with prior
algorithms for parametric query optimization.
8 We support
however multiple cost metrics and hence the definition of
the pruning function, the type of the used data structures,
and the implementation of elementary operations on those
data structures differ.
Many algorithms for parametric query optimization are
based on the guiding principles of parametric query optimi-
5 They partition the parameter space in a more and
more fine-grained manner until a single query plan is opti-
mal in each partition.
6, 9 The condition that allows to verify
whether a single query plan is optimal in a given partition is
query and plans for subqueries), and the number of solved
linear programs. We generated query templates joining
between 2 and 12 tables and having between one and two
Optimization time increases in the number of tables.
As predicted by our formal analysis in the previous section,
optimization time also increases in the number of parameters. Optimization time grows faster in the number of query
tables for star queries than for chain queries. The reason is
that the number of admissible join orders grows faster in the
number of query tables for star queries. Speaking of admissible join orders, we mean join orders that comply with the
restriction mentioned before. Optimization time, the number of generated plans, and the number of solved linear programs are all correlated. This is intuitive as the number of
generated plans relates to the number of plan comparisons
that are required during pruning. The number of linear programs is related to the number of plan comparisons since
plan comparisons are realized by solving linear programs.
The time required for generating plans and for solving linear programs adds to optimization time.
The query sizes that we consider in our benchmark are
typical for query sizes as they appear in standard benchmarks: the queries in the popular TPC-H benchmarkb join at
most eight tables. MPQ takes longer than traditional query
optimization. In contrast to traditional query optimization,
MPQ takes, however, place before runtime. This makes
higher optimization times acceptable.
No. of tables
No. of tables
1 Par. 2 Par.
Figure 5. Optimization time, number of generated plans, and number
of solved linear programs.
Figure 6. Multi-objective parametric query optimization generalizes
the cost models of multi-objective and of parametric query
c ∈ ;
c ∈ ;m
c ∈ ;n → ;
c ∈ ;n → ;m