浅谈查询优化器中的JOIN算法

核心提示： 值得注意的是，Hash Join与上述两种算法之间的较大区别同时也是一个较大限制是它只能应用于等值联结(equality join)，浅谈查询优化器中的JOIN算法(3)，这主要是由于哈希函数及其桶的确定性及无序性所导致的，算法：基本的Hash Join算法由以下两步组成：(1) Buil

值得注意的是，Hash Join与上述两种算法之间的较大区别同时也是一个较大限制是它只能应用于等值联结(equality join)，这主要是由于哈希函数及其桶的确定性及无序性所导致的。

算法：

基本的Hash Join算法由以下两步组成：

(1) Build Input Phase： 基于JOIN字段，使用哈希函数h2为较小的S集合构建内存中(in-memory)的哈希表，相同键值的以linked list组成一个桶(bucket)

(2) Probe Input Phase： 在较大的R集合上对哈希表进行核对以完成联结。其中核对操作包括：

　　foreachtuplerÎRdo
　　hashonthejoiningattributeusingthehashfunctionofstep1tofindabucketinthehashtable
　　ifthebucketisnonempty
　　foreachtuplesinthefoundbucket
　　ifri==sjthenaddtoresult

代价：

值得注意的是对于大集合R的每个元组 r ，hash bucket中对应 r 的那个bucket中的每个元组都需要与 r 进行比较，这也是算法最耗时的地方所在。

CPU开销是O (m + n * b) b是每个bucket的平均元组数量。

使用小结：

一般来说，查询优化器会首先考虑Nested Loop和Sort-Merge，但如果两个集合量都不小且没有合适的索引时，才会考虑使用Hash Join。

Hash Join也用于许多集合比较操作，inner join、left/right/full outer join、intersect、difference等等，当然了，需要保证都是等值联结。

另外，Hash Join的变种能够移除重复和进行分组，它只使用一个输入，兼做Build和Probe的角色。

其实产品级的优化器一般都改进了这些基本算法，而改进过的版本的确有较大的性能提升。在这里只是给需要判断执行计划优劣或者研究查询优化器实现的兄弟提供原理方面的介绍，在实际应用中我们还得结合丰富的statistics作出准确的判断。