A nested relational approach to processing SQL subqueries

ABSTRACT

One of the most powerful features of SQL is the use of nested queries. Most research work on the optimization of nested queries focuses on aggregate subqueries. However, the solutions proposed for non-aggregate subqueries are still limited, especially for queries having multiple subqueries and null values. In this paper, we show that existing approaches to queries containing non-aggregate subqueries proposed in the literature (including rewrites) are not adequate. We then propose a new efficient approach, the nested relational approach, based on the nested relational algebra. Our approach directly unnests non-aggregate subqueries using hash joins, and treats all subqueries in a uniform manner, being able to deal with nested queries of any type and any level. We report on experimental work that confirms that existing approaches have difficulties dealing with non-aggregate subqueries, and that our approach offers better performance. We also discuss some possibilities for algebraic optimization and the issue of integrating our approach in a relational database system.

REFERENCES

• 1: M. O. Akinde and M. H. Bohlen. Efficient computation of subqueries in complex olap. In Proceedings of the IEEE ICDE Conference, pages 163--174, 2003.
• 2: A. Badia. Computing sql subqueries with boolean aggregates. In Proceedings of the 5th International Conference on Data Warehousing and Knowledge Discovery (DAWAK'03), 2003.
• 3: Lars Baekgaard , Leo Mark, Incremental computation of nested relational query expressions, ACM Transactions on Database Systems (TODS), v.20 n.2, p.111-148, June 1995 [doi>10.1145/210197.210198]
• 4: T. Council. The tpc-h benchmark. http://www.tpc.org.
• 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ésar Galindo-Legaria , Milind Joshi, Orthogonal optimization of subqueries and aggregation, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.571-581, May 21-24, 2001, Santa Barbara, California, United States
• 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: 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
• 9: Ashish Gupta , Venky Harinarayan , Dallan Quass, Aggregate-Query Processing in Data Warehousing Environments, Proceedings of the 21th International Conference on Very Large Data Bases, p.358-369, September 11-15, 1995
• 10: 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]
• 11: Mark Levene , George Loizou, Semantics for null extended nested relations, ACM Transactions on Database Systems (TODS), v.18 n.3, p.414-459, Sept. 1993 [doi>10.1145/155271.155275]
• 12: Nikos Mamoulis, Efficient processing of joins on set-valued attributes, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872778]
• 13: M. Muralikrishna, Optimization and dataflow algorithms for nested tree queries, Proceedings of the 15th international conference on Very large data bases, p.77-85, July 1989, Amsterdam, The Netherlands
• 14: 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
• 15: Jan Paredaens , Paul De Bra , Marc Gyssens , Dirk Van Gucht, The structure of the relational database model, Springer-Verlag New York, Inc., New York, NY, 1989
• 16: Jun Rao , Bruce G. Lindsay , Guy M. Lohman , Hamid Pirahesh , David E. Simmen, Using EELs, a Practical Approach to Outerjoin and Antijoin Reordering, Proceedings of the 17th International Conference on Data Engineering, p.585-594, April 02-06, 2001
• 17: Praveen Seshadri , Joseph M. Hellerstein , Hamid Pirahesh , T. Y. Cliff Leung , Raghu Ramakrishnan , Divesh Srivastava , Peter J. Stuckey , S. Sudarshan, Cost-based optimization for magic: algebra and implementation, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.435-446, June 04-06, 1996, Montreal, Quebec, Canada
• 18: 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
• 19: Gottfried Vossen, Data models, database languages and database management systems, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1991