SQL多表连接查询优化的相关研究..ppt

多表连接查询优化的相关研究 吕 彬 2009.3.5 motivation Agenda Multi-table join overview Heuristic and randomized optimization for the join ordering problem Michael Steinbrunn，et al, The VLDB Journal (1997) 6: 191–208 Attribute correlation detection BHUNT: Automatic Discovery of Fuzzy Algebraic Constraints in Relational Data Paul G. Brown Peter J. Haas , Proceedings of the 29th VLDB Conference, 2003 CORDS: Automatic Discovery of Correlations and Soft Functional Dependencies Ihab F. Ilyas，Volker Markl, et al, SIGMOD 2004, June 13–18, 2004, COCA: More Accurate Multidimensional Histograms out of More Accurate Correlations Detection CAO Wei1, QIN Xiongpai, WANG Shan,WAIM2008 Star join Star Gazing from atop your DB2 z/OS Database Server Terry Purcell, et al, Intelligent Optimizer Star join revisited: Performance internals for cluster architectures Josep Aguilar-Saborit, Data Knowledge Engineering 63 (2007) 995–1013 Heuristic and randomized optimization for the join ordering problem Choosing join type based on cost Solution space for the join ordering problem Join ordering strategies Quantitative analysis Conclusion Choosing join type based on cost Cost models Nested loop join Sort-merge join Hash join Solution space for the join ordering problem Left-deep trees n! ways to allocate n base relations to the tree’s leaves good solutions because of exploiting the cost-reducing pipelining technique Bushy trees an adaptable plan enumeration strategy linear graphs (n3 ? n)/6 star graphs (n?1) 2n?2 Join ordering strategies Deterministic algorithms heuristic or exhaustive search Randomized algorithms Define a set of moves which constitute edges between the different solutions of the solution space performs a random walk along the edges according to certain rules, terminating as soon as no more applicable moves exist or a time limit is exceeded Genetic algorithms make use of a randomized search strategy very similar to biological evolution Hybrid algorithms combine the str