SQL query optimization: reordering for a general class of queries

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 significantly 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.

REFERENCES

• BHAR94: Bhargava, G., Goel, P. and Iyer, B., "Reordering of complex queries involving joins and outer joins," IBM Techn,cal Report TR03.567, July b1994.
• BHAR95a: Gautam Bhargava , Piyush Goel , Bala Iyer, Hypergraph based reorderings of outer join queries with complex predicates, Proceedings of the 1995 ACM SIGMOD international conference on Management of data, p.304-315, May 22-25, 1995, San Jose, California, United States
• BHAR95b: Gautam Bhargava , Piyush Goel , Balakrishna R. Iyer, No regression algorithm for the enumeration of projections in SQL queries with joins and outer joins, Proceedings of the 1995 conference of the Centre for Advanced Studies on Collaborative research, p.8, November 07-09, 1995, Toronto, Ontario, Canada
• BHAR95c: Gautam Bhargava , Piyush Goel , Balakrishna R. Iyer, Simplification of outer joins, Proceedings of the 1995 conference of the Centre for Advanced Studies on Collaborative research, p.7, November 07-09, 1995, Toronto, Ontario, Canada
• BHAR95d: Gautam Bhargava , Piyush Goel , Balakrishna R. Iyer, Efficient Processing of Outer Joins and Aggregate Functions, Proceedings of the Twelfth International Conference on Data Engineering, p.441-449, February 26-March 01, 1996
• GALI92a: César A. Galindo-Legaria , Arnon Rosenthal, How to Extend a Conventional Optimizer to Handle One- and Two-Sided Outerjoin, Proceedings of the Eighth International Conference on Data Engineering, p.402-409, February 03-07, 1992
• GALI92b: Cesar Alejandro Galindo-Legaria, Algebraic optimization of outerjoin queries, Harvard University, Cambridge, MA, 1992
• GALI94: César A. Galindo-Legaria, Outerjoins as disjunctions, Proceedings of the 1994 ACM SIGMOD international conference on Management of data, p.348-358, May 24-27, 1994, Minneapolis, Minnesota, United States
• GANS87: Richard A. Ganski , Harry K. T. Wong, Optimization of nested SQL queries revisited, Proceedings of the 1987 ACM SIGMOD international conference on Management of data, p.23-33, May 27-29, 1987, San Francisco, California, United States
• GUPT95: Gupta, A., Harinarayan, V. and Quass, D., "Generalized Projections: A powerful approach to aggregation", To appear in VLDB, 1995.
• MURA92: M. Muralikrishna, Improved Unnesting Algorithms for Join Aggregate SQL Queries, Proceedings of the 18th International Conference on Very Large Data Bases, p.91-102, August 23-27, 1992
• PIRA92: Hamid Pirahesh , Joseph M. Hellerstein , Waqar Hasan, Extensible/rule based query rewrite optimization in Starburst, Proceedings of the 1992 ACM SIGMOD international conference on Management of data, p.39-48, June 02-05, 1992, San Diego, California, United States
• ROSE90: Arnon Rosenthal , Cesar Galindo-Legaria, Query graphs, implementing trees, and freely-reorderable outerjoins, Proceedings of the 1990 ACM SIGMOD international conference on Management of data, p.291-299, May 23-26, 1990, Atlantic City, New Jersey, United States
• SELI79: P. Griffiths Selinger , M. M. Astrahan , D. D. Chamberlin , R. A. Lorie , T. G. Price, Access path selection in a relational database management system, Proceedings of the 1979 ACM SIGMOD international conference on Management of data, May 30-June 01, 1979, Boston, Massachusetts [doi>10.1145/582095.582099]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Optimization

General Terms:
Theory