---

---

排序合并连接

1.2.4.2.1  排序合并连接

排序合并连接（Sort Merge Join）是一种两个表在做表连接时用排序操作（Sort）和合并操作（Merge）来得到连接结果集的表连接方法。

如果两个表（这里将它们分别命名为表T1和表T2）在做表连接时使用的是排序合并连接，则Oracle会依次顺序执行如下步骤。

（1）首先以目标SQL中指定的谓词条件（如果有的话）去访问表T1，然后对访问结果按照表T1中的连接列来排序，排好序后的结果集我们记为结果集1。

（2）接着以目标SQL中指定的谓词条件（如果有的话）去访问表T2，然后对访问结果按照表T2中的连接列来排序，排好序后的结果集我们记为结果集2。

（3）最后对结果集1和结果集2执行合并操作，从中取出匹配记录来作为排序合并连接的最终执行结果。

我个人认为这个合并操作的具体执行步骤是这样的：首先遍历结果集1，即先取出结果集1中的第1条记录，然后去结果集2中按照连接条件判断是否存在匹配记录，然后再取出结果集1中的第2条记录，按照同样的连接条件再去结果集2中判断是否存在匹配的记录，直到最后遍历完结果集1中所有的记录。注意，这里去结果集2中判断是否存在匹配记录时会存在一个过滤的过程。因为结果集2已经按照表T2中的连接列排好序了，所以取出结果集1中的记录然后去找结果集2中的匹配记录时，只需要遍历结果集2中满足上述连接条件的那部分数据就可以了（这部分数据在结果集2中的存储位置肯定是在一起的），也就是说此时并不需要遍历结果集2中所有的记录，并且一旦在结果集2中找到匹配记录，就可以把该匹配记录从结果集2中删除，或者不删除但记录下其位置（这样下次再从结果集2中找匹配记录时就可以从这个位置开始了）。最后，结果集1和结果集2中所有的匹配结果就是上述排序合并连接的最终执行结果（注意，这个合并过程的具体执行步骤是我猜的，我不确定是否正确）。

对于排序合并连接的优缺点及适用场景，我们有如下总结。

通常情况下，排序合并连接的执行效率会远不如哈希连接，但前者的使用范围更广，因为哈希连接通常只能用于等值连接条件，而排序合并连接还能用于其他连接条件（例如<、<=、>、>=）。

通常情况下，排序合并连接并不适合OLTP类型的系统，其本质原因是因为对于OLTP类型的系统而言，排序是非常昂贵的操作，当然，如果能避免排序操作，那么即使是OLTP类型的系统，也还是可以使用排序合并连接的。比如两个表虽然是做排序合并连接，但实际上它们并不需要排序，因为这两个表在各自的连接列上都存在索引。

从严格意义上说，排序合并连接并不存在驱动表的概念，虽然我个人认为在执行合并的过程中，实际上还是存在驱动表和被驱动表的。

1.2.4.2.2  嵌套循环连接

嵌套循环连接（Nested Loops Join）是一种两个表在做表连接时依靠两层嵌套循环（分别为外层循环和内层循环）来得到连接结果集的表连接方法。

如果两个表（这里将它们分别命名为表T1和表T2）在做表连接时使用的是嵌套循环连接，则Oracle会依次顺序执行如下步骤。

（1）首先，优化器会按照一定的规则来决定表T1和T2中谁是驱动表、谁是被驱动表。驱动表用于外层循环，被驱动表用于内层循环。这里假设驱动表是T1，被驱动表是T2。

（2）接着以目标SQL中指定的谓词条件（如果有的话）去访问驱动表T1，访问驱动表T1后得到的结果集我们记为驱动结果集1。

（3）然后遍历驱动结果集1并同时遍历被驱动表T2，即先取出驱动结果集1中的第1条记录，接着遍历被驱动表T2并按照连接条件去判断T2中是否存在匹配的记录，然后再取出驱动结果集1中的第2条记录，按照同样的连接条件再去遍历被驱动表T2并判断T2中是否还存在匹配的记录，直到遍历完驱动结果集1中所有的记录为止。这里的外层循环是指遍历驱动结果集1所对应的循环，内层循环是指遍历被驱动表T2所对应的循环。显然，外层循环所对应的驱动结果集1有多少条记录，遍历被驱动表T2的内层循环就要做多少次，这就是所谓的"嵌套循环"的含义。

对于嵌套循环连接的优缺点及适用场景，我们有如下总结。

