Oracle的Filter,Nest loop,Merge sort join和Hash join(原创)

 Merge Sort Join
按照Merge Sort Join连接的两表地位完全相同。这种算法会把每个表按照连接列进行排序，生成两个排序集。然后对两个排序集进行一次遍历便可以得到最终结果集。这个算法的特点是，每个表都需要排序，排序后都需要遍历一次。

以下面的例子说明，Merge Sort Join的执行过程如下：
SQL> explain plan for select /*+ use_merge(tabs,cols) */*
  2   from tabs,cols where tabs.table_name=cols.table_name and tabs.owner like 'SC%' ;
Explained.
SQL>  select * from table(dbms_xplan.display);
PLAN_TABLE_OUTPUT
--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Plan hash value: 2945511789
------------------------------------------------------------------------------------
| Id  | Operation           | Name | Rows  | Bytes |TempSpc| Cost (%CPU)| Time     |
------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT    |      |   227 | 66738 |       |  1264   (1)| 00:00:16 |
|   1 |  MERGE JOIN         |      |   227 | 66738 |       |  1264   (1)| 00:00:16 |
|   2 |   SORT JOIN         |      |     5 |  1025 |       |    13   (8)| 00:00:01 |
|*  3 |    TABLE ACCESS FULL| TABS |     5 |  1025 |       |    12   (0)| 00:00:01 |
|*  4 |   SORT JOIN         |      | 57687 |  5013K|    11M|  1251   (1)| 00:00:16 |
|   5 |    TABLE ACCESS FULL| COLS | 57687 |  5013K|       |    65   (4)| 00:00:01 |
PLAN_TABLE_OUTPUT
--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
------------------------------------------------------------------------------------
Predicate Information (identified by operation id):
---------------------------------------------------
   3 - filter("TABS"."OWNER" LIKE 'SC%')
   4 - access("TABS"."TABLE_NAME"="COLS"."TABLE_NAME")
       filter("TABS"."TABLE_NAME"="COLS"."TABLE_NAME")
Note
-----
PLAN_TABLE_OUTPUT
--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
   - dynamic sampling used for this statement
23 rows selected.
1、根据tabs表的where条件，查找出符合条件的结果集。

2、以全表扫描的方式，扫描出cols表中的结果集。

3、按照table_name列对tabs表进行排序

4、按照table_name列对cols表进行排序

5、对两个有序的结果集进行合并，并返回最终记录集。

Sort Merge主要的开销在于对两表连接的排序，已经在连接关联列上已经进行了排序，则该连接操作就不需要再进行 sort 操作，这样可以大大提高这种连接操作的连接速度，特别是对于较大的表。

Nest Loop Join原理
Nest Loop Join是通过两层嵌套循环进行依次的匹配操作，最后返回结果集合。SQL语句只是描述出希望连接的对象和规则，而执行计划和执行操作要切实将一行行的记录进行匹配。
Nest Loop Join的操作过程很简单，很像我们最简单的排序检索算法，两层循环结构。进行连接的两个数据集合（数据表）分别称为驱动表(外侧表)和被驱动表(内测 表)。首先处理驱动表中每一行符合条件的数据，之后每一行数据和被驱动表进行连接匹配操作。最后可以获取到结果集合。NESTED LOOPS等于cost = outer access cost + (inner access cost * outer cardinality)，故驱动表较小cost较低也就很好理解

NESTED LOOPS 有其它连接方法没有的的一个优点是：

可以先返回已经连接的行，而不必等待所有的连接操作处理完才返回数据，这可以实现快速的响应时间。  这是从连接操作中可以得到第一个匹配行的最快的方法之一，这种类型的连接可以用在需要快速响应的语句中，以响应速度为主要目标。

以下面的例子说明，Nest Loop Join的执行过程如下：

