如果没有索引可用，或者CBO认为索引连接不够有效， 那么就会采用散列（HASH）连接。

原理说明

    我们知道，一个函数的输入，决定了函数的输出，　如：Y = F(X) = X  + 100, 则，如果A = B, 则F(A) = F(B)。这个简单的原则，就是散列连接的基础。

为了便于说明，　先创建一个T2表：

SQL>drop table t2;

操作已执行

已用时间: 22.633(ms) clock tick:46339156. Execute id is 8.

 

SQL>create table t2 as select id, name from sysobjects;

操作已执行

已用时间: 4.962(ms) clock tick:10150025. Execute id is 9.

 

SQL>select count(*) from t2;

 

行号       COUNT(*)

---------- -------------------

1          503

 

已用时间: 0.939(ms) clock tick:1919537. Execute id is 10.

　

现在需要与前面创建的T1做连接，　连接条件为T1.ID = T2.ID, 用HASH连接怎么处理呢？方法如下：

 

1.         先任意选择一个表，比如T2, 作为左表，T1为右表;　并初始化一个结果集合

2.         确定一个HASH函数， 比如上面的F(X);

3.         创建一个大小为N的一维数组，数组的每一个项可以想像为可以装无限个记录的桶。每个桶从０依次编号；

4.         扫描左表T2, 用连接字段ID作为输入，计算HASH函数的值HV, 然后取桶的序号NTH  =  HV mod N， 并把该记录放入NTH号桶中；

5.         重复4, 直到所有的T2表记录都放入了桶中；

6.         扫描右表，　对每一条记录，用连接字段ID作为输入，用同样的函数计算HV和NTH

7.         检查编号为NTH桶，对桶中每一条T2表的记录，检查T2.ID = T1.ID, 如果为真，则把相应的T1, T2记录合并为一条结果记录放入结果集中；

8.         重复步骤6, 继续下一条T2表的记录，直到处理完成

 

最后我们获得的结果集就是连接的结果。为什么第７步需要检查呢？因为不同的值可能有相同的HASH值，而相同值必定在同一个桶中。HASH连接分为两个阶段，其中1-5是构造HASH表阶段，6-8是扫描匹配阶段。

可配置的内存参数

    HASH连接需要一定的内存空间，而且HASH表的大小也影响性能，系统提供了几个参数来控制内存的使用和HASH表的尺寸：

SQL>select * from v$dm_ini 

where para_name in ('JOIN_HASH_SIZE', 'HJ_BUF_GLOBAL_SIZE', 'HJ_BUF_SIZE', 'HJ_BLK_SIZE');

 

行号       PARA_NAME          PARA_VALUE

---------- ------------------ ----------

1          HJ_BUF_GLOBAL_SIZE 500

2          JOIN_HASH_SIZE     500000

3          HJ_BLK_SIZE        1

4          HJ_BUF_SIZE        50

 

HJ_BUF_GLOBAL_SIZE缺省为500M, 表示系统允许同时进行的HASH连接最多使用500M内存，如果系统需要同时做很多个HASH连接，可以考虑增大这个参数；它只是个上限，增大它并不会实际分配这么多的内存。

 

JOIN_HASH_SIZE缺省为50万，用来确定HASH表的尺寸；值越大，则冲突的可能性越小，但是初始化HASH也是有代价的，如果系统中的HASH连接左表很小的话，减小这个值可以获得更好的性能；反之，如果左表很大，则为了减少冲突，可以增大它；

 

HJ_BLK_SIZE缺省为1M, 表示扫描左表，构造HASH的过程中，每次申请内存的数量；

 

HJ_BUF_SIZE缺省为50M, 表示单个HASH连接用于构造HASH表的最大内存使用量；对于类似TPC-H性能测试，或者大量使用HASH连接的应用，需要增大这个值。修改这个值并不会立即分配这么多内存， 也只是一个上限。

代价计算

         影响HASH连接性能的因素比较多，首先我们需要选取一个良好的HASH函数，尽可能地把记录分散到HASH表中，如果都集中在少数几个桶中，那就是所谓冲突很多，那么比较的次数也会很多，执行效率会降低。HASH函数用户不能指定，系统已经实现了一个性能良好的函数，对绝大部分应用已经足够了。

 

         其次，应该选择记录少的表作为左表，用于构造一个较小的HASH表。显然，如果左表比较大，那么构造HASH表的时间也会相应增大，而右表只须一趟扫描，不需要构造HASH表。因此，CBO在选择HASH连接的左表时，总是倾向于使用记录数较小的表做为左表。

         HASH连接的代价计算公式如下：

         HASH_COST =          BUILD_HASH_BASE_COST +                     

                              LEFT_COST +  

                              RIGHT_COST +

                              (BASE_HI_CPU + LEFT_CARD * HI_CPU + RIGHT_CARD * HI_SEARCH_CPU) / CPU_SPEED;

                 

