当前位置: 首页 > 调优 > 正文

表的连接方式介绍(NESTED LOOP, SORT MERGE JOIN, HASH JOIN )



循环嵌套链接(NESTED LOOP)

嵌套循环链接的内部处理的流程如下。
  • Oracle 优化器根据基于规则RBO或基于成本CBO的原则,选择两个表中的一个作为驱动表,并指定其为外部表。
  • Oracle 优化器再将另外一个表指定为内部表。
  • Oracle从外部表中读取第一行,然后和内部表中的数据逐一进行对比,所有匹配的记录放在结果集中。
  • Oracle读取外部表中的第二行,再和内部表中的数据逐一进行对比,所有匹配的记录添加到结果集中。
  • 重复上述步骤,直到外部表中的所有记录全部处理完。
  • 最后产生满足要求的结果集。

  使用嵌套循环链接是一种从结果集中提取第一批记录最快速的方法。在驱动行源表(就是正在查找的记录)较小或者内部行源表已链接的列有惟一的索引或高度可选的非惟一索引时, 嵌套循环链接效果是比较理想的。嵌套循环链接比其他链接方法有优势,它可以快速地从结果集中提取第一批记录,而不用等待整个结果集完全确定下来。这样,在理想情况下,终端用户就可以通过查询屏幕查看第一批记录,而在同时读取其他记录。不管如何定义链接的条件或者模式,任何两行记录源可以使用嵌套循环链接,所以嵌套循环链接是非常灵活的。
 
  然而,如果内部行源表(读取的第二张表)已链接的列上不包含索引或者索引不是高度可选时,嵌套循环链接效率是很低的。如果驱动表的记录非常庞大时,其他的链接方法可能更加有效。一般在nested loop中, 驱动表满足条件结果集不大,被驱动表的链接字段要有索引,这样就有nested loop。如果驱动表返回记录太多,就不适合nested loops了。如果链接字段没有索引,则适合走hash join,因为不需要索引。可以通过在SQL语句中添加HINTS,强制Oracle优化器产生嵌套循环链接的执行计划。

嵌套循环示例
被驱动表连接列创建索引
SQL> create index idx_t2 on t2(col2);
Index created.


当前数据库版本
SQL> select * from v$version;
BANNER
————————————————————————————————————————
Oracle Database 11g Enterprise Edition Release 11.2.0.4.0 – 64bit Production
PL/SQL Release 11.2.0.4.0 – Production
CORE    11.2.0.4.0      Production
TNS for Linux: Version 11.2.0.4.0 – Production
NLSRTL Version 11.2.0.4.0 – Production



查询方法一
SQL> select /*+ ordered use_nl(t2)*/ t1.col1,t1.col2,t2.col3 from t1,t2 where t1.col2=t2.col2;
Execution Plan
———————————————————-
Plan hash value: 1054738919
—————————————————————————————
| Id  | Operation                    | Name   | Rows  | Bytes | Cost (%CPU)| Time     |
—————————————————————————————
|   0 | SELECT STATEMENT             |        |     3 |    60 |     6   (0)| 00:00:01 |
|   1 |  NESTED LOOPS                |        |     3 |    60 |     6   (0)| 00:00:01 |
|   2 |   NESTED LOOPS               |        |     3 |    60 |     6   (0)| 00:00:01 |
|   3 |    TABLE ACCESS FULL         | T1     |     3 |    45 |     3   (0)| 00:00:01 |
|*  4 |    INDEX RANGE SCAN          | IDX_T2 |     1 |       |     0   (0)| 00:00:01 |
|   5 |   TABLE ACCESS BY INDEX ROWID| T2     |     1 |     5 |     1   (0)| 00:00:01 |
—————————————————————————————
Predicate Information (identified by operation id):
—————————————————
   4access("T1"."COL2"="T2"."COL2")

  

