ITPub博客

首页 > 应用开发 > IT综合 > Hash join算法原理

Hash join算法原理

原创 IT综合 作者:empo007 时间:2007-10-28 20:30:09 0 删除 编辑

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

[@more@]

一、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分割成多个不相连的分区(分别记作Si和Bi),这个阶段叫做分区阶段;然后各自相应的分区,即Si和Bi再做Hash join,这个阶段叫做join阶段。
如果在分区后,针对某个分区所建的hash table还是太大的话,oracle就采用nested-loops hash join。所谓的nested-loops hash join就是对部分Si建立hash table,然后读取所有的Bi与所建的hash table做连接,然后再对剩余的Si建立hash table,再将所有的Bi与所建的hash table做连接,直至所有的Si都连接完了。
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步。
第2步:决定fan-out数。
(Number of Partitions) * C<= Favm *M
其中C为Cluster size,
其值为DB_BLOCK_SIZE*HASH_MULTIBLOCK_IO_COUNT;Favm为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适合于小表与大表连接、返回大型结果集的连接。

来自 “ ITPUB博客 ” ,链接:http://blog.itpub.net/85922/viewspace-979145/,如需转载,请注明出处,否则将追究法律责任。

请登录后发表评论 登录
全部评论
  • 博文量
    126
  • 访问量
    1078784