一种分布式数据库查询优化算法

Ｃｈｅｎ和Ｙｕ提出了一种新的等联接操作结果估算模型，借助于它来估算ｊｏｉｎ缩减器带来的收益。本文在此基础上分析了收益之和与ｊｏｉｎ缩减器执行次序的关系，提出了复杂度为Ｏ（ｎ＾２）的优化算法。该算法除考虑采用局部收益最大的ｊｏｉｎ操作做为首选操作外，还考虑了算法产生的操作序列在一定的条件下具有全局上的优化特征：任意两个相邻ｊｏｉｎ操作构成的子序列是最优的。

AN ALGORITHM FOR OPTIMIZATION OF DISTRIBUTED QUERIES

Based on the estimation model of intermediate relation cardinality of, Chen and Yu, this paper analyzes the relationship between the executing orders of join reducers and gain sums under some assumptions, and presents an optimization algorithm of O(n2). The algorithm, in the course of determining a join reducer sequence, not only considers that the joins with greatest gains must be selected firstly,but also takes it into account that the join reducer sequence determined by the algorithm has following global optimization property: in the sequence, the arbitrary subsequence of two neighboring join reducers is optimum.