SQL Server 三大算法（嵌套，合并，哈希)的IO成本总结

SQL Server 三大算法（嵌套，合并，哈希)的IO成本

1. Nested Loop Join(嵌套循环联结)

算法：

其思路相当的简单和直接：对于关系R的每个元组 r 将其与关系S的每个元组 s 在JOIN条件的字段上直接比较并筛选出符合条件的元组。写成伪代码就是：

代价：

被联结的表所处内层或外层的顺序对磁盘I/O开销有着非常重要的影响。而CPU开销相对来说影响较小，主要是元组读入内存以后(in-memory)的开销，是 O (n * m)

对于I/O开销，根据 page-at-a-time 的前提条件，I/O cost = M + M * N， 翻译一下就是 I/O的开销 = 读取M页的I/O开销 + M次读取N页的I/O开销。

2. Sort-Merge Join (排序合并联结)

Nested Loop一般在两个集合都很大的情况下效率就相当差了，而Sort-Merge在这种情况下就比它要高效不少，尤其是当两个集合的JOIN字段上都有聚集索引(clustered index)存在时，Sort-Merge性能将达到最好。

算法：

基本思路也很简单(复习一下数据结构中的合并排序吧)，主要有两个步骤：

(1) 按JOIN字段进行排序

(2) 对两组已排序集合进行合并排序，从来源端各自取得数据列后加以比较(需要根据是否在JOIN字段有重复值做特殊的“分区”处理)

代价：(主要是I/O开销)

有两个因素左右Sort-Merge的开销：JOIN字段是否已排序 以及 JOIN字段上的重复值有多少。

? 最好情况下(两列都已排序且至少有一列没有重复值)：O (n + m) 只需要对两个集合各扫描一遍。（这里的m，n如果都能用到索引那就更好了）

? 最差情况下(两列都未排序且两列上的所有值都相同)：O (n * log n + m * log m + n * m) 两次排序以及一次全部元组间的笛卡尔乘积

3. Hash Join (哈希联结)

Hash Join在本质上类似于两列都有重复值时的Sort-Merge的处理思想——分区(patitioning)。但它们也有区别：Hash Join通过哈希来分区(每一个桶就是一个分区)而Sort-Merge通过排序来分区(每一个重复值就是一个分区)。

值得注意的是，Hash Join与上述两种算法之间的较大区别同时也是一个较大限制是它只能应用于等值联结(equality join)，这主要是由于哈希函数及其桶的确定性及无序性所导致的。 算法：

基本的Hash Join算法由以下两步组成：

同nested loop，在执行计划中build input位于上方，probe input位于下方。 hash join操作分两个阶段完成：build（构造）阶段和probe（探测）阶段。

(1) Build Input Phase： 基于JOIN字段，使用哈希函数h2为较小的S集合构建内存中(in-memory)的哈希表，相同键值的以linked list组成一个桶(bucket)

(2) Probe Input Phase： 在较大的R集合上对哈希表进行核对以完成联结。 代价：

值得注意的是对于大集合R的每个元组 r ，hash bucket中对应 r 的那个bucket中的每个元组都需要与 r 进行比较，这也是算法最耗时的地方所在。

CPU开销是O (m + n * b) b是每个bucket的平均元组数量。

总结：

三种join方法，都是拥有两个输入，优化的基本原则：

1. 避免大数据的hash join，（hash join适合低并发情况，他占用内存和io是很大的）。

2，尽量将其转化为高效的merge join、nested loop join。可能使用的手段有表结构设计、索引调整设计、SQL优化，以及业务设计优化

 

第二篇：SQL Server数据查询基本方法的总结

【IT168 技术文档】首先创建一个简单的数据库作为示例数据库，数据库名称为school_db,里面有三张表

Department_TBL(DNO,DName),Class_TBL(CNO,CName,DNO),Student_TBL(SNO,SName,SSex,CNO)

一 基本查询

基本语法：select (查询列表|*) from (表列表)

说明：“查询列表”可以是表的字段，表达式，函数。“表列表”可以包含多张表

示例：查询所有学生的基本信息

Select * from Student_TBL

二 where条件查询

基本语法：select (查询列表|*) from (表列表) where (限制条件) 说明：where关键字后面的限制条件不能包含聚合函数

示例：查询所在班级编号是“003”的学生的基本信息

Select * from Student_TBL where CNO=’003’

三 关键字in的使用

基本语法：select (查询列表|*) from (表列表) where (字段名) in (值集合)

说明：in关键字的作用是查询某一字段是否在一个集合中，一般在where语句中使用

示例:查询学号为23，34，35，40 学生的信息

Select * from Student_TBL where SNO in (23,34,35,40)

四 between和 Not between的使用

基本语法：select (查询列表|*) from (表列表) where (字段名) between||not between 值1 AND 值2

说明：判断某个字段的值是否在一个范围之内

示例：查询所有学号大于5小于30的学生的信息

Select * from Student_TBL where SNO between 5 and 30

五 消除结果集中的重复行

基本语法：select distinct column1,? from (表列表)

说明：去除结果集中跟在distinct关键字后面所有字段的值相等的记录 示例：查询所有学生的信息,删除名字相同的多余行

Select distinct column1,? from Student_TBL

六 返回指定的行数(百分率)

基本语法：select top n [percent](column1,?) from (表列表)

说明：n为要返回的行数，若含有percent关键字则按百分比返回，则此时n必须在0~100之间，若查询语句中含有order by 则先对查询结果进行排序，再执行筛选

示例：返回前十名学生的基本信息

Select top 10 * from Student_TBL

返回前百分之十的学生的基本信息

