参考http://www.cnitblog.com/weitom1982/archive/2006/03/31/8378.html
一. 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 步:决定 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) ,将连接键值映射至某个分区,同时采用 <span styl
分享到:
相关推荐
Hash join算法的一个基本思想就是根据小的row sources(称作build input,我们记较小的表为S,较大的表为B) 建立一个可以存在于hash area内存中的hash table,然后用大的row sources(称作probe input) 来探测前面所建...
hash join 原理和算法 1.Hash Join概述 2.Hash Join原理 3.Hash Join算法 4.Hash Join的成本
oracle hash join算法原理
Hash join算法原理 详细讲述了oracle sql语句的连接方式 对于sql调优提高有很大帮助
NULL 博文链接:https://juji1010.iteye.com/blog/1535638
Oracle中hash join研究.pdf
其中最引人注目的莫过于多表连接查询支持 hash join 方式了。我们先来看看官方的描述: MySQL 实现了用于内连接查询的 hash join 方式。例如,从 MySQL 8.0.18 开始以下查询可以使用 hash join 进行连接查询: ...
在MySQL 8.0.18中,增加了Hash Join新功能,它适用于未创建索引的字段,做等值关联查询。在之前的版本里,如果连接的字段没有创建索引,查询速度会是非常慢的,优化器会采用BNL(块嵌套)算法。 Hash Join算法是把...
数据库 我自己在 Java 中实现了 SortMergeJoin 和 HashJoin(来自 SQL 的著名 INNER JOIN)。 在更多信息。
Oracle CBO 学习笔记之(1) : 深入理解Oracle Hash Join的代价模型及其执行流程:word,pdf,图例
给大家介绍Mysql 8.0.18 hash join测试的相关知识,本文通过实例代码讲解,非常不错,具有一定的参考借鉴价值,需要的朋友参考下吧
1. 生成Hash Table:将参与join的左表生成Hash Table 3. FILTER处理:按照不等值条件进行过滤,进而输出最终结果 1. 对语法树生
第一次作业
1. 词法语法解析层 2. 逻辑计划层 3. 物理计划层 4. 物理操作符 1. 将左表的所有数据发送到一台MergerServer上,其中既包括ChunkSe
1、 测试概述 2、 实验环境 3、 实验测试观点说明 4、 实验结果
MySQL 8.0.18 稳定版(GA)已于昨日正式发布,Hash Join 也如期而至。 快速浏览一下这个版本的亮点! 1.Hash Join Hash Join 不需要任何索引来执行,并且在大多数情况下比当前的块嵌套循环算法更有效。 2.EXPLAIN ...