weitom1982

 

 

自从 oracke 7.3 以来， oracle 提供了一种新的 join 技术，就是 hash join 。 Hash Join 只能用于相等连接，且只能在 CBO 优化器模式下。相对于 nested loop join ， hash join 更适合处理大型结果集。 Hash join 不需要在驱动表上存在索引。

 

一．       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) ，将连接键值映射至某个分区，同时采用 hash_fun_2 函数对连接键值产生另外一个 hash 值，这个 hash 值用于创建 hash table 用，并且与连接键值存放在一起。

第 4 步：对 build input 建立位图向量。

第 5 步：如果内存中没有空间了，则将分区写至磁盘上。

第 6 步：读取小表 S 的剩余部分，重复第三步，直至小表 S 全部读完。

 

第 7 步：将分区按大小排序，选取几个分区建立 hash table( 这里选取分区的原则是使选取的数量最多 ) 。

 

第 8 步：根据前面用 hash_fun_2 函数计算好的 hash 值，建立 hash table 。

第 9 步：读取表 B ，采用位图向量进行位图向量过滤。

第 10 步：对通过过滤的数据采用 hash_fun_1 函数将数据映射到相应的分区中去，并计算 hash_fun_2 的 hash 值。

第 11 步：如果所落的分区在内存中，则将前面通过 hash_fun_2 函数计算所得的 hash 值与内存中已存在的 hash table 做连接， 将结果写致磁盘上。如果所落的分区不在内存中，则将相应的值与表 S 相应的分区放在一起。

第 12 步：继续读取表 B ，重复第 9 步，直至表 B 读取完毕。

 

第 13 步：读取相应的 (Si,Bi) 做 hash 连接。在这里会发生动态角色互换。

第 14 步：如果分区过后，最小的分区也比内存大，则发生 nested- loop hash join 。

四．       Hash Join 的成本

1.      In-Memory Hash Join

Cost(HJ)=Read(S)+ build hash table in memory(CPU)+Read(B) +

        Perform In memory Join(CPU)

忽略 cpu 的时间，则

Cost(HJ)=Read(S)+Read(B)

2.      On-Disk Hash Join

根据上述的步骤描述，我们可以看出

Cost(HJ)=Cost(HJ1)+Cost(HJ2)

其中 Cost(HJ1) 的成本就是扫描 S,B 表，并将无法放在内存上的部分写回磁盘，对应前面第 2 步至第 12 步。 Cost(HJ2) 即为做 nested-loop hash join 的成本，对应前面的第 13 步至第 14 步。

 

其中 Cost(HJ1) 近似等于 Read(S)+Read(B)+Write((S-M)+(B-B*M/S)) 。

 

因为在做 nested-loop hash join 时，对每一 chunk 的 build input ，都需要读取整个 probe input ，因此

Cost(HJ2) 近似等于 Read((S-M)+n*(B-B*M/S))

其中 n 是 nested-loop hash join 需要循环的次数。

n=(S/F)/M

一般情况下，如果 n 在于 10 的话， hash join 的性能将大大下降。从 n 的计算公式可以看出， n 与 Fan-out 成反比例，提高 fan-out ，可以降低 n 。当 hash_area_size 是固定时，可以降低 cluster size 来提高 fan-out 。

 

从这里我们可以看出，提高 hash_multiblock_io_count 参数的值并不一定提高 hash join 的性能。

五．       其它

1． 确认小表是驱动表

2． 确认涉及到的表和连接键分析过了。

3． 如果在连接键上数据不均匀的话，建议做柱状图。

4． 如果可以，调大 hash_area_size 的大小或 pga_aggregate_target 的值。

5． Hash Join 适合于小表与大表连接、返回大型结果集的连接。