联接算法

标签: 算法 | 发表时间:2014-01-22 21:04 | 作者:zhanghongju
出处:http://blog.csdn.net


本文摘自《锋利的SQL》: http://item.jd.com/10380652.html


在Microsoft SQLServer Management Studio中执行查询时,如果选定工具栏中的 按钮,可以看到为查询生成的执行计划。执行计划以图形方式显示了SQL Server查询优化器选择的数据检索方法,如表扫描、排序、哈希匹配等。对于联接查询,SQL Server会根据联接表之间的数据、索引等情况,选择使用嵌套循环联接、合并联接或哈希联接。

7.7.1嵌套循环联接

嵌套循环联接也称为“嵌套迭代”,它将一个联接输入用作外部输入表(显示为图形执行计划中的顶端输入),将另一个联接输入用作内部(底端)输入表。外部循环逐行处理外部输入表。内部循环会针对每个外部行执行,在内部输入表中搜索匹配行。简单地讲,就是扫描其中的一个联接表,并为该表中的每一行在另一个联接表中搜索匹配行。

如果外部输入较小(不到10行)而内部输入较大且预先创建了索引,则嵌套循环联接尤其有效。在许多小事务中(如那些只影响较小的一组行的事务),索引嵌套循环联接优于合并联接和哈希联接。但在大型查询中,嵌套循环联接通常不是最佳选择。

例如,下面的查询由于Sales.Customer表行数只有1行,而Sales.SalesOrderHeader数据量较大,因此将使用嵌套循环联接,生成的执行计划如图7-11所示。

USE AdventureWorks;

GO

SELECT *

FROM Sales.Customer  

 INNER JOINSales.SalesOrderHeader

   ONCustomer.CustomerID = SalesOrderHeader.CustomerID

WHERE Customer.CustomerID = 1;

图7-11使用嵌套循环的执行计划

在该计划中存在两个嵌套循环,其中只有左边的嵌套循环符用于Sales.Customer与Sales.SalesOrderHeader的联接,而右边的嵌套循环是用于Sales.SalesOrderHeader的索引查找与物理行定位(键查找)之间的联接。执行计划右上角的Sales.Customer表被作为外部输入,在聚集索引中查找客户。对于每个客户,嵌套循环运算将对SalesOrderHeader.CustomerID列上的IX_SalesOrderHeader_CustomerID索引执行一次查找,然后再跟一个键查找来定位要访问的数据行。

7.7.2合并联接

合并联接要求两个输入都在合并列上排序,合并列由联接谓词的等效(ON)子句定义。由于每个输入都已排序,因此合并联接将从每个输入获取一行并将其进行比较。例如,对于内联接操作,如果行相等则返回。如果行不相等,则废弃值较小的行并从该输入获得另一行。这一过程将重复进行,直到处理完所有的行为止。

合并联接操作可以是常规操作,也可以是多对多操作。多对多合并联接使用临时表存储行。如果每个输入中有重复值,则在处理其中一个输入中的每个重复项时,另一个输入必须重绕到重复项的开始位置。

合并联接本身的速度很快,但是如果合并列上未建立索引,选择合并联接有可能会非常费时,因为它首先要对列进行排序操作。然而,如果数据量很大且能够从索引中获得预排序的所需数据,则合并联接通常是最快的可用联接算法。

例如,下面的查询语句将获取订单的详细信息,由于SalesOrderHeader和SalesOrderDetail在合并列SalesOrderID上都具有聚集索引,已经将列进行了排序,所以查询优化器会选择合并联接。如图7-12所示。

USE AdventureWorks;

GO

SELECT *

FROM Sales.SalesOrderHeader  

 INNER JOINSales.SalesOrderDetail 

   ONSalesOrderHeader.SalesOrderID = SalesOrderDetail.SalesOrderID;

图7-12使用合并联接的执行计划

7.7.3哈希联接