查询方法二 
SQL> select /*+ use_nl(t1 t2)*/ t1.col1,t1.col2,t2.col3 from t1,t2 where t1.col2=t2.col2;
Execution Plan
———————————————————-
Plan hash value: 1054738919
—————————————————————————————
| Id  | Operation                    | Name   | Rows  | Bytes | Cost (%CPU)| Time     |
—————————————————————————————
|   0 | SELECT STATEMENT             |        |     3 |    60 |     6   (0)| 00:00:01 |
|   1 |  NESTED LOOPS                |        |     3 |    60 |     6   (0)| 00:00:01 |
|   2 |   NESTED LOOPS               |        |     3 |    60 |     6   (0)| 00:00:01 |
|   3 |    TABLE ACCESS FULL         | T1     |     3 |    45 |     3   (0)| 00:00:01 |
|*  4 |    INDEX RANGE SCAN          | IDX_T2 |     1 |       |     0   (0)| 00:00:01 |
|   5 |   TABLE ACCESS BY INDEX ROWID| T2     |     1 |     5 |     1   (0)| 00:00:01 |
—————————————————————————————
Predicate Information (identified by operation id):
—————————————————
   4access("T1"."COL2"="T2"."COL2")

  





群集链接( CLUSTER JOIN )

  群集链接实际上是嵌套循环链接的一种特例。如果所链接的两张源表是群集中的表,即两张表属于同一个段(Segment),那么Oracle能够使用群集链接。处理的过程是:Oracle从第一张行源表中读取第一行,然后在第二张行源表中使用Cluster索引查找能够匹配到的记录;继续上面的步骤处理行源表中的第二行,直到所有的记录全部处理完。群集链接的效率极高,因为两个参加链接的行源表实际上处于同一个物理块上。但是,群集链接也有其限制,没有群集的两个表不可能用群集链接。所以,群集链接实际上很少使用。



排序合并链接( SORT MERGE JOIN )

排序合并链接内部处理的流程如下。
  • 优化器判断第一个源表是否已经排序,如果已经排序,则到第3步,否则到第2步。
  • 第一个源表排序。
  • 优化器判断第二个源表是否已经排序,如果已经排序,则到第5步,否则到第4步。
  • 第二个源表排序。
  • 已经排过序的两个源表进行合并操作,并生成最终的结果集。

在缺乏数据的选择性或者可用的索引时,或者两个源表都过于庞大(所选的数据超过表记录数的5%)时,排序合并链接将比嵌套循环链接更加高效。排列合并链接需要比较大的临时内存块,以用于排序,这将导致在临时表空间占用更多的内存和磁盘I/O。

排序合并连接示例
SQL> select /*+ ordered use_merge(t2)*/ t1.col1,t1.col2,t2.col3 from t1,t2 where t1.col2=t2.col2;
Execution Plan
———————————————————-
Plan hash value: 412793182
—————————————————————————-
| Id  | Operation           | Name | Rows  | Bytes | Cost (%CPU)| Time     |
—————————————————————————-
|   0 | SELECT STATEMENT    |      |     3 |    60 |     8  (25)| 00:00:01 |
|   1 |  MERGE JOIN         |      |     3 |    60 |     8  (25)| 00:00:01 |
|   2 |   SORT JOIN         |      |     3 |    45 |     4  (25)| 00:00:01 |
|   3 |    TABLE ACCESS FULL| T1   |     3 |    45 |     3   (0)| 00:00:01 |
|*  4 |   SORT JOIN         |      |     3 |    15 |     4  (25)| 00:00:01 |
|   5 |    TABLE ACCESS FULL| T2   |     3 |    15 |     3   (0)| 00:00:01 |
—————————————————————————-
Predicate Information (identified by operation id):
—————————————————
   4access("T1"."COL2"="T2"."COL2")
       filter("T1"."COL2"="T2"."COL2")
Note
—–
   – dynamic sampling used for this statement (level=2)






笛卡尔链接 ( CARTESIAN JOIN )

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

笛卡尔链接示例