从上述嵌套循环连接的具体执行过程可以看出：如果驱动表所对应的驱动结果集的记录数较少，同时在被驱动表的连接列上又存在唯一性索引（或者在被驱动表的连接列上存在选择性很好的非唯一性索引），那么此时使用嵌套循环连接的执行效率就会非常高；但如果驱动表所对应的驱动结果集的记录数很多，即便在被驱动表的连接列上存在索引，此时使用嵌套循环连接的执行效率也不会高。

只要驱动结果集的记录数较少，那就具备了做嵌套循环连接的前提条件，而驱动结果集是在对驱动表应用了目标SQL中指定的谓词条件（如果有的话）后所得到的结果集，所以大表也可以作为嵌套循环连接的驱动表，关键看目标SQL中指定的谓词条件（如果有的话）能否将驱动结果集的数据量降下来。

嵌套循环连接有其他连接方法所没有的一个优点：嵌套循环连接可以实现快速响应，即它可以第一时间先返回已经连接过且满足连接条件的记录，而不必等待所有的连接操作全部做完后才返回连接结果。虽然排序合并连接和哈希连接也可以先返回已经连接过且满足连接条件的记录，而不必等待所有的连接操作都做完，但是它们并不是第一时间返回，因为排序合并连接要等到排完序后做合并操作时才能开始返回数据，而哈希连接则要等到驱动结果集所对应的Hash Table全部建完后才能开始返回数据。

如果Oracle使用的是嵌套循环连接，且在被驱动表的连接列上存在索引，那么Oracle在访问该索引时通常会使用单块读，这意味着嵌套循环连接的驱动结果集有多少条记录，Oracle就需要访问该索引多少次。另外，如果目标SQL中的查询列并不能全部从被驱动表的相关索引中获得，那么Oracle在做完嵌套循环连接后就还需要对被驱动表执行回表操作（即用连接结果集中每一条记录所含的ROWID去回表获取被驱动表中的相关查询列）。这个回表操作通常也会使用单块读，这意味着做完嵌套循环连接后的连接结果集有多少条记录，Oracle就需要回表多少次。

对于这种单块读而言，如果待访问的索引块或数据块不在Buffer Cache中，Oracle就需要耗费物理I/O去相应的数据文件中获取。显然，在单块读的数量不降低的情况下，如果能减少这种单块读所需要耗费的物理I/O数量，那么嵌套循环连接的执行效率也会随之提高。

为了提高嵌套循环连接的执行效率，在Oracle 11g中，Oracle引入了向量I/O（Vector I/O）。在引入向量I/O后，Oracle就可以将原先一批单块读所需要耗费的物理I/O组合起来，然后用一个向量I/O去批量处理它们，这样就实现了在单块读的数量不降低的情况下减少这些单块读所需要耗费的物理I/O数量，也就提高了嵌套循环连接的执行效率。

向量I/O的引入也反映在嵌套循环连接所对应的执行计划上。在Oracle 11g中，你会发现明明一次嵌套循环连接就可以处理完毕的SQL，但其执行计划的显示内容中嵌套循环连接的数量却由之前的一个变为了现在的两个。

这里还是以"1.2.4.1.1 内连接"中的测试表T1和T2为例来说明。我们在表T2的列COL2上创建一个名为IDX_T2的索引：

1. SQL> create index idx_t2 on t2(col2);  
2.  
3. Index created  

表T1、T2所在Oracle数据库的版本为Oracle 11.2.0.1：

1. SQL> select * from v$version;  
2. BANNER  
3. --------------------------------------------------------------------------------  
4. Oracle Database 11g Enterprise Edition Release 11.2.0.1.0 - Production  
5. PL/SQL Release 11.2.0.1.0 - Production  
6. CORE    11.2.0.1.0  Production  
7.  
8. TNS for 32-bit Windows: Version 11.2.0.1.0 - Production  
9. NLSRTL Version 11.2.0.1.0 - Production  

之前在"1.2.4.1.1 内连接"中介绍的范例SQL 10为如下所示：

1. select t1.col1, t1.col2, t2.col3  
2.   from t1, t2  
3.  where t1.col2 = t2.col2 ;  

我们现在在范例SQL 10中加入让其走嵌套循环连接的Hint（即/*+ ordered use_nl(t2) */），并实际执行一次：

1. SQL> set autotrace traceonly  
2. SQL> select /*+ ordered use_nl(t2) */t1.col1, t1.col2, t2.col3  
3.   2    from t1, t2  
4.   3   where t1.col2 = t2.col2;  

