article

Free access

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

Authors:

Yannis E. Ioannidis,

Younkyung Cha KangAuthors Info & Claims

ACM SIGMOD Record, Volume 20, Issue 2

Pages 168 - 177

https://doi.org/10.1145/119995.115813

Published: 01 April 1991 Publication History

PDF eReader

References

[1]

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.

Crossref

Google Scholar

[2]

Ibaraki, T. and T. Kameda, "On the Optimal Nesting Order for Computing N-Relational Joins", ACM TODS 9, 3 (September 1984), pp. 482-502.

Digital Library

Google Scholar

[3]

Ioannidis, Y. E. and E. Wong, "Query Optimization by Simulated Annealing", in Proc. of the 1987 ACM-SIGMOD Conference on the Management of Data, San Francisco, CA, May 1987, pp. 9-22.

Digital Library

Google Scholar

[4]

Ioannidis, Y. E. and Y. C. Kang, "Randomized Algorithms for Optimizing Large Join Queries", in Proc. of the 1990 ACM-SIGMOD Conference on the Management of Data, Atlantic City, NJ, May 1990, pp. 312-321.

Digital Library

Google Scholar

[5]

Jarke, M. and J. Koch, "Query Optimization in Database Systems", ACM Computing Surveys 16, 2 (June 1984), pp. 111-152.

Digital Library

Google Scholar

[6]

Kang, Y., "Randomized Algorithms for Query Optimization", Ph.D. Thesis, University of Wisconsin, Madison, WI, April 1991.

Digital Library

Google Scholar

[7]

Kim, W., D. Reiner, and D. Batory, Query Processing in Database Systems, Springer Verlag, New York, NY, 1986.

Digital Library

Google Scholar

[8]

Kirkpatrick, S., C. D. Gelatt, Jr., and M. P. Vecchi, "Optimization by Simulated Annealing", Science 220, 4598 (May 1983), pp. 671-680.

Google Scholar

[9]

Krishnamurthy, R., H. Boral, and C. Zaniolo, "Optimization of Nonrecursive Queries", in Proc. 12th International VLDB Conference, Kyoto, Japan, August 1986, pp. 128-137.

Digital Library

Google Scholar

[10]

Monma, C. L. and J. B. Sidney, "Sequencing with Series-Parallel Precedence Constraints", Mathematics of Operations Research 4, 3 (August 1979), pp. 212-224.

Digital Library

Google Scholar

[11]

Nahar, S., S. Sahni, and E. Shragowitz, "Simulated Annealing and Combinatorial Optimization", in Proc. of the 23rd Design Automation Conference, 1986, pp. 293-299.

Digital Library

Google Scholar

[12]

Rothschild, V. and N. Logothetis, Probability Distributions, John Wiley & Sons, New York, N.Y., 1986.

Google Scholar

[13]

Selinger, P. et al., "Access Path Selection in a Relational Data Base System", in Proc. of the 1979 ACM-SIGMOD Conference on the Management of Data, Boston, MA, June 1979, pp. 23-34.

Digital Library

Google Scholar

[14]

Sellis, T. K., "Global Query Optimization", in Proc. of the 1986 A CM-SIGMOD Conference on the Management of Data, Washington, DC, May 1986, pp. 191-205.

Digital Library

Google Scholar

[15]

Swami, A. and A. Gupta, "Optimization of Large Join Queries", in Proc. of the 1988 ACM-SIGMOD Conference on the Management of Data, Chicago, IL, June 1988, pp. 8-17.

Digital Library

Google Scholar

[16]

Ullman, J. D., Principles of Database Systems, Computer Science Press, Rockville, MD, 1982.

Digital Library

Google Scholar

Cited By

View all

Mouna MBellatreche LBoustia N(2022)ProRes: Proactive re-selection of materialized viewsComputer Science and Information Systems10.2298/CSIS210606003M19:2(735-762)Online publication date: 2022
https://doi.org/10.2298/CSIS210606003M
Yuan YMa DWen ZZhang ZWang G(2021)Subgraph matching over graph federationProceedings of the VLDB Endowment10.14778/3494124.349412915:3(437-450)Online publication date: 1-Nov-2021
https://dl.acm.org/doi/10.14778/3494124.3494129
Li GZhou XSun JYu XHan YJin LLi WWang TLi S(2021)openGaussProceedings of the VLDB Endowment10.14778/3476311.347638014:12(3028-3042)Online publication date: 28-Oct-2021
https://dl.acm.org/doi/10.14778/3476311.3476380
Show More Cited By

