Optimization of nested SQL queries revisited

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Optimization of nested SQL queries revisited

Full text

Pdf (1.08 MB)

Source

ACM SIGMOD Record archive
Volume 16 , Issue 3 (December 1987) table of contents

Pages: 23 - 33

Year of Publication: 1987

ISSN:0163-5808

Also published in ...

Authors

Richard A. Ganski	San Francisco State Univ., San Francisco, CA
Harry K. T. Wong	Univ. of California, Berkeley

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 19, Downloads (12 Months): 109, Citation Count: 48

Additional Information:

abstract references cited by index terms collaborative colleagues peer to peer

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/38714.38723 What is a DOI?

ABSTRACT

Current methods of evaluating nested queries in the SQL language can be inefficient in a variety of query and data base contexts. Previous research in the area of nested query optimization which sought methods of reducing evaluation costs is summarized, including a classification scheme for nested queries, algorithms designed to transform each type of query to a logically equivalent form which may then be evaluated more efficiently, and a description of a major bug in one of these algorithms. Further examination reveals another bug in the same algorithm. Solutions to these bugs are proposed and incorporated into a new transformation algorithm, and extensions are proposed which will allow the transformation algorithms to handle a larger class of predicates. A recursive algorithm for processing a general nested query is presented and the action of this algorithm is demonstrated. This algorithm can be used to transform any nested query.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	AST 75	M. M. Astrahan , D. D. Chamberlin, Implementation of a structured English query language, Communications of the ACM, v.18 n.10, p.580-588, Oct. 1975 [doi>10.1145/361020.361215]
	AST 76	M. M. Astrahan , M. W. Blasgen , D. D. Chamberlin , K. P. Eswaran , J. N. Gray , P. P. Griffiths , W. F. King , R. A. Lorie , P. R. McJones , J. W. Mehl , G. R. Putzolu , I. L. Traiger , B. W. Wade , V. Watson, System R: relational approach to database management, ACM Transactions on Database Systems (TODS), v.1 n.2, p.97-137, June 1976 [doi>10.1145/320455.320457]
	COD 79	E. F. Codd, Extending the database relational model to capture more meaning, ACM Transactions on Database Systems (TODS), v.4 n.4, p.397-434, Dec. 1979 [doi>10.1145/320107.320109]
	KIE 84	Fdesslmg, W SQL-Ltke and Quel.hke correlauon queries with aggregates revtstted. UCB/ERL Memo 84/75, Electronics Research Laboratory, Umv Cahforma, Berkeley (Sept. 1984)
	KIM 82	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]
	ORA 86	Oracle Corporauon Private product demonstratton (Sept 1986)
	SEL 79	Selmger, PG. Astrahan. M M. Chamberlm. D D. Lone. R A. and Price, T G Access path selecuon m a relauonal database system In Proc ACM Inter Conf Management of Data, Boston, Mass (May 1979), 23-34
	STO 76	Michael Stonebraker , Gerald Held , Eugene Wong , Peter Kreps, The design and implementation of INGRES, ACM Transactions on Database Systems (TODS), v.1 n.3, p.189-222, Sept. 1976 [doi>10.1145/320473.320476]