注意，上述执行计划的显示内容中关键字"NESTED LOOPS"出现了两次，这说明在Oracle 11gR2中执行上述SQL时确实用了两次嵌套循环连接。这里第二次嵌套循环连接的被驱动表部分所对应的执行步骤是"TABLE ACCESS BY INDEX ROWID | T2"，这可能是因为Oracle想表达此时在通过ROWID回表访问表T2时是把一批ROWID组合起来后通过一个向量I/O批量回表，而不是每拿到一个ROWID就用一次单块读回表。

我们现在在范例SQL 10中加入OPTIMIZER_FEATURES_ENABLE Hint（即optimizer_features_enable('9.2.0')）后再次执行：

1. SQL> select /*+ optimizer_features_enable('9.2.0') ordered use_nl(t2) */t1.col1,t1.col2, t2.col3  
2.   2    from t1, t2  
3.   3   where t1.col2 = t2.col2;  

上述OPTIMIZER_FEATURES_ENABLE Hint的作用是让解析SQL 10的优化器的版本回退到Oracle 9iR2，这样我们就可以观察到同一个SQL在Oracle 11g之前执行嵌套循环连接时的情况。

注意，上述执行计划的显示内容中关键字"NESTED LOOPS"只出现了一次，这说明在Oracle 9iR2中执行上述SQL时确实只用了一次嵌套循环连接。

1.2.4.2.3  哈希连接（1）

哈希连接（Hash Join）是一种两个表在做表连接时主要依靠哈希运算来得到连接结果集的表连接方法。

在Oracle 7.3之前，Oracle数据库中的常用表连接方法就只有排序合并连接和嵌套循环连接这两种，但这两种方法都各有其明显缺陷。对于排序合并连接，如果两个表在施加了目标SQL中指定的谓词条件（如果有的话）后得到的结果集很大且需要排序，则排序合并连接的执行效率一定不高；而对于嵌套循环连接，如果驱动表所对应的驱动结果集的记录数很大，即便在被驱动表的连接列上存在索引，此时使用嵌套循环连接的执行效率也会同样不高。

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

在Oracle 10g及其以后的Oracle数据库版本中，优化器（实际上是CBO，因为哈希连接仅适用于CBO）在解析目标SQL时是否考虑哈希连接是受限于隐含参数_HASH_JOIN_ENABLED，而在Oracle 10g以前，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 Bucket的集合。所有Hash Partition的集合就被称为Hash Table，即一个Hash Table由多个Hash Partition所组成，而一个Hash Partition又是由多个Hash Bucket所组成的）。

（2）表T1和T2在施加了目标SQL中指定的谓词条件（如果有的话）后，得到的结果集中数据量较少的那个结果集会被Oracle选为哈希连接的驱动结果集，这里我们假设T1所对应的结果集的数据量相对较少，记为S；T2所对应的结果集的数据量相对较多，记为B。显然这里S是驱动结果集，B是被驱动结果集。

（3）接着Oracle会遍历S，读取S中的每一条记录，并对每一条记录按照该记录在表T1中的连接列做哈希运算。这个哈希运算会使用两个内置哈希函数，这两个哈希函数会同时对该连接列计算哈希值，我们把这两个内置哈希函数分别记为hash_func_1和hash_func_2，它们所计算出来的哈希值分别记为hash_value_1和hash_value_2。

（4）然后Oracle会按照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写到磁盘上（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按照它们所包含的记录数来排序，然后把这些已经排好序的Hash Partition按顺序依次且尽可能全部放到内存中（PGA的工作区），当然，如果实在放不下，放不下的那部分Hash Partition还是会位于磁盘上。我个人认为这个按照Si的记录数来排序的动作不是必须要做的，因为这个排序动作的根本目的就是为了尽可能多地把那些记录数较小的Hash Partition保留在内存中，而将那些已经被写回磁盘、记录数较大且现有内存已经放不下的Hash Partition保留在磁盘上，显然，如果所有的Si本来就都在内存中，也没发生过将Si写回到磁盘的操作，这里根本就不需要排序了。

（9）至此Oracle已经处理完S，现在可以开始处理B了。

（10）Oracle会遍历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_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中的记录写回到磁盘的动作就是所谓的"位图过滤"（Oracle不一定会启用位图过滤，因为如果所有的Si本来就都在内存中，也没发生过将Si写回到磁盘的操作，那么这里Oracle就不需要启用位图过滤了）。我们把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里所包含的记录数过多，则可能会严重降低所对应哈希连接的执行效率，此时典型的表现就是该哈希连接执行了很长时间都没有结束，数据库所在数据库服务器上的CPU占用率很高，但目标SQL所消耗的逻辑读却很低，因为此时大部分时间都耗费在了遍历上述Hash Bucket里的所有记录上，而遍历Hash Bucket里的记录这个动作发生在PGA的工作区里，所以不耗费逻辑读。