哈希联接可以有效处理未排序的大型非索引输入。因此,它对处理复杂查询的中间结果很有用。查询的中间结果是未经索引的,而且通常不会为查询计划中的下一个操作进行适当的排序。并且,查询优化器只估计中间结果的大小。而对于复杂查询,估计可能有很大的误差,因此如果中间结果比预期的大得多,则处理中间结果的算法不仅必须有效而且必须适度弱化。再像合并联接那样严格要求具备排序列,对于中间结果而言是不现实的,排序成本的付出可能要远远大于数据的直接检索成本。

选择哈希联接的两种情况:一是没有为联接创建合适的索引,二是中间结果比较大。

哈希联接有两种输入:生成输入和探测输入。查询优化器会选择二者中较小的那个作为生成输入,对联接列值应用哈希函数,将生成输入中的行分配到哈希桶中。哈希桶是一种存放所访问数据位置的结构,有了它,进行数据检索时,可以避免不必要的表扫描。

为了验证无索引情况下的哈希联接使用,首先使用下面的语句创建Sales.Customer和Sales.SalesOrderHeader表的副本。

USE AdventureWorks;

GO

SELECT TOP 10 *

INTO MyCustomer

FROM Sales.Customer

ORDER BY CustomerID;

 

SELECT TOP 100 *

INTO MySalesOrderHeader

FROM Sales.SalesOrderHeader

ORDER BY CustomerID;

执行下面的查询,可以看到如图7-13所示的执行计划。

SELECT *

FROM MyCustomer

 INNER JOINMySalesOrderHeader

   ONMyCustomer.CustomerID = MySalesOrderHeader.CustomerID;

图7-13使用哈希联接的执行计划

下面再来看一个比较有趣的示例。下面的查询语句中仅选择了Sales.Customer中CustomerID = 1的行与Sales.SalesOrderHeader进行联接,由于联接行数很小,所产生中间结果的数据量也比较小,因此,可以看到查询优化器为语句使用了嵌套循环联接。如图7-14所示。

USE AdventureWorks;

GO

SELECT *

FROM Sales.Customer  

 INNER JOINSales.SalesOrderHeader

   ONCustomer.CustomerID = SalesOrderHeader.CustomerID

WHERE Customer.CustomerID = 1;    

图7-14数据量较小时使用嵌套循环联接

 同样是上面的联接,去除掉WHERE筛选条件后数据量明显增大,执行该语句会发现查询优化器使用了哈希联接方式。如图7-15所示。

SELECT *

FROM Sales.Customer  

 INNER JOINSales.SalesOrderHeader

   ONCustomer.CustomerID = SalesOrderHeader.CustomerID;  

图7-15数据量较大时使用哈希联接

7.7.4使用联接提示强制联接策略

联接提示用于指定查询优化器在两个表之间强制执行联接策略,提示符包括LOOP JOIN、MERGE JOIN和HASH JOIN,分别用于嵌套循环、哈希和合并联接。如果指定了多个联接提示,则优化器从允许的联接策略中选择开销最少的联接策略。此外,也可以使用OPTION子句指定联接策略。但是这种方式会影响查询中的所有联接,通常用于旧式联接语法。

1.为每个联接指定单独的联接策略

可以在FROM子句中使用LOOP JOIN、MERGE JOIN和HASH JOIN提示符为每个联接单独指定联接策略。例如,下面的查询语句指定使用嵌套循环联接。

USE AdventureWorks;

GO

SELECT *

FROM Sales.Customer  

 INNER LOOPJOIN Sales.SalesOrderHeader

   ONCustomer.CustomerID = SalesOrderHeader.CustomerID;

又如,下面的查询语句指定使用合并联接。

USE AdventureWorks;

GO

SELECT *

FROM Sales.Customer  

 INNERMERGE JOIN Sales.SalesOrderHeader

   ONCustomer.CustomerID = SalesOrderHeader.CustomerID;

在多表联接中使用联接提示时,会影响联接的执行顺序。在前面介绍了,在不影响返回结果正确的情况下,查询优化器会按照效率优先的原则,选择首先执行的联接。例如,下面语句的执行计划如图7-16所示,可以看到首先执行的是Sales.SalesOrderHeader与Sales.SalesOrderDetail的联接,然后将联接结果再与Sales.Customer进行联接。

