(转)oracle 表连接方式详解

  在查看sql执行计划时，我们会发现表的连接方式有多种，本文对表的连接方式进行介绍以便更好看懂执行计划和理解sql执行原理。

 

一、连接方式：

        嵌套循环（Nested  Loops （NL））

      （散列）哈希连接（Hash Join （HJ））

    （归并）排序合并连接(Sort Merge Join (SMJ) )

 

二、连接说明：

    1.Oracle一次只能连接两个表。不管查询中有多少个表，Oracle 在连接中一次仅能操作两张表。

    2.当执行多个表的连接时，优化器从一个表开始，将它与另一个表连接；然后将中间结果与下一个表连接，以此类推，直到处理完所有表为止。

 

三、表连接详解：

     1.嵌套循环（Nested  Loops （NL））：

        嵌套循环实现机制(伪代码)：

          For r1 in (select rows from table_1 where colx={value})

          loop

                for r2 in (select rows from table_2 that match current row from table_1)

               loop

                  output values from current row of table_1 and current row of table_2;

               end loop;

         End loop;

   这段代码由两个循环构成。

   嵌套循环中的这两个表通常称为外部表（outer table)和内部表(inner table)。

   在嵌套循环连接中,外部表又称为驱动表(driver table)

  伪代码中：table_1为驱动表，table_2为内表

  从伪代码中可以看出该连接过程就是一个2层嵌套循环，所以外层循环的次数越少越好，这也就是我们为什么将小表或返回较小结果集的表作为驱动表的原因。

  NEST LOOP JOIN COST =   从第一个表取得数据的成本 +    从第一个表得到结果的基数 Х 对第二个表访问一次的成本

  所以嵌套循环一般适合于驱动表记录集比较少（<10000）且内表有高效索引访问方式。

  使用USE_NL(table_1 table_2)可强制CBO 执行嵌套循环连接。

  驱动表确定：驱动表【select rows from table_1 where colx={value} 】一般为根据where条件能得到较小结果集的表，而不一定是整个表记录比较小的表。

         

    2.（散列）哈希连接（Hash Join （HJ））：

         Hash join一般用于一张小表和一张大表进行join时。在绝大多数情况下，hash join效率比其他join方式效率更高。

         对于hash join的详细理解，可参看网上一篇文章写的比较透彻：http://www.hellodba.com/reader.php?ID=144&lang=cn

 

    3.排序合并连接(Sort Merge Join (SMJ) )：

 

       通常情况下散列连接的效果都比排序合并连接要好，然而如果行源已经被排过序，在执行排序合并连接时不需要再排序了，这时排序合并连接的性能会优于散列连接。可以使用USE_MERGE(table_1 table_2)来强制使用排序合并连接。

过程：将两个表排序，然后将排序后两个表合并。

 

四、连接方式总结：

1)）嵌套循环(nest loop):

          对于被连接的数据子集较小的情况，嵌套循环连接是较好的选择。在嵌套循环中，外表驱动内表，外表返回的每一行都要在内表中检索找到它匹配的行，因此整个查询返回的结果集不能太大（大于10000不合适），要把返回子集较小的表作为外表（驱动表），而且在内表的连接字段上一定要有索引。

2）哈希连接(hash join):

         哈希连接是大数据集连接时常用的方式，优化器使用两个表中较小的表，利用连接键在内存中建立散列表，然后扫描较大的表并探测散列表，找出与散列表匹配的行。

        这种方式适用于较小的表完全可以放入内存的情况，这样成本就是访问两个表的成本之和。但是在表很大的情况下并不能完全放入内存，这时优化器将它分割成若干不同的分区，不能放入内存的部分就把该分区写入磁盘的临时段。

        哈希连接只能应用于等值连接(如WHERE A.COL3 = B.COL4)、非等值连接(WHERE A.COL3 > B.COL4)、外连接(WHERE A.COL3 = B.COL4(+))。

3）排序合并连接（Sort Merge Join ）

          通常情况下哈希连接的效果都比排序合并连接要好。然而如果行源已经被排过序，在执行排序合并连接时不需要再排序了，这时排序归并连接的性能会忧于哈希连接。

 

五、连接方式应用场景：

1.　哈希连接只适用于等值连接。

2.　嵌套循环是行源连接方式，只适合小量数据连接。

    　哈希连接和排序合并连接是集合连接方式，适合大量数据连接。