下面的查询,未指名链接条件,就会产生笛卡尔链接。
SQL> select t1.col1,t1.col2,t2.col3 from t1,t2;
9 rows selected.
Execution Plan
———————————————————-
Plan hash value: 787647388
—————————————————————————–
| Id  | Operation            | Name | Rows  | Bytes | Cost (%CPU)| Time     |
—————————————————————————–
|   0 | SELECT STATEMENT     |      |     9 |   162 |     9   (0)| 00:00:01 |
|   1 |  MERGE JOIN CARTESIAN|      |     9 |   162 |     9   (0)| 00:00:01 |
|   2 |   TABLE ACCESS FULL  | T1   |     3 |    45 |     3   (0)| 00:00:01 |
|   3 |   BUFFER SORT        |      |     3 |     9 |     6   (0)| 00:00:01 |
|   4 |    TABLE ACCESS FULL | T2   |     3 |     9 |     2   (0)| 00:00:01 |
—————————————————————————–
Note
—–
   – dynamic sampling used for this statement (level=2)

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






哈希链接( HASH JOIN )

    当内存能够提供足够的空间时,哈希(HASH)链接是Oracle优化器通常的选择。哈希链接中,优化器根据统计信息,首先选择两个表中的小表,在内存中建立这张表的基于链接键的哈希表;优化器再扫描表链接中的大表,将大表中的数据与哈希表进行比较,如果有相关联的数据,则将数据添加到结果集中。
   
    当表链接中的小表能够完全cache到可用内存的时候,哈希链接的效果最佳。哈希链接的成本只是两个表从硬盘读入到内存的成本。但是,如果哈希表过大而不能全部cache到可用内存时,优化器将会把哈希表分成多个分区,再将分区逐一cache到内存中。当表的分区超过了可用内存时,分区的部分数据就会临时地写到磁盘上的临时表空间上。因此,分区的数据写磁盘时,比较大的区间(EXTENT)会提高I/O性能。当哈希表构建完成后,进行下面的处理。
  • 第二个大表进行扫描。
  • 如果大表不能完全cache到可用内存的时候,大表同样会分成很多分区。
  • 大表的第一个分区cache到内存。
  • 对大表第一个分区的数据进行扫描,并与哈希表进行比较,如果有匹配的记录,添加到结果集里面。
  • 与第一个分区一样,其他的分区也类似处理。
  • 所有的分区处理完后,Oracle对产生的结果集进行归并,汇总,产生最终的结果。

   当哈希表过大或可用内存有限,哈希表不能完全Cache到内存。随着满足链接条件的结果集的增加,可用内存会随之下降,这时已经Cache到内存的数据可能会重新写回到硬盘去。如果出现这种情况,系统的性能就会下降。当链接的两个表是用等值链接并且表的数据量比较大时,优化器才可能采用哈希链接。哈希链接是基于CBO的。只有在数据库初始化参数HASH_JOIN_ENABLED设为True,并且为参数PGA_AGGREGATE_TARGET设置了一个足够大的值的时候,Oracle才会使用哈希链接。HASH_AREA_SIZE是向下兼容的参数,但在Oracle 9i之前的版本中应当使用HASH_AREA_SIZE。当使用ORDERED提示时,FROM子句中的第一张表将用于建立哈希表。可以通过在SQL语句中添加HINTS /*+ use_hash(a b)*/  强制Oracle优化器产生哈希链接的执行计划。
SQL> select /*+ use_hash(t1 t2)*/t1.col1,t1.col2,t2.col3 from t1,t2 where t1.col2=t2.col2;
Execution Plan
———————————————————-
Plan hash value: 1838229974
—————————————————————————
| Id  | Operation          | Name | Rows  | Bytes | Cost (%CPU)| Time     |
—————————————————————————
|   0 | SELECT STATEMENT   |      |     3 |    60 |     6   (0)| 00:00:01 |
|*  1 |  HASH JOIN         |      |     3 |    60 |     6   (0)| 00:00:01 |
|   2 |   TABLE ACCESS FULL| T1   |     3 |    45 |     3   (0)| 00:00:01 |
|   3 |   TABLE ACCESS FULL| T2   |     3 |    15 |     3   (0)| 00:00:01 |
—————————————————————————
Predicate Information (identified by operation id):
—————————————————
   1access("T1"."COL2"="T2"."COL2")


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






