浅谈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)。而在这种最差的情况下,优化器不会再采用嵌套循环,而是采用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。

 

补全索引后,我们最终获得的执行计划

 

 

 

 

二、合并排序

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

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

其实类似于代码

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创建了非聚集覆盖索引,所以也可以按照有序扫描以较小的代价获取有序数据。

因为都可以从两张表中以较小的代价获取按照连接列custid的顺序获取有序的数据,因此优化器选择了合并排序。

 

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

 

由于这个筛选器的选择性非常高,所获取的结果才1000多行,只占Orders表1000000总数下的0.1%。两权之下,另可放弃有序的全表扫描,而是先过滤再排序。

当然,计划器也有可能估计错误,如果所获取的结果选择性不高的话,排序所占用的开销往往非常大。这也是我们在发现优化器生成Merge计划时要注意的地方。

 

 

三、Hash联接

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

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

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

 

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

 

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

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

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


分享给朋友:
您可能感兴趣的文章:
随机阅读: