Left-deep vs. bushy trees

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Left-deep vs. bushy trees: an analysis of strategy spaces and its implications for query optimization

Full text

Pdf (1.21 MB)

Source

International Conference on Management of Data archive
Proceedings of the 1991 ACM SIGMOD international conference on Management of data table of contents

Denver, Colorado, United States

Pages: 168 - 177

Year of Publication: 1991

ISBN:0-89791-425-2

Also published in ...

Authors

Yannis E. Ioannidis	Computer Sciences Department, University of Wisconsin, Madison, WI
Younkyung Cha Kang	Computer Sciences Department, University of Wisconsin, Madison, WI

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGART: ACM Special Interest Group on Artificial Intelligence
SIGMOD: ACM Special Interest Group on Management of Data

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 8, Downloads (12 Months): 84, Citation Count: 40

Additional Information:

references cited by index terms collaborative colleagues

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/115790.115813 What is a DOI?

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.

	Gran81	Grant, J. and J. Minker, "Optimization in Deductive and Conventional Relational Database Systems", in Advances in Data Base Theory Vol. 1, edited by H. Gallaire, J. Minker and J. M. Nicolas, Plenum Press, New York, N.Y., 1981, pp. 195-234.
	Ibar84	Toshihide Ibaraki , Tiko Kameda, On the optimal nesting order for computing N-relational joins, ACM Transactions on Database Systems (TODS), v.9 n.3, p.482-502, Sept. 1984 [doi>10.1145/1270.1498]
	Ioan87	Yannis E. Ioannidis , Eugene Wong, Query optimization by simulated annealing, Proceedings of the 1987 ACM SIGMOD international conference on Management of data, p.9-22, May 27-29, 1987, San Francisco, California, United States
	Ioan90	Y. E. Ioannidis , Younkyung Kang, Randomized algorithms for optimizing large join queries, Proceedings of the 1990 ACM SIGMOD international conference on Management of data, p.312-321, May 23-26, 1990, Atlantic City, New Jersey, United States
	Jark84	Matthias Jarke , Jurgen Koch, Query Optimization in Database Systems, ACM Computing Surveys (CSUR), v.16 n.2, p.111-152, June 1984 [doi>10.1145/356924.356928]
	Kang91	Younkyung Cha Kang, Randomized algorithms for query optimization, University of Wisconsin at Madison, Madison, WI, 1991
	Kim86	Won Kim , D. S. Reiner , D. S. Batory, Query Processing in Database Systems, Springer-Verlag New York, Inc., Secaucus, NJ, 1985
	Kirk83	Kirkpatrick, S., C. D. Gelatt, Jr., and M. P. Vecchi, "Optimization by Simulated Annealing", Science 220, 4598 (May 1983), pp. 671-680.
	Kris86	Ravi Krishnamurthy , Haran Boral , Carlo Zaniolo, Optimization of Nonrecursive Queries, Proceedings of the 12th International Conference on Very Large Data Bases, p.128-137, August 25-28, 1986
	Monm79	Monma, C. L. and J. B. Sidney, "Sequencing with Series-Parallel Precedence Constraints", Mathematics of Operations Research 4, 3 (August 1979), pp. 212-224.
	Naha86	Surendra Nahar , Sartaj Sahni , Eugene Shragowitz, Simulated annealing and combinatorial optimization, Proceedings of the 23rd ACM/IEEE conference on Design automation, p.293-299, July 1986, Las Vegas, Nevada, United States
	Roth86	Rothschild, V. and N. Logothetis, Probability Distributions, John Wiley & Sons, New York, N.Y., 1986.
	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]
	Sell86	Timos K. Sellis, Global query optimization, Proceedings of the 1986 ACM SIGMOD international conference on Management of data, p.191-205, May 28-30, 1986, Washington, D.C., United States
	Swam88	Arun Swami , Anoop Gupta, Optimization of large join queries, Proceedings of the 1988 ACM SIGMOD international conference on Management of data, p.8-17, June 01-03, 1988, Chicago, Illinois, United States
	Ullm82	Jeffrey D. Ullman, Principles of Database Systems, W. H. Freeman & Co., New York, NY, 1983

