ACM SIGMOD Anthology VLDB dblp.uni-trier.de

Bypassing Joins in Disjunctive Queries.

Michael Steinbrunn, Klaus Peithner, Guido Moerkotte, Alfons Kemper: Bypassing Joins in Disjunctive Queries. VLDB 1995: 228-238
@inproceedings{DBLP:conf/vldb/SteinbrunnPMK95,
  author    = {Michael Steinbrunn and
               Klaus Peithner and
               Guido Moerkotte and
               Alfons Kemper},
  editor    = {Umeshwar Dayal and
               Peter M. D. Gray and
               Shojiro Nishio},
  title     = {Bypassing Joins in Disjunctive Queries},
  booktitle = {VLDB'95, Proceedings of 21th International Conference on Very
               Large Data Bases, September 11-15, 1995, Zurich, Switzerland},
  publisher = {Morgan Kaufmann},
  year      = {1995},
  isbn      = {1-55860-379-4},
  pages     = {228-238},
  ee        = {db/conf/vldb/SteinbrunnPMK95.html},
  crossref  = {DBLP:conf/vldb/95},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

The bypass technique, which was formerly restricted to selections only [KMPS94], is extended to join operations. Analogous to the selection case, the join operator may generate two outputstreams-the join result and its complement-whose subsequent operator sequence is optimized individually. By extending the bypass technique to joins, several problems have to be solved. (1) An algorithm for exhaustive generation of the search space for bypass plans has to be developed. (2) The search space for bypass plans is quite large. Hence, partial exploration strategies still resulting in sufficiently efficient plans have to be developed. (3) Since the complement of a join can be very large, those cases where the complement can be restricted to the complement of the semijoin have to be detected. We attack all three problems. Especially, we present an algorithm generating the optimal bypass plan andone algorithm producing near optimal plans exploring the search space onlypartially.

As soon as disjunctions occur, bypassing results in savings. Since the join operator is often more expensive than the selection, the savings for bypassing joins are even higher than those for selections only. We give a quantitative assessment of these savings on the basis of some example queries. Further, we evaluate the performance of the two bypass plan generating algorithms.

Copyright © 1995 by the VLDB Endowment. Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the VLDB copyright notice and the title of the publication and its date appear, and notice is given that copying is by the permission of the Very Large Data Base Endowment. To copy otherwise, or to republish, requires a fee and/or special permission from the Endowment.


Online Paper

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 1 Issue 5, VLDB '89-'97" and ... DVD Version: Load ACM SIGMOD Anthology DVD 1" and ...

Printed Edition

Umeshwar Dayal, Peter M. D. Gray, Shojiro Nishio (Eds.): VLDB'95, Proceedings of 21th International Conference on Very Large Data Bases, September 11-15, 1995, Zurich, Switzerland. Morgan Kaufmann 1995, ISBN 1-55860-379-4
Contents CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

References

[Bat86]
Don S. Batory: Extensible Cost Models and Query Optimization in GENESIS. IEEE Database Eng. Bull. 9(4): 30-36(1986) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[BGW+81]
Philip A. Bernstein, Nathan Goodman, Eugene Wong, Christopher L. Reeve, James B. Rothnie Jr.: Query Processing in a System for Distributed Databases (SDD-1). ACM Trans. Database Syst. 6(4): 602-625(1981) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[BMG93]
José A. Blakeley, William J. McKenna, Goetz Graefe: Experiences Building the Open OODB Query Optimizer. SIGMOD Conference 1993: 287-296 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Bry89]
François Bry: Towards an Efficient Evaluation of General Queries: Quantifier and Disjunction Processing Revisited. SIGMOD Conference 1989: 193-204 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Cat94]
R. G. G. Cattell: The Object Database Standard: ODMG-93 (Release 1.1). Morgan Kaufmann 1994
CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[CD92]
Sophie Cluet, Claude Delobel: A General Framework for the Optimization of Object-Oriented Queries. SIGMOD Conference 1992: 383-392 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[FMV93]
Johann Christoph Freytag, David Maier, Gottfried Vossen (Eds.): Query Processing for Advanced Database Systems, Selected Contributions from a Workshop on "Query Processing in Object-Oriented, Complex-Object and Nested Relation Databases", Interationales Begegnungs- und Forschungszentrum für Informatik, Schloss Dagstuhl, Germany, June 1991. Morgan Kaufmann 1994, ISBN 1-55860-271-2
Contents CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Fre87]
Johann Christoph Freytag: A Rule-Based View of Query Optimization. SIGMOD Conference 1987: 173-180 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[GD87]
Goetz Graefe, David J. DeWitt: The EXODUS Optimizer Generator. SIGMOD Conference 1987: 160-172 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[GM93]
Goetz Graefe, William J. McKenna: The Volcano Optimizer Generator: Extensibility and Efficient Search. ICDE 1993: 209-218 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Hel94]
Joseph M. Hellerstein: Practical Predicate Placement. SIGMOD Conference 1994: 325-335 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[HFLP89]
Laura M. Haas, Johann Christoph Freytag, Guy M. Lohman, Hamid Pirahesh: Extensible Query Processing in Starburst. SIGMOD Conference 1989: 377-388 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[HS93]
Joseph M. Hellerstein, Michael Stonebraker: Predicate Migration: Optimizing Queries with Expensive Predicates. SIGMOD Conference 1993: 267-276 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[JK84]
Matthias Jarke, Jürgen Koch: Query Optimization in Database Systems. ACM Comput. Surv. 16(2): 111-152(1984) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[KBZ86]
Ravi Krishnamurthy, Haran Boral, Carlo Zaniolo: Optimization of Nonrecursive Queries. VLDB 1986: 128-137 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[KM90]
Alfons Kemper, Guido Moerkotte: Advanced Query Processing in Object Bases Using Access Support Relations. VLDB 1990: 290-301 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[KM94]
Alfons Kemper, Guido Moerkotte: Object-Oriented Database Management: Applications in Engineering and Computer Science. Prentice-Hall 1994, ISBN 0-13-629239-9
Contents CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[KMP93]
Alfons Kemper, Guido Moerkotte, Klaus Peithner: A Blackboard Architecture for Query Optimization in Object Bases. VLDB 1993: 543-554 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[KMPS94]
Alfons Kemper, Guido Moerkotte, Klaus Peithner, Michael Steinbrunn: Optimizing Disjunctive Queries with Expensive Predicates. SIGMOD Conference 1994: 336-347 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[KTY82]
Larry Kerschberg, Peter D. Ting, S. Bing Yao: Query Optimization in Star Computer Networks. ACM Trans. Database Syst. 7(4): 678-711(1982) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[LMS94]
Alon Y. Levy, Inderpal Singh Mumick, Yehoshua Sagiv: Query Optimization by Predicate Move-Around. VLDB 1994: 96-107 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Loh88]
Guy M. Lohman: Grammar-like Functional Rules for Representing Query Optimization Alternatives. SIGMOD Conference 1988: 18-27 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[MDZ93]
Gail Mitchell, Umeshwar Dayal, Stanley B. Zdonik: Control of an Extensible Query Optimizer: A Planning-Based Approach. VLDB 1993: 517-528 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[MS79]
...
[Mur88]
...
[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) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[SPMK94]
...

Copyright © Tue Mar 16 02:22:05 2010 by Michael Ley (ley@uni-trier.de)