反连接( Anti Join )

反连接是一种特殊的连接类型,当做子查询展开时,Oracle经常会把那些外部where条件为NOT EXISTS、NOT IN、<>ALL的子查询转换成对应的反连接。
反连接示例

分别执行以下三条SQL
select * from t1 where col2 not in (select col2 from t2);
select * from t1 where col2 <>all(select col2 from t2);
select * from t1 where not exists (select 1 from t2 where col2=t1.col2);

SQL> select * from t1 where col2 not in (select col2 from t2);
      COL1 CO
———- —
         3 C
Execution Plan
———————————————————-
Plan hash value: 1275484728
—————————————————————————
| Id  | Operation          | Name | Rows  | Bytes | Cost (%CPU)| Time     |
—————————————————————————
|   0 | SELECT STATEMENT   |      |     3 |    51 |     6   (0)| 00:00:01 |
|*  1 |  HASH JOIN ANTI NA |      |     3 |    51 |     6   (0)| 00:00:01 |
|   2 |   TABLE ACCESS FULL| T1   |     3 |    45 |     3   (0)| 00:00:01 |
|   3 |   TABLE ACCESS FULL| T2   |     3 |     6 |     3   (0)| 00:00:01 |
—————————————————————————
Predicate Information (identified by operation id):
—————————————————
   1access("COL2"="COL2")

SQL> select * from t1 where col2 <>all(select col2 from t2);
      COL1 CO
———- —
         3 C
Execution Plan
———————————————————-
Plan hash value: 1275484728
—————————————————————————
| Id  | Operation          | Name | Rows  | Bytes | Cost (%CPU)| Time     |
—————————————————————————
|   0 | SELECT STATEMENT   |      |     3 |    51 |     6   (0)| 00:00:01 |
|*  1 |  HASH JOIN ANTI NA |      |     3 |    51 |     6   (0)| 00:00:01 |
|   2 |   TABLE ACCESS FULL| T1   |     3 |    45 |     3   (0)| 00:00:01 |
|   3 |   TABLE ACCESS FULL| T2   |     3 |     6 |     3   (0)| 00:00:01 |
—————————————————————————
Predicate Information (identified by operation id):
—————————————————
   1access("COL2"="COL2")

SQL> select * from t1 where not exists (select 1 from t2 where col2=t1.col2);
      COL1 CO
———- —
         3 C
Execution Plan
———————————————————-
Plan hash value: 1534930707
—————————————————————————–
| Id  | Operation          | Name   | Rows  | Bytes | Cost (%CPU)| Time     |
—————————————————————————–
|   0 | SELECT STATEMENT   |        |     3 |    51 |     3   (0)| 00:00:01 |
|   1 |  NESTED LOOPS ANTI |        |     3 |    51 |     3   (0)| 00:00:01 |
|   2 |   TABLE ACCESS FULL| T1     |     3 |    45 |     3   (0)| 00:00:01 |
|*  3 |   INDEX RANGE SCAN | IDX_T2 |     1 |     2 |     0   (0)| 00:00:01 |
—————————————————————————–
Predicate Information (identified by operation id):
—————————————————
   3access("COL2"="T1"."COL2")

   
由于表t1 t2的各自连接列col2上均没有NULL值,在这种情况下,上面三个SQL其实是等价的。所有的执行计划里面都有ANTI,说明在执行上面的SQL时,的确是用的反连接。




当表的连接列中有了NULL值的时候,这三个SQL就不完全等价了,这种影响又细分为两种情况。
1.t1表的连接列上出现NULL值
SQL> insert into t1 values (4,null);
1 row created.

SQL> commit;
Commit complete.

SQL> select * from t1;
      COL1 COL2
———- —–
         1 A
         2 B
         3 C
         4

–重新执行刚才的三个SQL

SQL> select * from t1 where col2 not in (select col2 from t2);
      COL1 COL2
———- —–
         3 C

