表连接总结--Hash Join

r囧r小猫 2022-09-25 11:24 163阅读 0赞

from：http://trophy.iteye.com/blog/1416410

在Oracle中，确定连接操作类型是[**执行计划**][Link 1]生成的重要方面。各种连接操作类型代表着不同的连接操作算法，不同的连接操作类型也适应于不同的数据量和数据分布情况。

无论是Nest Loop Join（嵌套循环），还是Merge Sort Join（合并排序连接），都是适应于不同特殊情况的古典连接方法。

Nest Loop Join算法虽然可以借助连接列索引，但是带来的随机读成本过大。

而Merge Sort Join虽然可以减少随机读的情况，但是带来的**大规模Sort操作**，对内存和Temp空间压力过大。两种算法在处理海量数据的时候，如果是**海量随机读还是海量排序，**都是不能被接受的连接算法。本篇中，我们介绍目前比较常用的一种连接方式[**Hash**][Link 1] 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

\----------------------------------------------------------------------------

\----------------------------------------------------------------------------

|  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的场景就会越来越多。下面通过一系列[**实验**][Link 1]来确定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**][Link 1] 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

\----------------------------------------------------------------------------

\----------------------------------------------------------------------------

|  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

\-----------------------------------------------------------------------------------------------

\-----------------------------------------------------------------------------------------------

|  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

\-------------------------------------------------------------------------------------

\-------------------------------------------------------------------------------------

|  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

详细对比见下图：

<table> 
 <tbody> 
 <tr> 
 <td> &nbsp; </td> 
 <td> 块读 </td> 
 <td> 排序 </td> 
 <td> CPU成本 </td> 
 <td> 执行时间 </td> 
 </tr> 
 <tr> 
 <td> Hash Join </td> 
 <td> 814 </td> 
 <td> 0 </td> 
 <td> 142 </td> 
 <td> 0.02 </td> 
 </tr> 
 <tr> 
 <td> NestLoopJoin </td> 
 <td> 5799 </td> 
 <td> 0 </td> 
 <td> 5023 </td> 
 <td> 1.01 </td> 
 </tr> 
 <tr> 
 <td> Merge Sort Join </td> 
 <td> 494 </td> 
 <td> 2 </td> 
 <td> 900 </td> 
 <td> 0.11 </td> 
 </tr> 
 </tbody> 
</table>

三种连接方式，[**SQL**][Link 1]数据量、语句相同，最后获取不同的成本消耗。可以看出，当数据量达到万级之后，Nest Loop Join的随机读会急剧增加，带来的CPU成本和总执行时间成本也会大大增加。

而使用Merge Sort Join带来的块读是相对较少，但是付出的CPU成本和执行时间也是不可忽视的。将数据集合排序映射到内存中（可能要利用Temp Tablespace），需要消耗很大的CPU和内存资源（排序段）。

**总体来说，Hash Join在这个SQL中还是能带来很好的综合性能的。只有块读稍大，其他指标都是可以接受的最好值。**

下面我们介绍与Hash Join相关的一些系统参数，和Hash Join进行的三种操作模式。不同的系统参数，可能会给CBO成本运算带来影响。不同的操作模式，帮助我们理解PGA中的hash\_area大小是如何影响到Hash Join操作的性能。

附录：

Oracle数据库中的优化器又叫查询优化器（Query Optimizer）。它是SQL分析和执行的优化工具，它负责生成、制定SQL的执行计划。Oracle的优化器有两种，基于规则的优化器（RBO）与基于代价的优化器（CBO)

RBO: Rule-Based Optimization 基于规则的优化器

CBO: Cost-Based Optimization 基于代价的优化器

RBO自ORACLE 6以来被采用，一直沿用至ORACLE 9i. ORACLE 10g开始，ORACLE已经彻底丢弃了RBO，它有着一套严格的使用规则，只要你按照它去写SQL语句，无论数据表中的内容怎样，也不会影响到你的“执行计划”，也就是说RBO对数据不“敏感”；它根据ORACLE指定的优先顺序规则，对指定的表进行执行计划的选择。比如在规则中，索引的优先级大于全表扫描;RBO是根据可用的访问路径以及访问路径等级来选择执行计划，在RBO中，SQL的写法往往会影响执行计划，它要求开发人员非常了解RBO的各项细则，菜鸟写出来的SQL脚本性能可能非常差。随着RBO的被遗弃，渐渐不为人所知。也许只有老一辈的DBA对其了解得比较深入。关于RBO的访问路径，官方文档做了详细介绍：

[Link 1]: http://space.itpub.net/17203031/viewspace-697442