在Oracle中，确定连接操作类型是执行计划生成的重要方面。各种连接操作类型代表着不同的连接操作算法，不同的连接操作类型也适应于不同的数据量和数据分布情况。
无论是Nest Loop Join（嵌套循环），还是Merge Sort Join（合并排序连接），都是适应于不同特殊情况的古典连接方法。Nest Loop Join算法虽然可以借助连接列索引，但是带来的随机读成本过大。而Merge Sort Join虽然可以减少随机读的情况，但是带来的大规模Sort操作，对内存和Temp空间压力过大。两种算法在处理海量数据的时候，如果是海量随机读还是海量排序，都是不能被接受的连接算法。本篇中，我们介绍目前比较常用的一种连接方式Hash Join连接。
1、Hash Join（哈希连接）原理
从Oracle 7.3开始，Hash Join正式进入优化器执行计划生成，只有CBO才能使用Hash Join操作。本质上说，Hash Join连接是借助Hash算法，连带小规模的Nest Loop Join，同时利用内存空间进行高速数据缓存检索的一种算法。
下面我们分步骤介绍Hash Join算法步骤：
i. Hash Join连接对象依然是两个数据表，首先选择出其中一个“小表”。这里的小表，就是参与连接操作的数据集合数据量小。对连接列字段的所有数据值，进行Hash函数操作。Hash函数是计算机科学中经常使用到的一种处理函数，利用Hash值的快速搜索算法已经被认为是成熟的检索手段。Hash函数处理过的数据特征是“相同数据值的Hash函数值一定相同，不同数据值的Hash函数值可能相同”；
ii. 经过Hash处理过的小表连接列，连同数据一起存放到Oracle PGA空间中。PGA中存在一块空间为hash_area，专门存放此类数据。并且，依据不同的Hash函数值，进行划分Bucket操作。每个Bucket中包括所有相同hash函数值的小表数据。同时建立Hash键值对应位图。
iii. 之后对进行Hash连接大表数据连接列依次读取，并且将每个Hash值进行Bucket匹配，定位到适当的Bucket上（应用Hash检索算法）；
iv. 在定位到的Bucket中，进行小规模的精确匹配。因为此时的范围已经缩小，进行匹配的成功率精确度高。同时，匹配操作是在内存中进行，速度较Merge Sort Join时要快很多；
下面是一个Hash Join的执行计划。
PLAN_TABLE_OUTPUT
--------------------------------------------------------------------------------
Plan hash value: 779051904
----------------------------------------------------------------------------
| Id | Operation | Name | Rows | Bytes | Cost (%CPU)| Time |
----------------------------------------------------------------------------
| 0 | SELECT STATEMENT | | 2617 | 572K| 142 (1)| 00:00:02 |
|* 1 | HASH JOIN | | 2617 | 572K| 142 (1)| 00:00:02 |
| 2 | TABLE ACCESS FULL| SEGS | 2503 | 312K| 16 (0)| 00:00:01 |
| 3 | TABLE ACCESS FULL| OBJTS | 31083 | 2914K| 126 (1)| 00:00:02 |
----------------------------------------------------------------------------
Predicate Information (identified by operation id):
---------------------------------------------------
1 - access("SEGS"."SEGMENT_NAME"="OBJTS"."OBJECT_NAME")
从原理过程来看，Hash Join与Nest Loop Join/Merge Sort Join存在一定相似度。
首先，Hash Join同Nest Loop Join一样，进行一定的嵌套循环匹配操作，不过差异在于匹配进行随机读的范围是受限范围。不会像Nest Loop Join一样直接频繁进行全表规模的随机读。
其次，Hash Join同之前介绍过的Merge Sort Join有相似点，都是利用PGA的空间进行独立操作。Hash Join中的Bucket就是保存在内存的PGA中，有一块专门Hash_Area进行该项操作。选择小表作为驱动连接表，就是尽量争取PGA内存中可以完全装下小表数据，尽量不要使用Temp表空间。这样，进行Hash匹配和精确匹配的速度就是有保证的。
最后，Hash Join使用的场景是有限制的。其中最大的一个就是连接操作仅能使用“=”连接。因为Hash匹配的过程只能支持相等操作。还有就是连接列的数据分布要尽量做到数据分布均匀，这样产生的Bucket也会尽可能均匀。这样限制匹配的速度才有保证。如果数据列分布偏移严重，Hash Join算法效率会有退化趋势。
随着系统数据量的不断增加，出现Hash Join的场景就会越来越多。下面通过一系列实验来确定Hash Join的各种特性。
2、Hash Join连接实验
首先是准备实验环境。
SQL> create table segs as select * from dba_segments where wner='SYS';
Table created
SQL> create table objts as select * from dba_objects where wner='SYS';
Table created
SQL> select count(*) from segs;
COUNT(*)
----------
2503
SQL> select count(*) from objts;
COUNT(*)
----------
31083
SQL> create index idx_segs_name on segs(segment_name);
Index created
SQL> create index idx_objts_name on objts(object_name);
Index created
SQL> exec dbms_stats.gather_table_stats(user,'SEGS',cascade => true);
PL/SQL procedure successfully completed
SQL> exec dbms_stats.gather_table_stats(user,'OBJTS',cascade => true);
PL/SQL procedure successfully completed
此时，我们对比三种连接方式的成本因素。
SQL> set autotrace traceonly;
SQL> select * from segs, objts where segs.segment_name=objts.object_name;
已选择4870行。
执行计划
----------------------------------------------------------
Plan hash value: 779051904
----------------------------------------------------------------------------
| Id | Operation | Name | Rows | Bytes | Cost (%CPU)| Time |
----------------------------------------------------------------------------
| 0 | SELECT STATEMENT | | 2617 | 572K| 142 (1)| 00:00:02 |
|* 1 | HASH JOIN | | 2617 | 572K| 142 (1)| 00:00:02 |
| 2 | TABLE ACCESS FULL| SEGS | 2503 | 312K| 16 (0)| 00:00:01 |
| 3 | TABLE ACCESS FULL| OBJTS | 31083 | 2914K| 126 (1)| 00:00:02 |
----------------------------------------------------------------------------
Predicate Information (identified by operation id):
---------------------------------------------------
1 - access("SEGS"."SEGMENT_NAME"="OBJTS"."OBJECT_NAME")
统计信息
----------------------------------------------------------
1 recursive calls
0 db block gets
814 consistent gets
0 physical reads
0 redo size
356347 bytes sent via SQL*Net to client
3940 bytes received via SQL*Net from client
326 SQL*Net roundtrips to/from client
0 sorts (memory)
0 sorts (disk)
4870 rows processed
SQL> select/*+use_nl(segs,objts)*/*from segs, objts where segs.segment_name=objts.object_name;
已选择4870行。
执行计划
----------------------------------------------------------
Plan hash value: 2045044449
-----------------------------------------------------------------------------------------------
| Id | Operation | Name | Rows | Bytes | Cost (%CPU)| Time |
-----------------------------------------------------------------------------------------------
| 0 | SELECT STATEMENT | | 2617 | 572K| 5023 (1)| 00:01:01 |
| 1 | NESTED LOOPS | | | | | |
| 2 | NESTED LOOPS | | 2617 | 572K| 5023 (1)| 00:01:01 |
| 3 | TABLE ACCESS FULL | SEGS | 2503 | 312K| 16 (0)| 00:00:01 |
|* 4 | INDEX RANGE SCAN | IDX_OBJTS_NAME | 1 | | 1 (0)| 00:00:01 |
| 5 | TABLE ACCESS BY INDEX ROWID| OBJTS | 1 | 96 | 2 (0)| 00:00:01 |
-----------------------------------------------------------------------------------------------
Predicate Information (identified by operation id):
---------------------------------------------------
4 - access("SEGS"."SEGMENT_NAME"="OBJTS"."OBJECT_NAME")
统计信息
----------------------------------------------------------
1 recursive calls
0 db block gets
5799 consistent gets
0 physical reads
0 redo size
406352 bytes sent via SQL*Net to client
3940 bytes received via SQL*Net from client
326 SQL*Net roundtrips to/from client
0 sorts (memory)
0 sorts (disk)
4870 rows processed
SQL> select/*+use_merge(segs,objts)*/*from segs, objts where segs.segment_name=objts.object_name;
已选择4870行。
执行计划
----------------------------------------------------------
Plan hash value: 2272228973
-------------------------------------------------------------------------------------
| Id | Operation | Name | Rows | Bytes |TempSpc| Cost (%CPU)| Time |
-------------------------------------------------------------------------------------
| 0 | SELECT STATEMENT | | 2617 | 572K| | 900 (1)| 00:00:11|
| 1 | MERGE JOIN | | 2617 | 572K| | 900 (1)| 00:00:11 |
| 2 | SORT JOIN | | 2503 | 312K| 920K| 90 (2)| 00:00:02 |
| 3 | TABLE ACCESS FULL| SEGS | 2503 | 312K| | 16 (0)| 00:00:01 |
|* 4 | SORT JOIN | | 31083 | 2914K| 8168K| 809 (1)| 00:00:10 |
| 5 | TABLE ACCESS FULL| OBJTS | 31083 | 2914K| | 126 (1)| 00:00:02 |
-------------------------------------------------------------------------------------
Predicate Information (identified by operation id):
---------------------------------------------------
4 - access("SEGS"."SEGMENT_NAME"="OBJTS"."OBJECT_NAME")
filter("SEGS"."SEGMENT_NAME"="OBJTS"."OBJECT_NAME")
统计信息
----------------------------------------------------------
1 recursive calls
0 db block gets
494 consistent gets
0 physical reads
0 redo size
427743 bytes sent via SQL*Net to client
3940 bytes received via SQL*Net from client
326 SQL*Net roundtrips to/from client
2 sorts (memory)
0 sorts (disk)
4870 rows processed
详细对比见下图：
|
|
块读 |
排序 |
CPU成本 |
执行时间 |
|
Hash Join |
814 |
0 |
142 |
0.02 |
|
NestLoopJoin |
5799 |
0 |
5023 |
1.01 |
|
Merge Sort Join |
494 |
2 |
900 |
0.11 |
三种连接方式，SQL数据量、语句相同，最后获取不同的成本消耗。可以看出，当数据量达到万级之后，Nest Loop Join的随机读会急剧增加，带来的CPU成本和总执行时间成本也会大大增加。
而使用Merge Sort Join带来的块读是相对较少，但是付出的CPU成本和执行时间也是不可忽视的。将数据集合排序映射到内存中（可能要利用Temp Tablespace），需要消耗很大的CPU和内存资源（排序段）。
总体来说，Hash Join在这个SQL中还是能带来很好的综合性能的。只有块读稍大，其他指标都是可以接受的最好值。
下面我们介绍与Hash Join相关的一些系统参数，和Hash Join进行的三种操作模式。不同的系统参数，可能会给CBO成本运算带来影响。不同的操作模式，帮助我们理解PGA中的hash_area大小是如何影响到Hash Join操作的性能。