SQL> create table tabs as select * from dba_tables;
Table created
SQL> create table cols as select owner,table_name, column_name, data_type from dba_tab_cols;
Table created
SQL> explain plan for select /*+ use_nl(tabs,cols) */* from tabs,cols where tabs.table_name=cols.table_name and tabs.owner='SCOTT';
Explained.
SQL> select * from table(dbms_xplan.display);
PLAN_TABLE_OUTPUT
--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Plan hash value: 1483644320
---------------------------------------------------------------------------
| Id  | Operation          | Name | Rows  | Bytes | Cost (%CPU)| Time     |
---------------------------------------------------------------------------
|   0 | SELECT STATEMENT   |      |   228 |   128K|   322   (3)| 00:00:04 |
|   1 |  NESTED LOOPS      |      |   228 |   128K|   322   (3)| 00:00:04 |
|*  2 |   TABLE ACCESS FULL| TABS |     5 |  2435 |    12   (0)| 00:00:01 |
|*  3 |   TABLE ACCESS FULL| COLS |    46 |  4094 |    62   (4)| 00:00:01 |
---------------------------------------------------------------------------
PLAN_TABLE_OUTPUT
--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Predicate Information (identified by operation id):
---------------------------------------------------
   2 - filter("TABS"."OWNER"='SCOTT')
   3 - filter("TABS"."TABLE_NAME"="COLS"."TABLE_NAME")
Note
-----
   - dynamic sampling used for this statement
20 rows selected.
1、读取驱动表tabs表中的第一条符合条件的记录
2、遍历被驱动表COLS，根据条件tabs.table_name=cols.table_name找到符合要求的记录，每找到一条记录立即返回给用户。

3、重复步骤1、2直到驱动表tabs中的记录都被处理，才能完成整个连接操作。

Note:从上述过程来看驱动表与被驱动表的遍历没有先后关系，是同时进行的
该算法的特点:

对驱动表tabs做一次遍历，而对被驱动表cols进行多次遍历，遍历次数等于驱动表tabs中处理的记录数量。
该算法返回第一条记录的速度非常快，不需要排序操作，同时可以用于非等值连接。
Nest Loop Join优化

如上文所述，Nest Loop Join的过程是双层嵌套循环的过程，所以外层嵌套的次数应越少越好，故应将小表或者返回结果集较小的表作为驱动表为佳。大部分情况下遵循这个指导原则会降低SQL的IO。有时不遵循这个原则会得到更好的效率。 

如 果在驱动表或者被驱动表的连接条件列上存在索引，在进行Nest Loop Join的时候，驱动表和被驱动表可以直接确定符合连接条件的被驱动表数据行对应的rowid。不需要直接对被驱动表进行检索，就可以获取到rowid 了。由于索引对应的体积一般要远远小于Inner Table，所以进行的块读取要少很多。所以连接列上存在索引与否，一定程度上也影响了Nest Loop Join的效率。
如 果驱动表比较小，并且在被驱动表上有唯一索引，或有高选择性非唯一索引时，使用这种方法可以得到较好的效率。如果不使用并行操作，最好的驱动表是那些应用 了 where 限制条件后，可以返回较少行数据的的表，所以大表也可能称为驱动表，关键看限制条件。对于并行查询，我们可以选择大表作为驱动表，因为大表可以充分利用并 行功能。当然，有时对查询使用并行操作并不一定会比查询不使用并行操作效率高，因为
最后可能每个表只有很少的行符合限制条件，而且还要看你的硬件配置是否可以支持并行(如是否有多个CPU，多个硬盘控制器)，所以要具体问题具体对待。
Filter

filter 的操作是对外表的每一行，都要对内表执行一次全表扫描，他其实很像我们熟悉的neested loop，但它的独特之处在于会维护一个hash table。其实filter的性能实际上跟列值distinct数有关，oracle在执行的时候实际上做了很大优化，最坏情况下才会出现对外表每一行 执行一次filter操作，如果distinct值比较少，那执行效率还是非常高的，甚至有可能比nl更高。

通过下面的例子来具体解释Filter和Nest loop的区别。

