sql 算法 : Nested Loop，Hash Join，Merge Join介绍

Nested Loop，Hash Join，Merge Join介绍

Nested Loop:
对于被连接的数据子集较小的情况，Nested Loop是个较好的选择。Nested Loop就是扫描一个表（外表），每读到一条记录，就根据Join字段上的索引去另一张表（内表）里面查找，若Join字段上没有索引查询优化器一般就不会选择 Nested Loop。在Nested Loop中，内表（一般是带索引的大表）被外表（也叫“驱动表”，一般为小表——不紧相对其它表为小表，而且记录数的绝对值也较小，不要求有索引）驱动，外表返回的每一行都要在内表中检索找到与它匹配的行，因此整个查询返回的结果集不能太大（大于1 万不适合）。Nested Loop适用于结果集很小（一般要求小于一万条），并且内表在Join字段上建有索引（这点非常非常非常重要）。

1.执行原理

例如：
select t1.*,t2.* from t1,t2 where t1.col1=t2.col2;
访问机制如下：
for i in (select * from t1) loop  ----t1为驱动表
 for j in (select * from t2 where col2=i.col1) loop
 display results;
 end loop;
 end loop;
类似一个嵌套循环
嵌套循环执行时，先是外层循环进入内层循环，并在内层循环终止之后
接着执行外层循环再由外层循环进入内层循环中，当外层循环全部终止时，程序结束


2.步骤如下
a.确定驱动表
b.把inner 表分配给驱动表
c.针对驱动表的每一行，访问被驱动表的所有行

3.执行计划大致如下
NESTED LOOPS
outer_loop  --驱动表
inner_loop

优化器模式为FIRST_ROWS时，我们经常会发现有大量的NESTED LOOP
这时，在返回数据给用户时，我们没有必要缓存任何数据，这是nested loop的一大亮点

4.使用场景
一般用在连接的表中有索引，并且索引选择性较好（也就是Selectivity接近1）的时候
  也就是驱动表的记录集比较小（<10000）而且inner表需要有有效的访问方法（Index）
  需要注意的是：JOIN的顺序很重要，驱动表的记录集一定要小，返回结果集的响应时间是最快的

5.和索引关系
  嵌套循环和索引就像一对孪生兄弟，一般需要共同考量与设计,这从优化器的执行机制可以看出.
  比如，存在2张表，一个10条记录，一个1000万条记录
  以小表为驱动表，则代价为：10*(通过索引在大表查询一条记录的代价)
  如果1000万的大表没有索引的时候，那么COST的代价可想而知
  因此，在多表连接时，注意被驱动表的连接字段是否需要创建索引
  或者连接字段与该表的其他约束条件字段上是否需要创建复合索引

Hash Join:
Hash Join是做大数据集连接时的常用方式，优化器使用两个表中较小（相对较小）的表利用Join Key在内存中建立散列表，然后扫描较大的表并探测散列表，找出与Hash表匹配的行。
这种方式适用于较小的表完全可以放于内存中的情况，这样总成本就是访问两个表的成本之和。但是在表很大的情况下并不能完全放入内存，这时优化器会将它分割成若干不同的分区，不能放入内存的部分就把该分区写入磁盘的临时段，此时要求有较大的临时段从而尽量提高I/O 的性能。它能够很好的工作于没有索引的大表和并行查询的环境中，并提供最好的性能。大多数人都说它是Join的重型升降机。Hash Join只能应用于等值连接(如WHERE A.COL3 = B.COL4)，这是由Hash的特点决定的。
Merge Join:
通常情况下Hash Join的效果都比排序合并连接要好，然而如果两表已经被排过序，在执行排序合并连接时不需要再排序了，这时Merge Join的性能会优于Hash Join。Merge join的操作通常分三步：
　　1. 对连接的每个表做table access full;
　　2. 对table access full的结果进行排序。
　　3. 进行merge join对排序结果进行合并。
在全表扫描比索引范围扫描再进行表访问更可取的情况下，Merge Join会比Nested Loop性能更佳。当表特别小或特别巨大的时候，实行全表访问可能会比索引范围扫描更有效。Merge Join的性能开销几乎都在前两步。Merge Join可适于于非等值Join（>，<，>=，<=，但是不包含!=，也即<>）

1.执行原理
select t1.*,t2.* from t1,t2 where t1.id=t2.id;
访问机制如下：
访问t1，并order by t1_1.id，这里的id代表连接字段
访问t2，并order by t2_1.id
join t1_1.id = t2_1.id，依次交替 比对 归并，但无所谓驱动

2.使用场景
虽说，hash join就是用来替代sj的，但如果你的服务器的CPU资源和MEM资源都很紧张的时候，建议用SORT MERGE JOIN
因为hash join比sort merge join需要的资源更多。特别是cpu
10g sql tuning 文档上写道：
On the other hand, sort-merge joins can perform better than hash joins if both of the following conditions are met:
The row sources are already sorted. 
A sort operation does not have to be done.
所以，sj大概就用在没有索引，并且数据已经排序的情况

Nested Loop，Hash JOin，Merge Join对比

类别	Nested Loop	Hash Join	Merge Join
使用条件	任何条件	等值连接（=）	等值或非等值连接(>，<，=，>=，<=)，‘<>’除外
相关资源	CPU、磁盘I/O	内存、临时空间	内存、临时空间
特点	当有高选择性索引或进行限制性搜索时效率比较高，能够快速返回第一次的搜索结果。	当缺乏索引或者索引条件模糊时，Hash Join比Nested Loop有效。通常比Merge Join快。在数据仓库环境下，如果表的纪录数多，效率高。	当缺乏索引或者索引条件模糊时，Merge Join比Nested Loop有效。非等值连接时，Merge Join比Hash Join更有效
缺点	当索引丢失或者查询条件限制不够时，效率很低；当表的纪录数多时，效率低。	为建立哈希表，需要大量内存。第一次的结果返回较慢。	所有的表都需要排序。它为最优化的吞吐量而设计，并且在结果没有全部找到前不返回数据。

参考：

https://www.cnblogs.com/xqzt/p/4469673.html

https://blog.csdn.net/dba_waterbin/article/details/8547451

https://www.cnblogs.com/polestar/p/4132911.html

http://www.jasongj.com/2015/03/07/Join1/

https://www.cnblogs.com/Dreamer-1/p/6076440.html