hash join

参考http://www.cnitblog.com/weitom1982/archive/2006/03/31/8378.html

 

一．       Hash Join 概述

Hash join 算法的一个基本思想就是根据小的 row sources( 称作 build input ，我们记较小的表为 S ，较大的表为 B) 建立一个可以存在于 hash area 内存中的 hash table ，然后用大的 row sources( 称作 probe input) 来探测前面所建的 hash table 。如果 hash area 内存不够大， hash table 就无法完全存放在 hash area 内存中。针对这种情况， Oracle 在连接键利用一个 hash 函数将 build input 和 probe input 分割成多个不相连的分区（分别记作 S_i 和 B_i ），这个阶段叫做分区阶段；然后各自相应的分区，即 S_i 和 B_i 再做 Hash join ，这个阶段叫做 join 阶段。

如果在分区后，针对某个分区所建的 hash table 还是太大的话， oracle 就采用 nested-loops hash join 。所谓的 nested-loops hash join 就是对部分 S_i 建立 hash table ，然后读取所有的 B_i 与所建的 hash table 做连接，然后再对剩余的 S_i 建立 hash table ，再将所有的 B_i 与所建的 hash table 做连接，直至所有的 S_i 都连接完了。

Hash Join 算法有一个限制，就是它是在假设两张表在连接键上是均匀的，也就是说每个分区拥有差不多的数据。但是实际当中数据都是不均匀的，为了很好地解决这个问题， oracle 引进了几种技术，位图向量过滤、角色互换、柱状图，这些术语的具体意义会在后面详细介绍。

 

二．       Hash Join 原理

我们用一个例子来解释 Hash Join 算法的原理，以及上述所提到的术语。

考虑以下两个数据集。

S={1,1,1,3,3,4,4,4,4,5,8,8,8,8,10}

B={0,0,1,1,1,1,2,2,2,2,2,2,3,8,9,9,9,10,10,11}

Hash Join 的第一步就是判定小表（即 build input ）是否能完全存放在 hash area 内存中。如果能完全存放在内存中，则在内存中建立 hash table ，这是最简单的 hash join 。

如果不能全部存放在内存中，则 build input 必须分区。分区的个数叫做 fan-out 。 Fan-out 是由 hash_area_size 和 cluster size 来决定的。其中 cluster size 等于 db_block_size * hash_multiblock_io_count ， hash_multiblock_io_count 在 oracle9i 中是隐含参数。这里需要注意的是 fan-out 并不是 build input 的大小 /hash_ara_size ，也就是说 oracle 决定的分区大小有可能还是不能完全存放在 hash area 内存中。大的 fan-out 导致许多小的分区，影响性能，而小的 fan-out 导致少数的大的分区，以至于每个分区不能全部存放在内存中，这也影响 hash join 的性能。

Oracle 采用内部一个 hash 函数作用于连接键上，将 S 和 B 分割成多个分区，在这里我们假设这个 hash 函数为求余函数，即 Mod(join_column_value,10) 。这样产生十个分区，如下表。

 

 

 

分区		B0	B1	B2	B3	B4	B5	B6	B7	B8	B9
值	0,0,10,10	1,1,1,1,11	2,2,2,2,2,2	3	NULL	NULL	NULL	NULL	8	9,9,9
S0	10	√
S1	1,1,1		√
S2	Null
S3	3,3				√
S4	4,4,4,4
S5	5
S6	NULL
S7	NULL
S8	8,8,8,8									√
S9	NULL

经过这样的分区之后，只需要相应的分区之间做 join 即可（也就是所谓的 partition pairs ），如果有一个分区为 NULL 的话，则相应的分区 join 即可忽略。

在将 S 表读入内存分区时， oracle 即记录连接键的唯一值，构建成所谓的位图向量，它需要占 hash area 内存的 5% 左右。在这里即为 {1,3,4,5,8,10} 。

当对 B 表进行分区时，将每一个连接键上的值与位图向量相比较，如果不在其中，则将其记录丢弃。在我们这个例子中， B 表中以下数据将被丢弃

{0,0,2,2,2,2,2,2,9,9,9,9,9} 。这个过程就是位图向量过滤。

当 S1,B1 做完连接后，接着对 Si,Bi 进行连接，这里 oracle 将比较两个分区，选取小的那个做 build input ，就是动态角色互换，这个动态角色互换发生在除第一对分区以外的分区上面。

 

三．       Hash Join 算法

第 1 步：判定小表是否能够全部存放在 hash area 内存中，如果可以，则做内存 hash join 。如果不行，转第二步。

第 2 步：决定 fan-out 数。

       (Number of Partitions) * C<= F_avm *M

        其中 C 为 Cluster size ，

其值为 DB_BLOCK_SIZE*HASH_MULTIBLOCK_IO_COUNT ； F_avm 为 hash area 内存可以使用的百分比，一般为 0.8 左右； M 为 Hash_area_size 的大小。

 

第 3 步：读取部分小表 S ，采用内部 hash 函数 ( 这里称为 hash_fun_1) ，将连接键值映射至某个分区，同时采用 <span styl