Optimization of queries with user-defined predicates.
Relational databases provide the ability to store user-defined functions and predicates which can be invoked in SQL queries. When evaluation of a user-defined predicate is relatively expensive, the traditional method of evaluating predicates as early as possible is no longer a sound heuristic. There are two previous approaches for optimizing such queries. However, neither is able to guarantee the optimal plan over the desired execution space. We present efficient techniques that are able to guarantee the choice of an optimal plan over the desired execution space. The optimization algorithm with complete rank-ordering improves upon the naive optimization algorithm by exploiting the nature of the cost formulas for join methods and is polynomial in the number of  user-defined predicates (for a given number of relations.) We also  propose pruning rules that significantly reduce the cost of searching the execution space for both the naive algorithm as well as for the optimization algorithm with complete rank-ordering, without compromising optimality. We also propose a conservative local heuristic that is simpler and has low optimization overhead. Although it is not always guaranteed to find the optimal plans, it produces close to optimal plans in most cases. We discuss how, depending on application requirements, to determine the algorithm of choice. It should be emphasized that our optimization algorithms handle user-defined selections as well as user-defined join predicates uniformly. We present complexity analysis  and experimental comparison of the algorithms.
Introduction
In order to efficiently execute complex database appli-
cations, many major relational database vendors provide
the ability to define and store user-defined func-
tions. Such functions can be invoked in SQL queries
and make it easier for developers to implement their
applications. However, such extensions make the task
of the execution engine and optimizer more challeng-
ing. In particular, when user-defined functions are used
in the Where clause of SQL, such predicates cannot be
treated as SQL built-in predicates. If the evaluation of
such a predicate involves a substantial CPU and I/O
cost, then the traditional heuristic of evaluating a predicate
as early as possible may result in a significantly
suboptimal plan. We will refer to such predicates as
user-defined (or, expensive) predicates.
Consider the problem of identifying potential customers
for a mail-order distribution. The mail-order
company wants to ensure that the customer has a high
credit rating, is in the age-group 30 to 40, resides in
the San Francisco bay area, and has purchased at least
$1,000 worth of goods in the last year. Such a query
involves a join between the Person and the Sales relation
and has two user-defined functions zone and
high credit rating.
Select name, street-address, zip
From Person, Sales
Where high-credit-rating(ss-no)
and age In [30,40]
and "bay area"
and Person.name = Sales.buyer-name
Group By name, street-address, zip
Having Sum(sales.amount) ? 1000
Let us assume that the predicate high credit rating
is expensive. In such a case, we may evaluate the
predicate after the join so that fewer tuples invoke the
above expensive predicate. However, if the predicate
is very selective, then it may still be better to execute
high credit rating so that the cost of the join is re-
duced. Such queries involving user-defined predicates
occur in many applications, e.g., GIS and multi-media.
This paper shows how commercial optimizers, many
of which are based on system R style dynamic programming
algorithm [SAC + 79], can be extended easily to be
able to optimize queries with user-defined predicates.
We propose an easy extension of the traditional optimizer
that is efficient and that guarantees the optimal.
We associate a per tuple cost of evaluation and a selectivity
with every user-defined predicate (as in [HS93]).
While the task of optimizing queries with user-defined
predicates is important, there are other interesting directions
of research in user-defined predicates, e.g., use
of semantic knowledge, e.g., [PHH92, CS93].
As pointed out earlier, the traditional heuristic of
evaluating predicates as early as possible is inappropriate
in the context of queries with user-defined predi-
cates. There are two known approaches to optimizing
queries that treat user-defined predicates in a special
way. The first technique, used in LDL [CGK89] is exponential
in the number of expensive predicates and
it fails to consider the class of traditional plans where
user-defined predicates are evaluated as early as possi-
ble. The second technique, known as Predicate Migration
[HS93] is polynomial in the number of expensive
predicates and takes into consideration the traditional
execution space as well. However, this algorithm cannot
guarantee finding the optimal plan. Moreover, in
the worst case, it may need to exhaustively enumerate
the space of joins (O(n!) in the number of joins n in
the query).
Our algorithm finds the optimal plan without ever
requiring to do an exhaustive enumeration of the space
of join orderings. The complexity of the algorithm is
polynomial in the number of user-defined functions 1 .
Our approach does not require any special assumptions
about the execution engine and the cost model. In
designing this optimization algorithm, we discovered a
powerful pruning technique (pushdown rule) that has
broader implication in other optimization problems as
well [CS96].
Although the optimization algorithm that guarantees
the optimal has satisfactory performance for a
large class of queries, its complexity grows with the
increasing query size. Therefore, we wanted to investigate
if simpler heuristics can be used as an alterna-
tive. The conservative local heuristic that we present
guarantees optimality in several cases and experimental
results show that it chooses an execution plan very
1 The complexity is exponential in the number of joins. This
is not unexpected since the traditional join optimization problem
itself is NP-hard.
close to the optimal while being computationally in-
expensive. Thus, this heuristic serves as an excellent
alternative where query size or complexity of the optimization
algorithm is a concern.
We have implemented the optimization algorithm as
well as the heuristic by extending a System-R style op-
timizer. We present experimental results that illustrate
the characteristics of the optimization algorithms proposed
in this paper.
The rest of the paper is organized as follows. In the
next section, we review the System R optimization algorithm
which is the basis of many commercial
optimizers. Next, we describe the desired execution
space and review the past work on optimizing queries
with user-defined predicates. Sections 4 and 5 describe
the optimization algorithm and the conservative local
heuristic respectively. The performance results and implementation
details are given in Section 6.
2 System R Dynamic Programming Algorith

Many commercial database management systems have
adopted the framework of the System R optimizer
which uses a dynamic programming
algorithm. The execution of a query is represented
syntactically as an annotated join tree where the internal
node is a join operation and each leaf node is
a base relation. The annotations provide the details
such as selection predicates, the choice of access paths,
join algorithms and projection attributes of the result
relation. The set of all annotated join trees for a query
that is considered by the optimizer will be called the
execution space of the query. A cost function is used to
determine the cost of a plan in the execution space and
the task of the optimizer is to choose a plan of minimal
cost from the execution space. Most optimizers of
commercial database systems restrict search to only a
subset of the space of join ordering. Most optimizers
of commercial database systems restrict search to only
a subset of the space of join ordering. In many opti-
mizers, the execution space is restricted to have only
linear join trees, whose internal nodes have at least
one of its two child nodes as a leaf (base relation). In
other words, a join with N relations is considered as
a linear sequence of 2-way joins. For each intermediate
relation, the cardinality of the result size and other
statistical parameters are estimated.