Index Terms

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

Recommendations

Left-deep vs. bushy trees: an analysis of strategy spaces and its implications for query optimization
SIGMOD '91: Proceedings of the 1991 ACM SIGMOD international conference on Management of data
Of snowstorms and bushy trees

Many workloads for analytical processing in commercial RDBMSs are dominated by snowstorm queries, which are characterized by references to multiple large fact tables and their associated smaller dimension tables. This paper describes a technique for ...
Applying Segmented Right-Deep Trees to Pipelining Multiple Hash Joins

The pipelined execution of multijoin queries in a multiprocessor-based database system is explored in this paper. Using hash-based joins, multiple joins can be pipelined so that the early results from a join, before the whole join is completed, are sent ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

ACM SIGMOD Record Volume 20, Issue 2

June 1991

447 pages

ISSN:0163-5808

DOI:10.1145/119995

Issue’s Table of Contents

SIGMOD '91: Proceedings of the 1991 ACM SIGMOD international conference on Management of data
April 1991
452 pages
ISBN:0897914252
DOI:10.1145/115790
Editors:
James Clifford,
Roger King

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 April 1991

Published in SIGMOD Volume 20, Issue 2

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

114
Total Citations
View Citations
1,810
Total Downloads

Downloads (Last 12 months)230
Downloads (Last 6 weeks)37

Reflects downloads up to 22 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Mouna MBellatreche LBoustia N(2022)ProRes: Proactive re-selection of materialized viewsComputer Science and Information Systems10.2298/CSIS210606003M19:2(735-762)Online publication date: 2022
https://doi.org/10.2298/CSIS210606003M
Yuan YMa DWen ZZhang ZWang G(2021)Subgraph matching over graph federationProceedings of the VLDB Endowment10.14778/3494124.349412915:3(437-450)Online publication date: 1-Nov-2021
https://dl.acm.org/doi/10.14778/3494124.3494129
Li GZhou XSun JYu XHan YJin LLi WWang TLi S(2021)openGaussProceedings of the VLDB Endowment10.14778/3476311.347638014:12(3028-3042)Online publication date: 28-Oct-2021
https://dl.acm.org/doi/10.14778/3476311.3476380
Kang XZhao YYuan PJin H(2021)Grace: An Efficient Parallel SPARQL Query System over Large-Scale RDF Data2021 IEEE 24th International Conference on Computer Supported Cooperative Work in Design (CSCWD)10.1109/CSCWD49262.2021.9437674(769-774)Online publication date: 5-May-2021
https://doi.org/10.1109/CSCWD49262.2021.9437674
Yu XLi GChai CTang N(2020)Reinforcement Learning with Tree-LSTM for Join Order Selection2020 IEEE 36th International Conference on Data Engineering (ICDE)10.1109/ICDE48307.2020.00116(1297-1308)Online publication date: Apr-2020
https://doi.org/10.1109/ICDE48307.2020.00116
Lai ZYang ZLai L(2019)Improving Distribued Subgraph Matching Algorithm on Timely Dataflow2019 IEEE 35th International Conference on Data Engineering Workshops (ICDEW)10.1109/ICDEW.2019.000-2(266-273)Online publication date: Apr-2019
https://doi.org/10.1109/ICDEW.2019.000-2
Ganian ROrdyniak SSzeider S(2019)A Join-Based Hybrid Parameter for Constraint SatisfactionPrinciples and Practice of Constraint Programming10.1007/978-3-030-30048-7_12(195-212)Online publication date: 23-Sep-2019
https://doi.org/10.1007/978-3-030-30048-7_12
Kolchinsky ISchuster A(2018)Join query optimization techniques for complex event processing applicationsProceedings of the VLDB Endowment10.14778/3236187.323618911:11(1332-1345)Online publication date: 1-Jul-2018
https://dl.acm.org/doi/10.14778/3236187.3236189
Yin SHameurlain AMorvan F(2018)SLA Definition for Multi-tenant DBMS and its Impact on Query OptimizationIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2018.2817235(1-1)Online publication date: 2018
https://doi.org/10.1109/TKDE.2018.2817235
Shah BPareek JKanziya D(2017)A Novel Approach to Optimize Subqueries for Open Source DatabasesSmart Trends in Systems, Security and Sustainability10.1007/978-981-10-6916-1_31(331-346)Online publication date: 31-Dec-2017
https://doi.org/10.1007/978-981-10-6916-1_31
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

References

Cited By

Index Terms

Recommendations