hash join

冷不防 2023-01-17 14:52 69阅读 0赞

其他参考：  
https://www.cnblogs.com/xqzt/p/4469673.html  
https://www.cnblogs.com/shangyu/p/6055181.html  
https://blog.csdn.net/expleeve/article/details/48734957

在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

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

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

| 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

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

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

| 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> Nest Loop Join </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数据量、语句相同，最后获取不同的成本消耗。可以看出，当数据量达到万级之后，Nest Loop Join的随机读会急剧增加，带来的CPU成本和总执行时间成本也会大大增加。

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

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

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

Hash Join是Oracle CBO时代经常出现的一种连接方式，对海量数据处理时经常出现在执行计划里。本篇的上篇（[http://space.itpub.net/17203031/viewspace-697442][http_space.itpub.net_17203031_viewspace-697442]） 介绍了Hash Join的一些外部特征和操作算法流程，下面我们一起看下一些影响到Hash Join的重要参数和内部指标。

**3、Hash Join相关参数**

Hash Join是CBO优化器才能生成的执行计划操作，如果是选择了RBO就不能生成包括Hash Join的执行计划。此外，与Hash Join相关的Oracle参数还包括下面几个：

ü Hash\_Join\_Enable

该参数是控制CBO启用Hash Join的开关。如果设置为True，则表示CBO可以使用Hash Join连接方式，否则就不可以使用。在目前的版本中，该参数已经演化为一个隐含参数，名称为“\_hash\_join\_enable”。

SQL> col name for a20;

SQL> col value for a10;

SQL> col DESCRIB for a30;

SQL> SELECT x.ksppinm NAME, y.ksppstvl VALUE, x.ksppdesc describ

2 FROM SYS.x$ksppi x, SYS.x$ksppcv y

3 WHERE x.inst\_id = USERENV ('Instance')

4 AND y.inst\_id = USERENV ('Instance')

5 AND x.indx = y.indx

6 AND x.ksppinm LIKE '%hash\_join\_enable%';

NAME VALUE DESCRIB

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

\_hash\_join\_enabled TRUE enable/disable hash join

该参数的隐式化，也就说明了CBO已经成熟到一定程度，Oracle官方不希望我们禁用掉这种Hash Join连接方式。当然，我们可以从system和session两层均可以暂时的禁用掉hash Join。

//此时\_hash\_join\_enable=true

SQL> explain plan for select \* from segs, tabs where segs.segment\_name=tabs.table\_name;

Explained

SQL> select \* from table(dbms\_xplan.display);

PLAN\_TABLE\_OUTPUT

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

Plan hash value: 2106473715

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

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

| 0 | SELECT STATEMENT | | 990 | 354K| 25 (4)| 00:00:01 |

|\* 1 | HASH JOIN | | 990 | 354K| 25 (4)| 00:00:01 |

| 2 | TABLE ACCESS FULL| TABS | 968 | 229K| 11 (0)| 00:00:01 |

| 3 | TABLE ACCESS FULL| SEGS | 2267 | 274K| 13 (0)| 00:00:01 |

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

Predicate Information (identified by operation id):

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

1 - access("SEGS"."SEGMENT\_NAME"="TABS"."TABLE\_NAME")

15 rows selected

//session层面禁用hash\_join连接

SQL> alter session set "\_hash\_join\_enabled"=false;

Session altered

NAME VALUE DESCRIB

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

\_hash\_join\_enabled FALSE enable/disable hash join

//相同的SQL，此时参数环境已经变化；

SQL> explain plan for select \* from segs, tabs where segs.segment\_name=tabs.table\_name;

Explained

SQL> select \* from table(dbms\_xplan.display);

PLAN\_TABLE\_OUTPUT

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

Plan hash value: 3475644097

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

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

| 0 | SELECT STATEMENT | | 990 | 354K| | 144 (2)| 00:00:02 |

| 1 | MERGE JOIN | | 990 | 354K| | 144 (2)| 00:00:02 |

| 2 | SORT JOIN | | 968 | 229K| 712K| 65 (2)| 00:00:01 |

| 3 | TABLE ACCESS FULL| TABS | 968 | 229K| | 11 (0)| 00:00:01 |

|\* 4 | SORT JOIN | | 2267 | 274K| 824K| 79 (2)| 00:00:01 |

| 5 | TABLE ACCESS FULL| SEGS | 2267 | 274K| | 13 (0)| 00:00:01 |

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

Predicate Information (identified by operation id):

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

4 - access("SEGS"."SEGMENT\_NAME"="TABS"."TABLE\_NAME")

filter("SEGS"."SEGMENT\_NAME"="TABS"."TABLE\_NAME")

已选择18行。

可见，当我们session级别禁用了hash Join连接之后，CBO不能进行Hash Join路径选择。于是选择了Merge Join路径，显然无论是执行时间还是CPU成本，Merge Join略逊一筹。

ü Hash\_Area\_Size

Hash Join操作是依赖独立的私有空间，我们称之为Hash\_Area。Hash Area在Join过程中的作用就是将连接小表尽可能的缓存在Hash Area中，供进行Hash匹配和Bucket内部精确匹配。Hash Area是贮存在PGA中，属于会话session独立的一块空间。如果Hash Area较小，不足以存放小表全部数据，就会引起Temp表空间的使用，进而影响Hash Join性能。

SQL> show parameter hash

NAME TYPE VALUE

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

hash\_area\_size integer 131072

因为每一个会话都会开启一个Hash Area进行Hash 操作，所以通常Hash Area的大小不会设置很大。与Hash Area类似的空间是Sort Area，用于进行SQL语句中的Order by操作，也是一个依赖分配的参数项目。通常，Hash Area被分配大小为Sort Area的两倍。

SQL> show parameter sort\_area

NAME TYPE VALUE

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

sort\_area\_retained\_size integer 0

sort\_area\_size integer 65536

进入Oracle 9i之后，特别是10g出现，Oracle共享内存和独占内存分配策略呈现自动化和自适应化的趋势，而且这种技术也逐渐成熟。DBA只需要确定Oracle数据库总的内存使用大小（memory\_target），就会根据算法、负载不断调整实现自适应的内存分区调整。

作为PGA分配，Oracle推出的自动调控参数是pga\_aggregate\_target，表示所有会话的PGA总分配大小。如果不启用PGA自动分配，该参数值就是设置为0。

SQL> show parameter pga

NAME TYPE VALUE

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

pga\_aggregate\_target big integer 0

ü Hash\_multiblock\_io\_count

该参数表示在进行Hash Join连接操作的时候，一次可以读取的块个数。在最新的版本中，该参数已经变成了一个隐含参数。

SQL> SELECT x.ksppinm NAME, y.ksppstvl VALUE, x.ksppdesc describ

2 FROM SYS.x$ksppi x, SYS.x$ksppcv y

3 WHERE x.inst\_id = USERENV ('Instance')

4 AND y.inst\_id = USERENV ('Instance')

5 AND x.indx = y.indx

6 AND x.ksppinm LIKE '%hash\_multiblock%';

NAME VALUE DESCRIB

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

\_hash\_multiblock\_io\_count 0 number of blocks hash join wil

l read/write at once

这个参数可以追溯到Oracle 8i时代，当时设置的默认值为1。在以后的版本中，通常设置为0。这个参数对IO影响重大，不同的硬件环境、系统负载下效果不同。所以，当设置为0的时候，Oracle是会每次自动计算该值。

作为我们来讲，最好不要进行该参数的设置。

**4、连接三模式**

Hash Join比较Merge Sort Join一个比较优势的地方，就是对PGA空间的有限使用上。但是，使用PGA毕竟是一种风险操作。因为Hash Area同Sort Area一样，在小表不能完全装入系统时，会调用Temp表空间的硬盘空间。这样，就会引起一些问题。

下面关于三种模式的阐述，**借鉴八神前辈的《Oracle Hash Join》（http://www.alidba.net/index.php/archives/440）。特此表示感谢。**

针对不同的状态，Oracle分别有不同的模式对应。

Optimal模式

这是我们进行Hash Join的最理想情况。驱动表（小表）生成的Hash数据集合可以完全存放在Hash Area的时候，我们称之为Optimal模式。

ü 首先找到驱动表，获取到驱动表。存放在Hash\_Area中；

ü 在Hash Area中，对驱动表进行Hash操作，形成Hash Bulket，形成对应的分区信息。针对多个Bulket，同时形成一个Bitmap列表，做到Bulket与Bitmap位的联系；

ü 在各个Bulket中，分布着不同的数据行。如果连接列分布比较均匀，Bulket中数据也就比较均匀。如果Bulket中包括数据，对应该Bulket的Bitmap位上为1，否则为0；

ü 找被驱动表的每一列，将连接列值进行Hash处理。匹配Bitmap位，如果Bitmap为0，表示该列值没有存在，直接抛弃。否则进入Bulket进行精确匹配；

Onepass模式

如果我们设置的PGA空间小，或者连接的小表体积就已经很大了，那么就会利用到临时表空间。具体处理，就是进行两次的Hash处理，在Bulket层面的上面建立Partition分区。

当进行Hash操作的时候，出现的情形是一部分的Partition在内存中，另一部分Partition被存放在Temp表空间上。

在进行连接匹配的时候，如果能够在Bitmap中确定到Partition在内存中，那么直接在内存中进行检索和精确匹配过程。否则从Temp表空间中将对应的Partition调取到内存中，进行匹配操作。

Multipass模式

这是一种很极端的情况，如果Hash Area小到一个Partition都装不下。当进行Hash操作后，只有半个Partition能装入到Hash Area。

这种情况下，如果一个Partition匹配没有做到，还不能够放弃操作，要将剩下一半的Partition获取到进行Hash Join匹配。也就是一个Partition要经过两次的Bitmap匹配过程。

**5、结论**

Hash Join是一种效率很高，CBO时代很常见的连接方式。但是，相对于其他古典算法，Hash Join的综合效率很高，特别在海量数据时代。

[http_space.itpub.net_17203031_viewspace-697442]: http://space.itpub.net/17203031/viewspace-697442

hash join

发表评论取消回复

还没有评论，来说两句吧...

相关阅读

相关 hash join

相关表连接总结--Hash Join

相关 Oracle中的Hash Join祥解

相关对oracle hash join trace的研究

相关 Oracle的Filter,Nest loop,Merge sort join和Hash join

相关 Oracle中的Hash Join祥解

相关高级数据库十九：并行JOIN算法（Hashing）

相关 Spark Join——Broadcast Join、Shuffle Hash Join、Sort Merge Join

相关 Oracle表连接操作——Hash Join（哈希连接）

相关 [Oracle] Sql优化系列--Hash join详解