哈希连接只适用于CBO，它也只能用于等值连接条件（即使是哈希反连接，Oracle实际上也是将其转换成了等价的等值连接）。

哈希连接很适合于小表和大表之间做表连接且连接结果集的记录数较多的情形，特别是在小表的连接列的可选择性非常好的情况下，这时候哈希连接的执行时间就可以近似看作是和全表扫描那个大表所耗费的时间相当。

当两个表做哈希连接时，如果在施加了目标SQL中指定的谓词条件（如果有的话）后得到的数据量较小的那个结果集所对应的Hash Table能够完全被容纳在内存中（PGA的工作区），则此时的哈希连接的执行效率会非常高。

1.2.4.2.3  哈希连接（2）

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

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

1. oradebug setmypid  
2. oradebug event 10104 trace name context forever, level 1  
3. set autotrace traceonly  
4. 实际执行目标SQL（必须要实际执行该SQL，不能用explain plan for）  
5. oradebug tracefile_name  

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

1. kxhfInit(): enter  
2. kxhfInit(): exit  
3. *** RowSrcId: 1 HASH JOIN STATISTICS (INITIALIZATION) ***  
4. Join Type: INNER join  
5. Original hash-area size: 3642760  
6. Memory for slot table: 2826240  
7. Calculated overhead for partitions and row/slot managers: 816520  
8. Hash-join fanout: 8  
9. Number of partitions: 8  
10. Number of slots: 23  
11. Multiblock IO: 15  
12. Block size(KB): 8  
13. Cluster (slot) size(KB): 120  
14. Minimum number of bytes per block: 8160  
15. Bit vector memory allocation(KB): 128  
16. Per partition bit vector length(KB): 16  
17. ……省略显示部分内容  
18.   Slot table resized: old=23 wanted=12 got=12 unload=0 
19. *** RowSrcId: 1 HASH JOIN RESIZE BUILD (PHASE 1) ***  
20. Total number of partitions: 8  
21. Number of partitions which could fit in memory: 8  
22. Number of partitions left in memory: 8  
23. Total number of slots in in-memory partitions: 8  
24. kxhfResize(enter): resize to 14 slots (numAlloc=8, max=12)  
25. kxhfResize(exit): resized to 14 slots (numAlloc=8, max=14)  
26.   set work area size to: 2215K (14 slots)  
27. *** RowSrcId: 1 HASH JOIN BUILD HASH TABLE (PHASE 1) ***  
28. Total number of partitions: 8  
29. Number of partitions left in memory: 8  
30. Total number of rows in in-memory partitions: 1000  
31.    (used as preliminary number of buckets in hash table)  
32. Estimated max # of build rows that can fit in avail memory: 79800  
33. ### Partition Distribution ###  
34. Partition:0    rows:120        clusters:1      slots:1      kept=1 
35. Partition:1    rows:122        clusters:1      slots:1      kept=1 
36. ……省略显示部分内容  
37. Partition:6    rows:118        clusters:1      slots:1      kept=1 
38. Partition:7    rows:137        clusters:1      slots:1      kept=1 
39. *** (continued) HASH JOIN BUILD HASH TABLE (PHASE 1) ***  
40. Revised number of hash buckets (after flushing): 1000  
41. Allocating new hash table.  
42. *** (continued) HASH JOIN BUILD HASH TABLE (PHASE 1) ***  
43. Requested size of hash table: 256  
44. Actual size of hash table: 256  
45. Number of buckets: 2048  
46. Match bit vector allocated: FALSE  
47. *** (continued) HASH JOIN BUILD HASH TABLE (PHASE 1) ***  
48. Total number of rows (may have changed): 1000  
49. Number of in-memory partitions (may have changed): 8  
50. Final number of hash buckets: 2048  
51. Size (in bytes) of hash table: 8192  
52. qerhjBuildHashTable(): done hash-table on partition=7, index=0 last_slot#=3 rows=137 total_rows=137 
53. qerhjBuildHashTable(): done hash-table on partition=6, index=1 last_slot#=4 rows=118 total_rows=255 
54. ……省略显示部分内容  
55. qerhjBuildHashTable(): done hash-table on partition=1, index=6 last_slot#=2 rows=122 total_rows=880 
56. qerhjBuildHashTable(): done hash-table on partition=0, index=7 last_slot#=5 rows=120 total_rows=1000 
57. kxhfIterate(end_iterate): numAlloc=8, maxSlots=14 
58. *** (continued) HASH JOIN BUILD HASH TABLE (PHASE 1) ***  
59. ### Hash table ###  
60. # NOTE: The calculated number of rows in non-empty buckets may be smaller  
61. #       than the true number.  
62. Number of buckets with   0 rows:       1249  
63. Number of buckets with   1 rows:        626  
64. Number of buckets with   2 rows:        149  
65. Number of buckets with   3 rows:         21  
66. Number of buckets with   4 rows:          3  
67. Number of buckets with   5 rows:          0  
68. ……省略显示部分内容  
69. Number of buckets with between  90 and  99 rows:          0  
70. Number of buckets with 100 or more rows:          0  
71. ### Hash table overall statistics ###  
72. Total buckets: 2048 Empty buckets: 1249 Non-empty buckets: 799  
73. Total number of rows: 1000  
74. Maximum number of rows in a bucket: 4  
75. Average number of rows in non-empty buckets: 1.251564  
76. Disabled bitmap filtering: filtered rows=0 minimum required=50 out of=1000 
77. qerhjFetch: max probe row length (mpl=0)  
78. *** RowSrcId: 1, qerhjFreeSpace(): free hash-join memory  
79. 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"等，这说明上述哈希连接驱动结果集的记录数为1,000，共有8个Hash Partition、2,048个Hash Bucket，这2,048个Hash Bucket中有1,249个是空的（即没有记录），799个有记录，包含记录数最多的那个Hash Bucket所含记录的数量为4，以及上述哈希连接并没有启用位图过滤。