Figure

1 (adopted from [GHK92]) illustrates the System
R dynamic programming algorithm that finds an
optimal plan in the space of linear (left-deep) join
trees 79]. The input for this algorithm is a select-
project-join (SPJ) query on relations R 1 ,.,R n . The
procedure DP Algorithm:
for to n do f
for all S ' fR 1 ; :::; Rng s.t.
bestPlan := a dummy plan with infinite cost
for all R j
if cost(p) - cost(bestPlan)
bestPlan := p

Figure

1: System R Algorithm for Linear Join Trees
function joinPlan(p,R) extends the plan p into another
plan that is the result of p being joined with the base relation
R in the best possible way. The function cost(p)
returns the cost of the plan p. Optimal plans for sub-sets
are stored in the optPlan() array and are reused
rather than recomputed.
The above algorithm does not expose two important
details of the System R optimization algorithm. First,
the algorithm uses heuristics to restrict the search
space. In particular, all selection conditions and secondary
join predicates are evaluated as early as pos-
sible. Therefore, all selections on relations are evaluated
before any join is evaluated. Next, the algorithm
also considers interesting orders. Consider a plan P for
uses sort-merge join and costs more than
another plan P 0 that uses hash-join. Nonetheless, P
may still be the optimal plan if the sort-order used in
P can be reused in a subsequent join. Thus, the System
R algorithm saves not a single plan, but multiple optimal
plans for every subset S in the Figure, one for each
distinct such order, termed interesting order [SAC
Thus, a generous upper bound on the number of plans
that must be optimized for a query with joins among
n tables is O(2 n ) (the number of subsets of n tables)
times the number of interesting orders.
3 Execution Space and Previous Ap-
proaches
As mentioned earlier, for traditional SPJ queries, many
optimizers find an optimal from the space of linear
join orderings only. When user-defined predicates are
present, the natural extension to this execution space
consists of considering linear sequence of joins, and allowing
an expensive predicate to be placed following
any number of (including zero) joins. Thus, an expensive
selection condition can be placed either immediately
following the scan of the relation on which it ap-
plies, or after any number of joins following the scan.
Likewise, an expensive secondary join predicate can be
placed either immediately after it becomes evaluable
(following the necessary joins), or after any number of
subsequent joins. In other words, this execution space
restricts the join ordering to be linear but allows expensive
predicates to be freely interleaved wherever they
are evaluable. We refer to this execution space as unconstrained
linear join trees. This is the same execution
space that is studied in [HS93, Hel94]. In this
section, we discuss two approaches that have been studied
in the past for optimizing queries with user-defined
predicates.
3.1 Approach
In this approach, an expensive predicate is treated
as a relation from the point of view of optimiza-
tion. This approach was first used in the LDL project
at MCC [CGK89] and subsequently at the Papyrus
project at HP Laboratories [CS93]. Viewing expensive
predicates as relations has the advantage that the
System-R style dynamic programming algorithm can
be used for enumerating joins as well as expensive pred-
icates. Thus, if e is an expensive predicate and R 1 and
R 2 are two relations, then the extended join enumeration
algorithm will treat the optimization problem as
that of ordering R 1 , R 2 and e using the dynamic programming
algorithm.
Shortcoming of the
This approach suffers from two drawbacks both of
which stem from the problem of over-generalizing and
viewing an expensive predicate as a relation. First, the
optimization algorithm is exponential not only in the
number of relations but also in the number of expensive
predicates. Let us consider the case where only
linear join trees are considered for execution. Thus, in
order to optimize a query that consists of a join of n
relations and k expensive predicates, the dynamic programming
algorithm will need to construct O(2 n+k ) optimal
subplans. In other words, the cost of optimizing
a relation with n relations and k expensive predicates
will be as high as that of optimizing (n+k) relations.
Another important drawback of this approach is that
if we restrict ourselves to search only linear join trees,
then the algorithm cannot be used to consider all plans
in the space of unconstrained linear trees. In particu-
lar, the algorithm fails to consider plans that evaluate
expensive predicates on both operands of a join prior
to taking the join [Hel94]. For example, assume that
R 1 and R 2 are two relations with expensive relations
e 1 and e 2 defined on them. Since the LDL algorithm
treats expensive predicates and relations alike, it will
only consider linear join sequences of joins and selec-
tions. However, the plan which applies e 1 on R 1 and
e 2 on R 2 and then takes the join between the relations
R 1 and R 2 , is not a linear sequence of selections and
joins. Thus, this algorithm may produce plans that
are significantly worse than plans produced by even
the traditional optimization algorithm.
3.2 Predicate Migration
Predicate Migration algorithm improves on the LDL
approach in two important ways. First, it considers
the space of unconstrained linear trees for finding a
plan, i.e., considers pushing down selections on both
operands of a join. Next, the algorithm is polynomial
in the number of user defined predicates. However,
the algorithm takes a step backwards from the LDL
approach in other respects. This will be discussed later
in this section.
We will discuss two aspects of this approach. First,
we will discuss the predicate migration algorithm,
which given a join tree, chooses a way of interleaving
the join and the selection predicates. Next, we will describe
how predicate migration may be integrated with
a System R style optimizer [HS93, Hel94].
The predicate migration algorithm takes as input a
join tree, annotated with a given join method for each
join node and access method for every scan node, and
a set of expensive predicates. The algorithm places the
expensive predicates in their "optimal" (see discussion
about the shortcomings) position relative to the join
nodes. The algorithm assumes that join costs are linear
in the sizes of the operands. This allows them to
assign a rank for each of the join predicate in addition
to assigning ranks for expensive predicates. The notion
of rank has been studied previously in [MS79, KBZ86].
Having assigned ranks, the algorithm iterates over each
stream, where a stream is a path from a leaf to a root
in the execution tree. Every iteration potentially rearranges
the placement of the expensive selections. The
iteration continues over the streams until the modified
operator tree changes no more. It is shown in [HS93]
that convergence occurs in a polynomial number of
steps in the number of joins and expensive predicates.
The next part of this optimization technique concerns
integration with the System R style optimizer.
The steps of the dynamic programming algorithm are
followed and the optimal plan for each subexpression
is generated with the following change. At each
join step, the option of evaluating predicates (if ap-
plicable) is considered: Let P be the optimal plan of
oe e (R 1 S) and P 0 be the optimal plan for oe e (R) 1 S.
then the algorithm prunes the
plan P 0 without compromising the optimal. However,
if the plan for P 0 is cheaper, then dynamic programming
cannot be used to extend the plan P 0 . Rather, the
plan P 0 is marked as unprunable. Subsequently, when
constructing larger subplans, the algorithm ignores the
unprunable plans. After the dynamic programming algorithm
terminates, each such unprunable plans needs
to be extended through exhaustive enumeration, i.e.,
all possible ways of extending each unprunable plan
are considered.
Shortcomings of the
This approach to optimization has three serious drawbacks
that limit its applicability. First, the algorithm
requires that cost formulas of join to be linear in the
sizes of the inputs. Next, the algorithm cannot guarantee
an optimal plan even if a linear cost model is
used. This is because the use of predicate migration
algorithm may force estimations to be inaccurate. In
a nutshell, predicate migration requires a join predicate
to be assigned a rank , which depends on the cost
of the join and the latter is a function of the input
sizes of the relations. Unfortunately, the input sizes
for the join depends on whether the expensive predicates
have been evaluated! This cyclic dependency
forces predicate migration to make an ad-hoc choice in
calculating the rank. During this step, the algorithm
potentially underestimates the join cost by assuming
that all expensive predicates have been pushed down.
This ad-hoc assumption sacrifices the guarantee of the
optimality (See Section 5.2 of [Hel94] for a detailed dis-
cussion). Finally, the global nature of predicate migration
hinders integration with a System R style dynamic
programming algorithm. The algorithm may degenerate
into exhaustive enumeration. Let us consider a
query that has n relations and a single designated expensive
predicate e on the relation R 1 . Let us assume
that for the given database, the traditional plan where
the predicate e is evaluated prior to any join, is the
optimal plan. In such a case, plans for oe e (R
(i 6= 1) will be marked as unprunable. For each of
these plans, there are (n \Gamma 2)! distinct join orderings
and for each of these join orderings, there can be a
number of join methods. Thus, in the worst case, the
optimization process requires exhaustive enumeration
of the join space.
4 Dynamic Programming Based Optimization
Algorithms
Our discussion of the previous section shows that none
of the known approaches are guaranteed to find an optimal
plan over the space of unconstrained linear join
trees. In this section, we present our optimization algorithm
which is guaranteed to produce an optimal plan
over the above execution space. To the best of our
knowledge, this is the first algorithm that provides such
a guarantee of optimality. The techniques presented in
this section are readily adaptable for other join execution
spaces as well (e.g., bushy join trees) [CS96].
Our algorithm has the following important properties
as well: (1) it is remarkably robust . It is free from
special restrictions on cost model or requirements for
caching (2) The algorithm integrates well with dynamic
programming based algorithm used in commercial op-
timizers, and never requires exhaustive enumeration.
(3) The algorithm is polynomial in the number of user-defined
predicates. We provide a succinct characterization
of what makes this optimization problem polynomial
and the parameters that determine its complexity
of optimization.
Thus, our algorithm successfully addresses the short-comings
of the Predicate migration algorithm without
sacrificing the benefit of considering the execution
space of unconstrained linear join trees and ensuring
that the complexity of optimization grows only polynomially
with the increasing number of user-defined
functions.
For notational convenience, we will indicate ordering
of the operators in a plan by nested algebraic expres-
sions. For example, (oe e (R
a plan where we first apply selection e on relation
that relation with R 2 before joining
it with the relation R 3 , which has been reduced
by application of a selection condition e 0 . In describing
the rest of this section, we make the following two
assumptions: (a) all user-defined predicates are selec-
tions. This assumption is to simplify the presentation.
Our algorithms accommodate user-defined join predicates
as well and preserves the guarantee of optimality
as well as properties (1)-(3) above [CS96] (b) no traditional
interesting orders are present. This assumption
is for ease of exposition only.
We begin by presenting the "naive" optimization algorithm
that guarantees optimality and has properties
(1) through (3) above. Next, we present two powerful
pruning techniques that significantly enhance the efficiency
of the optimization algorithm, as will be shown
later in the experimental section.
4.1 Naive Optimization Algorithm
The enumeration technique of our algorithm relies on
clever use of the following two key observations:
Equivalent Plan Pruning Rule: The strength of the
traditional join enumeration lies in being able to compare
the costs of different plans that represent the same
subexpression but evaluated in different orders. Since
selection and join operations may be commuted, we
can extend the same technique to compare and prune
plans for queries that have the same expensive predicates
and joins, i.e., if P and P 0 are two plans that
represent the same select-project-join queries with the
same physical properties, and if
then P may be pruned. For example, we can compare
the costs of the plans P and P 0 where P is the
plan (oe e (R is the plan
(R (R 1 ).
Selection Ordering: Let us consider conjunction of a set
of expensive selection predicates applied on a relation.
The problem of ordering the evaluation of these predicates
is the selection ordering problem. The complexity
of selection ordering is very different from that of ordering
joins among a set of relations. It is well-known
that for traditional cost models, the latter problem is
NP-hard. On the other hand, the selection ordering
problem can be solved in polynomial time. Further-
more, the ordering of the selections does not depend
on the size of the relation on which they apply. The
problem of selection ordering was addressed in [HS93]
(cf. [KBZ86, MS79, WK90]). It utilizes the notion of
a rank. The rank of a predicate is the ratio
where c is its cost per tuple and s is its selectivity.
Theorem 4.1: Consider the query oe e (R) where
. The optimal ordering of the predicates in
e is in the order of ascending ranks and is independent
of the size of R.
For example, consider two predicates e and e 0 with
selectivities :2 and :6 and costs 100 and 25. Although
the predicate e is more selective, its rank is 125 and
the rank of e 0 is 62:5. Therefore evaluation of e 0 should
precede that of e. The above technique of selection
ordering can be extended to broader classes of boolean
expressions [KMS92].
Ensuring Complete Enumeration Efficiently
Equivalent plan pruning rule allows us to compare two
plans that represent the same expression. This observation
will help us integrate well with the System
R algorithm and avoid exhaustive enumeration (unlike
predicate migration). On the other hand, selection ordering
tells us that (in contrast to the LDL algorithm),
we can treat selections unlike relations to make enumeration
efficient. Indeed, this observation is what makes
our algorithm polynomial in the number of user-defined
predicates. Therefore, the challenge is to treat selections
differently from joins while enumerating but to
be still able to compare costs of two plans when they
represent the same expression. In order to achieve this
goal, we exploit the well-known idea of interesting orders
in a novel way.
We keep multiple plans that represent the join of the
same set of relations but differ in the sets of predicates
that have been evaluated. In other words, with every
join plan, an additional "tag" is placed, which records
the set of predicates that have been evaluated in the
plan. Thus, a tag acts very much like an interesting order
from the point of view of join enumeration. This is
a useful way of thinking about enumerating the space
of execution plans since the selection ordering rule ensures
that we need "a few" tags. Notice that whenever
two plans represent the join of same set of relations and
agree on the tags, they can be compared and pruned.

Figure

2 illustrates the execution plans (and sub-
plans) that need to be considered when there are three
relations and two expensive selection predicates e 1 and
e 2 on R 1 . P 1 , P 2 and P 3 are possible plans for R 1
(each with differing tags). The plans from P 5 to P 13
are for R 1 We will distinguish between
since they will have different tags, but will
keep a single plan among P 5 , P 7 . We now
formalize the above idea.
Tags
Let us consider a join step where we join two relations
R 1 and R 2 . Let us assume that (p are the
predicates applicable on R 1 , in the order of the increasing
rank. From the selection ordering criterion, we conclude
that if the predicate p j is applied on R 1 prior to
the join, then so must all the predicates p 1 In
other words, there can be at most (m possibilities
for pushing down selections on R 1 : (a) not applying
any predicate at all (b) applying the first j predicates
only where j is between 1 and m. Likewise, if the predicates
applicable on R 2 are (q are
at most (s+1) possibilities. Thus, altogether there can
be (m plans for the join between R 1 and
R 2 that differ in the applications of selections prior to
the join. We can denote these plans by P
where P r;t designates the plan that results from evaluating
to the join. The selection ordering plays a crucial role
in reducing the number of tags from exponential to
a polynomial in the number of user defined predicates.
Observe that if we cannot have a linear ordering among
selections, then we have to consider cases where any
subset of the selection predicates are chosen for evaluation
prior to the join. In that case, in the above join
between R 1 and R 2 , the number of plans can be as
many as 2 m+1 :2 s+1 .
We generalize the above idea in a straight-forward
fashion. For a subquery consisting of the join among
relations fR there will be at most (m 1
plans that need
to be kept where m j represents the number of expensive
predicates that apply on R ij . We will associate a
distinct tag with each of these plans over the same sub-
query. We now sketch how tags may be represented.
We assign a number to each expensive predicate according
to the ordering by rank. If an user-defined
selection condition is present over w of the relations
(say, R in the query, then with each plan,
we associate a vector of width w. If ! a
the tag vector with a plan P , then it designates that
all expensive predicates of rank lower or equal to a j on
R uj have been evaluated in P for all 1 - j - w. We
defer a full discussion of the scheme for tagging to the
extended version of our forthcoming report [CS96], but
illustrate the scheme with the following example.
Example 4.2 : Consider a query that represents a
join among four relations R selections
where the selections are numbered by their relative increasing
rank. The relation R 1 has three predicates
numbered 2,5,6. Let R 2 have three predicates 1,3,4.
Let R 3 have predicates 7,8,9. The relation R 4 has no
predicates defined. The tag vector has three positions,
where the ith position represents predicates on the relation
R i . There are altogether 16 plans for join over
each with a distinct tag. Consider the plan
for the tag vector ! 5; 4; 0 ?. This plan can be joined
with the relation R 3 . Depending on the selection predicates
evaluated prior to the join, there will be altogether
8 plans with different tag vectors that extend
the above plan. In particular, a plan will be generated
with a tag vector ! 5; 4; 8 ?. This plan can be compared
with the plan obtained by extending a plan for
with the tag vector ! 0; 4; 8 ? through a join
with R 1 and evaluating predicates 2 and 5 on R 1 prior
to the join.
In the above example, we illustrated how we can prune
plans with the same tag vector and over the same set
of relations. This is unlike the approaches in [HS93,
Hel94] where once a user-defined predicate has been
"pushed-down", the plan is unprunable.
Algorithm: The extensions needed to the algorithm
in

Figure

1 for the naive optimization algorithm are
straightforward. There is no longer a single optimal
plan for S j (in Figure 1), but there may be multiple
plans, one for each tag vector. Thus, we will need to
iterate over the set of possible tags. For each such optimal
plan S t
j with a tag t, we consider generating all
(R1

Figure

2: Search Space of Naive Optimization Algorithm
possible legal tags for S. For each such tag t 0 , joinPlan
needs to be invoked to extend the optimal plan S t
. We
need to also ensure that we compare costs of plans that
have the same tag.
4.2 Complexity
In the optimization algorithm that we presented, we exploited
dynamic programming as well as selection or-
dering. The latter makes it possible for us to have
an optimization algorithm which is polynomial in k
whereas the former made it possible for us to retain
the advantage of avoiding exhaustive enumeration of
the join ordering. The efficiency of our algorithm is
enhanced by the applications of pruning rules that will
be described in the next section.
Let us consider a query that consists of a join among
relations and that has k user-defined predicates. Let
us assume that only g of the n relations have one or
more user-defined selection conditions. Furthermore,
let w be the maximum number of expensive predicates
that may apply on one relation. In such cases, the
number of tags can be no more than (1+w) g . Further-
more, we can show that the total number of subplans
that need to be stored has a generous upper-bound of
. Note that since n is the total number
of relations and k is the total number of user-defined
predicates, k. Therefore, the above formula
can be used to derive an upper-bound of (2+k) n .
Hence, for a given n, the upper-bound is a polynomial
in k. The above is a very generous upper bound and
a more detailed analysis will be presented in [CS96].
Observe that as in the case of traditional join enumer-
ation, the complexity is exponential in n.
The analysis of our complexity shows that the complexity
is sensitive to the distribution of predicates
among relations as well as to the number of predicates
that may apply to a single relation. In particular, if
all user-defined predicates apply to the same relation,
then the complexity is O(2 n )(1+k=2), a linear function
of k. The complexity of this algorithm grows with the
number of relations over which user-defined predicates
occur since they increase the number of tags exponen-
tially. In the full paper, we study the effect of varying
distributions of user-defined predicates on efficiency of
the optimization algorithms [CS96].
It is important to recognize how we are able to avoid
the worst cases that predicate migration algorithm en-
counters. Predicate migration algorithm has worst running
time when user-defined predicates turn out to be
relatively inexpensive (i.e., has low rank). It is so since
in such cases, unprunable plans are generated (See Section
3). On the other hand, our optimization algorithm
prepares for all possible sequences of predicate push-down
through the use of tags. Furthermore, since in
many applications, we expect the number of expensive
user-defined functions in the query to be a few and less
than the number of joins, it is important to ensure that
the cost of join enumeration does not increase sharply
due to presence of a few user-defined predicates. How-
ever, as pointed out earlier, even with a single user-defined
predicate over n joins, the worst-case complexity
of predicate migration can be O(n!). Our approach
overcomes the above shortcoming of predicate migration
effectively.
4.3 Efficient Pruning Strategies
The naive algorithm can compare plans that have the
same tags only. In this section, we will augment our
"naive" optimization algorithm with two pruning tech-
niques. The pruning techniques that we propose here
allow us to compare and prune plans that have different
tags. These pruning techniques are sound, i.e., guaranteed
not to compromise the optimality of the chosen
plan.
Pushdown Rule
This rule says that if the cost of evaluating the selections
(prior to the join) together with the cost of the
join after the selections are applied, is less than the cost
of the join without having applied the selections, then
we should push down the selections 2 . For example,
in

Figure

2, if the cost of P 5 is less than the cost of
8 we can prune P 8 . In naive optimization algorithm,
we had to keep both P 5 and P 8 since they had different
tags, i.e., different numbers of expensive predicates
were applied.
be a plan for the join R 1 S.
Let P be a plan that applies an user-defined predicate
e on the relation R before taking the join with S, (i.e.,
may be pruned.
We refer to the above lemma as the pushdown rule.
The soundness of the above lemma follows from the observation
that for SPJ queries with the same interesting
order, the cost is a monotonic function of sizes of relations
[CS96]. A consequence of this rule is that if P 0 is
a plan that has a set S 0 of expensive predicates applied,
then it can be pruned by another plan P over the same
set of relations where (a)
has a set S of expensive predicates applied where S is
a superset of S 0 (therefore, S Given two plans
over the same set of relations, we can easily check (b)
by examining the tag vectors of P and P 0 [CS96]. If
indeed (b) holds, then we say T dominates T 0 , where
are tags of P 0 and P . We can rephrase the
above lemma to conclude the following:
are two plans over the
same set of relations with the tags T and T 0 such that
dominates
may be pruned.
For a given plan P , the set of plans (e.g., P 0 ) that the
above corollary allows us to prune will be denoted by
pushdown expensive(P ).
Strictly speaking, the lemma can be used to compare plans
that have the same interesting order.
us consider the previous exam-
ple. For the plan that represents the join among
there will be altogether 64 tags. How-
ever, if the cost of the plan with the tag ! 6; 4; 9 ? is
lower than that of ! 5; 4; 8 ?, we can use the pushdown
rule to prune the latter plan.
Pullover Rule
This rule says that if locally deferring evaluation of a
predicate leads to a cheaper plan than the plan that
evaluates the user-defined predicate before the join,
then we can defer the evaluation of the predicate without
compromising the optimal. The soundness of this
rule uses the dynamic programming nature of the System
R algorithm and can be established by an inductive
argument. For example, if the cost of the plan extending
P 6 with evaluation of e 2 (i.e., oe e2 (oe e1 R 1
less than the cost of P 5 in Figure 2, we can prune P 5 .
In naive optimization algorithm, we had to keep both
since they had different tags, i.e., different
number of predicates were applied to each of the plans.
e be a user-defined predicate on a
relation R. Let P and P 0 represent the optimal plans for
oe e (R 1 S) and oe e (R) 1 S respectively. If Cost(P
may be pruned.
We refer to the above as the pullover rule since the
plan P in the lemma corresponds to the case where the
predicate is pulled up. This rule can also be used in the
context of predicate migration to reduce the number of
unprunable plans generated (cf. [HS93]). We can use
the pullover rule for pruning plans as follows. Let us
consider plans P and P 0 over the same set of relations
but with different tags T and T 0 . If the tag T dominates
predicates that are evaluated in T 0 are also
evaluated in T . Let Diff(T; T 0 ) represent the set of
predicates that are evaluated in T but not in T 0 . We
can then use the Pullover rule to obtain the following
corollary. Intuitively, the corollary says that we can
compare cost(P ), with that of cost(P
the cost of evaluating predicates Diff(T; T 0 ) after the
join in P 0 .
Corollary 4.7: Let P and P 0 be two plans with tags T
and T 0 over the same set of relations and T dominates
be the plan obtained by applying the predicates
in Diff(T; T 0 ) to P 0 . If cost(P 00
then P may be pruned.
For a given P , we can construct a set of all such plans
each of which may be used to prune P . We can refer
to the above set as pullover cheaper(P ). The following
example illustrates the corollary. For example, consider
Example 4.5 with the following change: the cost of the
plan P with the tag T =! 6; 4; 9 ? is higher than the
cost of the plan P 0 with the tag T 0 =! 5; 4; 8 ?. Notice
that the tag ! 6; 4; 9 ? dominates the tag ! 5; 4; 8 ?.
The set Diff(T; T 9g. In such a case, the above
lemma allows us to prune the plan P if the cost of the
plan P 0 with the added cost of evaluating the set of
predicates f6; 9g after the join exceeds the cost of P .
4.4 Optimization Algorithm with Pruning
In this section, we augment the naive optimization algorithm
with the pruning strategies. The extended algorithm
is presented in Figure 3. The P lantable data
structure stores all plans that need to be retained for
future steps of the optimizer. For every subset of re-
lations, the data structure stores potentially multiple
plans. The different plans correspond to different tags.
Storing such plans requires a simple extension of the
data structure used to represent plans with interesting
orders in the traditional optimizers.
In determining the access methods and choice of join
methods, the algorithm behaves exactly like the traditional
algorithm in Figure 1. However, when there
are s applicable user-defined predicates on the operand
applicable predicates on the operand R j , the
algorithm iteratively considers all (r possibilities
which corresponds to applying the first u predicates
and the first v predicates on S j and R j respectively
where the predicates are ordered by ranks. This
is the inner loop of the algorithm and is represented by
extjoinP lan. It should be noted that S j is an intermediate
relation and so the first u predicates on S j may
include predicates on multiple relations that have been
joined to form S j .
The choices of u and v uniquely determine the tag
for the plan p in Figure 3. The plan p will be compared
against plans over the same set of relations that have
already been stored. The plan p is pruned and the
iteration steps to the next (u; v) combination if one
of the following two conditions holds: (1) If p is more
expensive than the plan in the P lantable with the same
tag, if any. (2) If the set of plans pullover cheaper(p)
is empty, i.e., the pullover rule cannot be used to prune
p.
Otherwise, the predicate addtotable(p) becomes true
and the plan p is added to P lantable. Next, this new
plan p is used to prune plans that are currently in
plantable. In the algorithm, we have designated this
set of pruned plans by pruneset(p). They may be:
(1) The stored plan with the same tag, if it exists in
the P lantable and is more expensive. (2) The set of
plans in pushdown expensive(p) , i.e., plans that may
be pruned with p using the pushdown rule.
procedure Extended DP-Algorithm:
for to n do f
for all S ' fR 1 ; :::; Rng s.t.
bestPlan := a dummy plan with infinite cost
for all R j
s := Number of evaluable predicates on S j
r := Number of evaluable predicates on R j
for all u := 0 to s do
for all v := 0 to r do
if addtotable(p) then f
remove pruneset(p)
add p to Plantable
for all plan q of fR 1 ; :::; Rng do
complete the plan q
and estimate its cost
return (MinCost(Final))

Figure

3: The Optimization Algorithm with Pruning
for Linear Join Trees
At the end of the final join, we consider all plans
over the relations fR ng. Some of these plans may
need to be completed by adding the step to evaluate
the remainder of the predicates. Finally, the cheapest
among the set of completed plans is chosen.
5 Conservative Local Heuristic
Although the optimization algorithm with novel pruning
techniques guarantees the optimal plan and is computationally
efficient, the conservative local heuristic
that we propose in this section has remarkable qualities
that make it an attractive alternative for implementa-
tion. First, incorporating the heuristic in an existing
System-R style optimizer is easier since tags do not
need to be maintained. Next, incorporating the heuristic
increases the number of subplans that need to be
optimized for a query by no more than a factor of 2
compared to the traditional optimization, independent
of the number of user-defined predicates in the query.
Finally, there are a number of important cases where
the algorithm guarantees generation of an optimal execution
plan.
The simplest heuristics correspond to pushing all expensive
predicates down or deferring evaluation of all
expensive predicates until the last join. These heuristics
do not take into account the costs and selectivities
of the predicates and therefore generate plans of low
quality. Recently, a new heuristic, Pullrank , was proposed
but it was found that the heuristic fails to generate
plans of acceptable quality [Hel94]. We begin by describing
PullRank, characterizing its shortcomings and
then presenting the conservative local heuristic.
Pullrank maintains at most one plan over the same
set of relations. At each join step, for every choice of
the set of predicates that are pushed down, the Pull-
rank algorithm estimates the sum of the costs (we will
call it completion cost) of the following three components
(i) Cost of evaluating expensive predicates that
are pushed down at this step (ii) Cost of the join, taking
into account the selectivities of expensive predicates
that are applied (iii) Cost of evaluating the remainder
of the user-defined functions that are evaluable
before the join but were deferred past the join.
Pullrank chooses the plan that has the minimum completion
cost. Thus, the algorithm greedily pushes down
predicates if the cost of deferring the evaluation of predicates
past the join is more expensive, i.e., if Pullrank
decides that evaluating a predicate u before a join j is
cheaper than evaluating the predicate u immediately
following j, then evaluation of u will precede j in the
final plan, i.e., Pullrank will not consider any plans
where u is evaluated after j. Thus, Pullrank fails to
explore such plans where deferring evaluation of predicates
past more than one joins is significantly better
than choosing to greedily push down predicates based
on local comparison of completion costs.
In order to address the above drawback of Pullrank,
the conservative local heuristic picks one additional
plan (in addition to the plan picked by Pullrank) at
each join step based on sum of the costs of (i) and
(ii) only. Let us refer to this cost metric as pushdown-
join cost. This is the same as assuming that deferred
predicates are evaluated for "free" (i.e., cost component
(iii) is zero). In other words, the plans chosen
using such a metric favor deferring predicates unless
the evaluation of predicates helps reduce the cost of
the current join. Thus, since conservative local heuristic
picks two plans, one for completion cost and the
other for pushdown-join cost, it is possible that the
plan where the predicate u is deferred past j as well as
the plan where u is pushed down prior to j (chosen by
Pullrank), is considered towards the final plan. Thus,
conservative local heuristic can find optimal plans that
Pullrank and other global heuristics fail to find due to
its greedy approach. This is illustrated by the following
example.
Example 5.1 : Consider the query
us assume that the plan oe e (R 1
R 3 ) is optimal. Note that none of the global heuristic
that either pushes down or pulls up all the selections
can find the optimal. If the plan for oe e (R
is cheaper than oe e (R 1 greedily
pushes down P and fails to obtain the optimal. How-
ever, our algorithm uses the plan R 1 in the next
join step to obtain the optimal. This is an example
where a pullup followed by a pushdown was optimal
and therefore only our algorithm was able to find it.
For join of every subset of relations, at most two
plans are stored by conservative local heuristic. There-
fore, we never need to consider optimizing more than
plans. Thus, unlike the algorithm in Figure 3,
the number of subplans that need to be optimized does
not grow with the increasing number of user-defined
predicates. In general, conservative local heuristic may
miss an optimal plan. Intuitively, this is because in
this algorithm, distinctions among the tags are not
made. Nevertheless, the experimental results indicate
that the quality of the plan is very close to the optimal
plan [CS96]. Furthermore, as the following lemma
states, the conservative local heuristic produces an optimal
plan in several important special cases.
Lemma 5.2: The conservative local heuristic produces
an optimal execution plan if any one or more of the following
conditions are true:(1) The query has a single
join. (2) The query has a single user-defined predicate.
(3) The optimal plan corresponds to the case where all
the predicates are pushed down. (4) The optimal corresponds
to the case where all the predicates are deferred
until all the joins are completed.
6 Performance Evaluation
We implemented the optimization algorithms proposed
in this paper by extending a System R style optimizer.
In this section, we present results of doing performance
evaluations on our implementations. In particular, we
(1) The pruning strategies that we proposed improve
the performance of naive optimization algorithm significantly

(2) The plans generated by the traditional optimization
algorithm suffers from poor quality.
(3) The plans generated by PullRank algorithm are
better (less expensive) than the plans generated by
a traditional optimizer, but is still significantly worse
than the optimal.
(4) The conservative local heuristic algorithm reduces
the optimization overhead and it generates plans that
are very close to the optimal.
Number
of
Enumerated
Plans
Number of UDPs for One Relation
Traditional Algorithm
Pull-Rank Algorithm
Conservative Local Heuristic Algorithm
Optimization Algorithm with Pruning
Naive Optimization Algorithm
Relative
Cost
Number of UDPs for One Relation
Traditional Algorithm
Pull-Rank Algorithm
Conservative Local Heuristic Algorithm
Optimization Algorithm with Pruning
6 Join Query

Figure

4: Performance on Varying Number of User-defined Predicates
Experimental Testbed
Experiments ware performed on an IBM RS/6000
workstation with 128 MB of main memory, and running
AIX 3.2.5. We have used an experimental framework
similar to that in [IK90, CS94]. The algorithms were
run on queries consisting of equality joins only. The
queries were tested with a randomly generated relation
catalog where relation cardinalities ranged from 1000 to
100000 tuples, and the numbers of unique values in join
columns varied from 10% to 100% of the corresponding
relation cardinality. The selectivity of expensive predicates
were randomly chosen from 0.0001 to 1.0 and the
cost per tuple of expensive predicates was represented
by the number of I/O (page) accesses and was selected
randomly from 1 to 1000. Each query was generated to
have two projection attributes. Each page of a relation
was assumed to contain 32 tuples. Each relation had
four attributes, and was clustered on one of them. If a
relation was not physically sorted on the clustered at-
tribute, there was a B + -tree or hashing primary index
on that attribute. These three alternatives were equally
likely. For each of the other attributes, the probability
that it had a secondary index was 1/2, and the choice
between a -tree and hashing secondary index were
again uniformly random. We considered block nested-
loops, merge-scan, and simple and hybrid hash joins.
The interesting orders are considered for storing sub-
plans. In our experiment, only the cost for number of
I/O (page) accesses was accounted.
We performed two sets of experiments. In the first
set, we varied the number of user-defined predicates
that apply on one relation. In the second set, we varied
the distribution of the user-defined predicates on
multiple relations in the query. Due to lack of space,
we present only the experiments where the number of
user-defined selections that apply on a relation are var-
ied. The results of the other experiments will be discussed
in [CS96]. The second set of experiments shed
light on how the distribution of the user-defined predicates
among relations in the query influences the cost
of optimization. The results also shows how our conservative
local heuristic sharply reduces the overhead
of optimization under varying distributions.
Effect of Number of User defined Predicates
Due to the lack of space, we will show the results for
6-join (i.e. join among 7 relations) queries only but similar
results were obtained for other queries (e.g. 4-join
and 10-join queries) as well. The detailed performance
study with various queries will be presented in [CS96].
In this experiment, one relation in the query was chosen
randomly and the number of expensive predicates
applicable was varied from 1 to 6. The results presented
here for each data point represents averages of
100 queries, generated randomly.
We experimented how the optimization algorithms
behave as we increase the number of expensive predicates
for the randomly selected relation in the queries.

Figure

4 shows the number of enumerated plans and
the quality of plans generated by each algorithm. A
comparison of the performances of the naive optimization
algorithm and optimization algorithm with pruning
shows that our proposed pruning techniques are extremely
effective. Note that both these algorithms are
guaranteed to be optimal. Over all queries, the naive
optimization algorithm enumerated about 3 times more
plans than optimization algorithm with pruning.
The result on quality of plans shows the relative cost
of plans generated by each algorithms. The cost of plan
generated by optimization algorithm with pruning was
scaled as 1.0. Since naive optimization algorithm and
optimization algorithm with pruning always generate
optimal plans, 1.0 represents the cost of both optimal
plans. The figure illustrates that the quality of plan
generated by traditional optimizer suffers significantly
while the quality of plan generated by PullRank algorithm
gets worse as the number of expensive predicates
increases.
Conservative local heuristic chooses plans that are
identical to or very close to the optimal 3 . This is illustrated
by the fact that the graphs for the heuristic
and the optimization algorithm are practically indistin-
guishable. Although in this experiment, conservative
local heuristic doesn't reduce the number of enumerated
plans significantly compared to the optimization
algorithm with pruning, this observation does not extend
in general, particularly when the user-defined selections
are distributed among multiple relations In the
latter cases, the conservative local heuristic proves to
be the algorithm of choice, since it continues to choose
plans close to the optimal plan with much less optimization
overhead [CS96].

Acknowledgement

: We are indebted to Joe Hellerstein
for giving us detailed feedback on our draft in a
short time. The anonymous referees provided us with
insightful comments that helped improve the draft.
Thanks are due to Umesh Dayal, Nita Goyal, Luis
Gravano and Ravi Krishnamurthy for their help and
comments. Without the support of Debjani Chaudhuri
and Yesook Shim, it would have been impossible
to complete this work.



--R


Query optimization in the presence of foreign functions.
Including group-by in query optimization
Optimization with user-defined predicates
Query optimization for parallel execution.
Predicate migration place- ment
Predicate migration: Optimization queries with expensive predicates.
Randomized algorithms for optimizing large join queries.
Optimization of nonrecursive queries.
Optimizing boolean expressions in object-bases
Sequencing with series-parallel precedence constraints
Extensible/rule based query optimization in starburst.

Query optimization in a memory-resident domain relational calculus database system
--TR
Join processing in database systems with large main memories
The EXODUS optimizer generator
Query optimization in a memory-resident domain relational calculus database system
Introduction to algorithms
Towards an open architecture for LDL
Randomized algorithms for optimizing large join queries
Query optimization for parallel execution
migration
Practical predicate placement
Advanced query optimization techniques for relational database systems
Optimization and execution techniques for queries with expensive methods
Access path selection in a relational database management system
Optimization of Nonrecursive Queries
Implementing an Interpreter for Functional Rules in a Query Optimizer
Optimizing Boolean Expressions in Object-Bases
Query Optimization in the Presence of Foreign Functions
Including Group-By in Query Optimization
Optimization of Queries with User-defined Predicates
The Volcano Optimizer Generator

--CTR
Utkarsh Srivastava , Kamesh Munagala , Jennifer Widom, Operator placement for in-network stream query processing, Proceedings of the twenty-fourth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 13-15, 2005, Baltimore, Maryland
Ihab F. Ilyas , Jun Rao , Guy Lohman , Dengfeng Gao , Eileen Lin, Estimating compilation time of a query optimizer, Proceedings of the ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California
David Taniar , Hui Yee Khaw , Haorianto Cokrowijoyo Tjioe , Eric Pardede, The use of Hints in SQL-Nested query optimization, Information Sciences: an International Journal, v.177 n.12, p.2493-2521, June, 2007
Iosif Lazaridis , Sharad Mehrotra, Optimization of multi-version expensive predicates, Proceedings of the 2007 ACM SIGMOD international conference on Management of data, June 11-14, 2007, Beijing, China
Kamesh Munagala , Utkarsh Srivastava , Jennifer Widom, Optimization of continuous queries with shared expensive filters, Proceedings of the twenty-sixth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 11-13, 2007, Beijing, China
Chang-Won Park , Jun-Ki Min , Chin-Wan Chung, Structural function inlining technique for structurally recursive XML queries, Proceedings of the 28th international conference on Very Large Data Bases, p.83-94, August 20-23, 2002, Hong Kong, China
Shivnath Babu , Rajeev Motwani , Kamesh Munagala , Itaru Nishizawa , Jennifer Widom, Adaptive ordering of pipelined stream filters, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France
Surajit Chaudhuri , Prasanna Ganesan , Sunita Sarawagi, Factorizing complex predicates in queries to exploit indexes, Proceedings of the ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California
Zhiyuan Chen , Johannes Gehrke , Flip Korn, Query optimization in compressed database systems, ACM SIGMOD Record, v.30 n.2, p.271-282, June 2001
Utkarsh Srivastava , Kamesh Munagala , Jennifer Widom , Rajeev Motwani, Query optimization over web services, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
Zhen Liu , Srinivasan Parthasarthy , Anand Ranganathan , Hao Yang, Scalable event matching for overlapping subscriptions in pub/sub systems, Proceedings of the 2007 inaugural international conference on Distributed event-based systems, June 20-22, 2007, Toronto, Ontario, Canada
Caetano Traina, Jr. , Agma J. M. Traina , Marcos R. Vieira , Adriano S. Arantes , Christos Faloutsos, Efficient processing of complex similarity queries in RDBMS through query rewriting, Proceedings of the 15th ACM international conference on Information and knowledge management, November 06-11, 2006, Arlington, Virginia, USA
Fosca Giannotti , Giuseppe Manco , Franco Turini, Specifying Mining Algorithms with Iterative User-Defined Aggregates, IEEE Transactions on Knowledge and Data Engineering, v.16 n.10, p.1232-1246, October 2004
Jayaprakash Pisharath , Alok Choudhary , Mahmut Kandemir, Energy management schemes for memory-resident database systems, Proceedings of the thirteenth ACM international conference on Information and knowledge management, November 08-13, 2004, Washington, D.C., USA
Surajit Chaudhuri , Luis Gravano , Amelie Marian, Optimizing Top-k Selection Queries over Multimedia Repositories, IEEE Transactions on Knowledge and Data Engineering, v.16 n.8, p.992-1009, August 2004
Zhen He , Byung Suk Lee , Robert Snapp, Self-tuning cost modeling of user-defined functions in an object-relational DBMS, ACM Transactions on Database Systems (TODS), v.30 n.3, p.812-853, September 2005
Brian Babcock , Shivnath Babu , Mayur Datar , Rajeev Motwani , Dilys Thomas, Operator scheduling in data stream systems, The VLDB Journal  The International Journal on Very Large Data Bases, v.13 n.4, p.333-353, December 2004
Panagiotis G. Ipeirotis , Eugene Agichtein , Pranay Jain , Luis Gravano, To search or to crawl?: towards a query optimizer for text-centric tasks, Proceedings of the 2006 ACM SIGMOD international conference on Management of data, June 27-29, 2006, Chicago, IL, USA
Srinath Shankar , Ameet Kini , David J. DeWitt , Jeffrey Naughton, Integrating databases and workflow systems, ACM SIGMOD Record, v.34 n.3, September 2005
query optimization;user-defined predicates;dynamic programming