CITED BY 40

	Wolfgang Scheufele , Guido Moerkotte, On the complexity of generating optimal plans with cross products (extended abstract), Proceedings of the sixteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.238-248, May 11-15, 1997, Tucson, Arizona, United States
	Allen Van Gelder, Multiple join size estimation by virtual domains (extended abstract), Proceedings of the twelfth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.180-189, May 25-28, 1993, Washington, D.C., United States
	Jun Rao , Chun Zhang , Nimrod Megiddo , Guy Lohman, Automating physical database design in a parallel database, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin
	Donald Kossmann, The state of the art in distributed query processing, ACM Computing Surveys (CSUR), v.32 n.4, p.422-469, Dec. 2000
	Dimitris Papadias , Nikos Mamoulis , Yannis Theodoridis, Processing and optimization of multiway spatial joins using R-trees, Proceedings of the eighteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.44-55, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
	Hui-I Hsiao , Ming-Syan Chen , Philip S. Yu, On parallel execution of multiple pipelined hash joins, ACM SIGMOD Record, v.23 n.2, p.185-196, June 1994
	Florian Waas , César Galindo-Legaria, Counting, enumerating, and sampling of execution plans in a cost-based query optimizer, ACM SIGMOD Record, v.29 n.2, p.499-509, June 2000
	Panos Kalnis , Nikos Mamoulis , Dimitris Papadias, View selection using randomized search, Data & Knowledge Engineering, v.42 n.1, p.89-111, July 2002
	Abdelkader Hameurlain , Franck Morvan, CPU and incremental memory allocation in dynamic parallelization of SQL Queries, Parallel Computing, v.28 n.4, p.525-556, April 2002
	Bennet Vance , David Maier, Rapid bushy join-order optimization with Cartesian products, ACM SIGMOD Record, v.25 n.2, p.35-46, June 1996
	Kien A. Hua , S. D. Lang , Wen K. Lee, A decomposition-based simulated annealing technique for data clustering, Proceedings of the thirteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.117-128, May 24-27, 1994, Minneapolis, Minnesota, United States
	Ihab F. Ilyas , Jun Rao , Guy Lohman , Dengfeng Gao , Eileen Lin, Estimating compilation time of a query optimizer, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California
	Mikal Ziane , Mohamed Zaït , Pascale Borla-Salamet, Parallel query processing with zigzag trees, The VLDB Journal — The International Journal on Very Large Data Bases, v.2 n.3, July 1993
	Philip S. Yu , Douglas W. Cornell, Buffer management based on return on consumption in a multi-query environment, The VLDB Journal — The International Journal on Very Large Data Bases, v.2 n.1, p.1-38, January 1993
	Ming-Syan Chen , Mingling Lo , Philip S. Yu , Honesty C. Young, Applying Segmented Right-Deep Trees to Pipelining Multiple Hash Joins, IEEE Transactions on Knowledge and Data Engineering, v.7 n.4, p.656-668, August 1995
	Adel Shrufi , Thodoros Topaloglou, Query processing for knowledge bases using join indices, Proceedings of the fourth international conference on Information and knowledge management, p.158-166, November 29-December 02, 1995, Baltimore, Maryland, United States
	Ram D. Gopal , R. Ramesh , Stanley Zionts, Criss-Cross Hash Joins: Design and Analysis, IEEE Transactions on Knowledge and Data Engineering, v.13 n.4, p.637-653, July 2001
	Min J. Yu , P. C.-Y. Sheu, Adaptive Join Algorithms in Dynamic Distributed Databases, Distributed and Parallel Databases, v.5 n.1, p.5-30, Jan. 1997
	E. N. Hanson , S. Bodagala , U. Chadaga, Trigger Condition Testing and View Maintenance Using Optimized Discrimination Networks, IEEE Transactions on Knowledge and Data Engineering, v.14 n.2, p.261-280, March 2002
	Hui-I Hsiao , Ming-Syan Chen , Philip S. Yu, Parallel Execution of Hash Joins in Parallel Databases, IEEE Transactions on Parallel and Distributed Systems, v.8 n.8, p.872-883, August 1997
	Myra Spiliopoulou , Michael Hatzopoulos , Yannis Cotronis, Parallel Optimization of Large Join Queries with Set Operators and Aggregates in a Parallel Environment Supporting Pipeline, IEEE Transactions on Knowledge and Data Engineering, v.8 n.3, p.429-445, June 1996
	Bojan Groselj , Qutaibah M. Malluhi, Combinatorial Optimization of Distributed Queries, IEEE Transactions on Knowledge and Data Engineering, v.7 n.6, p.915-927, December 1995
	D. K. Subramanian , K. Subramanian, Query Optimization in Multidatabase Systems, Distributed and Parallel Databases, v.6 n.2, p.183-210, April 1998
	Anna Pagh , Rasmus Pagh, Scalable computation of acyclic joins, Proceedings of the twenty-fifth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 26-28, 2006, Chicago, IL, USA
	Ming-Syan Chen , Hui-I Hsiao , Philip S. Yu, On applying hash filters to improving the execution of multi-join queries, The VLDB Journal — The International Journal on Very Large Data Bases, v.6 n.2, p.121-131, May 1997
	Yannis E. Ioannidis , Raymond T. Ng , Kyuseok Shim , Timos K. Sellis, Parametric query optimization, The VLDB Journal — The International Journal on Very Large Data Bases, v.6 n.2, p.132-151, May 1997
	Michael Steinbrunn , Guido Moerkotte , Alfons Kemper, Heuristic and randomized optimization for the join ordering problem, The VLDB Journal — The International Journal on Very Large Data Bases, v.6 n.3, p.191-208, August 1997
	John Mylopoulos , Vinay Chaudhri , Dimitris Plexousakis , Adel Shrufi , Thodoros Topologlou, Building knowledge base management systems, The VLDB Journal — The International Journal on Very Large Data Bases, v.5 n.4, p.238-263, December 1996
	Arjan Pellenkoft , César A. Galindo-Legaria , Martin L. Kersten, The Complexity of Transformation-Based Join Enumeration, Proceedings of the 23rd International Conference on Very Large Data Bases, p.306-315, August 25-29, 1997
	Ming-Syan Chen , Ming-Ling Lo , Philip S. Yu , Honesty C. Young, Using Segmented Right-Deep Trees for the Execution of Pipelined Hash Joins, Proceedings of the 18th International Conference on Very Large Data Bases, p.15-26, August 23-27, 1992
	César A. Galindo-Legaria , Arjan Pellenkoft , Martin L. Kersten, Fast, Randomized Join-Order Selection - Why Use Transformations?, Proceedings of the 20th International Conference on Very Large Data Bases, p.85-95, September 12-15, 1994
	Eugene J. Shekita , Honesty C. Young , Kian-Lee Tan, Multi-Join Optimization for Symmetric Multiprocessors, Proceedings of the 19th International Conference on Very Large Data Bases, p.479-492, August 24-27, 1993
	Rosana S. G. Lanzelotte , Patrick Valduriez , Mohamed Zaït, On the Effectiveness of Optimization Search Strategies for Parallel Execution Spaces, Proceedings of the 19th International Conference on Very Large Data Bases, p.493-504, August 24-27, 1993
	Ming-Syan Chen , Hui-I Hsiao , Philip S. Yu, Applying Hash Filters to Improving the Execution of Bushy Trees, Proceedings of the 19th International Conference on Very Large Data Bases, p.505-516, August 24-27, 1993
	Yannis E. Ioannidis , Raymond T. Ng , Kyuseok Shim , Timos K. Sellis, Parametric Query Optimization, Proceedings of the 18th International Conference on Very Large Data Bases, p.103-114, August 23-27, 1992
	Hongjun Lu , Kian-Lee Tan , Son Dao, The Fittest Survives: An Adaptive Approach to Query Optimization, Proceedings of the 21th International Conference on Very Large Data Bases, p.251-262, September 11-15, 1995
	CORPORATE Univ. of Wisconsin, Database research at Wisconsin, ACM SIGMOD Record, v.22 n.1, p.74-81, March 1993
	Celso C. Ribeiro , Cláudio D. Ribeiro , Rosana S. G. Lanzelotte, Query Optimization in Distributed Relational Databases, Journal of Heuristics, v.3 n.1, p.5-23, Fall 1997
	Josep Aguilar-Saborit , Mohammad Jalali , Dave Sharpe , Victor Muntés Mulero, Exploiting pipeline interruptions for efficient memory allocation, Proceeding of the 17th ACM conference on Information and knowledge management, October 26-30, 2008, Napa Valley, California, USA
	Michael Stillger , Myra Spiliopoulou, Genetic programming in database query optimization, Proceedings of the First Annual Conference on Genetic Programming, July 28-31, 1996, Stanford, California