崔华:Oracle 里的哈希连接原理解析

崔华,网名 dbsnake

Oracle ACE Director,ACOUG 核心专家

编辑手记:感谢崔华授权我们独家转载其精品文章,也欢迎大家向“Oracle”社区投稿。

哈希连接(HASH JOIN)是一种两个表在做表连接时主要依靠哈希运算来得到连接结果集的表连接方法。

在 Oracle 7.3之前,Oracle 数据库中的常用表连接方法就只有排序合并连接嵌套循环连接这两种,但这两种表连接方法都有其明显缺陷:

  1. 对于排序合并连接,如果两个表在施加了目标 SQL 中指定的谓词条件(如果有的话)后得到的结果集很大且需要排序的话,则这种情况下的排序合并连接的执行效率一定是很差的;
  2. 而对于嵌套循环连接,如果驱动表所对应的驱动结果集的记录数很大,即便在被驱动表的连接列上存在索引,此时使用嵌套循环连接的执行效率也同样会很差。

为了解决排序合并连接和嵌套循环连接在上述情形下执行效率不高的问题,同时也为了给优化器提供一种新的选择,Oracle 在 Oracle 7.3 中引入了哈希连接。从理论上来说,哈希连接的执行效率会比排序合并连接和嵌套循环连接的执行效率要高,当然,实际情况并不总是这样。

在 Oracle 10g 及其以后的 Oracle 数据库版本中,优化器(实际上是 CBO,因为哈希连接仅适用于 CBO)在解析目标 SQL 时是否考虑哈希连接是受限于隐含参数 _HASH_JOIN_ENABLED,而在 Oracle 10g 以前的 Oracle 数据库版本中,CBO 在解析目标 SQL 时是否考虑哈希连接是受限于参数 HASH_JOIN_ENABLED。

_HASH_JOIN_ENABLED 的默认值是 TRUE,表示允许 CBO 在解析目标 SQL时考虑哈希连接。当然,即使你将该参数的值改成了 FALSE,我们使用 USE_HASH Hint 依然可以让 CBO 在解析目标 SQL 时考虑哈希连接,这说明 USE_HASH Hint 的优先级高于参数 _HASH_JOIN_ENABLED