SQL> select * from t1 where col2 <>all(select col2 from t2);
      COL1 COL2
———- —–
         3 C

SQL> select * from t1 where not exists (select 1 from t2 where col2=t1.col2);
      COL1 COL2
———- —–
         3 C
         4



2.T2表的连接列出现NULL
SQL> delete from t1 where col1=4;
1 row deleted.

SQL> insert into t2 values (null,‘E2’);
1 row created.

SQL> commit;
Commit complete.

SQL> select * from t2;
COL2  COL3
—– —-
A     A2
B     B2
D     D2
      E2

–重新执行上面的三个SQL
SQL> select * from t1 where col2 not in (select col2 from t2);
no rows selected

SQL> select * from t1 where col2 <>all(select col2 from t2);
no rows selected

SQL> select * from t1 where not exists (select 1 from t2 where col2=t1.col2);
      COL1 COL2
———- —–
         3 C

        
        
结论:
(1) 当表的连接列出现了NULL值,上述范例中的SQL就不等价了。
(2) NOT IN 和 <>ALL 对NULL值敏感,这意味着NOT IN后面的子查询或常量集合一旦有NULL值出现,则整个SQL的执行结果就会为NULL,不会包含任何记录  
(3) NOT EXISTS对NULL值不敏感,也就是说NULL值对NOT EXISTS的执行结果不会有什么影响。



  为了解决NOT IN 和 <>ALL 对NULL值敏感,Oracle推出了改良的反连接,被称为Null-Aware Anti Join,执行计划中出现的HASH JOIN ANTI NA,这个关键字NA就是Null-Aware的缩写,这里oracle就是要告知所采用的不是普通的hash反连接,而是改良的反连接,是可以处理null值的。Oracle是否启用Null-Aware Anti Join受隐含参数_OPTIMIZER_NULL_AWARE_ANTIJOIN控制,默认是TRUE,表示启用Null-Aware Anti Join

改良反连接示例
如果把该隐含参数改为FALSE,则Oracle不能再用改良反连接,而又因为NOT IN对NULL值敏感,所以Oracle此时也不能用普通的反连接。
SQL> alter session set "_OPTIMIZER_NULL_AWARE_ANTIJOIN" = false;
Session altered.

SQL> select * from t1 where col2 <>all(select col2 from t2);
      COL1 CO
———- —
         3 C
Execution Plan
———————————————————-
Plan hash value: 895956251
—————————————————————————
| Id  | Operation          | Name | Rows  | Bytes | Cost (%CPU)| Time     |
—————————————————————————
|   0 | SELECT STATEMENT   |      |     1 |    15 |     5   (0)| 00:00:01 |
|*  1 |  FILTER            |      |       |       |            |          |
|   2 |   TABLE ACCESS FULL| T1   |     3 |    45 |     3   (0)| 00:00:01 |
|*  3 |   TABLE ACCESS FULL| T2   |     3 |     6 |     2   (0)| 00:00:01 |
—————————————————————————
Predicate Information (identified by operation id):
—————————————————
   1 – filter( NOT EXISTS (SELECT 0 FROM "T2" "T2" WHERE
              LNNVL("COL2"<>:B1)))
   3 – filter(LNNVL("COL2"<>:B1))

可以看到这里的执行计划走了FILTER,而不再是HASH JOIN ANTI NA。





半连接( Semi Join )

半连接是一种特殊的连接类型,与反连接一样,Oracle数据库里面也没有相关的关键字可以在SQL文本中专门表示半连接。半连接和普通的内连接不同,半连接会去重。

半连接示例

分别执行以下三条SQL
select * from t1 where col2 in (select col2 from t2);
select * from t1 where col2=any (select col2 from t2);
select * from t1 where exists (select 1 from t2 where col2=t1.col2);

SQL> select * from t1 where col2 in (select col2 from t2);
      COL1 CO
———- —
         1 A
         2 B
