Optimizing Disjunctive Queries with Expensive Predicates.

Alfons Kemper, Guido Moerkotte, Klaus Peithner, Michael Steinbrunn: Optimizing Disjunctive Queries with Expensive Predicates. SIGMOD Conference 1994: 336-347

@inproceedings{DBLP:conf/sigmod/KemperMPS94,
  author    = {Alfons Kemper and
               Guido Moerkotte and
               Klaus Peithner and
               Michael Steinbrunn},
  editor    = {Richard T. Snodgrass and
               Marianne Winslett},
  title     = {Optimizing Disjunctive Queries with Expensive Predicates},
  booktitle = {Proceedings of the 1994 ACM SIGMOD International Conference on
               Management of Data, Minneapolis, Minnesota, May 24-27, 1994},
  publisher = {ACM Press},
  year      = {1994},
  pages     = {336-347},
  ee        = {http://doi.acm.org/10.1145/191839.191906, db/conf/sigmod/KemperMPS94.html},
  crossref  = {DBLP:conf/sigmod/94},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

In this work, we propose and assess a technique called bypass processing for optimizing the evaluation of disjunctive queries with expensive predicates. The technique is particularly useful for optimizing selection predicates that contain terms whose evaluation costs vary tremendously; e.g., the evaluation of a nested subquery or the invocation of a user-defined function in an object-oriented or extended relational model may beorders of magnitude more expensive than an attribute access (and comparison). The idea of bypass processing consists of avoiding the evaluation of such expensive terms whenever the outcome of the entire selection predicate can already be induced by testing other, less expensive terms. In order to validatethe viability of bypass evaluation, we extend a previously developed optimizer architecture and incorporate three alternative optimization algorithms for generating bypass processing plans.

Copyright © 1994 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.

ACM SIGMOD Anthology

Online Version (ACM WWW Account required): Full Text in PDF Format

CDROM Version: Load the CDROM "Volume 1 Issue 1, SIGMOD '93-'97" and ...

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Mac: Click here
UNIX/LINUX: mount the CD and click on the path of your mount point:
/Anthology/smod9397 or /cdrom

DVD Version: Load ACM SIGMOD Anthology DVD 1" and ...

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Mac: Click here
UNIX/LINUX: mount the DVD and click on the path of your mount point:
/Anthology/aDVD1 or /dvd

Printed Edition

Richard T. Snodgrass, Marianne Winslett (Eds.): Proceedings of the 1994 ACM SIGMOD International Conference on Management of Data, Minneapolis, Minnesota, May 24-27, 1994. ACM Press 1994

, SIGMOD Record 23(2), June 1994
Contents

Online Edition: ACM Digital Library

[Abstract and Index Terms]
[Full Text in PDF Format, 1225 KB]

References

[Bat86]: Don S. Batory: Extensible Cost Models and Query Optimization in GENESIS. IEEE Database Eng. Bull. 9(4): 30-36(1986)
[BG92]: Ludger Becker, Ralf Hartmut Güting: Rule-Based Optimization and Query Processing in an Extensible Geometric Database System. ACM Trans. Database Syst. 17(2): 247-303(1992)
[BMG93]: José A. Blakeley, William J. McKenna, Goetz Graefe: Experiences Building the Open OODB Query Optimizer. SIGMOD Conference 1993: 287-296
[CD92]: Sophie Cluet, Claude Delobel: A General Framework for the Optimization of Object-Oriented Queries. SIGMOD Conference 1992: 383-392
[FMV93]: ...
[Fre87]: Johann Christoph Freytag: A Rule-Based View of Query Optimization. SIGMOD Conference 1987: 173-180
[GD87]: Goetz Graefe, David J. DeWitt: The EXODUS Optimizer Generator. SIGMOD Conference 1987: 160-172
[GM93]: Goetz Graefe, William J. McKenna: The Volcano Optimizer Generator: Extensibility and Efficient Search. ICDE 1993: 209-218
[Han77]: Michael Z. Hanani: An Optimal Evaluation of Boolean Expressions in an Online Query System. Commun. ACM 20(5): 344-347(1977)
[HFLP89]: Laura M. Haas, Johann Christoph Freytag, Guy M. Lohman, Hamid Pirahesh: Extensible Query Processing in Starburst. SIGMOD Conference 1989: 377-388
[HS93]: Joseph M. Hellerstein, Michael Stonebraker: Predicate Migration: Optimizing Queries with Expensive Predicates. SIGMOD Conference 1993: 267-276
[JK84]: Matthias Jarke, Jürgen Koch: Query Optimization in Database Systems. ACM Comput. Surv. 16(2): 111-152(1984)
[KM90]: Alfons Kemper, Guido Moerkotte: Advanced Query Processing in Object Bases Using Access Support Relations. VLDB 1990: 290-301
[KM93]: ...
[KM94]: Alfons Kemper, Guido Moerkotte: Object-Oriented Database Management: Applications in Engineering and Computer Science. Prentice-Hall 1994, ISBN 0-13-629239-9
Contents
[KMP93]: Alfons Kemper, Guido Moerkotte, Klaus Peithner: A Blackboard Architecture for Query Optimization in Object Bases. VLDB 1993: 543-554
[KMS92]: Alfons Kemper, Guido Moerkotte, Michael Steinbrunn: Optimizing Boolean Expressions in Object-Bases. VLDB 1992: 79-90
[Loh88]: Guy M. Lohman: Grammar-like Functional Rules for Representing Query Optimization Alternatives. SIGMOD Conference 1988: 18-27
[LV91]: Rosana S. G. Lanzelotte, Patrick Valduriez: Extending the Search Strategy in a Query Optimizer. VLDB 1991: 363-373
[MDZ93]: Gail Mitchell, Umeshwar Dayal, Stanley B. Zdonik: Control of an Extensible Query Optimizer: A Planning-Based Approach. VLDB 1993: 517-528
[MS79]: ...
[OS90]: Dave D. Straube, M. Tamer Özsu: Queries and Query Processing in Object-Oriented Database Systems. ACM Trans. Inf. Syst. 8(4): 387-430(1990)
[Pea84]: ...
[SAC+79]: Patricia G. Selinger, Morton M. Astrahan, Donald D. Chamberlin, Raymond A. Lorie, Thomas G. Price: Access Path Selection in a Relational Database Management System. SIGMOD Conference 1979: 23-34
[Sel86]: Timos K. Sellis: Global Query Optimization. SIGMOD Conference 1986: 191-205
[SMK93]: ...