refers to a scenario in which two cost metrics, namely execution time and execution fees, are of interest. Cost functions
depend on a single parameter, called “Parameter 1” in the
figure, that could refer to unspecified predicates in the input
query template. We see the cost functions of three plans.
For parameter value 0, plan 1 is Pareto-optimal since it has
lowest execution fees. Plan 3 is Pareto-optimal since it has
lower execution time than all other plans. Plan 2 is, however,
dominated by plan 1 since plan 1 has equivalent execution
time and lower execution cost. This means that plan 2 is not
Pareto-optimal for parameter value 0. For parameter value 2,
the situation is similar and plans 1 and 3 are Pareto-optimal
while plan 2 is not. For parameter values between 0.5 and
1. 5, plan 2 is however Pareto-optimal. Even though the same
set of plans is Pareto-optimal at the borders of the parameter
value interval [0, 2], additional plans can be Pareto-optimal
for values at the interior of that interval. All plan cost functions are linear in the example and an interval is a special
case of a convex polytope. The example is minimal for MPQ:
having less than two cost metrics would lead to parametric
query optimization. Having less than one parameter would
lead to multi-objective query optimization. Hence, we can
conclude from this example that the guiding principles do
not apply for MPQ in general.
4. 2. Algorithm analysis
The space and time complexity of dynamic programming-based query optimization algorithms depends on the
number of plans stored per subquery. In traditional query
optimization, plans are compared according to one cost
metric and cost functions do not depend on parameters.
If we assume that alternative query plans are compared
based on their cost values alone then exactly one plan, a
plan with minimal cost, remains after pruning an arbitrary
set of plans. In parametric query optimization, plans are
compared according to one cost metric but cost functions
depend on parameters. This means that different plans
can be optimal for different parameter values. In multi-objective query optimization, we compare plans according to different cost metrics. Hence multiple plans can be
Pareto-optimal for each subquery. As a result, we generally
need to store multiple plans per subquery in parametric
and in multi-objective query optimization. The number
of plans to store depends on many factors. Research in
parametric query optimization has focused on analyzing
how the number of plans per subquery depends on the
number of parameters. Research in multi-objective query
optimization has focused on the dependency between the
number of plans and the number of cost metrics. Such
analysis is necessarily based on simplifying assumptions.
Traditionally, the weights that define the cost functions
of different query plans are assumed to follow independent random distributions.
6, 7 Based on that assumption,
the number of remaining plans after pruning can be considered a random variable as well and we can calculate its
expected value. This reasoning led to an asymptotic upper
bound of 2m, where m designates the number of cost metrics, on the expected number of plans per subquery in
multi-objective query optimization.
condition. The algorithm by Bemporad verifies whether the
union of a given set of convex polytopes forms a convex polytope again. If this is the case then the algorithm constructs
that polytope. The condition can only be verified
if forms a convex polytope. In that case, the algorithm
by Bemporad constructs the polytope and a linear
solver can verify whether P− and P+ are equivalent.
We analyze the formal properties of the freshly introduced
MPQ problem in this section. We also analyze the complexity of the algorithm described in the last section.
4. 1. Problem analysis
MPQ generalizes parametric query optimization since it
allows to consider multiple plan cost metrics instead of
only one. We compare the formal properties of MPQ to
the properties of parametric query optimization in the
The parametric query optimization problem with linear
cost functions has the following property: if the same query
plan is optimal at all vertices of a convex polytope in the
parameter space then that plan must be optimal inside the
polytope as well.
6 This property is commonly known as one
of the “guiding principle of parametric query optimization.”
Many algorithms for parametric query optimization exploit
this property as follows6, 9: they recursively decompose the
parameter space into convex polytopes and calculate optimal query plans at the vertices. Due to the guiding principle,
the decomposition of the parameter space can be stopped
once the same plan is optimal at all vertices of a polytope.
Such algorithms transform the parametric query optimization problem into a series of traditional query optimization
problems (calculating the optimal plan at a polytope vertex
is a traditional query optimization problem). This has the
advantage that traditional query optimizers can be used for
parametric query optimization with minimal changes. It is
therefore interesting to verify whether an analog property
holds for MPQ.
Unfortunately this is not the case as we show next. The
following property for MPQ would be analog to the guiding
principle of parametric query optimization: if the same set
of plans is Pareto-optimal at all vertices of a polytope in the
parameter space then that set of plans must be Pareto-optimal
inside the polytope as well. Figure 4 illustrates a counter
example showing that this property does not hold. The figure
0 0.5 1 1. 5 2
0 0.5 1 1. 5 2
Cost of Plan 1 Cost of Plan 2 Cost of Plan 3
Figure 4. The guiding principle of parametric query optimization
does not hold for multi-objective parametric query optimization.