CITED BY 48

	Kian-Lee Tan , Cheng Hian Goh , Beng Chin Ooi, Online Feedback for Nested Aggregate Queries with Multi-Threading, Proceedings of the 25th International Conference on Very Large Data Bases, p.18-29, September 07-10, 1999
	Calisto Zuzarte , Hamid Pirahesh , Wenbin Ma , Qi Cheng , Linqi Liu , Kwai Wong, WinMagic: subquery elimination using window aggregation, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California
	Ravindra Guravannavar , S. Sudarshan, Rewriting procedures for batched bindings, Proceedings of the VLDB Endowment, v.1 n.1, August 2008
	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
	Alon Y. Levy , Inderpal Singh Mumick , Yehoshua Sagiv, Query Optimization by Predicate Move-Around, Proceedings of the 20th International Conference on Very Large Data Bases, p.96-107, September 12-15, 1994
	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
	Kian-Lee Tan , Cheng Hian Goh , Beng Chin Ooi, Progressive evaluation of nested aggregate queries, The VLDB Journal — The International Journal on Very Large Data Bases, v.9 n.3, p.261-278, December 2000
	Rafi Ahmed , Allison Lee , Andrew Witkowski , Dinesh Das , Hong Su , Mohamed Zait , Thierry Cruanes, Cost-based query transformation in Oracle, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
	Antonio Badia , Matt Chanda , Bin Cao, Adding subqueries to MySQL, what does it take to have a decision-support engine?, Proceedings of the 5th ACM international workshop on Data Warehousing and OLAP, p.49-56, November 08-08, 2002, McLean, Virginia, USA
	C. H. C. Leung , H. T. Ghogomu, A high-performance parallel database architecture, Proceedings of the 7th international conference on Supercomputing, p.377-386, July 19-23, 1993, Tokyo, Japan
	Gautam Bhargava , Piyush Goel , Bala Iyer, Hypergraph based reorderings of outer join queries with complex predicates, ACM SIGMOD Record, v.24 n.2, p.304-315, May 1995
	Ravindra Guravannavar , H. S. Ramanujam , S. Sudarshan, Optimizing nested queries with parameter sort orders, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
	Hamid Pirahesh , Joseph M. Hellerstein , Waqar Hasan, Extensible/rule based query rewrite optimization in Starburst, ACM SIGMOD Record, v.21 n.2, p.39-48, June 1, 1992
	Graham J. L. Kemp , Peter M. D. Gray , Andreas R. Sjöstedt, Improving Federated Database Queries Using Declarative Rewrite Rules for Quantified Subqueries, Journal of Intelligent Information Systems, v.17 n.2-3, p.281-299, December 2001
	Jun Rao , Kenneth A. Ross, Reusing invariants: a new strategy for correlated queries, ACM SIGMOD Record, v.27 n.2, p.37-48, June 1998
	Inderpal Singh Mumick , Hamid Pirahesh, Implementation of magic-sets in a relational database system, ACM SIGMOD Record, v.23 n.2, p.103-114, June 1994
	G. N. Paulley , Per-Åke Larson, Exploiting uniqueness in query optimization, Proceedings of the 1993 conference of the Centre for Advanced Studies on Collaborative research: distributed computing, October 24-28, 1993, Toronto, Ontario, Canada
	Leonore Neugebauer, Optimization and evaluation of database queries including embedded interpolation procedures, ACM SIGMOD Record, v.20 n.2, p.118-127, June 1991
	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
	David Taniar , Hui Yee Khaw , Haorianto Cokrowijoyo Tjioe , Eric Pardede, The use of Hints in SQL-Nested query optimization, Information Sciences: an International Journal, v.177 n.12, p.2493-2521, June, 2007
	Bin Cao , Antonio Badia, A nested relational approach to processing SQL subqueries, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland
	Daniel F. Lieuwen , David J. DeWitt, A transformation-based approach to optimizing loops in database programming languages, ACM SIGMOD Record, v.21 n.2, p.91-100, June 1, 1992
	Piyush Goel , Bala Iyer, SQL query optimization: reordering for a general class of queries, ACM SIGMOD Record, v.25 n.2, p.47-56, June 1996
	Inderpal Singh Mumick , Sheldon J. Finkelstein , Hamid Pirahesh , Raghu Ramakrishnan, Magic conditions, ACM Transactions on Database Systems (TODS), v.21 n.1, p.107-155, March 1996
	Hennie J. Steenhagen , Peter M. G. Apers , Henk M. Blanken , Rolf A. de By, From Nested-Loop to Join Queries in OODB, Proceedings of the 20th International Conference on Very Large Data Bases, p.618-629, September 12-15, 1994
	S. B. Yoo , P. C.-Y. Sheu, Evaluation and Optimization of Query Programs in an Object-Oriented and Symbolic Information System, IEEE Transactions on Knowledge and Data Engineering, v.5 n.3, p.479-495, June 1993
	Praveen Seshadri , Miron Livny , Raghu Ramakrishnan, Sequence query processing, ACM SIGMOD Record, v.23 n.2, p.430-441, June 1994
	I. S. Mumick , S. J. Finkelstein , Hamid Pirahesh , Raghu Ramakrishnan, Magic is relevant, ACM SIGMOD Record, v.19 n.2, p.247-258, Jun. 1990
	P. Bohannon , S. Ganguly , H. F. Korth , P. P. S. Narayan , P. Shenoy, Optimizing view queries in ROLEX to support navigable result trees, Proceedings of the 28th international conference on Very Large Data Bases, p.119-130, August 20-23, 2002, Hong Kong, China
	M. Negri , G. Pelagatti , L. Sbattella, Formal semantics of SQL queries, ACM Transactions on Database Systems (TODS), v.16 n.3, p.513-534, Sept. 1991
	Mihnea Andrei , Patrick Valduriez, User-Optimizer Communication using Abstract Plans in Sybase ASE, Proceedings of the 27th International Conference on Very Large Data Bases, p.29-38, September 11-14, 2001
	César A. Galindo-Legaria, Outerjoins as disjunctions, ACM SIGMOD Record, v.23 n.2, p.348-358, June 1994
	Sudhir G. Rao , Antonio Badia , Dirk van Gucht, Providing better support for a class of decision support queries, ACM SIGMOD Record, v.25 n.2, p.217-227, June 1996
	Alin Deutsch , Yannis Papakonstantinou , Yu Xu, The NEXT framework for logical XQuery optimization, Proceedings of the Thirtieth international conference on Very large data bases, p.168-179, August 31-September 03, 2004, Toronto, Canada
	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
	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
	Q. Yang , W. Zhang , C. Liu , J. Wu , C. Yu , H. Nakajima , N. D. Rishe, Efficient Processing of Nested Fuzzy SQL Queries in a Fuzzy Database, IEEE Transactions on Knowledge and Data Engineering, v.13 n.6, p.884-901, November 2001
	Leonidas Fegaras, Query unnesting in object-oriented databases, ACM SIGMOD Record, v.27 n.2, p.49-60, June 1998
	Jens Claußen , Alfons Kemper , Guido Moerkotte , Klaus Peithner, Optimizing Queries with Universal Quantification in Object-Oriented and Object-Relational Databases, Proceedings of the 23rd International Conference on Very Large Data Bases, p.286-295, August 25-29, 1997
	S. Finkelstein , M. Schkolnick , P. Tiberio, Physical database design for relational databases, ACM Transactions on Database Systems (TODS), v.13 n.1, p.91-128, March 1988
	Bin Cao , Antonio Badia, SQL query optimization through nested relational algebra, ACM Transactions on Database Systems (TODS), v.32 n.3, p.18-es, August 2007
	William J. McKenna , Louis Burger , Chi Hoang , Melissa Truong, EROC: A Toolkit for Building NEATO Query Optimizers, Proceedings of the 22th International Conference on Very Large Data Bases, p.111-121, September 03-06, 1996
	Surajit Chaudhuri, An overview of query optimization in relational systems, Proceedings of the seventeenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.34-43, June 01-04, 1998, Seattle, Washington, United States
	Mitch Cherniack , Stanley B. Zdonik, Rule languages and internal algebras for rule-based optimizers, ACM SIGMOD Record, v.25 n.2, p.401-412, June 1996
	L. M. Haas , J. C. Freytag , G. M. Lohman , H. Pirahesh, Extensible query processing in starburst, ACM SIGMOD Record, v.18 n.2, p.377-388, June 1989
	Surajit Chaudhuri , Umeshwar Dayal, An overview of data warehousing and OLAP technology, ACM SIGMOD Record, v.26 n.1, p.65-74, March 1997
	Norman May , Sven Helmer , Guido Moerkotte, Strategies for query unnesting in XML databases, ACM Transactions on Database Systems (TODS), v.31 n.3, p.968-1013, September 2006
	Leonidas Fegaras , David Maier, Optimizing object queries using an effective calculus, ACM Transactions on Database Systems (TODS), v.25 n.4, p.457-516, Dec. 2000