ACM SIGMOD Anthology ACM SIGMOD dblp.uni-trier.de

Hypergraph Based Reorderings of Outer Join Queries with Complex Predicates.

Gautam Bhargava, Piyush Goel, Balakrishna R. Iyer: Hypergraph Based Reorderings of Outer Join Queries with Complex Predicates. SIGMOD Conference 1995: 304-315
@inproceedings{DBLP:conf/sigmod/BhargavaGI95,
  author    = {Gautam Bhargava and
               Piyush Goel and
               Balakrishna R. Iyer},
  editor    = {Michael J. Carey and
               Donovan A. Schneider},
  title     = {Hypergraph Based Reorderings of Outer Join Queries with Complex
               Predicates},
  booktitle = {Proceedings of the 1995 ACM SIGMOD International Conference on
               Management of Data, San Jose, California, May 22-25, 1995},
  publisher = {ACM Press},
  year      = {1995},
  pages     = {304-315},
  ee        = {http://doi.acm.org/10.1145/223784.223847, db/conf/sigmod/sigmod95-24.html},
  crossref  = {DBLP:conf/sigmod/95},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

Complex queries containing outer joins are, for the most part, executed by commercial DBMS products in an ``as written" manner. Only a very few reorderings of the operations are considered and the benefits of considering comprehensive reordering schemes are not exploited. This is largely due to the fact there are no readily usable results for reordering such operations for relations with duplicates and/or outer join predicates that are other than "simple". Most previous approaches have ignored duplicates and complex predicates; the very few that have considered these aspects have suggested approaches that lead to a possibly exponential number of, and redundant intermediate joins. Since traditional query graph models are inadequate for modeling outer join queries with complex predicates, in this paper we present the needed hypergraph abstraction and algorithms for reordering such outer join queries. This allows the query optimizer to explore a significantly larger space of execution plans, and choose one with a low cost. Additionally, these algorithms are easily incorporated into well known and widely used enumeration methods such as dynamic programming.

Copyright © 1995 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 ...

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

Printed Edition

Michael J. Carey, Donovan A. Schneider (Eds.): Proceedings of the 1995 ACM SIGMOD International Conference on Management of Data, San Jose, California, May 22-25, 1995. ACM Press 1995 BibTeX , SIGMOD Record 24(2), June 1995
Contents

Online Edition: ACM Digital Library

[Index Terms]
[Full Text in PDF Format, 1032 KB]

References

[BHAR94a]
...
[BHAR94b]
...
[CHEN90]
...
[DATE83]
C. J. Date: The Outer Join. ICOD 1983: 76-106 BibTeX
[DAYA87]
Umeshwar Dayal: Of Nests and Trees: A Unified Approach to Processing Queries That Contain Nested Subqueries, Aggregates, and Quantifiers. VLDB 1987: 197-208 BibTeX
[GANS87]
Richard A. Ganski, Harry K. T. Wong: Optimization of Nested SQL Queries Revisited. SIGMOD Conference 1987: 23-33 BibTeX
[GALI92a]
César A. Galindo-Legaria, Arnon Rosenthal: How to Extend a Conventional Optimizer to Handle One- and Two-Sided Outerjoin. ICDE 1992: 402-409 BibTeX
[GALI92b]
...
[GALI93]
César A. Galindo-Legaria, Arnon Rosenthal: Outerjoin Simplification and Reordering for Query Optimization. ACM Trans. Database Syst. 22(1): 43-73(1997) BibTeX
[GALI94]
César A. Galindo-Legaria: Outerjoins as Disjunctions. SIGMOD Conference 1994: 348-358 BibTeX
[KOO94]
...
[LAFO86]
Stéphane Lafortune, Eugene Wong: A State Transition Model for Distributed Query Processing. ACM Trans. Database Syst. 11(3): 294-322(1986) BibTeX
[LEE94]
Byung Suk Lee, Gio Wiederhold: Outer Joins and Filters for Instantiating Objects from Relational Databases Through Views. IEEE Trans. Knowl. Data Eng. 6(1): 108-119(1994) BibTeX
[PIRA92]
Hamid Pirahesh, Joseph M. Hellerstein, Waqar Hasan: Extensible/Rule Based Query Rewrite Optimization in Starburst. SIGMOD Conference 1992: 39-48 BibTeX
[PIRA93]
...
[ROSE90]
Arnon Rosenthal, César A. Galindo-Legaria: Query Graphs, Implementing Trees, and Freely-Reorderable Outerjoins. SIGMOD Conference 1990: 291-299 BibTeX
[SCHO87]
Marc H. Scholl, H.-Bernhard Paul, Hans-Jörg Schek: Supporting Flat Relations by a Nested Relational Kernel. VLDB 1987: 137-146 BibTeX
[SELI79]
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 BibTeX
[ULLN82]
Jeffrey D. Ullman: Principles of Database Systems, 2nd Edition. Computer Science Press 1982, ISBN 0-914894-36-6
BibTeX

Referenced by

  1. Shashi K. Gadia, Sunil S. Nair: Algebraic Identities and Query Optimization in a Parametric Model for Relational Temporal Databases. IEEE Trans. Knowl. Data Eng. 10(5): 793-807(1998)
  2. César A. Galindo-Legaria, Arnon Rosenthal: Outerjoin Simplification and Reordering for Query Optimization. ACM Trans. Database Syst. 22(1): 43-73(1997)
  3. P. Krishnan, Jeffrey Scott Vitter, Balakrishna R. Iyer: Estimating Alphanumeric Selectivity in the Presence of Wildcards. SIGMOD Conference 1996: 282-293
  4. Piyush Goel, Balakrishna R. Iyer: SQL Query Optimization: Reordering for a General Class of Queries. SIGMOD Conference 1996: 47-56
  5. Gautam Bhargava, Piyush Goel, Balakrishna R. Iyer: Efficient Processing of Outer Joins and Aggregate Functions. ICDE 1996: 441-449
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Sat May 16 23:40:26 2009