1.2.4.2.4  笛卡儿连接

笛卡儿连接（Cross Join）又称为笛卡儿乘积（Cartesian Product），它是一种两个表在做表连接时没有任何连接条件的表连接方法。

如果两个表（这里将它们分别命名为表T1和表T2）在做表连接时使用的是笛卡儿连接，则Oracle会依次顺序执行如下步骤。

（1）首先以目标SQL中指定的谓词条件（如果有的话）访问表T1，此时得到的结果集我们记为结果集1，这里假设结果集1的记录数为m。

（2）接着以目标SQL中指定的谓词条件（如果有的话）访问表T2，此时得到的结果集我们记为结果集2，这里假设结果集2的记录数为n。

（3）最后对结果集1和结果集2执行合并操作，从中取出匹配记录来作为笛卡儿连接的最终执行结果。这里的特殊之处在于对于笛卡儿连接而言，因为没有表连接条件，所以在对结果集1和结果集2执行合并操作时，对于结果集1中的任意一条记录，结果集2中的所有记录都满足条件，即它们都会是匹配记录，所以上述笛卡儿连接的连接结果的记录数就是m和n的乘积（即m n）。

从上述笛卡儿连接的执行过程我们可以看出，笛卡儿连接实际上是一种特殊的"合并连接"，这里的"合并连接"和排序合并连接类似，只不过笛卡儿连接不需要排序，并且在执行合并操作时没有连接条件而已。关于这一点，实际上可以从笛卡儿连接所对应的执行计划中看出些端倪。

这里还是以"1.2.4.1.1 内连接"中的测试表T1和T2为例来说明。表T1和T2还是和原来一样，各有3条记录，我们执行如下不带连接条件的SQL：

1. SQL> set autotrace on  
2. SQL> select t1.col1,t2.col3 from t1,t2;  

上述SQL的执行结果包含9条记录，这刚好就是表T1和表T2记录数的乘积（9 = 3 3）。

上述执行计划和排序合并连接所对应的执行计划非常相似，并且Id = 1的Operation列的值为"MERGE JOIN CARTESIAN"，只是在排序合并连接的合并部分所对应的关键字"MERGE JOIN"后添加了一个单词"CARTESIAN"，所以我们才说笛卡儿连接实际上就是一种特殊的"合并连接"。

标准SQL用关键字"CROSS JOIN"来表示笛卡儿连接，这里我们用标准SQL的方式来改写上述SQL并再执行一次：

1. SQL> select t1.col1,t2.col3 from t1 cross join t2; 

从上述显示内容可以看出，用标准SQL改写后其执行结果和执行计划与原先的确实是一模一样的。

对于笛卡儿连接的优缺点及适用场景，我们有如下总结。

（1）笛卡儿连接的出现通常是由于目标SQL中漏写了表连接条件，所以笛卡儿连接一般是不好的，除非刻意这样做（比如有些情况下可以利用笛卡儿连接来减少对目标SQL中大表的全表扫描次数）。

（2）有时候出现笛卡儿连接是因为在目标SQL中使用了ORDERED Hint，同时在该SQL的SQL文本中位置相邻的两个表之间又没有直接的关联条件。

