Article

Analysis of two existing and one new dynamic programming algorithm for the generation of optimal bushy join trees without cross products

Authors:

Guido Moerkotte,

Thomas NeumannAuthors Info & Claims

VLDB '06: Proceedings of the 32nd international conference on Very large data bases

Pages 930 - 941

Published: 01 September 2006 Publication History

Get Access

Abstract

Two approaches to derive dynamic programming algorithms for constructing join trees are described in the literature. We show analytically and experimentally that these two variants exhibit vastly diverging runtime behaviors for different query graphs. More specifically, each variant is superior to the other for one kind of query graph (chain or clique), but fails for the other. Moreover, neither of them handles star queries well. This motivates us to derive an algorithm that is superior to the two existing algorithms because it adapts to the search space implied by the query graph.

References

[1]

{1} T. Cormen, C. Leiserson, R. Rivest, and C. Stein. Introduction to Algorithms. MIT Press, 2001. 2nd Edition.

Digital Library

Google Scholar

[2]

{2} P. Gassner, G. Lohman, and K. Schiefer. Query optimization in the IBM DB2 family. IEEE Data Engineering Bulletin, 16:4-18, Dec. 1993.

Google Scholar

[3]

{3} D. Kossmann and K. Stocker. Iterative dynamic programming: a new class of query optimization algorithms. ACM Trans. on Database Systems, 25(1):43-82, 2000.

Digital Library

Google Scholar

[4]

{4} G. Moerkotte. Dp-counter analytics. Technical Report 2, University of Mannheim, 2006.

Google Scholar

[5]

{5} K. Ono and G. Lohman. Measuring the complexity of join enumeration in query optimization. In Proc. Int. Conf. on Very Large Data Bases (VLDB), pages 314-325, 1990.

Digital Library

Google Scholar

[6]

{6} G. Rücker and C. Rücker. Automatic enumeration of all connected subgraphs. Commun. Math. Comput. Chem., 41:145-149, 2000.

Google Scholar

[7]

{7} P. Selinger, M. Astrahan, D. Chamberlin, R. Lorie, and T. Price. Access path selection in a relational database management system. In Proc. of the ACM SIGMOD Conf. on Management of Data, pages 23-34, 1979.

Digital Library

Google Scholar

[8]

{8} A. R. Sharafat and O. R. Ma'rouzi. A novel and efficient algorithm for scanning all minimal cutsets of a graph. ArXiv Mathematics e-prints, 2002.

Google Scholar

[9]

{9} B. Vance. Join-order Optimization with Cartesian Products. PhD thesis, Oregon Graduate Institute of Science and Technology, 1998.

Digital Library

Google Scholar

[10]

{10} B. Vance and D. Maier. Rapid bushy join-order optimization with cartesian products. In Proc. of the ACM SIGMOD Conf. on Management of Data, pages 35-46, 1996.

Digital Library

Google Scholar

Cited By

View all

Birler AKemper ANeumann T(2024)Robust Join Processing with Diamond Hardened JoinsProceedings of the VLDB Endowment10.14778/3681954.368199517:11(3215-3228)Online publication date: 1-Jul-2024
https://dl.acm.org/doi/10.14778/3681954.3681995
Schönberger MTrummer IMauerer W(2023)Quantum-Inspired Digital Annealing for Join OrderingProceedings of the VLDB Endowment10.14778/3632093.363211217:3(511-524)Online publication date: 1-Nov-2023
https://dl.acm.org/doi/10.14778/3632093.3632112
Schönberger MScherzinger SMauerer W(2023)Ready to Leap (by Co-Design)? Join Order Optimisation on Quantum HardwareProceedings of the ACM on Management of Data10.1145/35889461:1(1-27)Online publication date: 30-May-2023
https://dl.acm.org/doi/10.1145/3588946
Show More Cited By

Index Terms

Analysis of two existing and one new dynamic programming algorithm for the generation of optimal bushy join trees without cross products

Recommendations

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 ...
Rapid bushy join-order optimization with Cartesian products