Execution Plan
———————————————————-
Plan hash value: 3783859632
—————————————————————————–
| Id  | Operation          | Name   | Rows  | Bytes | Cost (%CPU)| Time     |
—————————————————————————–
|   0 | SELECT STATEMENT   |        |     3 |    51 |     3   (0)| 00:00:01 |
|   1NESTED LOOPS SEMI |        |     3 |    51 |     3   (0)| 00:00:01 |
|   2 |   TABLE ACCESS FULL| T1     |     3 |    45 |     3   (0)| 00:00:01 |
|*  3 |   INDEX RANGE SCAN | IDX_T2 |     3 |     6 |     0   (0)| 00:00:01 |
—————————————————————————–   

SQL> select * from t1 where col2=any (select col2 from t2);
      COL1 CO
———- —
         1 A
         2 B
Execution Plan
———————————————————-
Plan hash value: 3783859632
—————————————————————————–
| Id  | Operation          | Name   | Rows  | Bytes | Cost (%CPU)| Time     |
—————————————————————————–
|   0 | SELECT STATEMENT   |        |     3 |    51 |     3   (0)| 00:00:01 |
|   1NESTED LOOPS SEMI |        |     3 |    51 |     3   (0)| 00:00:01 |
|   2 |   TABLE ACCESS FULL| T1     |     3 |    45 |     3   (0)| 00:00:01 |
|*  3 |   INDEX RANGE SCAN | IDX_T2 |     3 |     6 |     0   (0)| 00:00:01 |
—————————————————————————–

SQL> select * from t1 where exists (select 1 from t2 where col2=t1.col2);
      COL1 CO
———- —
         1 A
         2 B
Execution Plan
———————————————————-
Plan hash value: 3783859632
—————————————————————————–
| Id  | Operation          | Name   | Rows  | Bytes | Cost (%CPU)| Time     |
—————————————————————————–
|   0 | SELECT STATEMENT   |        |     3 |    51 |     3   (0)| 00:00:01 |
|   1NESTED LOOPS SEMI |        |     3 |    51 |     3   (0)| 00:00:01 |
|   2 |   TABLE ACCESS FULL| T1     |     3 |    45 |     3   (0)| 00:00:01 |
|*  3 |   INDEX RANGE SCAN | IDX_T2 |     3 |     6 |     0   (0)| 00:00:01 |
—————————————————————————–

上述三个SQL的执行结果是一样的,而且它们的执行计划的现实内容均有关键字SEMI,这个关键字就说明Oracle执行这三个SQL是在用半连接。

 




几种主要表连接的比较

类别

嵌套循环链接

排序合并链接

哈希链接

优化器提示

USE_NL

USE_MERGE

USE_HASH

使用的条件

任何链接

主要用于不等价链接,如< <= > >=;但是不包括<>

仅用于等价链接

相关资源

CPU、磁盘I/O

内存、临时空间

内存、临时空间

特点

当有高选择性索引或进行限制性搜索时效率比较高,能够快速返回第一次的搜索结果

当缺乏索引或者索引条件模糊时,排序合并链接比嵌套循环有效

当缺乏索引或者索引条件模糊时,哈希链接比嵌套循环有效。通常比排序合并链接快。在数据仓库环境下,如果表的记录数多,效率高

缺点

当索引丢失或者查询条件限制不够时,效率很低;当表的记录数多时,效率低

所有的表都需要排序。它为最优化的吞吐量而设计,并且在结果没有全部找到前不返回数据

为建立哈希表,需要大量内存。第一次的结果返回较慢







本文固定链接: http://www.htz.pw/2015/04/09/%e8%a1%a8%e7%9a%84%e8%bf%9e%e6%8e%a5%e6%96%b9%e5%bc%8f%e4%bb%8b%e7%bb%8dnested-loop-sort-merge-join-hash-join.html | 认真就输

该日志由 huangtingzhong 于2015年04月09日发表在 调优 分类下, 通告目前不可用,你可以至底部留下评论。
原创文章转载请注明: 表的连接方式介绍(NESTED LOOP, SORT MERGE JOIN, HASH JOIN ) | 认真就输
关键字: , ,