（3）有时候出现笛卡儿连接是因为目标SQL中相关表的统计信息不准。比如三个表T1、T2、T3做表连接，T1和T2的连接条件为T1.ID1=T2.ID1，T2和T3的连接条件为T2.ID2=T3.ID2，同时在表T2的连接列ID1和ID2上存在一个包含这两个连接列的组合索引。如果表T1和T3的统计信息不准，导致Oracle认为表T1和T3都只有很少量的记录（比如都只有1条记录），则此时Oracle很可能会选择先对表T1和T3做笛卡儿连接，然后再和表T2做表连接。因为Oracle认为表T1和T3做笛卡儿连接后连接结果集的Cardinality的值是1，并且连接结果中会同时包含列ID1和列ID2，这意味着此时Oracle就可以利用表T2中的上述组合索引了。这种笛卡儿连接通常是有问题的，还是拿这个例子来说，如果表T1和表T3的实际记录数并不都是1，而全部是1000，那么此时表T1和表T3做笛卡儿连接的连接结果集的Cardinality的值就将是100万，显然这种情况下如果还是按照笛卡儿连接的方式来执行的话，则该SQL的执行效率就会受到严重影响。

一 表的连接

表的连接是指在一个SQL语句中通过表与表之间的关联，从一个或多个表检索出相关的数据。连接是通过SQL语句中FROM从句的多个表名，以及WHERE从句里定义的表之间的连接条件来实现的。如果一个SQL语句的关联表超过两个，那么连接的顺序如何呢？ORACLE首先连接其中的两个表，产生一个结果集；然后将产生的结果集与下一个表再进行关联；继续这个过程，直到所有的表都连接完成；最后产生所需的数据。下面都以两个表的连接为例

create table user_info(user_name char(10),user_id char(10));

create table dev_info(dev_no char(10),user_id char(10),dev_type char(10));

说明和分析表的各种连接方式。

ORACLE 从6的版本开始，优化器使用4种不同的表的连接方式：

?  嵌套循环连接（NESTED LOOP JOIN）

?  群集连接     (CLUSTER JOIN)

?  排序合并连接（SORT MERGE JOIN）

?  笛卡尔连接   (CARTESIAN JOIN)

ORACLE 7.3中，新增加了

?  哈希连接(HASH JOIN)。

在ORACLE 8中，新增加了

?  索引连接(INDEX JOIN)。

这六种连接方式都有其独特的技术特点，在一定的条件下，可以充分发挥高效的性能。

但是也都有其局限性，如果使用不当，不仅不能提高效率，反而会严重影响系统的性能。因此，深入地探讨连接方式的内部运行机制对于性能优化是必要的。

1 嵌套循环连接

嵌套循环连接的内部处理的流程：

1） Oracle 优化器根据基于规则RBO或基于成本CBO的原则，选择两个表中的一个作为驱动表，并指定其为外部表。

2） Oracle 优化器再将另外一个表指定为内部表。

3） Oracle从外部表中读取第一行,然后和内部表中的数据逐一进行对比，所有匹配的记录放在结果集中。

4） Oracle读取外部表中的第二行，再和内部表中的数据逐一进行对比，所有匹配的记录添加到结果集中。

5） 重复上述步骤，直到外部表中的所有纪录全部处理完。

6） 最后产生满足要求的结果集。

通过查询SQL语句的执行计划可以看出哪个表是外部表，哪个为内部表。

如 select a.user_name,b.dev_no

   from user_info a, dev_info b

   where a.user_id = b.user_id;

的执行计划:

SELECT STATEMENT ptimizer=CHOOSE

NESTED LOOPS

TABLE ACCESS (FULL) OF 'USER_INFO' --驱动表，外部表

TABLE ACCESS (FULL) OF 'DEV_INFO'  --内部表

使用嵌套循环连接是一种从结果集中提取第一批记录最快速的方法。在驱动行源表(就是正在查找的记录)较小、或者内部行源表已连接的列有惟一的索引或高度可选的非惟一索引时, 嵌套循环连接效果是比较理想的。嵌套循环连接比其他连接方法有优势,它可以快速地从结果集中提取第一批记录,而不用等待整个结果集完全确定下来。这样,在理想情况下,终端用户就可以通过查询屏幕查看第一批记录,而在同时读取其他记录。不管如何定义连接的条件或者模式,任何两行记录源可以使用嵌套循环连接,所以嵌套循环连接是非常灵活的。

然而,如果内部行源表(读取的第二张表)已连接的列上不包含索引,或者索引不是高度可选时, 嵌套循环连接效率是很低的。如果驱动表的记录非常庞大时,其他的连接方法可能更加有效。