如果两个表(这里将它们分别命名为表 T1 和表 T2)在做表连接时使用的是哈希连接,则 Oracle 在做哈希连接时会依次顺序执行如下步骤:

  1. 首先 Oracle 会根据参数 HASH_AREA_SIZE、DB_BLOCK_SIZE 和_HASH_MULTIBLOCK_IO_COUNT 的值来决定 Hash Partition 的数量(Hash Partition 是一个逻辑上的概念,所有 Hash Partition 的集合就被称之为 Hash Table,即一个 Hash Table 是由多个 Hash Partition 所组成,而一个 Hash Partition 又是由多个 Hash Bucket 所组成);
  2. 表T1和T2在施加了目标 SQL 中指定的谓词条件(如果有的话)后,得到的结果集中数据量较小的会被 Oracle 选为哈希连接的驱动结果集,这里我们假设 T1 所对应的结果集的数据量相对较小,记为 S;T2 所对应的结果集的数据量相对较大,记为 B;显然这里 S 是驱动结果集,B 是被驱动结果集;
  3. 遍历 S,读取 S 中的每一条记录,并对 S 中的每一条记录按照该记录在表 T1 中的连接列做哈希运算,这个哈希运算会使用两个内置哈希函数,这两个哈希函数会同时对该连接列计算哈希值,把这两个内置哈希函数分别记为 hash_func_1 和 hash_func_2,计算的哈希值分别记为 hash_value_1 和 hash_value_2;
  4. 按照 hash_value_1 的值把相应的 S 中的对应记录存储在不同 Hash Partition 的不同 Hash Bucket 里,同时和该记录存储在一起的还有该记录用 hash_func_2 计算出来的 hash_value_2 的值。注意,存储在 Hash Bucket 里的记录并不是目标表的完整行记录,而是只需要存储位于目标 SQL 中的跟目标表相关的查询列和连接列就足够了;把 S 所对应的每一个 Hash Partition 记为 Si
  5. 在构建 Si 的同时,Oracle 会构建一个位图(BITMAP),这个位图用来标记 Si 所包含的每一个 Hash Bucket 是否有记录(即记录数是否大于0);
  6. 如果 S 的数据量很大,那么在构建 S 所对应的 Hash Table 时,就可能会出现 PGA 的工作区(WORK AREA)被填满的情况,这时候 Oracle 会把工作区中现有的 Hash Partition 中包含记录数最多的 Hash Partition 写到磁盘上(TEMP 表空间);接着 Oracle 会继续构建 S 所对应的 Hash Table,在继续构建的过程中,如果工作区又满了,则 Oracle 会继续重复上述挑选包含记录数最多的 Hash Partition 并写回到磁盘上的动作;如果要构建的记录所对应的 Hash Partition 已经事先被 Oracle 写回到了磁盘上,则此时 Oracle 就会去磁盘上更新该 Hash Partition,即会把该条记录和 hash_value_2 直接加到这个已经位于磁盘上的 Hash Partition 的相应 Hash Bucket 中;注意,极端情况下可能会出现只有某个 Hash Partition 的部分记录还在内存中,该 Hash Partition 的剩余部分和余下的所有 Hash Partition 都已经被写回到磁盘上
  7. 上述构建 S 所对应的 Hash Table 的过程会一直持续下去,直到遍历完 S 中的所有记录为止;
  8. 接着,Oracle 会对所有的 Si 按照它们所包含的记录数来排序,然后 Oracle 会把这些已经排好序的 Hash Partition 按顺序依次、并且尽可能的全部放到内存中(PGA 的工作区),当然,如果实在放不下的话,放不下的那部分 Hash Partition 还是会位于磁盘上。我认为这个按照 Si 的记录数来排序的动作不是必须要做的,因为这个排序动作的根本目的就是为了尽可能多的把那些记录数较小的 Hash Partition 保留在内存中,而将那些已经被写回到磁盘上、记录数较大且现有内存已经放不下的 Hash Partition 保留在磁盘上,显然,如果所有的 Si 本来就都在内存中,也没发生过将 Si 写回到磁盘的操作,那这里根本就不需要排序了
  9. 至此 Oracle 已经处理完 S,现在可以来开始处理 B 了;
  10. Oracle 会遍历 B,读取 B 中的每一条记录,并对 B 中的每一条记录按照该记录在表 T2 中的连接列做哈希运算,这个哈希运算和步骤3中的哈希运算是一模一样的,即这个哈希运算还是会用步骤3中的 hash_func_1 和 hash_func_2,并且也会计算出两个哈希值 hash_value_1 和hash_value_2;接着 Oracle 会按照该记录所对应的哈希值 hash_value_1 去 Si 里找匹配的 Hash Bucket;如果能找到匹配的 Hash Bucket,则 Oracle 还会遍历该 Hash Bucket 中的每一条记录,并会校验存储于该 Hash Bucket 中的每一条记录的连接列,看是否是真的匹配(即这里要校验 S 和 B 中的匹配记录所对应的连接列是否真的相等,因为对于 Hash 运算而言,不同的值经过哈希运算后的结果可能是一样的),如果是真的匹配,则上述 hash_value_1 所对应 B 中的记录的位于目标 SQL 中的查询列和该 Hash Bucket 中的匹配记录便会组合起来,一起作为满足目标 SQL 连接条件的记录返回;如果找不到匹配的 Hash Bucket,则 Oracle 就会去访问步骤5中构建的位图,如果位图显示该 Hash Bucket 在 Si 中对应的记录数大于0,则说明该 Hash Bucket 虽然不在内存中,但它已经被写回到了磁盘上,则此时 Oracle就会按照上述 hash_value_1 的值把相应 B 中的对应记录也以 Hash Partition 的方式写回到磁盘上,同时和该记录存储在一起的还有该记录用 hash_func_2 计算出来的 hash_value_2 的值;如果位图显示该 Hash Bucket 在 Si 中对应的记录数等于0,则 Oracle 就不用把上述 hash_value_1所对应 B 中的记录写回到磁盘上了,因为这条记录必然不满足目标 SQL 的连接条件;这个根据位图来决定是否将上述 hash_value_1 所对应B中的记录写回到磁盘的动作就是所谓的“位图过滤”;我们把B所对应的每一个 Hash Partition 记为 Bj;
  11. 上述去 Si 中查找匹配 Hash Bucket 和构建 Bj 的过程会一直持续下去,直到遍历完 B 中的所有记录为止;
  12. 至此 Oracle 已经处理完所有位于内存中的 Si 和对应的 Bj,现在只剩下位于磁盘上的 Si 和 Bj 还未处理;
  13. 因为在构建 Si 和 Bj 时用的是同样的哈希函数 hash_func_1 和hash_func_2,所以 Oracle 在处理位于磁盘上的 Si 和 Bj 的时候可以放心的配对处理,即只有对应 Hash Partition Number 值相同的 Si 和 Bj 才可能会产生满足连接条件的记录;这里我们用 Sn 和 Bn 来表示位于磁盘上且对应 Hash Partition Number 值相同的 Si 和 Bj
  14. 对于每一对儿 Sn 和 Bn,它们之中记录数较少的会被当作驱动结果集,然后 Oracle 会用这个驱动结果集的 Hash Bucket 里记录的 hash_value_2 来构建新的 Hash Table,另外一个记录数较大的会被当作被驱动结果集,然后 Oracle会用这个被驱动结果集的 Hash Bucket 里记录的 hash_value_2 去上述构建的新 Hash Table 中找匹配记录;注意,对每一对儿 Sn 和 Bn 而言,Oracle 始终会选择它们中记录数较少的来作为驱动结果集,所以每一对儿 Sn 和 Bn 的驱动结果集都可能会发生变化,这就是所谓的“动态角色互换”
  15. 步骤14中如果存在匹配记录,则该匹配记录也会作为满足目标 SQL 连接条件的记录返回;
  16. 上述处理 Sn 和 Bn 的过程会一直持续下去,直到遍历完所有的 Sn 和 Bn 为止。

