浅谈SQL SERVER中的物理联接算法

dsqzhaoyue

　　在深入聚集索引与非聚集索引（一）（二）中，（好吧，由于没什么人看，因此没写二），我们详细的分析了SQL SERVER是如何用堆和B树来组织表，并用这两个数据结构帮助我们查询的。
　　
　　这里我们继续的内容就是探讨SQL SERVER中的连接算法。
　　
　　联接算法是指在物理上把多个数据源如何联接起来,SQL SERVER支持三种联接算法
　　1.nested loop 嵌套循环算法
　　2.merge 合并算法
　　3.hash 哈希算法
　　
　　其实这几种算法我们在通常的编程中也经常会用到，并不是很难理解。
　　
一、嵌套循环
　　一般来说嵌套循环就对应着两层for循环，对于外层for中的每一个项，在内层循环中都要匹配一次。
　　相应的，外层for对应着外部输入表，在执行计划的图示中排在上面，内层for则是内层输入表，在执行计划中排在下面。
　　这里值得强调的是，外部输入是每一行的都要使用来匹配的，而内部表却不一定每一行都在匹配中使用。假设外部输入有N行，内部输入表有M行，最差的时间复杂度就是O(N*M)。而在这种最差的情况下，优化器不会再采用嵌套循环，而是采用Hash匹配算法。关于Hash匹配算法，后面会有说明。
　　因此我们可以得到下面的推论
　　1.外部输入越小越好，因为外部输入每一行都要被用来匹配，不能减少。
　　2.内部输入表作为匹配的，则可以利用索引来减少匹配条件的范围，这样就可以通过少量的搜索来获取匹配行。
　　因此嵌套循环算法在连接条件的选择性比较强，而且在内部输入的连接列上有可以利用的有效索引时，是最有效的。
　　
　　在下面这个例子中，Customers表的记录数要远比Orders表的记录数少（客户数肯定要比订单数少），因此Customers表中的数据被优化器选择作为外部输入，从图中可以看出Customers表是在Orders表的上方。
　　当我们直接查询是，SQL SERVER还会很智能的告诉你缺少什么索引。在下面这个例子中，我们缺少的正是作为内部输入的“连接列 custid”和“查询列 orderdate”上的非聚集索引
　　

　　
　　当我们输入下面这条语句加上索引后
　　CREATE INDEX idx_nc_cid_od_i_oid_eid_sid
  ON dbo.Orders(custid, orderdate)         
  INCLUDE(orderid, empid, shipperid);

　　
　　SQL SERVER仍然报缺少索引，是因为我们对于外部输入的表仍然是可以利用索引来先筛选一轮，以起到减小外部输入的目的。
　　为了达到这个目的，缺少的是这个非聚集索引，custname作为筛选列，加上custid同样是为了起到覆盖作用。
　　CREATE INDEX idx_nc_cn_i_cid        
  ON dbo.Customers(custname) INCLUDE(custid);
　　这时对于Customers表的index scan就会变成Index seek。
　　
　　补全索引后，我们最终获得的执行计划

　　
　　
　　
　　
二、合并排序
　　对于两个输入列都有序的情况下，合并联接的效率高。
　　排序的重要性毋庸置疑了，什么二分查找等等查找都是建立在输入序列有序的基础上。
　　为什么先讲索引呢？我们可以从索引中发现有现成的排序好的数据结构吗？有的，B树中的叶层就是按照一定的逻辑顺序维护的。也就是说，聚集索引和非聚集覆盖索引，都可以通过对叶层的有序扫描以较小的代价就可以获取有序的数据。在这种情况下，就算输入表的规模比较大，合并联接也相当给力。如果计划分析器确定连接的一侧记录集中的元素是唯一确定的，那么就会采用一对多的匹配方式（多指另一侧的元素会有重复），在这种情况下，合并排序效率应该是几种连接方式中最高的。
　　但如果所需的数据列并不存在上述的条件的时候，对于较大的输入来说排序往往是一个开销非常大的操作（因为基于比较的排序最快也就是n log n的），因此优化器通常不会在这种情况下选用合并联接。但是对于较小的输入排序的消耗还是可以接受的。较小的输入可以像上例一样通过对自身的筛选来获得。
　　

　　
　　分析：
　　对于连接列custid,对于Customers表不用说，是该表的聚集索引的聚集键，对于order表来说，我们在上面给custid创建了非聚集覆盖索引，所以也可以按照有序扫描以较小的代价获取有序数据。
　　因为都可以从两张表中以较小的代价获取按照连接列custid的顺序获取有序的数据，因此优化器选择了合并排序。
　　
　　可以看出Orders表的扫描在整体开销中所占的比例是最大的达到68%，因为Orders表的数据非常多。那么假设我们在Orders表上还有其他的筛选条件呢？比如对orderdate进行限定

　　
　　由于这个筛选器的选择性非常高，所获取的结果才1000多行，只占Orders表1000000总数下的0.1%。两权之下，另可放弃有序的全表扫描，而是先过滤再排序。
　　当然，计划器也有可能估计错误，如果所获取的结果选择性不高的话，排序所占用的开销往往非常大。这也是我们在发现优化器生成Merge计划时要注意的地方。
　　
　　
三、Hash联接
　　原理参照我写的这篇文章，为了减少内存占用因此使用数据量较小的表来构造hashtable,然后另逐行扫描另一张表通过hash函数算出hashtable的某个位置上是否已存在值来判断相等。
　　通常用到hash联接,是因为缺少现成的索引，特别是在数据仓库类型(OLTP)的应用中.
　　我们在未创建任何索引的第一个示例中，采取的就是Hash匹配。逐行扫描Customer表构造hashtable,因为我们where条件中有orderdate可以减小匹配的范围，所以先用聚集索引减少Orders表中匹配的记录数，然后再用hash函数逐行匹配前面构造好的hashtable.

　　
　　缺少合适的索引也可能会采用Hash匹配。我们把orderdate的范围增加了几十倍，由一天改成了查询几个月，这时合并联接算法不再适合。

　　
　　
　　总结：
　　采用Hash联接算法，从时间复杂度上来说是最优的，联接一张M条记录的表和一张N条记录的表的时间复杂度为O(M+N),好于带有聚集索引的嵌套联接算法O（M * log2n）。但是如果在构造hashtable时内存不足以保存Hashtable时，会产生临时空间交换，导致而外大量的IO从而抵消了联接时所产生的益处。
　　
　　当然如果你觉得有帮助，请点击推荐，或者留点评论说说想法，讨论讨论。
　　下面打算写写我在学习Object C和Git中的一些心得体会系列文章。