资源描述：
《oraclehashjoin算法原理》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、Hashjoin算法原理自从oracke7.3以来，oracle提供了一种新的join技术，就是hashjoin。HashJoin只能用于相等连接（equijoin），且只能在CBO优化器模式下。相对于nestedloopjoin，hashjoin更适合处理大型结果集。Hashjoin不需要在驱动表上存在索引。一．HashJoin概述Hashjoin算法的一个基本思想就是根据小的rowsources(称作buildinput，我们记较小的表为S，较大的表为B)建立一个可以存在于hasharea内存中的hashtable，然后用大的rowsources(称作probeinpu
2、t)来探测前面所建的hashtable。如果hasharea内存不够大，hashtable就无法完全存放在hasharea内存中。针对这种情况，Oracle在连接键利用一个hash函数将buildinput和probeinput分割成多个不相连的分区--bucket（分别记作Si和Bi），这个阶段叫做分区阶段；然后各自相应的分区，即Si和Bi再做Hashjoin，这个阶段叫做join阶段。如果在分区后，针对某个分区所建的hashtable还是太大的话，oracle就采用nested-loopshashjoin。所谓nested-loopshashjoin就是对部分Si建立h
3、ashtable，然后读取所有的Bi与所建的hashtable做连接，然后再对剩余的Si建立hashtable，再将所有的Bi与所建的hashtable做连接，直至所有的Si都连接完了。HashJoin算法有一个限制，就是假设两张表在连接键上是均匀分布的，也就是说每个分区拥有差不多的数据。但是实际当中数据都是不均匀的，为了很好地解决这个问题，oracle引进了几种技术，位图向量过滤、角色互换、柱状图，这些术语的具体意义会在后面详细介绍。二．HashJoin原理我们用一个例子来解释HashJoin算法的原理，以及上述所提到的术语。考虑以下两个数据集。S={1,1,1,3,3,
4、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}HashJoin的第一步就是判定小表（即buildinput）是否能完全存放在hasharea内存中。如果能完全存放在内存中，则在内存中建立hashtable，这是最简单的hashjoin。如果不能全部存放在内存中，则buildinput必须分区。分区的个数叫做fan-out。Fan-out是由hash_area_size和clustersize来决定的。其中clustersize=db_block_size*hash_multiblock_
5、io_count，hash_multiblock_io_count在oracle9i中是隐含参数。这里需要注意的是fan-out并不是buildinput的大小/hash_area_size，也就是说oracle决定的分区大小有可能还是不能完全存放在hasharea内存中。大的fan-out导致许多小的分区，影响性能，而小的fan-out导致少数的大的分区，以至于每个分区不能全部存放在内存中，这也影响hashjoin的性能。Oracle采用一个内部hash函数作用于连接键上，将S和B分割成多个分区，在这里我们假设这个hash函数为求余函数，即Mod(join_column_
6、value,10)。这样产生十个分区，如下表。分区B0B1B2B3B4B5B6B7B8B9值0,0,10,101,1,1,1,112,2,2,2,2,23NULLNULLNULLNULL89,9,9S010√S11,1,1√S2NullS33,3√S44,4,4,4S55S6NULLS7NULLS88,8,8,8√S9NULL经过这样的分区之后，只需要相应的分区之间做join即可（也就是所谓的partitionpairs），如果有一个分区为NULL的话，则相应的分区join即可忽略。在将S表读入内存分区时，oracle即记录连接键的唯一值，构建成所谓的位图向量，它需要占ha
7、sharea内存的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将比较两个分区，选取小的那个做buildinput，就是动态角色互换，这个动态角色互换发生在除第一对分区以外的分区上面。一．HashJoin算法第1步：判定小表是否能够全部存放