USE AdventureWorks;

GO

SELECT *

FROM Sales.Customer  

 INNER JOINSales.SalesOrderHeader

   ONCustomer.CustomerID = SalesOrderHeader.CustomerID

 INNER JOINSales.SalesOrderDetail

   ONSalesOrderHeader.SalesOrderID = SalesOrderDetail.SalesOrderID; 

图7-16未使用联接提示的执行计划

下面的语句为Sales.Customer和Sales.SalesOrderHeader指定了合并联接提示,并且这个提示仅对这两个表起作用,与Sales.SalesOrderDetail的联接策略仍旧由查询优化器决定。由于明确指定了Sales.Customer与Sales.SalesOrderHeader使用合并联接,优化器会先执行该联接,而不是先执行Sales.SalesOrderHeader与Sales.SalesOrderDetail的联接。否则,就会造成Sales.Customer与Sales.SalesOrderHeader和Sales.SalesOrderDetail的联接结果再执行合并联接。图7-17是该语句的执行计划。

SELECT *

FROM Sales.Customer  

 INNERMERGE JOIN Sales.SalesOrderHeader

   ONCustomer.CustomerID = SalesOrderHeader.CustomerID

 INNER JOINSales.SalesOrderDetail

   ONSalesOrderHeader.SalesOrderID = SalesOrderDetail.SalesOrderID; 

图7-17使用联接提示后的执行计划

如果希望Sales.Customer与Sales.SalesOrderHeader和Sales.SalesOrderDetail的联接结果执行合并联接,则应当使用嵌套联接的方式实现,参考下面的语句:

SELECT *

FROM Sales.Customer  

 INNERMERGE JOIN (Sales.SalesOrderHeader

                   INNER JOIN Sales.SalesOrderDetail

                     ONSalesOrderHeader.SalesOrderID = SalesOrderDetail.SalesOrderID)

   ONCustomer.CustomerID = SalesOrderHeader.CustomerID;

2.为全部联接指定统一的联接策略

当使用旧式联接语法时,应当使用OPTION子句指定联接策略,但是,这种策略会影响语句中的全部联接,无法为每个联接单独指定不同的联接策略,如:

SELECT *

FROM Sales.Customer, Sales.SalesOrderHeader,Sales.SalesOrderDetail

WHERE Customer.CustomerID =SalesOrderHeader.CustomerID

 ANDSalesOrderHeader.SalesOrderID = SalesOrderDetail.SalesOrderID

OPTION (MERGE JOIN); 

该语句的执行计划如图7-18所示,可以看到三个表之间全部使用了合并联接策略。

图7-18为全部联接使用统一联接策略的执行计划

在ANSI SQL:1992规范中,也可以使用OPTION子句,它同样也是影响语句中的全部联接,如:

SELECT *

FROM Sales.Customer  

 INNER JOINSales.SalesOrderHeader

   ONCustomer.CustomerID = SalesOrderHeader.CustomerID

 INNER JOINSales.SalesOrderDetail

   ONSalesOrderHeader.SalesOrderID = SalesOrderDetail.SalesOrderID

OPTION (MERGE JOIN);

 

作者:zhanghongju 发表于2014-1-22 21:04:14 原文链接
阅读:93 评论:0 查看评论

相关 [算法] 推荐:

缓存算法

- lostsnow - 小彰
没有人能说清哪种缓存算法由于其他的缓存算法. (以下的几种缓存算法,有的我也理解不好,如果感兴趣,你可以Google一下  ). 大家好,我是 LFU,我会计算为每个缓存对象计算他们被使用的频率. 我是LRU缓存算法,我把最近最少使用的缓存对象给踢走. 我总是需要去了解在什么时候,用了哪个缓存对象.

BFPRT算法

