Digital Review dblp.uni-trier.de

Review - Predicate Migration: Optimizing Queries with Expensive Predicates.

Eric Simon: Review - Predicate Migration: Optimizing Queries with Expensive Predicates. ACM SIGMOD Digital Review 2: (2000) BibTeX

Review

This paper addresses the problem of optimizing SQL queries with expensive predicates. These predicates are likely to occur in all database systems supporting user-defined functions that perform arbitrary computations. The problem is of importance because many applications ranging from multimedia to scientific applications make an heavy use of user-defined functions that are applied over voluminous data, either in a centralized or distributed environment. In these applications, finding the appropriate ordering of joins with respect to expensive functions is crucial for performance.

his paper addresses the problem in a systematic way. Although a journal version appeared later on in TODS, the Sigmod conference version is very well written and presents all the ideas in a detailed manner. Thus, I recommend reading it. The paper presents an elegant and simple algorithm, called predicate migration algorithm, which given a query plan of joins, determines where to optimally place restrictions in this plan. The algorithm is efficient (it runs in polynomial time) and can be nicely incorporated into an optimizer that performs typical join enumeration. The paper makes very clear the assumptions made by the algorithm: function caching is supported, and join costs are linear in the size of their inputs. The paper describes the implementation made in Postgres and reports on performance measurements run on an ad-hoc benchmark. The paper is a typical end to end paper, establishing theory, describing its implementation, and evaluating its effectiveness. It gives raise to several subsequent papers that addressed the same problem. However, I like this paper and recommend it as a good starter to the domain.

Copyright © 2000 by the author(s). Review published with permission.


References

[1]
Joseph M. Hellerstein, Michael Stonebraker: Predicate Migration: Optimizing Queries with Expensive Predicates. SIGMOD Conference 1993: 267-276 BibTeX
BibTeX
Digital Review - DBLP: [Home | Search: Author, Title | Conferences | Journals]
Digital Review: Copyright © by ACM (info@acm.org),
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Sat May 16 23:57:28 2009