SQL ServerSQL算法多线程数据结构
1.基本概念:
Merge Join([排序]合并联接)、Nested Loops(嵌套循环联接)、Hash Match都是物理运算符。
Merge Join常执行Inner Join(内部联接)、Left Outer Join(左外部联接)、Left Semi Join(左半部联接)、Left Anti Semi Join(左反半部联接)、Right Outer Join(右外部联接)、Right Semi Join(右半部联接)、Right Anti Semi Join(右反半部联接)和Union(联合)逻辑操作。
在 Argument 列中,如果操作执行一对多联接,则 Merge Join 运算符将包含 MERGE:() 谓词;如果操作执行多对多联接,则该运算符将包含 MANY-TO-MANY MERGE:() 谓词。Argument 列还包含一个用于执行操作的列的列表,该列表以逗号分隔。Merge Join 运算符要求在各自的列上对两个输入进行排序,这可以通过在查询计划中插入显式排序操作来实现。如果不需要显式排序(例如,如果数据库内有合适的 B 树索引或可以对多个操作(如合并联接和对汇总分组)使用排序顺序),则合并联接尤其有效。
Nested Loops常执行Inner Join(内部联接)、Left Outer Join(左外部联接)、Left Semi Join(左半部联接)和Left Anti Semi Join(左反半部联接)逻辑操作。
Nested Loops通常使用索引在内部表中搜索外部表的每一行。根据预计的开销,Microsoft SQL Server决定是否对外部输入进行排序来改变内部输入索引的搜索位置。
将基于所执行的逻辑操作返回所有满足 Argument 列内的(可选)谓词的行。
Hash Match运算符通过计算其生成输入中每行的哈希值生成哈希表。HASH:()谓词以及一个用于创建哈希值的列的列表出现在Argument列内。然后,该谓词为每个探测行(如果适用)使用相同的哈希函数计算哈希值并在哈希表内查找匹配项。如果存在残留谓词(由 Argument 列中的 RESIDUAL:() 标识),则还须满足此残留谓词,只有这样行才能被视为是匹配项。行为取决于所执行的逻辑操作:
(1)对于联接,使用第一个(顶端)输入生成哈希表,使用第二个(底端)输入探测哈希表。按联接类型规定的模式输出匹配项(或不匹配项)。如果多个联接使用相同的联接列,这些操作将分组为一个哈希组。
(2)对于非重复或聚合运算符,使用输入生成哈希表(删除重复项并计算聚合表达式)。生成哈希表时,扫描该表并输出所有项。
(3)对于 union 运算符,使用第一个输入生成哈希表(删除重复项)。使用第二个输入(它必须没有重复项)探测哈希表,返回所有没有匹配项的行,然后扫描该哈希表并返回所有项。
2.执行步骤
Merge Join第一个步骤是确保两个关联表都是按照关联的字段进行排序。如果关联字段有可用的索引,并且排序一致,则可以直接进行Merge Join操作;否则,SQL Server需要先对关联的表按照关联字段进行一次排序(就是说在Merge Join前的两个输入上,可能都需要执行一个Sort操作,再进行Merge Join)。
两个表都按照关联字段排序好之后,Merge Join操作从每个表取一条记录开始匹配,如果符合关联条件,则放入结果集中;否则,将关联字段值较小的记录抛弃,从这条记录对应的表中取下一条记录继续进行匹配,直到整个循环结束。
在多对多的关联表上执行Merge Join时,通常需要使用临时表进行操作。例如A join B使用Merge Join时,如果对于关联字段的某一组值,在A和B中都存在多条记录A1、A2...An、B1、B2...Bn,则为A中每一条记录A1、A2...An,都必须在B中对所有相等的记录B1、B2...Bn进行一次匹配。这样,指针需要多次从B1移动到Bn,每一次都需要读取相应的B1...Bn记录。将B1...Bn的记录预先读出来放入内存临时表中,比从原数据页或磁盘读取要快。
Nested Loops也称为嵌套迭代,它将一个联接输入用作外部输入表(显示为图形执行计划中的顶端输入),将另一个联接输入用作内部(底端)输入表。外部循环逐行消耗外部输入表。内部循环为每个外部行执行,在内部输入表中搜索匹配行。最简单的情况是,搜索时扫描整个表或索引;这称为单纯嵌套循环联接。如果搜索时使用索引,则称为索引嵌套循环联接。如果将索引生成为查询计划的一部分(并在查询完成后立即将索引破坏),则称为临时索引嵌套循环联接。
Hash Match有两个输入:build input(也叫做outer input)和probe input(也叫做inner input),不仅用于inner/left/right join等,象union/group by等也会使用hash join进行操作,在group by中build input和probe input都是同一个记录集。
Hash Match操作分两个阶段完成:Build(构造)阶段和Probe(探测)阶段。
Build(构造)阶段主要构造哈希表(hash table)。在inner/left/right join等操作中,表的关联字段作为hash key;在group by操作中,group by的字段作为hash key;在union或其它一些去除重复记录的操作中,hash key包括所有的select字段。
Build操作从build input输入中取出每一行记录,将该行记录关联字段的值使用hash函数生成hash值,这个hash值对应到hash table中的hash buckets(哈希表目)。如果一个hash值对应到多个hash buckts,则这些hash buckets使用链表数据结构连接起来。当整个build input的table处理完毕后,build input中的所有记录都被hash table中的hash buckets引用/关联了。
Probe(探测)阶段,SQL Server从probe input输入中取出每一行记录,同样将该行记录关联字段的值,使用build阶段中相同的hash函数生成hash值,根据这个hash值,从build阶段构造的hash table中搜索对应的hash bucket。hash算法中为了解决冲突,hash bucket可能会链接到其它的hash bucket,probe动作会搜索整个冲突链上的hash bucket,以查找匹配的记录。
如果build input记录数非常大,构建的hash table无法在内存中容纳时,SQL Server分别将build input和probe input切分成多个分区部分(partition),每个partition都包括一个独立的、成对匹配的build input和probe input,这样就将一个大的hash join切分成多个独立、互相不影响的hash join,每一个分区的hash join都能够在内存中完成。SQL Server将切分后的partition文件保存在磁盘上,每次装载一个分区的build input和probe input到内存中,进行一次hash join。这种hash join叫做Grace Hash join,使用的Grace Hash Join算法。
3.性能分析
Merge Join(合并联接)本身的速度很快,但如果需要排序操作,选择合并联接就会非常费时。然而,如果数据量很大且能够从现有 B 树索引中获得预排序的所需数据,则合并联接通常是最快的可用联接算法。如果是无序的数据,Merge Join首先做的是排序,如果数据量大,排序就会溢出到tempdb, 效率就将低了。
如果外部输入很小(<10000)而内部输入很大且预先创建了索引,则Nested Loops(嵌套循环联接)尤其有效。在许多小事务中(如那些只影响较小的一组行的事务),索引嵌套循环联接远比合并联接和哈希联接优越。但在大查询中,嵌套循环联接通常不是最佳选择。
如果两个表的数据量差别很大,则使用Hash Match。但需要注意的是:如果HASH表太大,无法一次构造在内存中,则分成若干个partition,写入磁盘的temporary segment,则会多一个I/O的代价,会降低效率,此时需要有较大的temporary segment从而尽量提高I/O的性能。Hash join的主要资源消耗在于CPU(在内存中创建临时的HASH表,并进行HASH计算),而Merge join的资源消耗主要在于磁盘I/O(扫描表或索引)。
4.优化原则
一般情况下,Hash Join处理代价非常高,是数据库服务器内存和CPU的头号杀手之一,尤其是涉及到分区(数据量太大导致内存不够的情况,或者并发访问很高导致当前处理线程无法获得足够的内存,那么数据量不是特大的情况下也可能需要进行分区),为了尽快的完成所有的分区步骤,将使用大量异步的I/O操作,因此期间单一一个线程就可能导致多个磁盘驱动器出于忙碌状态,这很有可能阻塞其它线程的执行。 因此,
1. 要避免大数据的Hash Join,尽量将其转化为高效的Merge Join、Nested Loops。可能使用的手段有表结构设计、索引调整设计、SQL优化,以及业务设计优化。例如冗余字段的运用,将统计分析结果用service定期跑到静态表中,适当的冗余表,使用AOP或类似机制同步更新等。
2. 尽量减少join两个输入端的数据量。这一点比较常犯的毛病是,条件不符合SARG,在子查询内部条件给的不充分(SQL过于复杂情况下SQL Server查询优化器经常犯傻,写在子查询外部的条件不会被用在子查询内部,影响子查询内部的效率或者是跟子查询再join时候的效率)。
本文来自CSDN博客,转载请标明出处:http://blog.csdn.net/yongsheng0550/archive/2010/04/05/5452200.aspx
分享到:
相关推荐
数据库 我自己在 Java 中实现了 SortMergeJoin 和 HashJoin(来自 SQL 的著名 INNER JOIN)。 在更多信息。
在对传统的Sort-Merge-Join算法进一步研究的基础上,提出了一种改进的闪存数据库Sort-Merge-Join算法。该算法只对小关系进行外...通过理论分析和与传统Sort-Merge-Join算法在闪存上的比较实验,证明了该算法的优越性。
数据库中JOIN操作的实现主要有三种:嵌套循环连接(Nested Loop Join),归并连接(Merge Join)和散列连接或者哈稀连接(Hash Join)。其中嵌套循环连接又视情况又有两种变形:块嵌套循环连接和索引嵌套循环连接。
NULL 博文链接:https://forlan.iteye.com/blog/2245814
Sql中的三种物理连接操作 嵌套循环连接(Nested Loop Join) 合并连接(Merge Join) 哈希匹配(Hash Join)
sql学习 Merge Sort Join优化第4式(保证PGA尺寸).sql
sql学习 Merge Sort Join优化第2式(连接条件索引消除排序).sql
sql学习 Merge Sort Join优化第1式(两表限制条件有索引).sql
在 Hibernate 中,merge 方法是非常重要的一个方法,它能够帮助开发者轻松地处理数据的更新和插入操作。那么,merge 方法到底如何工作的呢?下面,我们将对 merge 方法进行详细的解释。 首先,merge 方法是一个可以...
里面给大家内嵌了Araxis Merge v6.5和Araxis Merge 2017两个版本,并配备了使用说明。 Araxis Merge v6.5:免安装版本,解压直接运行merge.exe即可正常使用(目前好像不支持Win10系统了,但是我同事的win10可以用,...
sql学习 Merge Sort Join优化第3式(避免取多余列致排序尺寸过大).sql
android中include和merge标记的区别和使用
Hibernate中session的merge以及update方法
Araxis.Merge.Professional.v2012.4162.x64-BEAN_的中文启动包
通过 Merge Into 语句,我们能够在一个语句中对一个表同时执行 Insert 和 Update 操作,根据这个表或子查询的连接条件对另一个表进行查询,连接条件匹配上的进行 Update 操作,并且在其后面还可以接删除操作,无法...
Android UI优化之merge标签的使用,主要介绍merge方法使用的注意事项及方法实现。
Oracle中merge into的使用 很有用的哦 学习一下
为SQL生成最佳的执行计划,比如什么时候是全表扫描(FTS full table scan),什么时候是 索引范围搜索(Index Range Scan),或者是全...HASH_JOIN 还是NESTED LOOPS 或者是MERGE JOIN。这些因素直接决定了SQL 的执行效率。
* merge 和 union 一般来说是对要素类中的“要素”来说的,也就是说,对某一部分要素进行操作 * merge 是对同一个要素类中的要素的操作,操作完成后原来的要素消失 * union 则灵活一些,可以对不同图层的要素进行...
Oracle 提供了多种表连接方式,包括 Hash Join、Nested Loop 和 Sort Merge。每种方式都有其特点和工作原理: * Nested Loop:使用条件:任何连接;优点:当有高选择性索引或进行限制性搜索时效率比较高,能够快速...