Query optimizers often limit the search space for join orderings, for example by excluding Cartesian products in subplans or by restricting plan trees to left-deep vines. Such exclusions are widely assumed to reduce optimization effort while minimally ...
A new join algorithm

This paper introduces a new efficient join algorithm to increase the speed of the join relational operation. Using a divide and conquer strategy, stack oriented filter technique in the new join algorithm filters unwanted tuples as early as possible ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

VLDB '06: Proceedings of the 32nd international conference on Very large data bases

September 2006

1269 pages

Publisher

VLDB Endowment

Publication History

Published: 01 September 2006

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

44
Total Citations
View Citations
891
Total Downloads

Downloads (Last 12 months)55
Downloads (Last 6 weeks)9

Reflects downloads up to 14 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Birler AKemper ANeumann T(2024)Robust Join Processing with Diamond Hardened JoinsProceedings of the VLDB Endowment10.14778/3681954.368199517:11(3215-3228)Online publication date: 1-Jul-2024
https://dl.acm.org/doi/10.14778/3681954.3681995
Schönberger MTrummer IMauerer W(2023)Quantum-Inspired Digital Annealing for Join OrderingProceedings of the VLDB Endowment10.14778/3632093.363211217:3(511-524)Online publication date: 1-Nov-2023
https://dl.acm.org/doi/10.14778/3632093.3632112
Schönberger MScherzinger SMauerer W(2023)Ready to Leap (by Co-Design)? Join Order Optimisation on Quantum HardwareProceedings of the ACM on Management of Data10.1145/35889461:1(1-27)Online publication date: 30-May-2023
https://dl.acm.org/doi/10.1145/3588946
Haffner IDittrich J(2023)Efficiently Computing Join Orders with Heuristic SearchProceedings of the ACM on Management of Data10.1145/35889271:1(1-26)Online publication date: 30-May-2023
https://dl.acm.org/doi/10.1145/3588927
Schleich MShaikhha ASuciu D(2023)Optimizing Tensor Programs on Flexible StorageProceedings of the ACM on Management of Data10.1145/35887171:1(1-27)Online publication date: 30-May-2023
https://dl.acm.org/doi/10.1145/3588717
Mancini RKarthik SChandra BMageirakos VAilamaki AIves ZBonifati AEl Abbadi A(2022)Efficient Massively Parallel Join Optimization for Large QueriesProceedings of the 2022 International Conference on Management of Data10.1145/3514221.3517871(122-135)Online publication date: 10-Jun-2022
https://dl.acm.org/doi/10.1145/3514221.3517871
Wi SHan WChang CKim K(2020)Towards multi-way join aware optimizer in SAP HANAProceedings of the VLDB Endowment10.14778/3415478.341553113:12(3019-3031)Online publication date: 1-Aug-2020
https://dl.acm.org/doi/10.14778/3415478.3415531
Wang YHutchison SLeang JHowe BSuciu D(2020)SPORESProceedings of the VLDB Endowment10.14778/3407790.340779913:12(1919-1932)Online publication date: 14-Sep-2020
https://dl.acm.org/doi/10.14778/3407790.3407799
Dreseler MBoissier MRabl TUflacker M(2020)Quantifying TPC-H choke points and their optimizationsProceedings of the VLDB Endowment10.14778/3389133.338913813:8(1206-1220)Online publication date: 3-May-2020
https://dl.acm.org/doi/10.14778/3389133.3389138
Ding BChaudhuri SNarasayya VMaier DPottinger RDoan ATan WAlawini ANgo H(2020)Bitvector-aware Query Optimization for Decision Support QueriesProceedings of the 2020 ACM SIGMOD International Conference on Management of Data10.1145/3318464.3389769(2011-2026)Online publication date: 11-Jun-2020
https://dl.acm.org/doi/10.1145/3318464.3389769
Show More Cited By

View Options

Get Access

Login options

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

Cited By

Index Terms

Recommendations

Of snowstorms and bushy trees

Rapid bushy join-order optimization with Cartesian products

A new join algorithm