Oracle的Hash Join之探究整理
Hash join算法原理

自从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分割成多个不相连的分区（分别记作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                         &nb