3.　在等值连接方式下，返回少量记录（<10000）且内部表在连接列上存在索引，适合嵌套循环连接。若返回大量记录则适合哈希连接。

4.　在等值连接方式下，两个行源集合都很大，若连接列是高基数列，则适合哈希连接，否则适合排序合并连接。

5.　嵌套循环连接可以先返回已经连接的行，而不必等待所有的连接操作处理完才返回数据。而其它两种连接方式则不行。

6.    排序合并连接的两个数据集可以并行处理,而嵌套循环和哈希连接不能.

 

注： 整理自网络

 

NLJ：
根据连接键，把小表的每一行，和大笔的每一行做对比。 一般情况下会对大表连接键上建index。
成本计算：读小表的行+（小表的每一行×读取大表的行）

SMJ:
读取小表和大表读的行，根据连接键排序，然后根据排序后的数据集（小表的和大表的）合进行连接。
理想状态：2个表的排序操作都能在内存进行
常规情况：2阶段进行：
          1.sort run阶段：数据读取到内存，排序，写出到临时表空间。直到所有的row sourse完成排序。
          2.merge阶段：之前每次写到临时表空间的数据（即sort run）被重新读入到内存，进行merge。
成本计算：读取小表的行+写小表的run sort到temp表空间+
          读取大表的行+写大表的run sort到temp表空间+
          cpu对小表和大表的排序消耗

join连接中的并行机制：
能在NLJ和SMJ中使用。并发查询的执行计划是一个树形结构（DFO），每个树上的DFO节点是一个sql操作过程，并且能把该操作过程能指派到一个query slave进程中。

Hash Join：
用在条件为等号的环境下，hash连接的效率要比SMJ和NLJ要高（如果索引的blevel比较高），且hash join不要求一定要有索引。
hash join的基本算法是在内存中建立hash table，小表叫做build input，理想状态下，build input在内存中；大表叫做probe input。
在实际的情况下，build input不一定能完全放在内存中，此时，和probe input一样，build input的溢出部分，会在磁盘上用hash函数分割成小的不连续的分区。
hash连接分2个阶段进行：
1.partitioning阶段：即在内存中存放build input，若放不下，则和probe input一样，在磁盘上利用hash函数将input分割成小的不连续的分区。
1.join阶段：在相同的键值上，将build input和probe input的分区进行一一配对，并且join。
以上的hash连接的算法也叫grace join。
 
hash算法的限制：该算法是假设hash之后连接值倾斜度（skew）不高，使得每个partition上保持大约相同数量的rows。但是事实上不可能保证每个partition有大约相同数量的rows。
 
hybrid hash join是在oracle 7.3之后应用的比较高效的hash算法，它是在grace join的基础上，尽量在内存在搭建build input。
但是由于不可能在每个partition中保证相同的rows，后来有出来一些技术如bit-vector filtering、role reversal和histograms。我们将在后面的章节讲到这些技术。
分区的数量，我们叫做fan-out。fan-out太多会导致partition较多，从而影响IO，但是如果fan-out太少又会造成数量较少的大partition，这些大partition无法放在hash内存中。因此选择一个合适的fan-out和partition 大小，是hash join调优的关键。
 
当partitioning之后，build input或者probe input如果在内存中无法放下，hash table的溢出部分将会做nested-loops hash join。
hash table是由部分（在内存内的）build input partition和所有的probe input连接构成。剩余的不在内存中的build input将通过迭代的方式继续获取，直到所有的build input被迭代完。
 
hash join 规则：
假设有2个表：
S = { 1, 1, 1, 3, 3, 4, 4, 4, 4, 5, 8, 8, 8, 8, 10 }
B = { 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 3, 8, 9, 9, 9, 10, 10, 11}
首先会根据hash_area_size确定小表是否能做build table。如果build input不能完全的在内存中，那么build input就被会分区，分区的数量我们称为fan-out，
fan-out是由hash_area_size和cluster size决定的，cluster size是指分区中还没被写出到临时表空间的连续块的数量。
cluster size=db_block_size * hash_multiblock_io_count，hash_multiblock_io_count在oracle9i中是隐含参数
hash算法会把S和B表的连接列分成不连接的桶（bucket），桶也叫做分区（partition），hash算法是尽量的减少数据的倾斜度，使得数据尽量均匀的分布。
 
