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

标签: sql server 物理 | 发表时间:2012-08-18 00:40 | 作者:浪雪
出处:http://www.cnblogs.com/

在深入聚集索引与非聚集索引(一)(二)中,(好吧,由于没什么人看,因此没写二),我们详细的分析了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”上的非聚集索引

 

image

 

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

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的),因此优化器通常不会在这种情况下选用合并联接。但是对于较小的输入排序的消耗还是可以接受的。较小的输入可以像上例一样通过对自身的筛选来获得。

 

image

 

分析:

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

 

 

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

image

 

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

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

 

 

三、Hash联接

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

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

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

image

 

 

 

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

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

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

本文链接

相关 [sql server 物理] 推荐:

SQL Server--索引

- - CSDN博客推荐文章
         1,概念:  数据库索引是对数据表中一个或多个列的值进行排序的结构,就像一本书的目录一样,索引提供了在行中快速查询特定行的能力..             2.1优点:  1,大大加快搜索数据的速度,这是引入索引的主要原因..                             2,创建唯一性索引,保证数据库表中每一行数据的唯一性..

SQL Server 面试

- - SQL - 编程语言 - ITeye博客
在SQL语言中,一个SELECT…FROM…WHERE语句称为一个查询块,将一个查询块嵌套在另一个查询块的WHERE子句中的查询称为子查询. 子查询分为嵌套子查询和相关子查询两种. 嵌套子查询的求解方法是由里向外处理,即每个子查询在其上一级查询处理之前求解,子查询的结果作为其父查询的查询条件. 子查询只执行一次,且可以单独执行;.

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

- - 博客园_首页
在深入聚集索引与非聚集索引(一)(二)中,(好吧,由于没什么人看,因此没写二),我们详细的分析了SQL SERVER是如何用堆和B树来组织表,并用这两个数据结构帮助我们查询的. 这里我们继续的内容就是探讨SQL SERVER中的连接算法. 联接算法是指在物理上把多个数据源如何联接起来,SQL SERVER支持三种联接算法.

SQL Server优化50法

- - CSDN博客推荐文章
虽然查询速度慢的原因很多,但是如果通过一定的优化,也可以使查询问题得到一定程度的解决.   查询速度慢的原因很多,常见如下几种:没有索引或者没有用到索引(这是查询慢最常见的问题,是程序设计的缺陷).   I/O吞吐量小,形成了瓶颈效应.   没有创建计算列导致查询不优化.   内存不足网络速度慢查询出的数据量过大(可以采用多次查询,其他的方法降低数据量).

SQL Server 中的事务

- - CSDN博客推荐文章
       事务要有非常明确的开始和结束点,SQL Server 中的每一条数据操作语句,例如SELECT、INSERT、UPDATE和DELETE都是隐式事务的一部分. 即使只有一条语句,系统也会把这条语句当做一个事务,要么执行所有的语句,要么什么都不执行.         事务开始之后,事务所有的操作都会写到事务日志中,写到日志中的事务,一般有两种:一是针对数据的操作,例如插入、修改和删除,这些操作的对象是大量的数据;另一种是针对任务的操作,例如创建索引.

SQL Server优化50法

- - CSDN博客数据库推荐文章
  虽然查询速度慢的原因很多,但是如果通过一定的优化,也可以使查询问题得到一定程度的解决.   查询速度慢的原因很多,常见如下几种:. 没有索引或者没有用到索引(这是查询慢最常见的问题,是程序设计的缺陷). I/O吞吐量小,形成了瓶颈效应. 查询出的数据量过大(可以采用多次查询,其他的方法降低数据量).

SQL Server 查询步骤 - pursuer.chen

- - 博客园_首页
标签:SQL SERVER/MSSQL SERVER/数据库/DBA/查询步骤.       查询步骤是很基础也挺重要的一部分,但是我还是在周围发现有些人虽然会语法,但是对于其中的步骤不是很清楚,这里就来分解一下其中的步骤,在技术内幕系列里面都会有讲到.  TOP于ORDER BY的关系. INSERT INTO Customers VALUES(1,'深圳'),(2,'广州'),(3,'武汉'),(4,'上海'),(5,'北京').

sql server复灾 你懂了吗?

- brett80 - 博客园-首页原创精华区
很多时候我们不小心错误delete了一下,或者update一下怎么办,或者直接把数据库删除了,怎么办呢,是不是就一定没有办法呢. 下面让我来教大家我现学现卖的两招. 做之前我们要设置数据库恢复模式:. 首先我们创建一个表:插入几条数据. 我们现在有五条数据了,我们对数据做一个备份. 做任何差异备份,和日志之前,一定要做一个完整备份.

监控 SQL Server 的运行状况

- Bloger - 博客园-首页原创精华区
Microsoft SQL Server 2005 提供了一些工具来监控数据库. 动态管理视图 (DMV) 和动态管理函数 (DMF) 返回的服务器状态信息可用于监控服务器实例的运行状况、诊断问题和优化性能. 常规服务器动态管理对象包括:. dm_db_*:数据库和数据库对象. dm_exec_*:执行用户代码和关联的连接.

SQL Server 数据库巡检脚本

- - CSDN博客数据库推荐文章
select '现在没有阻塞和死锁信息' as message. select '引起数据库死锁的是: '+ CAST(@bl AS VARCHAR(10)) + '进程号,其执行的SQL语法如下'. select '进程号SPID:'+ CAST(@spid AS VARCHAR(10))+ '被' + '进程号SPID:'+ CAST(@bl AS VARCHAR(10)) +'阻塞,其当前进程执行的SQL语法如下'.