SQL> explain plan for select tabs.* from tabs where  exists (select /*+ no_unnest */ cols.table_name from cols where tabs.table_name=cols.table_name) and tabs.owner like 'SC%';
Explained.
SQL> select * from table(dbms_xplan.display);
PLAN_TABLE_OUTPUT
--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Plan hash value: 2962517934
---------------------------------------------------------------------------
| Id  | Operation          | Name | Rows  | Bytes | Cost (%CPU)| Time     |
---------------------------------------------------------------------------
|   0 | SELECT STATEMENT   |      |     1 |   205 |    17   (0)| 00:00:01 |
|*  1 |  FILTER            |      |       |       |            |          |
|*  2 |   TABLE ACCESS FULL| TABS |     5 |  1025 |    12   (0)| 00:00:01 |
|*  3 |   TABLE ACCESS FULL| COLS |   577 |  9809 |     2   (0)| 00:00:01 |
---------------------------------------------------------------------------
PLAN_TABLE_OUTPUT
--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Predicate Information (identified by operation id):
---------------------------------------------------
   1 - filter( EXISTS (SELECT /*+ NO_UNNEST */ 0 FROM "COLS" "COLS"
              WHERE "COLS"."TABLE_NAME"=:B1))
   2 - filter("TABS"."OWNER" LIKE 'SC%')
   3 - filter("COLS"."TABLE_NAME"=:B1)
Note
-----
   - dynamic sampling used for this statement
22 rows selected.
举例，从tabs的查询结果集中(owner like 'SC%')里取出table_name='A'，那么对于colsb表来说即select cols.table_name from cols where cols.table_name='A',如果条件满足，则将tabs表中，tabs.table_name='A'和table_name='A'的结果集存储在hash table里。然后接着从tabs取出table_name='B'，如果子查询依旧条件满足，那么将tabs.table_name='B'和table_name='B'的结果集存储在hash table里。接着假设tabs里有重复的table_name，例如我们第三次从取出tabs.table_name='B'，那么由于我们对于子查询来说，已经有输入输出对tabs.table_name='B'在hash table里了，ORACLE会非常智能的将tabs.table_name='B'的查询结果作为结果集，而不再对cols表进行全表扫描。这样，filter和neested loop相比,省去了一次全表扫描cols。这个hash table是有大小限制的，当被占满的时候，后续新的tabs.table_name的FILTER就类似neested loop了。
由此可见，当连接字段的distinct value值较小时，FILTER性能优于nested loop。

Hash Join
从Oracle 7.3开始，Hash Join正式进入优化器执行计划生成，只有CBO才能使用Hash Join操作。 在hash join算法中也有驱动表和被驱动表的概念。本质上说，Hash Join连接是借助Hash算法，连带小规模的Nest Loop Join，同时利用内存空间进行高速数据缓存检索的一种算法。

Hash join算法的一个基本思想就是根据小的row sources(称作build input，我们记较小的表为S，较大的表为B) 建立一个可以存在于hash area内存中的hash table，然后用大的row sources(称作probe input) 来探测前面所建的hash table。如果hash area内存不够大，hash table就无法完全存放在hash area内存中。针对这种情况，Oracle在连接键利用一个hash函数将build input和probe input分割成多个不相连的Bucket（分别记作Si和Bi），这个阶段叫做准备阶段；然后各自相应的Bucket，即Si和Bi再做Hash join，这个阶段叫做探测阶段。
如 果在计算完Hash Bucket后，针对某个Bucket所建的hash table还是太大的话，oracle就采用nested-loops hash join。所谓的nested-loops hash join就是对部分Si建立hash table，然后读取所有的Bi与所建的hash table做连接，然后再对剩余的Si建立hash table，再将所有的Bi与所建的hash table做连接，直至所有的Si都连接完了。
Hash Join算法有一个限制，就是它是在假设两张表在连接键上是均匀的，也就是说每个分区拥有差不多的数据。但是实际当中数据都是不均匀的，为了很好地解决这个问题，oracle引进了几种技术，位图向量过滤、角色互换、柱状图。