对于哈希连接的优缺点及适用场景,我们有如下总结:

  • 哈希连接不一定会排序,或者说大多数情况下都不需要排序;
  • 哈希连接的驱动表所对应的连接列的可选择性应尽可能的好,因为这个可选择性会影响对应 Hash Bucket 中的记录数,而 Hash Bucket 中的记录数又会直接影响从该 Hash Bucket 中查找匹配记录的效率;如果一个 Hash Bucket 里所包含的记录数过多,则可能会严重降低所对应哈希连接的执行效率,此时典型的表现就是该哈希连接执行了很长时间都没有结束,数据库所在 database server 上的 CPU 占用率很高,但目标 SQL 所消耗的逻辑读却很低,因为此时大部分时间都耗费在了遍历上述 Hash Bucket 里的所有记录上,而遍历 Hash Bucket 里记录这个动作是发生在 PGA 的工作区里,所以不耗费逻辑读;
  • 哈希连接只适用于 CBO、它也只能用于等值连接条件(即使是哈希反连接,Oracle 实际上也是将其转换成了等价的等值连接);
  • 哈希连接很适合于一个小表和大表之间的表连接,特别是在小表的连接列的可选择性非常好的情况下,这时候哈希连接的执行时间就可以近似看作是和全表扫描那个大表所耗费的时间相当;
  • 当两个表做哈希连接时,如果这两个表在施加了目标 SQL 中指定的谓词条件(如果有的话)后得到的结果集中数据量较小的那个结果集所对应的 Hash Table 能够完全被容纳在内存中时(PGA 的工作区),则此时的哈希连接的执行效率会非常高。

可以借助于10104事件所产生的 trace 文件来观察目标 SQL 在做哈希连接时的大致过程和一些统计信息(比如用了多少个 Hash Partition、多个少 Hash Bucket 以及各个 Hash Bucket 都分别有多少条记录等),10104 事件在我们实际诊断哈希连接的性能问题时非常有用。

使用 10104 事件观察目标 SQL 做哈希连接的具体过程为:

oradebug setmypid

oradebug event 10104 trace name context forever, level 1

set autotrace traceonly

实际执行目标 SQL(必须要实际执行该 SQL,不能用 explain plan for)

oradebug tracefile_name

