oracle表连接-hashjoin哈希连接 - 数据库编程

一. hash 连接(哈希连接)原理

指的是两个表连接时, 先利用两表中记录较少的表在内存中建立 hash 表, 然后扫描记录较多的表并探测 hash 表, 找出与 hash 表相匹配的行来得到结果集的表连接方法. 哈希连接只能用于等值连接条件(=)。

假设下面的 sql 语句中表 T1 和 T2 的连接方式是哈希连接, T1 是驱动表

select *
from T1, T2
where T1.id = T2.id and T1.name = 'David';

oracle 执行步骤如下:

1 计算 hash partition 的数量 (分区数量)

这个数字由 hash_area_size, db_block_size, _hash_multiblock_io_count 的值来决定

hash partition 是一个逻辑上的概念, 它由多个 hash bucket 组成, 而一个 hash table 又由多个 hash partition 组成. hash partition 是 I/O 单位, 当 hash table 过大时, 以 hash partition 为单位写出到磁盘; hash bucket 是 hash 运算映射的单位, 可以把 hash bucket 想象为一个链表.

2 构建驱动结果集 S 的 hash table

2.1 遍历驱动结果集, 计算 hash 值

根据谓词条件(T1.name = 'David') 过滤驱动表 T1 的数据, 得到驱动结果集 S. 读取 S 中的每一条数据, 并根据连接列(T1.id)做 hash 运算.

oracle 采用两种 hash 算法进行计算, S 中的每一条记录都会得到两个哈希值记为 hash_value_1, hash_value_2.

2.2 存储数据到 hash partition

oracle 按照 hash_value_1 的值把驱动结果集 S 的记录映射存储在不同的 hash partition 中不同 hash bucket 里, 存储在 hash bucket 中的内容包括 sql 中的查询列, 连接列以及 hash_value_2 的值.

我们把驱动结果集 S 所对应的每一个 hash partition 记为 S[i].

2.3 构建位图

这个位图用来标记 S[i] 所包含的每一个 hash bucket 是否有记录

2.4 如果驱动结果集 S 数据量很大, 则将数据交换到磁盘上(temp 表空间)

如果驱动结果集 S 的数据量很大, 构建 S 对应的 hash table 时就会造成 PGA中的 hash_area_szie 被填满, 这时候 oracle 会把 hash area 中记录数最多的 hash partition 写到磁盘上. 重复步骤 2.1 - 2.4 直至读取数据完毕.

另外, 在构建 S 对应的 hash table 时, 如果记录对应的 hash partition 已经被写到磁盘上, oracle 就会将 sql 中的查询列, 连接列以及hash_value_2 的值写到已经位于磁盘上的 hash partition 中不同 hash bucket 里.

2.5 排序

对驱动结果集 S 的 hash partition 根据记录数多少进行排序

3 遍历被驱动结果集 B

3.1 遍历驱动结果集 B 及位图过滤

把被驱动结果集 (T2) 记为 B, 读取 B 中的每一条记录, 并按照连接列(T2.id)做 hash 运算, 同步骤 (2) 一样得到两个哈希值 hash_value_1, hash_value_2. oracle 根据这个 hash_value_1 去 S[i] 匹配 hash bucket,

如果能够找到匹配的 bucket, 则进一步比较连接列是否相等, 如果相等, 则将记录 join 后返回; 如果不相等, 则舍弃; 如果找不到匹配的 bucket, 就会去访问 2.3 中构建的位图, (1) 如果位图显示该 hash bucket 在 S[i] 中对应的记录数大于 0, 则说明该 hash bucket 虽然不在内存中, 但实际上是被写到了磁盘上, 此时 oracle 会按照 hash_value_1 的值把被驱动结果集 B 的记录映射存储在磁盘上一个新的 hash partition 中的 hash bucket, 存储在 hash bucket 中的内容包括 sql 中的关于 B 的查询列, 连接列以及 hash_value_2 的值; (2) 如果位图显示该 hash bucket 在 S[i] 中对应的记录数等于 0, 则说明这条记录不符合连接连接需舍弃.

【这个位图决定是否将 hash_value_1 所对应 B 中的记录写回到磁盘的动作就是所谓的位图过滤】

我们将 B 所对应的每一个 hash partition 记为 B[j]。遍历完 B 中的所有记录, 构建 B[j] 完毕.

3.2 再次构建 hash table

现在 oracle 已经处理完成内存中的 S[i] 和 B[j], 只剩下磁盘上的 S[i] 和 B[j] 还未处理.

由于构建 S[i] 和 B[j] 使用的相同的 hash 函数, 只有对应 hash partition number 相同的 S[i] 和 B[j] 才有可能满足连接条件, 所以处理磁盘上的 S[i] 和 B[j] 只需处理 hash partition number 相同的 S[i] 和 B[j].

对于每一对相同 hash partition number 的 S[i] 和 B[j], oracle 会选择记录数较少的当作驱动结果集, 同时根据 hash bucket 中 hash_value_2 构建新的 hash table, 记录数较多的当作被驱动结果集根据 hash_value_2 去匹配, 如果匹配成功, 则返回记录, 匹配不成功则丢弃.

【对于每一对相同 hash partition number 的 S[i] 和 B[j], oracle 会选择记录数较少的当作驱动结果集, 所以每一对相同 hash partition number 的 S[i] 和 B[j] 的驱动结果集都可能发生变化, 这就是动态角色互换】

处理完每一对相同 hash partition number 的 S[i] 和 B[j] 后, 哈希连接处理完成.

二. hash 连接特性

1. hash 连接只能用在等值连接条件

2. 驱动表的选择对执行效率及性能有影响

3. 驱动表和被驱动表最多被访问一次

构造测试数据

SQL> CREATE TABLE t1 (
  2    id NUMBER NOT NULL,
  3    n NUMBER,
  4    pad VARCHAR2(4000),
  5    CONSTRAINT t1_pk PRIMARY KEY(id)
  6  );

Table created.

SQL> CREATE TABLE t2 (
  2    id NUMBER NOT NULL,
  3    t1_id NUMBER NOT NULL,
  4    n NUMBER,
  5    pad VARCHAR2(4000),
  6    CONSTRAINT t2_pk PRIMARY KEY(id),
  7    CONSTRAINT t2_t1_fk FOREIGN KEY (t1_id) REFERENCES t1
  8  );

Table created.

SQL> CREATE TABLE t3 (
  2    id NUMBER NOT NULL,
  3    t2_id NUMBER NOT NULL,
  4    n NUMBER,
  5    pad VARCHAR2(4000),
  6    CONSTRAINT t3_pk PRIMARY KEY(id),
  7    CONSTRAINT t3_t2_fk FOREIGN KEY (t2_id) REFERENCES t2
  8  );

Table created.
SQL> CREATE TABLE t4 (
  2    id NUMBER NOT NULL,
  3    t3_id

oracle表连接-hashjoin哈希连接(一)