SQL Query Optimization: Reordering for a General Class of Queries.

Piyush Goel, Balakrishna R. Iyer: SQL Query Optimization: Reordering for a General Class of Queries. SIGMOD Conference 1996: 47-56

@inproceedings{DBLP:conf/sigmod/GoelI96,
  author    = {Piyush Goel and
               Balakrishna R. Iyer},
  editor    = {H. V. Jagadish and
               Inderpal Singh Mumick},
  title     = {SQL Query Optimization: Reordering for a General Class of Queries},
  booktitle = {Proceedings of the 1996 ACM SIGMOD International Conference on
               Management of Data, Montreal, Quebec, Canada, June 4-6, 1996},
  publisher = {ACM Press},
  year      = {1996},
  pages     = {47-56},
  ee        = {http://doi.acm.org/10.1145/233269.233318, db/conf/sigmod/GoelI96.html},
  crossref  = {DBLP:conf/sigmod/96},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

The strength of commercial query optimizers like DB2 comes from their ability to select an optimal order by generating all equivalent reorderings of binary operators. However, there are no known methods to generate all equivalent reorderings for a SQL query containing joins, outer joins, and groupby aggregations. Consequently, some of the reorderings with significant lower cost may be missed. Using hypergraph model and a set of novel identities, we propose a method to reorder a SQL query containing joins, outer joins, and groupby aggregations. While these operators are sufficient to capture the SQL semantics, it is during their reordering that we identify a powerful primitive needed for a dbms. We report our findings of a simple, yet fundamental operator, generalized selection, and demonstrate its power to solve the problem of reordering of SQL queries containing joins, outer joins, and groupby aggregations.

Copyright © 1996 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

H. V. Jagadish, Inderpal Singh Mumick (Eds.): Proceedings of the 1996 ACM SIGMOD International Conference on Management of Data, Montreal, Quebec, Canada, June 4-6, 1996. ACM Press 1996

, SIGMOD Record 25(2), June 1996
Contents

Online Edition: ACM Digital Library

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

References

[BHAR94]: ...
[BHAR95a]: Gautam Bhargava, Piyush Goel, Balakrishna R. Iyer: Hypergraph Based Reorderings of Outer Join Queries with Complex Predicates. SIGMOD Conference 1995: 304-315
[BHAR95b]: ...
[BHAR95c]: ...
[BHAR95d]: Gautam Bhargava, Piyush Goel, Balakrishna R. Iyer: Efficient Processing of Outer Joins and Aggregate Functions. ICDE 1996: 441-449
[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
[GALI92b]: ...
[GALI94]: César A. Galindo-Legaria: Outerjoins as Disjunctions. SIGMOD Conference 1994: 348-358
[GANS87]: Richard A. Ganski, Harry K. T. Wong: Optimization of Nested SQL Queries Revisited. SIGMOD Conference 1987: 23-33
[GUPT95]: Ashish Gupta, Venky Harinarayan, Dallan Quass: Aggregate-Query Processing in Data Warehousing Environments. VLDB 1995: 358-369
[MURA92]: M. Muralikrishna: Improved Unnesting Algorithms for Join Aggregate SQL Queries. VLDB 1992: 91-102
[PIRA92]: Hamid Pirahesh, Joseph M. Hellerstein, Waqar Hasan: Extensible/Rule Based Query Rewrite Optimization in Starburst. SIGMOD Conference 1992: 39-48
[ROSE90]: Arnon Rosenthal, César A. Galindo-Legaria: Query Graphs, Implementing Trees, and Freely-Reorderable Outerjoins. SIGMOD Conference 1990: 291-299
[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