以下面的例子说明，Hash Join的执行过程如下：
SQL> explain plan for select /*+ use_hash(tabs,cols) */* from tabs,cols where tabs.table_name=cols.table_name and tabs.owner like 'SC%'
Explained.
SQL> set autotrace off
SQL> select * from table(dbms_xplan.display);
PLAN_TABLE_OUTPUT
--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Plan hash value: 1399132210
---------------------------------------------------------------------------
| Id  | Operation          | Name | Rows  | Bytes | Cost (%CPU)| Time     |
---------------------------------------------------------------------------
|   0 | SELECT STATEMENT   |      |   227 | 66738 |    78   (4)| 00:00:01 |
|*  1 |  HASH JOIN         |      |   227 | 66738 |    78   (4)| 00:00:01 |
|*  2 |   TABLE ACCESS FULL| TABS |     5 |  1025 |    12   (0)| 00:00:01 |
|   3 |   TABLE ACCESS FULL| COLS | 57687 |  5013K|    65   (4)| 00:00:01 |
---------------------------------------------------------------------------
PLAN_TABLE_OUTPUT
--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Predicate Information (identified by operation id):
---------------------------------------------------
   1 - access("TABS"."TABLE_NAME"="COLS"."TABLE_NAME")
   2 - filter("TABS"."OWNER" LIKE 'SC%')
Note
-----
   - dynamic sampling used for this statement
20 rows selected.

 1、计算小表的分区（bucket）数
决 定hash join的一个重要因素是小表的分区（bucket）数。这个数字由hash_area_size、hash_multiblock_io_count和 db_block_size参数共同决定。Oracle会保留hash area的20%来存储分区的头信息、hash位图信息和hash表。因此，这个数字的计算公式是：
Bucket数=0.8*hash_area_size/(hash_multiblock_io_count*db_block_size)
2、Hash计算  
根据结果集读取小表tabs数据（简称为R），并对每一条数据根据hash算法进行计算。Oracle采用两种hash算法进行计算，计算出能达到最快速度的hash值
（第一hash值和第二hash值）。而关于这些分区的全部hash值（第一hash值）就成为hash表。
3、存放数据到hash内存中
将经过hash算法计算的数据，根据各个bucket的hash值（第一hash值）分别放入相应的bucket中。第二hash值就存放在各条记录中。
4、创建hash位图
与此同时，也创建了一个关于这两个hash值映射关系的hash位图。
5、超出内存大小部分被移到磁盘
如果hash area被占满，那最大一个分区就会被写到磁盘（临时表空间）上去。任何需要写入到磁盘分区上的记录都会导致磁盘分区被更新。这样的话，就会严重影响性能，因此一定要尽量避免这种情况。
持续2～5步骤，直到整个表的数据读取完毕。
6、对分区排序
为了能充分利用内存，尽量存储更多的分区，Oracle会按照各个分区的大小将他们在内存中排序。
7、读取大表数据，进行hash匹配
接 下来就开始读取大表cols表（简称S）中的数据。按顺序每读取一条记录，计算它的hash值，并检查是否与内存中的分区的hash值一致。如果是，返回 join数据。如果内存中的分区没有符合的，就将S中的数据写入到一个新的分区中，这个分区也采用与计算R一样的算法计算出hash值。也就是说这些S中 的数据产生的新的分区数应该和R的分区集的分区数一样。这些新的分区被存储在磁盘（临时表空间）上。
8、完成大表全部数据的读取
一直按照7进行，直到大表中的所有数据的读取完毕。
9、处理没有join的数据
这个时候就产生了一大堆join好的数据和从R和S中计算存储在磁盘上的分区。
10、二次hash计算
从R和S的分区集中抽取出最小的一个分区，使用第二种hash函数计算出并在内存中创建hash表。采用第二种hash函数的原因是为了使数据分布性更好。
11、二次hash匹配
在从另一个数据源（与hash在内存的那个分区所属数据源不同的）中读取分区数据，与内存中的新hash表进行匹配。返回join数据。
12、完成全部hash join
继续按照9-11处理剩余分区，直到全部处理完毕。

注 意:hash算法中的位图包含了每个hash分区是否有值的信息。它记录了有数据的分区的hash值。这个位图的最大作用就是，如果S表中的数据没有与内 存中的hash表匹配上，先查看这个位图，已决定是否将没有匹配的数据写入磁盘。那些不可能匹配到的数据（即位图上对应的分区没有数据）就不再写入磁盘。