Select top 10 percent * from Student_TBL

七 改变查询标题

基本语法：select ‘自定义标题’=column1,?. From (表列表)，select column1 ‘自定义标题’,?. From (表列表)，select column1 as ‘自定义标题’,? from (表列表)

说明：改变的只是查询结果的标题，并没有改变表的标题

示例：查询学生的基本信息，SNO，SName，CNO分别用“学号”，“姓名”,”所属班级”显示

、这里只使用第三种方法演示了

Select ‘学号’ as SNO,’姓名’ as SName,’所属班级’ as ‘CNO’ from Student_TBL

八 在查询结果中显示字符串

基本语法：在select 语句中，将增加的字符串用单引号括起来然后和列的名字写在一起，中间用逗号分开

示例：查询所有学生信息，显示的结果的形式是“学号+“我的姓名是+”性命+班级编号”

Select SNO,’我的姓名是’,SName,CNO from Student_TBL

九 order by的使用

基本语法：

select * from table_Name [where..] order by column1 [asc]desc]?

说明：order by 后面可以指定多个列，默认是按升序方式排列的，order by 放在where 语句之后

示例：查询所有学好大于23号的学生信息，并按学号的降序排列 Select * from Student_TBL where SNO>23 order by SNO desc

十 使用Like实现模糊查询

基本语法：select * from table_Name where column like (匹配条件) 说明：“%”匹配任意长度的(长度可以为0)字符串，“_”匹配任意单个字符，“[]”：匹配所给定范围或集合中的任意单个字符，“[^]”匹配所给定的不在所给定的集合或范围中的任意单个字符，通配符或字符串必须用单引号括起来

示例：查询所有姓李的同学地信息

Select * from Student_TBL where SName like ‘李%’

查询所有学生名字中第二个字为“冰”的同学的信息

Select * from Student_TBL where SName like ‘_冰%’

查询所有编号中含有’e,t,y’字符的班级信息

Select * from Class_TBL where CNO like ‘[e,t,y]’

查询所有编号中不含有’e,t,y’字符的班级信息

Select * from Class_TBL where CNO like ‘[^e,t,y]’

十一 使用is null

基本语法：

select * from table_Name where column is null

说明：查询指定列为输入数据的数据行，通常用在where语句中 示例：查询还没有分配班级的学生的信息

十二 使用compute进行计算

基本语法：select * from table_name where 查询条件 compute 聚合函数 说明：用来计算总计或进行分组小计，总计或小计值作为附加行出现在查询结果中

示例：计算在编号为‘001’班级的学生的信息并统计该班有多少个学生 Select * from Student_TBL where CNO=’001’ compute count(*) 十三 使用compute by分组查询结果

基本语法：select * from table_Name [where..] order by column compute 聚合函数 by column

说明：在使用compute by之前必须先使用order by 对要进行分组的列进行排序，注意，在oerder by 中进行排序的列的数量和顺序必须和compute by 后的项一样

示例：根据不同班级分组统计各个班级学生的信息

Select * from Student_TBL order by CNO compute count(SNO) by CNO 十四 使用group by

基本语法：select * from table_name [where?] group by column

说明：在select 子句中使用聚合函数时，group by计算每组的汇总值，使用group by子句时，在select 子句中出现的列名或者出现在聚合函数中，或者出现在group by 子句后面，否则会抱错，另外group by后面还可以恩 with cube||rollup,

示例：统计每个班级有多少学生，不显示学生的信息，只显示统计信息 Select CNO,count(SNO) from Student_TBL group by CNO

十五使用having语句

基本语法：select * from table_name [where ?] group by column having ?

说明：having子句用于限定对组或者聚合函数的查询条件，该子句常用于group by 子句后面，在查询结果分组后对组判断是否满足查询条件，在分组之前可以用where语句判断查询条件，使用where比使用having更有效，因为它先将不满足条件的行过滤掉，从而减少了要进行分组的行数

示例：分组统计除编号为‘001’外所有班级学生的人数 Select CNO,count(SNO) from Student_TBL group by CNO having CNO<>’001’

十六 子查询

基本语法：

说明：子查询是在查询中包含另一个查询的查询，可以使用子查询代替表达式，自查询只能返回一列数，有时只返回但个值

示例：查询班级人数大于平均班级人数的班级 Select * from Class_TBL where (select count(*)

from student where CNO=Class_TBL.CNO)>((select count(*) from Student_TBL)/(

十七 使用union运算符合并多个查询结果

基本语法：

select column1 from table1_name union select column2 from table2_name

说明：所有查询中的列数和列的顺序必须相同，所有查询中按顺序对应列的数据类型必须相同或兼容，如果希望重新排序多个查询结果的合并结果，则在最后的select 语句中使用order by子句

十八 查询多个表或视图的信息

基本语法：select column1,column2,? from talbe1,table2,?

说明：在涉及多表查询时必须使用where语句给出多表之间的连接条件，对来自N各表或视图查询要写出N-1 个连接条件

示例：查询每个学生所在的系部的名称，班级的名称和姓名 Select DName,CName,SName

from Student_TBL S,Class_TBL C,Department_TBL Dwhere S.CNO=C.CNO and

C.DNO=D.DNO

十九 相等连接与自然连接：相等连接是将要连接的列作相等比较的连接，在相等连接列中只保留一个连接列的连接称为自然连接

二十 比较连接：表与表之间的连接不使用“=”连接，而是使用比较运算符的连接

二十一 自连接就是表与它自己进行连接

二十二 左连接，右连接和全连接

二十三 使用exists：在where子句中可以使用exists子句，它用于测试跟随的子查询中的行是否存在