《oraclehashjoin算法原理》由会员分享，可在线阅读，更多相关《oraclehashjoin算法原理（4页珍藏版）》请在金锄头文库上搜索。
1、Hash join算法原理自从oracke 7.3以来，oracle提供了一种新的join技术，就是hash join。Hash Join只能用于相等连接（equijoin），且只能在CBO优化器模式下。相对于nested loop join，hash join更适合处理大型结果集。Hash join不需要在驱动表上存在索引。一 Hash Join概述Hash join算法的一个基本思想就是根据小的row sources(称作build input，我们记较小的表为S，较大的表为B) 建立一个可以存在于hash area内存中的hash table，然后用大的row sources(称作pro
2、be input) 来探测前面所建的hash table。如果hash area内存不够大，hash table就无法完全存放在hash area内存中。针对这种情况，Oracle在连接键利用一个hash函数将build input和probe input分割成多个不相连的分区-bucket（分别记作Si和Bi），这个阶段叫做分区阶段；然后各自相应的分区，即Si和Bi再做Hash join，这个阶段叫做join阶段。如果在分区后，针对某个分区所建的hash table还是太大的话，oracle就采用nested-loops hash join。所谓nested-loops hash join就
3、是对部分Si建立hash table，然后读取所有的Bi与所建的hash table做连接，然后再对剩余的Si建立hash table，再将所有的Bi与所建的hash table做连接，直至所有的Si都连接完了。Hash Join算法有一个限制，就是假设两张表在连接键上是均匀分布的，也就是说每个分区拥有差不多的数据。但是实际当中数据都是不均匀的，为了很好地解决这个问题，oracle引进了几种技术，位图向量过滤、角色互换、柱状图，这些术语的具体意义会在后面详细介绍。二 Hash Join原理我们用一个例子来解释Hash Join算法的原理，以及上述所提到的术语。考虑以下两个数据集。S=1,1,1
4、,3,3,4,4,4,4,5,8,8,8,8,10B=0,0,1,1,1,1,2,2,2,2,2,2,3,8,9,9,9,10,10,11Hash 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_multibl
5、ock_io_count， hash_multiblock_io_count在oracle9i中是隐含参数。这里需要注意的是fan-out并不是build input的大小/hash_area_size， 也就是说oracle决定的分区大小有可能还是不能完全存放在hash area内存中。大的fan-out导致许多小的分区，影响性能，而小的fan-out导致少数的大的分区，以至于每个分区不能全部存放在内存中，这也影响hash join的性能。Oracle采用一个内部hash函数作用于连接键上，将S和B分割成多个分区，在这里我们假设这个hash函数为求余函数，即Mod(join_column_v
6、alue,10)。这样产生十个分区，如下表。分区B0B1B2B3B4B5B6B7B8B9值0,0,10,101,1,1,1,112,2,2,2,2,23NULLNULLNULLNULL89,9,9S010S11,1,1S2NullS33,3S44,4,4,4S55S6NULLS7NULLS88,8,8,8S9NULL经过这样的分区之后，只需要相应的分区之间做join即可（也就是所谓的partition pairs），如果有一个分区为NULL的话，则相应的分区join即可忽略。在将S表读入内存分区时，oracle即记录连接键的唯一值，构建成所谓的位图向量，它需要占hash area内存的5%左右
7、。在这里即为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-ou
8、t数。(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步：
9、如果内存中没有空间了，则将分区写至磁盘上。第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做连接，
10、 将结果写至磁盘上。如果所落的分区不在内存中，则将相应的值与表S相应的分区放在一起。第12步：继续读取表B，重复第9步，直至表B读取完毕。第13步：读取相应的(Si,Bi)做hash连接。在这里会发生动态角色互换。第14步：如果分区过后，最小的分区也比内存大，则发生nested- loop hash join。四 Hash Join的成本1. In-Memory Hash JoinCost(HJ)=Read(S)+ build hash table in memory(CPU)+Read(B) + Perform In memory Join(CPU)忽略cpu的时间，则Cost(HJ)=Re
11、ad(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
12、，因此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适合于小表与大表连接、返回大型结果集的连接。