其中， BUILD_HASH_BASE_COST为一个可配置的调节参数，缺省为0， LEFT_COST, RIGHT_COST分别表示获取左、右表的代价，BASE_HI_CPU, HI_CPU和HI_SEARCH_CPU也是可配置的参数，分别表示一次HASH连接的基本CPU时钟数，构造hash表时，平均处理一条记录的时钟周期数，以及在hash表中探测一次所需要的时钟周期；因此我们看到总的代价包括了左右表原来的代价， 加上构造HASH表的代价和探测代价。构造HASH表的代价与左表的记录数目成正比，而探测代价与右表的记录数目成正比，而且一般HI_CPU比HI_SEARCH_CPU要大，以确保同样条件下，使用小表做为左表。

 

下面是T1, T2连接的一个例子， 为了确保使用HASH连接，先确保T1(ID)上没有索引。虽然这个查询中，T1放在前面，但是CBO还是选择小表T2做了左表。

SQL>drop index t1l01;

drop index t1l01

第1 行附近出现错误[-2139]:索引[T1L01]不存在.

SQL>select count(*) from t1;

 

行号       COUNT(*)

---------- -------------------

1          100000

 

已用时间: 0.791(ms) clock tick:1611850. Execute id is 31.

 

SQL>select count(*) from t2;

 

行号       COUNT(*)

---------- -------------------

1          503

 

已用时间: 0.438(ms) clock tick:891520. Execute id is 32.

 

SQL>explain select count(*) from t1, t2 where t1.id = t2.id;

 

#NSET2: [21, 1, 0]

  #PRJT2: [21, 1, 8]; exp_num(1), is_atom(FALSE)

    #AAGR2: [21, 1, 8]; grp_num(0), sfun_num(1)

      #HASH2 INNER JOIN: [21, 1646, 8];  KEY_NUM(1);

        #CSCN2: [0, 503, 4]; INDEX33555508(T2)

        #CSCN2: [13, 100000, 4]; INDEX33555505(T1)

 

已用时间: 0.928(ms) clock tick:1893860. Execute id is 0.

 

SQL>select count(*)  from t1, t2 where t1.id = t2.id;

 

行号       COUNT(*)

---------- -------------------

1          158

 

已用时间: 19.468(ms) clock tick:39860176. Execute id is 33.

散列归并连接( Hash & Merge)

如果内存不足，或者在创建HASH表的阶段，申请的内存达到了HJ_BUF_SIZE设定的值，且左表还没有扫描结束时，就把当前的HASH连接自动转换为Hash-Merge连接。

 

这是一个比较复杂的过程。系统会创建一个NSORT对象A， 然后把当前HASH表的记录，附上桶号后，提交给对象A，然后继续扫描左表，重复这个过程, 直到把所有的记录都提交给A。 对右表也创建一个NSORT对象B, 重复同样的操作，直到把右表的记录都提交给了B。A, B两个NSORT对象会自动以（桶号， 连接KEY）作为组合键给数据排序，系统只需要对A,B两路数据作一个归并就可以获得连接结果。

 

NSORT是 DM7内部一个专么用于排序的模块，它支持利用临时表空间进行外排序。临时表空间的访问通过RECYCLE系统缓冲区，因此增大RECYCLE缓冲区的大小，可以减少甚至避免物理IO, 从而有效提升Hash-Merge的连接性能。RECYCLE的大小（单位为M）可以查询：

SQL>select * from v$dm_ini where para_name = 'RECYCLE';

 

行号       PARA_NAME PARA_VALUE

---------- --------- ----------

1          RECYCLE   64

归并连接(Merge Join)

         当连接的两个KEY都是有序时，就可以做归并连接。归并连接不需要额外的空间，也没有Nest Loop Index Join那样有索引定位非常离散时的风险，因此是个非常稳定的连接方式。但是归并连接一般都需要做全表或者全索引扫描，不能利用先选择过滤掉一部份数据，因此有时候代价反而较高。

 

SQL>explain select t1.id, t3.id from t1, t3 where t1.id = t3.id;

 

#NSET2: [26, 32738, 0]

  #PRJT2: [26, 32738, 8]; exp_num(2), is_atom(FALSE)

    #MERGE INNER JOIN3: [26, 32738, 8];

      #SSCN: [1, 10000, 4]; T3L01(T3)

      #SSCN: [13, 100000, 4]; T1L01(T1)

 

其代价计算的基本公式如下：

         COST_MERGE = LEFT_COST +

                      RIGHT_COST +

                      (BASE_MI_CPU +

                       MI_CPU * MAX(LEFT_CARD + RIGHT_CARD, OUTPUT_CARD)) / CPU_SPEED;