Effective and Robust Pruning for Top-Down Join Enumeration Algorithms
2012
Finding the optimal execution order of join operations is a crucial task of today's cost-based query optimizers. There are two approaches to identify the best plan: bottom-up and top-down join enumeration. For both optimization strategies efficient algorithms have been published. However, only the top-down approach allows for branch-and-bound pruning. Two pruning techniques can be found in the literature. We add six new ones. Combined, they improve performance roughly by an average factor of 2 - 5. Even more important, our techniques improve the worst case by two orders of magnitude. Additionally, we introduce a new, very efficient, and easy to implement top-down join enumeration algorithm. This algorithm, together with our improved pruning techniques, yields a performance which is by an average factor of 6 - 9 higher than the performance of the original top-down enumeration algorithm with the original pruning methods.
Keywords:
- Branch and bound
- Heuristic (computer science)
- Killer heuristic
- Enumeration
- Pruning
- Robustness (computer science)
- Algorithm
- Machine learning
- Query optimization
- Computer science
- Artificial intelligence
- Pruning (decision trees)
- Upper and lower bounds
- enumeration algorithm
- Theoretical computer science
- Top-down and bottom-up design
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
16
References
17
Citations
NaN
KQI