Bennet Vance
Abstract
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 affecting plan quality. However, we show that searching the complete space of plans is more affordable than has been previously recognized, and that the common exclusions may be of little benefit.We start by presenting a Cartesian product optimizer that requires at most a few seconds of workstation time to search the space of bushy plans for products of up to 15 relations. Building on this result, we present a join-order optimizer that achieves a similar level of performance, and retains the ability to include Cartesian products in subplans wherever appropriate. The main contribution of the paper is in fully separating join-order enumeration from predicate analysis, and in showing that the former problem in particular can be solved swiftly by novel implementation techniques. A secondary contribution is to initiate a systematic approach to the benchmarking of join-order optimization, which we apply to the evaluation of our method.
- CM95 Sophie Cluet and Guido Moerkotte. On the complexity of generating optimal left-deep processing trees with cross products. In Proceedings of the 5th Internatwnal Conference on Database Theory, volume 893 of Lecture Notes zn Computer Science, pages 54-67, Prague, Czech Republic, January 1995. Springer-Verlag. Google Scholar
Digital Library
- GLPK94 C@sar Galindo-Legaria, Arian Pellenkoft, and Martin Kersten. Fast, randomized join-order selection--why use transformations? In Proceedings of the 20th International Conference on Very Large Data Bases, pages 85-95, Santiago, Chile, September 1994. Morgan Kaufmann. Google ScholarDigital Library
- GM93 Goetz Graefe and William J. McKenna. The Volcano optimizer generator: Extensibility and efficient search. In Proceedings of the IEEE Conference on Data Engmeemng, pages 209-218, Vienna, Austria, April 1993. Google ScholarDigital Library
- HS93 J oseph M. Hellerstein and Michael Stonebraker. Predicate migration: Optimizing queries with expensive predicates. In Proceedings of the 1993 A CM SIGMOD International Conference on Management of Data, pages 267-276, Washington, DC, May 1993. Google ScholarDigital Library
- IK84 Toshihide Ibaraki and Tiko Kameda. On the optimal nesting order for computing N-relational joins. A CM Transactions on Database Systems, 9(3):482-502, September 1984. Google ScholarDigital Library
- IK91 Yannis E. Ioannidis and Younkyung Cha Kang. Left-deep vs. bushy trees: An analysis of strategy spaces and its implications for query optimization. In Proceedings of the 1991 A CM SIG- MOD InternatzonaI Conference on Management of Data, pages 168-177, Denver, Colorado, June 1991. Google ScholarDigital Library
- Knu73 Donald E. Knuth. Fundamental Algorithms, volume 1 of The Art o/ Computer Programming. Addison-Wesley, second edition, 1973.Google Scholar
- MO O. Martin and S. Otto. Combining simulated annealing with local search heuristics. To appear as a chapter of Metaheumst~cs in Combinatorial Optim~zatzon, volume 60 in the series Annals of Operations Research, edited by G. Laporte and I. Osman.Google Scholar
- OL90 Kiyoshi Ono and Guy M. Lohman. Measuring the complexity of join enumeration in query optimization. In Proceedings of the 16th International Conference on Very Large Data Bases, pages 314-325, Brisbane, Australia, August 1990. Google ScholarDigital Library
- SAC+79 P. Griffiths Selinger, M. M. Astrahan, D. D. Chamberlin, R. A. Lorie, and T. G. Price. Access path selection in a relational database management system. In Proceedings of the A CM-SIGMOD 1979 International Conference on Management of Data, pages 23-34, Boston, Massachusetts, May 1979. Google ScholarDigital Library
- SMK93 Michael Steinbrunn, Guido Moerkotte, and A1- fons Kemper. Optimizing join orders. Technical Report MIP-9307, Universit~t Passau, 1993.Google Scholar
- Ste96 M. Steinbrunn. Heuristic and Randomised Opt~misat~on Techniques in Object-Omented Database Systems. infix-Verlag, Ringstrafle 32, 53757 St. Augustin, Germany, 1996. Dissertation, Universit~t Passau.Google Scholar
Index Terms
- Rapid bushy join-order optimization with Cartesian products
Recommendations
Rapid bushy join-order optimization with Cartesian products
SIGMOD '96: Proceedings of the 1996 ACM SIGMOD international conference on Management of dataQuery 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 ...
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 ...
Comments