一个典型的 10104 事件所产生的 trace 文件内容为如下所示:

kxhfInit(): enter

kxhfInit(): exit

*** RowSrcId: 1 HASH JOIN STATISTICS (INITIALIZATION) ***

Join Type: INNER join

Original hash-area size: 3642760

Memory for slot table: 2826240

Calculated overhead for partitions and row/slot managers: 816520

Hash-join fanout: 8

Number of partitions: 8

Number of slots: 23

Multiblock IO: 15

Block size(KB): 8

Cluster (slot) size(KB): 120

Minimum number of bytes per block: 8160

Bit vector memory allocation(KB): 128

Per partition bit vector length(KB): 16

……省略显示部分内容

Slot table resized: old=23 wanted=12 got=12 unload=0

*** RowSrcId: 1 HASH JOIN RESIZE BUILD (PHASE 1) ***

Total number of partitions: 8

Number of partitions which could fit in memory: 8

Number of partitions left in memory: 8

Total number of slots in in-memory partitions: 8

kxhfResize(enter): resize to 14 slots (numAlloc=8, max=12)

kxhfResize(exit): resized to 14 slots (numAlloc=8, max=14)

set work area size to: 2215K (14 slots)

*** RowSrcId: 1 HASH JOIN BUILD HASH TABLE (PHASE 1) ***

Total number of partitions: 8

Number of partitions left in memory: 8

Total number of rows in in-memory partitions: 1000

(used as preliminary number of buckets in hash table)

Estimated max # of build rows that can fit in avail memory: 79800

### Partition Distribution ###

Partition:0 rows:120 clusters:1 slots:1 kept=1

Partition:1 rows:122 clusters:1 slots:1 kept=1

……省略显示部分内容

Partition:6 rows:118 clusters:1 slots:1 kept=1

Partition:7 rows:137 clusters:1 slots:1 kept=1

*** (continued) HASH JOIN BUILD HASH TABLE (PHASE 1) ***

Revised number of hash buckets (after flushing): 1000

Allocating new hash table.

*** (continued) HASH JOIN BUILD HASH TABLE (PHASE 1) ***

Requested size of hash table: 256

Actual size of hash table: 256

Number of buckets: 2048

Match bit vector allocated: FALSE

*** (continued) HASH JOIN BUILD HASH TABLE (PHASE 1) ***

Total number of rows (may have changed): 1000

Number of in-memory partitions (may have changed): 8

Final number of hash buckets: 2048

Size (in bytes) of hash table: 8192

qerhjBuildHashTable(): done hash-table on partition=7, index=0 last_slot#=3 rows=137 total_rows=137

qerhjBuildHashTable(): done hash-table on partition=6, index=1 last_slot#=4 rows=118 total_rows=255

……省略显示部分内容

qerhjBuildHashTable(): done hash-table on partition=1, index=6 last_slot#=2 rows=122 total_rows=880

qerhjBuildHashTable(): done hash-table on partition=0, index=7 last_slot#=5 rows=120 total_rows=1000

kxhfIterate(end_iterate): numAlloc=8, maxSlots=14

*** (continued) HASH JOIN BUILD HASH TABLE (PHASE 1) ***

### Hash table ###

# NOTE: The calculated number of rows in non-empty buckets may be smaller

# than the true number.

Number of buckets with 0 rows: 1249

Number of buckets with 1 rows: 626

Number of buckets with 2 rows: 149

Number of buckets with 3 rows: 21

Number of buckets with 4 rows: 3

Number of buckets with 5 rows: 0

……省略显示部分内容

Number of buckets with between 90 and 99 rows: 0

Number of buckets with 100 or more rows: 0

### Hash table overall statistics ###

Total buckets: 2048 Empty buckets: 1249 Non-empty buckets: 799

Total number of rows: 1000

Maximum number of rows in a bucket: 4

Average number of rows in non-empty buckets: 1.251564

Disabled bitmap filtering: filtered rows=0 minimum required=50 out of=1000

qerhjFetch: max probe row length (mpl=0)

*** RowSrcId: 1, qerhjFreeSpace(): free hash-join memory

kxhfRemoveChunk: remove chunk 0 from slot table