Hash Join的相关参数
HASH_JOIN_ENABLED
这个参数是控制查询计划是否采用hash join的“总开关”。它可以在会话级和实例级被修改。默认为TRUE，既可以（不是一定，要看优化器计算出来的代价）使用。如果设为FALSE，则禁止使用hash join。
HASH_AREA_SIZE
这 个参数控制每个会话的hash内存空间有多大。它也可以在会话级和实例级被修改。默认（也是推荐）值是sort area空间大小的两倍（2*SORT_AREA_SIZE）。要提高hash join的效率，就一定尽量保证sort area足够大，能容纳下整个小表的数据。但是因为每个会话都会开辟一个这么大的内存空间作为hash内存，所以不能过大（一般不建议超过2M）。在 Oracle9i及以后版本中，Oracle不推荐在dedicated server中使用这个参数来设置hash内存，而是推荐通过设置PGA_AGGRATE_TARGET参数来自动管理PGA内存。保留 HASH_AREA_SIZE只是为了向后兼容。在dedicated server中，hash area是从PGA中分配的，而在MTS(Multi-Threaded Server)中，hash area是从UGA中分配的。另外，还要注意的是，每个会话并不一定只打开一个hash area，因为一个查询中可能不止一个hash join，这是就会相应同时打开多个hash area。
HAHS_MULTIBLOCK_IO_COUNT
这 个参数决定每次读入hash area的数据块数量。因此它会对IO性能产生影响。他只能在init.ora或spfile中修改。在8.0及之前版本，它的默认值是1，在8i及以后 版本，默认值是0。一般设置为1-(65536/DB_BLOCK_SIZE)。在9i中，这个参数是一个隐藏参 数：_HASH_MULTIBLOCK_IO_COUNT，可以通过表x$ksppi查询和修改。另外，在MTS中，这个参数将不起作用（只会使用1）。 它的最大值受到OS的IO带宽和DB_BLOCK_SIZE的影响。既不能大于MAX_IO_SIZE/DB_BLOCK_SIZE。在8i及以后版本， 如果这个值设置为0，则表示在每次查询时，Oracle自己自动计算这个值。这个值对IO性能影响非常大，因此，建议不要修改这个参数，使用默认值0，让 Oracle自己去计算这个值。
如果一定要设置这个值，要保证以下不等式能成立：
     R/M < Po2(M/C)
其中，R表示小表的大小；M=HASH_AREA_SIZE*0.9；Po2(n)为n的2的次方C=HASH_MULTIBLOCK_IO_COUNT*DB_BLOCK_SIZE。

总结

1、Filter

原理上和Nest Loop Join类似，不同点在于维护hash table，总体上性能优于Nest Loop Join。
2、嵌套循环(Nest Loop Join):
对 于被连接的数据子集较小的情况，嵌套循环连接是较好的选择。在嵌套循环中，外表驱动内表，外表返回的每一行都要在内表中检索找到它匹配的行，因此整个查询 返回的结果集不能太大（大于10000不合适），要把返回子集较小的表作为外表（驱动表），而且在内表的连接字段上建议有索引。

3、排序合并连接（Sort Merge Join ）
通常情况下哈希连接的效果都比排序合并连接要好。然而如果行源已经被排过序，在执行排序合并连接时不需要再排序了，这时排序归并连接的性能会忧于哈希连接。
4、哈希连接(hash join):
哈希连接是大数据集连接时常用的方式，优化器使用两个表中较小的表，利用连接键在内存中建立散列表，然后扫描较大的表并探测散列表，找出与散列表匹配的行。
这种方式适用于较小的表完全可以放入内存的情况，这样成本就是访问两个表的成本之和。但是在表很大的情况下并不能完全放入内存，这时优化器将它分割成若干不同的分区，不能放入内存的部分就把该分区写入磁盘的临时段。

参考至：http://lizhen3708693.iteye.com/blog/1631406
                 http://wenku.baidu.com/view/29d54443be1e650e52ea99df.html
                 http://lizhen3708693.iteye.com/blog/1631407
                 http://hwhuang.iteye.com/blog/1479076
                 http://trophy.iteye.com/blog/1416410
                 http://www.itpub.net/thread-1406613-1-1.html
                 http://www.hellodba.com/reader.php?ID=144&lang=cn
                 http://lizhen3708693.iteye.com/blog/1631360
                 http://blog.csdn.net/guogang83/article/details/8279796
本文原创，转载请注明出处、作者
如有错误，欢迎指正
邮箱:[e-mail]

评论

1 楼 zhachunling 2013-05-30  

写的很好,