BIB-VERSION:: CS-TR-v2.0
ID:: UCB//S2K-92-13 
ENTRY:: February 18, 1994 
TITLE:: Predicate Migration: Optimizing Queries with 
        Expensive Predicates 
DATE:: December 3, 1992 
AUTHOR:: Hellerstein, Joseph M. 
PAGES:: 22
ABSTRACT:: The traditional focus of relational query optimization
schemes has been on the choice of join methods and join orders.
Restrictions have typically been handled in query optimizers by 
"predicate pushdown" rules, which apply restrictions in some
random order before as many joins as possible.  These rules work
under the assumption that restrictions is essentially a zerO-
time operation. However, today's extensible and object-oriented
database systems allow users to define time-consuming functions, 
which may be used in a query's restriction and join predicates.
furthermore, SQL has long supported subquery predicates, which
may be arbitrarily time-consuming to check. Thus restrictions
should not be considered zero-time operations, and the model of 
query optimization must be enhanced.

In this paper we develop a theory for moving expensive predicates
in a query plan so that the total cost of the plan--including the
costs of both joins and restrictions--is minimal. We present an 
algorithm to implement the theory, as well as results of our 
implementation in POSTGRES. Our experience with the newly enhanced
POSTGRES are orders of magnitude faster than plans generated by a 
traditional query optimizer. The additional complexity of considering
expensive predicates during optimization is found to be manageably 
small. 
RETRIEVAL:: postscript (in all.ps)
END:: UCB//S2K-92-13