注意到上述显示内容中我粗体标出的部分,如

“Number of in-memory partitions (may have changed):8”、 “Final number of hash buckets: 2048”、 “Total buckets: 2048 Empty buckets: 1249 Non-empty buckets: 799”、 “Total number of rows: 1000”、 “Maximum number of rows in a bucket:4”、 “Disabled bitmap filtering: filtered rows=0 minimum required=50 out of=1000”

等,这说明上述哈希连接驱动结果集的记录数为1000,共有8个 Hash Partition、2048个 Hash Bucket,这2048个 Hash Bucket 中有1249个是空的(即没有记录)、799个有记录,包含记录数最多的一个 Hash Bucket 所含记录的数量为4以及上述哈希连接并没有启用位图过滤。

近期文章

新年贺礼:云和恩墨大讲堂期刊发行

2015 Oracle 十大热门文章精选

Oracle 12c ASM 防火防盗新特性揭秘

DBA入门之路:学习与进阶之经验谈

DBA入门之路:关于日常工作的建议

三十八载,Oracle伴我同行—记我的成长之路

从Approx_Count_Distinct到M7的CPU集成

诊断工具与方法:从OS到数据库

Cloud时代DBA的DevOps最佳实践 - SQL 审核

Oracle Database 12.2新特性详解

数据驱动,成就未来。整合业界顶尖的技术与合作伙伴资源,围绕数据及相关领域,提供解决方案和专业服务。

业务架构

电子渠道(网络销售)分析系统、数据治理

IT基础架构

分布式存储解决方案

数据架构

Oracle DB2 MySQL NoSQL

专项服务:架构/安全/容灾/优化/整合/升级/迁移

运维服务:运维服务 代维服务

人才培养:个人认证 企业内训

软件产品:SQL审核、监控、数据恢复

应用架构

应用软件和中间件:数据建模 | SQL审核和优化 | 中间件服务

原文发布于微信公众号 - 数据和云(OraNews)

原文发表时间:2016-01-14

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Golang

influxdb 简介与实现(一)

InfluxDB是一个开源的没有外部依赖的时间序列数据库。适用于记录度量,事件及执行分析。

1314
来自专栏JAVA高级架构

分布式之延时任务方案解析

471
来自专栏架构师小秘圈

分布式唯一ID极简教程

一,题记 所有的业务系统,都有生成ID的需求,如订单id,商品id,文章ID等。这个ID会是数据库中的唯一主键,在它上面会建立聚集索引! ID生成的核心需求有两...

3477
来自专栏一枝花算不算浪漫

Java应用集群下的定时任务处理方案(mysql)

4158
来自专栏JAVA高级架构

结合RPC框架通信谈 netty如何解决TCP粘包问题

因为自己造一个RPC框架的轮子时,需要解决TCP的粘包问题,特此记录,希望方便他人。这是我写的RPC框架的 GitHub地址 https://github.co...

643
来自专栏数据和云

Oracle 12.2 - 启用数据库对象的In-Memory转换填充

所谓数据库的列式转换填充,就是数据库从磁盘读取现有的行格式数据,将其转换为列格式,然后再存储到IM列存储中的过程。将数据库对象填充到列式存储会极大地提高访问效率...

3064
来自专栏GuZhenYin

浅析Entity Framework Core中的并发处理

前言 Entity Framework Core 2.0更新也已经有一段时间了,园子里也有不少的文章.. 本文主要是浅析一下Entity Framework C...

2918
来自专栏MYSQL轻松学

MYSQL INNODB表压缩

压缩前提 表压缩能提升性能,减少存储空间,主要是用在字符类型比较大的表上(VARCHAR,VARBINARY和BLOB和TEXT类型),且读多写少的情况下,如果...

4224
来自专栏.NET开发者社区

什么是ORM?为什么用ORM?浅析ORM的使用及利弊

什么是ORM ORM(Object-relational mapping),中文翻译为对象关系映射,是一种为了解决面向对象与关系数据库存在的互不匹配的现象的技术...

18510
来自专栏张善友的专栏

写入Ring Buffer

原文地址:http://mechanitis.blogspot.com/2011/07/dissecting-disruptor-writing-to-ring...

1686

扫描关注云+社区