Orthogonal optimization of subqueries and aggregation

ABSTRACT

There is considerable overlap between strategies proposed for subquery evaluation, and those for grouping and aggregation. In this paper we show how a number of small, independent primitives generate a rich set of efficient execution strategies —covering standard proposals for subquery evaluation suggested in earlier literature. These small primitives fall into two main, orthogonal areas: Correlation removal, and efficient processing of outerjoins and GroupBy. An optimization approach based on these pieces provides syntax-independence of query processing with respect to subqueries, i. e. equivalent queries written with or without subquery produce the same efficient plan.

We describe techniques implemented in Microsoft SQL Server (releases 7.0 and 8.0) for queries containing sub-queries and/or aggregations, based on a number of orthogonal optimizations. We concentrate separately on removing correlated subqueries, also called “query flattening,” and on efficient execution of queries with aggregations. The end result is a modular, flexible implementation, which produces very efficient execution plans. To demonstrate the validity of our approach, we present results for some queries from the TPC-H benchmark. From all published TPC-H results in the 300GB scale, at the time of writing (November 2000), SQL Server has the fastest results on those queries, even on a fraction of the processors used by other systems.

REFERENCES

• 1: Pedro Celis , Hansjörg Zeller, Subquery Elimination: A Complete Unnesting Algorithm for an Extended Relational Algebra, Proceedings of the Thirteenth International Conference on Data Engineering, p.321, April 07-11, 1997
• 2: Damianos Chatziantoniou , Kenneth A. Ross, Groupwise Processing of Relational Queries, Proceedings of the 23rd International Conference on Very Large Data Bases, p.476-485, August 25-29, 1997
• 3: Surajit Chaudhuri , Kyuseok Shim, Including Group-By in Query Optimization, Proceedings of the 20th International Conference on Very Large Data Bases, p.354-366, September 12-15, 1994
• 4: Sophie Cluet , Claude Delobel, A general framework for the optimization of object-oriented queries, Proceedings of the 1992 ACM SIGMOD international conference on Management of data, p.383-392, June 02-05, 1992, San Diego, California, United States
• 5: Umeshwar Dayal, Of Nests and Trees: A Unified Approach to Processing Queries That Contain Nested Subqueries, Aggregates, and Quantifiers, Proceedings of the 13th International Conference on Very Large Data Bases, p.197-208, September 01-04, 1987
• 6: C. A. Galindo-Legaria. Parameterized queries and nesting equivalences. Technical report, Microsoft, 2001. MSR-TR-2000-31.
• 7: César Galindo-Legaria , Arnon Rosenthal, Outerjoin simplification and reordering for query optimization, ACM Transactions on Database Systems (TODS), v.22 n.1, p.43-74, March 1997 [doi>10.1145/244810.244812]
• 8: G. Graefe. The Cascades framework for query optimization. Data Engineering Bulletin, 18(3):19-29, 1995.
• 9: Goetz Graefe , William J. McKenna, The Volcano Optimizer Generator: Extensibility and Efficient Search, Proceedings of the Ninth International Conference on Data Engineering, p.209-218, April 19-23, 1993
• 10: M. M. Joshi and C. A. Galindo-Legaria. Properties of the GroupBy/Aggregate relational operator. Technical report, Microsoft, 2001. MSR-TR-2001-13.
• 11: Won Kim, On optimizing an SQL-like nested query, ACM Transactions on Database Systems (TODS), v.7 n.3, p.443-469, Sept. 1982 [doi>10.1145/319732.319745]
• 12: Theodore W. Leung , Gail Mitchell , Bharathi Subramanian , Bennet Vance , Scott L. Vandenberg , Stanley B. Zdonik, The AQUA Data Model and Algebra, Proceedings of the Fourth International Workshop on Database Programming Languages - Object Models and Languages, p.157-175, August 30-September 01, 1993
• 13: Jim Melton , Alan R. Simon, Understanding the new SQL: a complete guide, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1993
• 14: 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
• 15: Praveen Seshadri , Hamid Pirahesh , T. Y. Cliff Leung, Complex Query Decorrelation, Proceedings of the Twelfth International Conference on Data Engineering, p.450-458, February 26-March 01, 1996
• 16: Gail M. Shaw , Stanley B. Zdonik, An object-oriented query algebras, Proceedings of the second international workshop on Database programming languages, p.103-112, December 1989, Salishan Lodge, Gleneden Beach, Oregon, United States
• 17: Q. Wang, D. Maier, and L. Shapiro. Algebraic unnesting of nested object queries. Technical report, Oregon Graduate Institute, 1999. CSE-99-013.
• 18: Weipeng P. Yan , Per-Åke Larson, Eager Aggregation and Lazy Aggregation, Proceedings of the 21th International Conference on Very Large Data Bases, p.345-357, September 11-15, 1995

INDEX TERMS

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

Additional Classification:
  C. Computer Systems Organization
  C.5 COMPUTER SYSTEM IMPLEMENTATION

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS

  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.4 Systems and Software
          Subjects: Performance evaluation (efficiency and effectiveness)

General Terms:
Design, Management, Measurement, Performance, Theory