- zii - 小彰
BFPRT算法的作者是5位真正的大牛(Blum 、 Floyd 、 Pratt 、 Rivest 、 Tarjan),该算法入选了在StackExchange上进行的当今世界十大经典算法,而算法的简单和巧妙颇有我们需要借鉴学习之处. BFPRT解决的问题十分经典,即从某n个元素的序列中选出第k大(第k小)的元素,通过巧妙的分析,BFPRT可以保证在最坏情况下仍为线性时间复杂度.

贪心算法

- Shan - 博客园-首页原创精华区
顾名思义,贪心算法总是作出在当前看来最好的选择. 也就是说贪心算法并不从整体最优考虑,它所作出的选择只是在某种意义上的局部最优选择. 当然,希望贪心算法得到的最终结果也是整体最优的. 虽然贪心算法不能对所有问题都得到整体最优解,但对许多问题它能产生整体最优解. 如单源最短路经问题,最小生成树问题等.

缓存算法

- 成 - FeedzShare
来自: 小彰 - FeedzShare  . 发布时间:2011年09月25日,  已有 2 人推荐. 没有人能说清哪种缓存算法由于其他的缓存算法. (以下的几种缓存算法,有的我也理解不好,如果感兴趣,你可以Google一下  ). 大家好,我是 LFU,我会计算为每个缓存对象计算他们被使用的频率.

K-Means 算法

- - 酷壳 - CoolShell.cn
最近在学习一些数据挖掘的算法,看到了这个算法,也许这个算法对你来说很简单,但对我来说,我是一个初学者,我在网上翻看了很多资料,发现中文社区没有把这个问题讲得很全面很清楚的文章,所以,把我的学习笔记记录下来,分享给大家. k-Means 算法是一种  cluster analysis 的算法,其主要是来计算数据聚集的算法,主要通过不断地取离种子点最近均值的算法.

查找算法:

- - CSDN博客推荐文章
从数组的第一个元素开始查找,并将其与查找值比较,如果相等则停止,否则继续下一个元素查找,直到找到匹配值. 注意:要求被查找的数组中的元素是无序的、随机的. 比如,对一个整型数组的线性查找代码:. // 遍历整个数组,并分别将每个遍历元素与查找值对比. 要查找的值在数组的第一个位置. 也就是说只需比较一次就可达到目的,因此最佳情况的大O表达式为:O(1).

排序算法

- - 互联网 - ITeye博客
排序算法有很多,所以在特定情景中使用哪一种算法很重要. 为了选择合适的算法,可以按照建议的顺序考虑以下标准: .     对于数据量较小的情形,(1)(2)差别不大,主要考虑(3);而对于数据量大的,(1)为首要.  一、冒泡(Bubble)排序——相邻交换 .  二、选择排序——每次最小/大排在相应的位置 .

联接算法

- - CSDN博客数据库推荐文章
本文摘自《锋利的SQL》: http://item.jd.com/10380652.html. 在Microsoft SQLServer Management Studio中执行查询时,如果选定工具栏中的 按钮,可以看到为查询生成的执行计划. 执行计划以图形方式显示了SQL Server查询优化器选择的数据检索方法,如表扫描、排序、哈希匹配等.

理解EM算法

- Chin - 我爱自然语言处理
EM(Expectation-Maximization)算法在机器学习和自然语言处理应用非常广泛,典型的像是聚类算法K-means和高斯混合模型以及HMM(Hidden Markov Model). 笔者觉得讲EM算法最好的就是斯坦福大学Andrew Ng机器学习课的讲课笔记和视频. 本文总结性的给出普遍的EM算法的推导和证明,希望能够帮助接触过EM算法但对它不是很明白的人更好地理解这一算法.

Memcached的LRU算法

- Eric - 平凡的世界
最近计划对Memcached做一些尝试性的改造,主要是针对Memcached在处理过期数据的时候进行改造,以实现在一个缓存的过期时间达到的时候,可以对该缓存的数据进行一个验证和存储的处理. 这个需求,主要是为了解决MySQL的写入瓶颈,通过延期、合并写入请求来减少MySQL的并发写入量. 现在逐渐记录出来和有需要的朋友一起讨论.