Guido Moerkotte
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.
- {1} T. Cormen, C. Leiserson, R. Rivest, and C. Stein. Introduction to Algorithms. MIT Press, 2001. 2nd Edition. Google Scholar
Digital Library
- {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} 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. Google ScholarDigital Library
- {4} G. Moerkotte. Dp-counter analytics. Technical Report 2, University of Mannheim, 2006.Google Scholar
- {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. Google ScholarDigital Library
- {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} 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. Google ScholarDigital Library
- {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} B. Vance. Join-order Optimization with Cartesian Products. PhD thesis, Oregon Graduate Institute of Science and Technology, 1998. Google ScholarDigital Library
- {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. Google ScholarDigital Library
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