Effective and robust pruning for top-down join enumeration algorithms
Fender P, Moerkotte G, Neumann T, Leis V (2012)
Publication Type: Conference contribution
Publication year: 2012
Pages Range: 414-425
Conference Proceedings Title: Proceedings - International Conference on Data Engineering
DOI: 10.1109/ICDE.2012.27
Abstract
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. © 2012 IEEE.
Authors with CRIS profile
Involved external institutions
Germany (DE)How to cite
APA:
Fender, P., Moerkotte, G., Neumann, T., & Leis, V. (2012). Effective and robust pruning for top-down join enumeration algorithms. In Proceedings - International Conference on Data Engineering (pp. 414-425).
MLA:
Fender, Pit, et al. "Effective and robust pruning for top-down join enumeration algorithms." Proceedings of the IEEE 28th International Conference on Data Engineering, ICDE 2012 2012. 414-425.
BibTeX: Download