OCTOBER 2017 | VOL. 60 | NO. 10 | COMMUNICATIONS OF THE ACM 85
to determine the parameter space region in which one function has lower values than the other one. Now, we generalize from linear cost functions to piecewise-linear functions.
Each piecewise-linear function partitions the parameter
space into convex polytopes in which the function is linear. If we compare two piecewise-linear functions then we
can partition the parameter space such that both functions
are linear in each partition. More precisely, we obtain the
aforementioned partitioning by intersecting the partitions
associated with the first cost function with the partitions
associated with the second function. Figure 3 illustrates
how we intersect two parameter space partitionings in a
two-dimensional parameter space. Having this partitioning, we apply the method for linear cost functions separately
in each partition. If we have the subregion in which a first
plan dominates a second one for each parameter space
region then the union of those subregions is the total area
in which the first plan dominates. If we have multiple cost
metrics instead of only one, then we can apply the method
described before for each cost metric separately. If we have
for each cost metric the parameter space region in which the
first plan dominates the second one then the intersection of
those areas (over all cost metrics) yields the area in which the
first plan is better according to all cost metrics.
Given the area in which a plan is dominated, we must subtract it from that plan’s Pareto region. The implementation
of this operation is straightforward: as discussed before, we
represent Pareto regions as a union of convex polytopes from
which other convex polytopes have been subtracted. The
region in which one plan dominates another one must consist of convex polytopes. In order to subtract such a region
from the Pareto region, we simply add the corresponding
polytopes to the list of subtracted polytopes.
We must determine whether a given Pareto region is
empty. A Pareto region is a set of polytopes from which other
polytopes have been subtracted. We consider first the special
case of one polytope P+ from which another set of polytopes
have been subtracted. We want to verify whether the
given polytope becomes empty after the subtractions. We
can verify that as follows. Assume that all subtracted poly-
topes are contained within P+. Then the region remaining
after subtraction becomes empty if and only if . We
can use the algorithm by Bemporad et al.
2 to check the latter
up to an arbitrary degree of precision (using more pieces
increases precision). In contrast to that, we cannot freely
decide which class of shapes we consider for representing
Pareto regions. The algorithm must be able to represent
each shape that could potentially occur during pruning.
Our decision to use piecewise-linear cost functions implies
the class of shapes that we need to consider as Pareto
We describe our representation of Pareto regions. We
motivate this representation in an informal way. It is, however, relatively easy to prove that the proposed representation covers all possible cases.
We start by considering the special case of linear cost
functions. Parametric query optimization is a special case
of MPQ. It has been shown in the domain of parametric query optimization that the parameter space region
in which one plan is better than another plan according
to one cost metric is a convex polytope if both plans have
linear cost functions.
6 In a setting with multiple cost metrics, a plan is strictly better than another plan if it is better
according to each cost metric. The region in which a plan
is better than another one is therefore an intersection of
multiple convex polytopes. An intersection of convex polytopes is a convex polytope again. The region in which all
other plans are better than a given plan is, hence, a union
of convex polytopes.
Now, let us generalize that reasoning from linear cost
functions to piecewise-linear cost functions. The generalization is straightforward. Given two piecewise-linear cost
functions, we can always partition the parameter space into
convex polytopes such that both cost functions are linear
in each polytope. Thereby we reduce the case of piecewise-linear cost functions to the case of linear cost functions. In
summary, we can represent the Pareto region of a plan as a
union of convex polytopes from which we subtract another
union of convex polytopes.
3. 4. Elementary operations
Having described the data structures used to represent cost
functions and Pareto regions, we outline now how to implement elementary operations on those data structures. We
require the following elementary operations to realize the
pruning function as described before. First, given the cost
functions of two plans, we must determine the parameter
space region in which one plan dominates the other one.
Second, given a Pareto region of a plan and a region in which
it is dominated, we must reduce the Pareto region by that
region. Third, given a Pareto region, we must determine
whether it is empty.
Convex polytopes are described by a set of linear inequalities and we consider linear cost functions. All elementary
operations that we describe in the following can, hence, be
realized by solving systems of linear inequalities. Executing
the elementary operations therefore requires a linear
We describe how to determine the parameter space
region in which one plan dominates another one. Assume
first that we have only one cost metric and that cost functions are linear. Then, we can directly use the linear solver
Figure 3. To compare two piecewise-linear cost functions, we
intersect the parameter space partitions in which each function is
linear. We compare the functions separately in each of the resulting