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

在深入聚集索引与非聚集索引（一）（二）中，（好吧，由于没什么人看，因此没写二），我们详细的分析了SQL SERVER是如何用堆和B树来组织表，并用这两个数据结构帮助我们查询的。

这里我们继续的内容就是探讨SQL SERVER中的连接算法。

联接算法是指在物理上把多个数据源如何联接起来,SQL SERVER支持三种联接算法

1.nested loop 嵌套循环算法

2.merge 合并算法

3.hash 哈希算法

其实这几种算法我们在通常的编程中也经常会用到，并不是很难理解。

一、嵌套循环

一般来说嵌套循环就对应着两层for循环，对于外层for中的每一个项，在内层循环中都要匹配一次。

相应的，外层for对应着外部输入表，在执行计划的图示中排在上面，内层for则是内层输入表，在执行计划中排在下面。

这里值得强调的是，外部输入表是每一行的都要使用来匹配的，而内部表却不一定每一行都在匹配中使用。假设外部输入表有N行，内部输入表有M行，最差的时间复杂度就是O(N*M)。

因此我们可以得到下面的推论

1.外部输入越小越好，因为外部输入每一行都要被用来匹配，不能减少。

2.内部输入表作为匹配的，则可以利用索引来减少匹配条件的范围，这样就可以通过少量的搜索来获取匹配行。

因此嵌套循环算法在连接条件的选择性比较强，而且在内部输入的连接列上有可以利用的有效索引时，是最有效的。

当我们直接查询是，SQL SERVER还会很智能的告诉你缺少什么索引。在下面这个例子中，我们缺少的正是作为内部输入的“连接列 custis”和“查询列 orderdate”上的非聚集索引

当我们输入下面这条语句加上索引后

CREATE INDEX idx_nc_cid_od_i_oid_eid_sid
  ON dbo.Orders(custid, orderdate)
  INCLUDE(orderid, empid, shipperid);

SQL SERVER仍然报缺少索引，是因为我们对于外部输入的表仍然是可以利用索引来先筛选一轮，以起到减小外部输入的目的。缺少的是这个非聚集索引，加上custid同样是为了起到覆盖作用，custname作为筛选列。

CREATE INDEX idx_nc_cn_i_cid
  ON dbo.Customers(custname) INCLUDE(custid);

二、合并排序

对于两个输入列都有序的情况下，合并联接的效率高。

排序的重要性毋庸置疑了，什么二分查找等等查找都是建立在输入序列有序的基础上。

其实类似于代码

public static IEnumerable<string> Join(    IEnumerable<string> first,    IEnumerable<string> second){    using (IEnumerator<string> firstSequence =        first.GetEnumerator())    {        using (IEnumerator<string> secondSequence =            second.GetEnumerator())        {            while (firstSequence.MoveNext() &&                secondSequence.MoveNext())            {                yield return string.Format("{0} {1}",                    firstSequence.Current,                    secondSequence.Current);            }        }    }}

为什么先讲索引呢？我们可以从索引中发现有现成的排序好的数据结构吗？有的，B树中的叶层就是按照一定的逻辑顺序维护的。也就是说，聚集索引和非聚集覆盖索引，都可以通过对叶层的有序扫描以较小的代价就可以获取有序的数据。在这种情况下，就算输入表的规模比较大，合并联接也相当给力。但如果所需的数据列并不存在上述的条件的时候，对于较大的输入来说排序往往是一个开销非常大的操作（因为基于比较的排序最快也就是n log n的），因此优化器通常不会在这种情况下选用合并联接。但是对于较小的输入排序的消耗还是可以接受的。较小的输入可以像上例一样通过对自身的筛选来获得。

分析：

对于连接列custid,对于Customers表不用说，是该表的聚集索引的聚集键，对于order表来说，我们在上面给custid创建了非聚集覆盖索引，所以也可以按照有序扫描以较小的代价获取有序数据。

可以看出order表的扫描在整体开销中所占的比例是最大的，因为order表的数据非常多。那么假设我们在order表上还有其他的筛选条件呢？比如对orderdate进行限定

由于这个筛选器的选择性非常高，所获取的结果才1000行，两权之下，另可放弃有序的全表扫描，而是先过滤再排序。

当然，计划器也有可能估计错误，如果所获取的结果选择性不高的话，排序所占用的开销往往非常大。

三、Hash联接

这个原理参照我原来写的 这篇文章，这里想说的是什么情况下会用到hash联接。

是因为缺少现成的索引，特别是在数据仓库类型(OLTP)的应用中.

我们在未创建任何索引的第一个示例中，采取的就是HASH匹配。

数据库到这里暂时告一段落了，因为发觉没什么人看，也没什写下去的劲头了。

当然如果你觉得有帮助，请点击推荐，或者留点评论说说想法，讨论讨论。

下面打算写写我在学习 Object C和 Git中的一些心得体会系列文章。

本文链接