可以通过在SQL语句中添加HINTS,强制ORACLE优化器产生嵌套循环连接的执行计划。

select /*+ use_nl(a b) */ a.user_name,b.dev_no

   from user_info a, dev_info b

   where a.user_id = b.user_id;

2 群集连接（CLUSTER JOIN）

  群集连接实际上是嵌套循环连接的一种特例。如果所连接的两张源表是群集中的表，即两张表属于同一个段（SEGMENT）,，那么ORACLE能够使用群集连接。处理的过程是：ORACLE从第一张行源表中读取第一行，然后在第二张行源表中使用CLUSTER索引查找能够匹配到的纪录；继续上面的步骤处理行源表中的第二行，直到所有的记录全部处理完。

   群集连接的效率极高，因为两个参加连接的行源表实际上处于同一个物理块上。但是，群集连接也有其限制，没有群集的两个表不可能用群集连接。所以，群集连接实际上很少使用。

3 排序合并连接（SORT MERGE JOIN）

排序合并连接内部处理的流程：

1)  优化器判断第一个源表是否已经排序，如果已经排序，则到第3步，否则

到第2步。

2)  第一个源表排序

3)  优化器判断第二个源表是否已经排序，如果已经排序，则到第5步，否则

到第4步。

4)  第二个源表排序

5)  已经排过序的两个源表进行合并操作，并生成最终的结果集。

在缺乏数据的选择性或者可用的索引时,或者两个源表都过于庞大(所选的数据超过表记录数的5%)时,排序合并连接将比嵌套循环连更加高效。

排列合并连接需要比较大的临时内存块,以用于排序，这将导致在临时表空间占用更多的内存和磁盘I/O。

select a.user_name,b.dev_no

   from user_info a, dev_info b

   where a.user_id > b.user_id;

Plan

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

SELECT STATEMENT ptimizer=CHOOSE (Cost=7 Card=336 Bytes=16128)

 MERGE JOIN (Cost=7 Card=336 Bytes=16128)

 SORT (JOIN) (Cost=4 Card=82 Bytes=1968)

       TABLE ACCESS (FULL) OF 'USER_INFO' (Cost=2 Card=82 Bytes=1968)

 SORT (JOIN) (Cost=4 Card=82 Bytes=1968)

       TABLE ACCESS (FULL) OF 'DEV_INFO' (Cost=2 Card=82 Bytes=1968)

可以通过在SQL语句中添加HINTS,强制ORACLE优化器产生排序合并连接的执行计划。

select /*+ use_merge(a b) */ a.user_name,b.dev_no

   from user_info a, dev_info b

   where a.user_id > b.user_id;

   排序合并连接是基于RBO的。

4 笛卡尔连接   (CARTESIAN JOIN)

   笛卡尔连接是指在sql语句中没有写出表连接的条件，优化器把第一个表的每一条记录和第二个表的所有纪录相连接。如果第一个表的纪录数为m, 第二个表的纪录数为m,则会产生m*n条纪录数。

   下面的查询，未指名连接条件，就会产生笛卡尔连接。

   select a.user_name,b.dev_no

 from user_info a ,dev_info b;

   由于笛卡尔连接会导致性能很差的SQL,因此一般也很少用到。

 

5 哈希连接

当内存能够提供足够的空间时,哈希(HASH)连接是Oracle优化器通常的选择。哈希连接中，优化器根据统计信息，首先选择两个表中的小表，在内存中建立这张表的基于连接键的哈希表；优化器再扫描表连接中的大表，将大表中的数据与哈希表进行比较，如果有相关联的数据，则将数据添加到结果集中。

    当表连接中的小表能够完全cache到可用内存的时候，哈希连接的效果最佳。哈希连接的成本只是两个表从硬盘读入到内存的成本。

    但是，如果哈希表过大而不能全部cache到可用内存时，优化器将会把哈希表分成多个分区，再将分区逐一cache到内存中。当表的分区超过了可用内存时，分区的部分数据就会临时地写到磁盘上的临时表空间上。因此，分区的数据写磁盘时，比较大的区间（EXTENT）会提高I/O性能。ORACLE推荐的临时表空间的区间是1MB。临时表空间的区间大小由UNIFORM. SIZE指定。

当哈希表构建完成后，进行下面的处理：

1）  第二个大表进行扫描

2）  如果大表不能完全cache到可用内存的时候，大表同样会分成很多分区

3）  大表的第一个分区cache到内存

4）  对大表第一个分区的数据进行扫描，并与哈希表进行比较，如果有匹配的纪录，添加到结果集里面

5）  与第一个分区一样，其它的分区也类似处理。

