hash join 原理和算法
需积分: 50 58 浏览量
2011-03-21
16:21:18
上传
评论
收藏 50KB DOC 举报
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 分
割成多个不相连的分区（分别记作 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)。这样产生十个分区，如下表。
资源评论