以上面的S表和B表为例，如果我们简单的假设hash算法是取余，则：
S的分区为:{0,1,3,4,5,8}
B的分区为:{0,1,2,3,8,9}
经过这样的分区之后，只需要相应的分区之间做join即可（也就是所谓的partition pairs），如果有一个分区为NULL的话，则相应的分区join即可忽略。即他们可以在0,1,3,8上做连接。
相应的如果我们用SMJ或者NLJ，在连接上的消耗要高很多。
 
当build input被读入hash area内存准备进行分区的时候，build input表中的唯一列值被作为连接键构建起来，即所谓的位图向量（bitmap vector）。
按照上面的例子，bitmap vector为：{1,3,4,8,10}。
bitmap vector用来决定在partitioning 阶段和大表（probe input）进行连接的时候，哪些行是需要的，哪些是不需要的，不需要的将被丢弃，这就是我们上面说的bit-vector filtering技术。
当对B表进行分区时，将每一个连接键上的值与位图向量相比较，如果不在其中，则将其记录丢弃。在我们这个例子中，B表中以下数据将被丢弃
这个例子中，B表中以下数据将被丢弃{0,0,2,2,2,2,2,2,9,9,9,9,9}。
 
当第一个S分区和B分区做完连接后，需要将第i个S分区和B分区读入内存中做连接，此时会根据分区的大小，自动的选择哪个做build input，哪个做probe input。这就是动态角色转换技术，即我们前面所说的role reversal。

总体说来，hash算法为如下步骤（以下考虑的是hash area size不够大，需要写出到磁盘的情况）：
1.决定fanout的数量，即分区的数量。分区数量×cluster大小<=内存中能用的hash area比例×hash area size大小
2.读取S表，根据内部的hash算法（我们暂时称作hash_fun_1），将连接列上的值map到分区。在此步骤，还利用另一个hash函数（我们称作hash_fun_2）产生另一个hash值，和连接键一起存放。该值将在后续的构建hash table中用到。
3.为S表的独立的连接键形成的bitmap向量
4.根据partition的大小排序，使得尽量多（也就是尽量小的partition进入内存。这也就是之前要根据partition大小排序的原因）的分区放入内存来构建hash table。如果内存不够放下所有的parittion，则输出到temp segment上）。
5.利用之前的hash值，构建S表的hash table。
6.读取B表，根据位图向量过滤，如果通过hash算法后B的值与位图向量比较不在其中，则丢弃该行。
7.将过滤后B表的行，利用内部的hash_fun_1和连接键，形成partition。
8.如果B表的行能在内存中形成分区，就利用内部的hash_fun_2执行连接，并且形成合适的hash桶。
9.如果不能在内存中形成分区，则将S的分区、连接键、B表的剩余行写出到磁盘。
10.从磁盘中读取未处理的S表和B表的分区。利用内部hash_fun_2值，构建hash table，在构建时将使用动态角色转换技术。在第一次循环中，优化器将先使用小表做build input，大表做probe input，角色转换技术仅在第一次循环后使用。
11.如果probe input或者build input中（已经经过角色转换了）较小的那个还是不能放入到内存中，则将读取较小的那个build input到内存chunk中，并且循环的和probe input做hash 连接。这我们叫做nested hash loops join。

hash join的成本计算：
1.最简单的情况，hash area足够大能放下S表分区后的所有的build input：
cost（HJ）=read（S）+build hash table in memory（cpu）+read（B）+perform in memory join（cpu）
如果忽略cpu的成本，cost（HJ）无限接近于 read（s）+read（b）
 
2.当hash area（后面用M表示）不够大，不能容纳build input，S，它将会写出到磁盘。当然了，表B也会写出到磁盘：
total cost 无限接近于 cost（HJ循环1）+cost（HJ循环2）
其中cost（HJ循环1） 无限接近于 read（S）+read（B）+write（（S-M）+（B-B*M/S））
即上述2至9步。
 
由于HJ循环2使用了nested hash loops join，hash join的算法处理Si和Bi分区。当每个build input的chunk被读取时，probe input将被多次读。
因此cost（HJ循环2） 无限接近于 read（（S-M）+n×（B-B*M/S））
即上述10至11步。
n为进行nested hash loops join的次数，n一般在10以上，也就是需要构建的partition大于10倍的hash area。