6）  所有的分区处理完后，ORACLE对产生的结果集进行归并，汇总，产生最终的结果。

当哈希表过大或可用内存有限，哈希表不能完全CACHE到内存。随着满足连接条件的结果集的增加，可用内存会随之下降，这时已经CACHE到内存的数据可能会重新写回到硬盘去。如果出现这种情况，系统的性能就会下降。

    当连接的两个表是用等值连接并且表的数据量比较大时，优化器才可能采用哈希连接。哈希连接是基于CBO的。只有在数据库初始化参数HASH_JOIN_ENABLED设为True,并且为参数PGA_AGGREGATE_TARGET设置了一个足够大的值的时候,Oracle才会使用哈希边连接。HASH_AREA_SIZE是向下兼容的参数,但在Oracle9i之前的版本中应当使用HASH_AREA_SIZE。当使用ORDERED提示时,FROM子句中的第一张表将用于建立哈希表。

   select  a.user_name,b.dev_no

   from user_info a, dev_info b

   where a.user_id = b.user_id;

Plan

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

   0      SELECT STATEMENT ptimizer=CHOOSE (Cost=5 Card=82 Bytes=3936

          )

   1    0   HASH JOIN (Cost=5 Card=82 Bytes=3936)

   2    1     TABLE ACCESS (FULL) OF 'USER_INFO' (Cost=2 Card=82 Bytes

          =1968)

   3    1     TABLE ACCESS (FULL) OF 'DEV_INFO' (Cost=2 Card=82 Bytes=

          1968)

可以通过在SQL语句中添加HINTS,强制ORACLE优化器产生哈希连接的执行计划。

select /*+ use_hash(a b)*/ a.user_name,b.dev_no

   from user_info a, dev_info b

   where a.user_id = b.user_id;

当缺少有用的索引时，哈希连接比嵌套循环连接更加有效。哈希连接也可能比嵌套循环连接更快，因为处理内存中的哈希表比检索B_树索引更加迅速。

 

6 索引连接

如果一组已存在的索引包含了查询所需要的所有信息，那么优化器将在索引中有选择地生成一组哈希表。可通过范围或者快速全局扫描访问到每一个索引，而选择何种扫描方式取决于WHERE子句中的可有条件。在一张表有大量的列，而您只想访问有限的列时，这种方法非常有效。WHERE子句约束条件越多，执行速度越快。因为优化器在评估执行查询的优化路径时，将把约束条件作为选项看待。您必须在合适的列（那些满足整个查询的列）上建立索引，这样可以确保优化器将索引连接作为可选项之一。这个任务通常牵涉到在没有索引，或者以前没有建立联合索引的列上增加索引。相对于快速全局扫描，连接索引的优势在于：快速全局扫描只有一个单一索引满足整个查询;索引连接可以有多个索引满足整个查询。

假设表dev_info上有两个索（一个在dev_no,一个在dev_type 上）。

作如下的查询

select   dev_no,dev_type

from user_info

where   user_id =  ‘U101010’

and     dev_type  =  ‘1010’;

二 几种主要表连接的比较

类别	嵌套循环连接	排序合并连接	哈希连接
提示	USE_NL	USE_MERGE	USE_HASH
使用的条件	任何连接	主要用于不等价连接，如<、<=、 >、 >=; 但是不包括 <>	·仅用于等价连接
相关资源	CPU、磁盘I/O	内存、临时空间	内存、临时空间
特点	当有高选择性索引或进行限制性搜索时效率比较高，能够快速返回第一次的搜索结果。	当缺乏索引或者索引条件模糊时，排序合并连接比嵌套循环有效。	当缺乏索引或者索引条件模糊时，哈希连接连接比嵌套循环有效。通常比排序合并连接快。 在数据仓库环境下，如果表的纪录数多，效率高。
缺点	当索引丢失或者查询条件限制不够时，效率很低； 当表的纪录数多时，效率低。	所有的表都需要排序。它为最优化的吞吐量而设计，并且在结果没有全部找到前不返回数据。	为建立哈希表，需要大量内存。第一次的结果返回较慢。

 

三 结束语

    深入地理解和掌握oracle的表连接对于优化数据库的性能至关重要。由于优化器选择方式的不同，以及统计信息的缺失或统计信息的不准确，ORACLE自动选择的表连接方式不一定是最优的。当SQL语句的执行效率很低时，可通过auto trace对执行计划进行跟踪和分析。当出现多表连接时，需要仔细分析是否有更佳的连接条件。根据系统的特点，必要时可以在SQL中添加HINTS,从而改变SQL的执行计划，从而达到性能优化的目的。