SQL数据库使⽤JOIN的优化⽅法（转）
很早以前，也是⼀提到SQL Server，就觉得它的性能没法跟Oracle相⽐，⼀提到⼤数据处理就想到Oracle。⾃⼰⼀路⾛来，在本地blog上记录了很多优化⽅⾯的 post，对的错的都有，没有时间系列的整理出来，这篇⽂章将join⽅法的概念稍微整理在⼀起，给⼤家个参考。通过查资料了解⾥⾯提到的各种概念，在实 际中不断验证总结，完全可以对数据库⼀步步深⼊理解下去的。
我只对SQL Server 2000⽐较了解，但这并不阻碍我在Oracle、MySql进⾏SQL调优、产品架构，因为在数据库理论原理上，各⼤数据库基本出⼊不⼤，对数据库的深⼊理解，也不会影响你架构设计思想变坏，相反给你带来的是更深层次的思考。
关于执⾏计划的说明
在SQL Server查询分析器的Query菜单中选择Show Execution Plan，运⾏SQL查询语句，在结果窗⼝中有Grid、Execution Plan、Messages三个Tab。看图形形式的执⾏计划，顺序是从右到左，这也是执⾏的顺序。执⾏计划中的每⼀个图标表⽰⼀个操作，每⼀个操作都会 有⼀个或多个输⼊，也会有⼀个或多个输出。输⼊和输出，有可能是⼀个物理数据表、索引数据结构，或者是执⾏过程中的⼀些中间结果集/数据结构。⿏标移动到 图标上，会显⽰这个操作的具体信息，例如逻辑和物理操作名称、记录的数量和⼤⼩、I/O成本、CPU成本、操作的具体表达式（参数Argument）。⿏ 标移动到连接箭头上，会显⽰箭
头起始端的操作输出结果集的记录数、记录的⼤⼩，⼀般情况下可以将这个输出结果集理解为箭头结束端的输⼊。
另 外关于执⾏计划的⼀些补充说明：1. 执⾏计划中显⽰的信息，都是⼀个“评估”的结果，不是100%准确的信息，例如记录数量是取⾃统计信息，I/O成本、CPU成本来⾃执⾏计划⽣成过程中基 于统计信息等得出的评估结果。2. 执⾏计划不⼀定准确，⼀⽅⾯受SQL Server 维护的统计信息准确性的影响，另⼀⽅⾯SQL语句编译时刻与执⾏时刻的环境（内存使⽤状况、CPU状况等）可能会不⼀样。
关于统计信息、I/O成本和CPU成本的评估、SQL语句的编译和执⾏过程，这⾥不再深⼊。另外尽管执⾏计划不⼀定准确，但它仍是SQL语句分析最重要的依据，因为你可以理解为，绝⼤部分情况下，SQL Server是以这种⽅式来执⾏的。
JOIN⽅法说明
数据库中，象tableA inner join tableB、tableA left out join tableB这样的SQL语句是如何执⾏join操作的？就是说SQL Server使⽤什么算法实现两个表数据的join操作？
SQL Server 2000有三种⽅式：nested loop、merge、hash。Oracle也是使⽤这三种⽅式，不过Oracle选择使⽤nested loop的条件跟SQL Server有点差别，内存管理机制跟SQL Server不⼀样，因此
查看执⾏计划，Oracle中nested loop运⽤⾮常多，⽽merge和hash⽅式相对较少，SQL Server中，merge跟hash⽅式则是⾮常普遍。
以SQL Server 2000为例对这三种⽅式进⾏说明，穿插在⾥⾯讲解执⾏计划的⼀些初级使⽤。
1. nested loop join
1.1 ⽰例SQL
select ... from tableA inner join tableB l1 l2=? l2=?tableA中没有建⽴任何索引，tableB中在col1上有建⽴⼀个主键（聚集索引）。
1.2 算法伪代码描述
foreach rowA in tableA l2=?{search rowsB from tableB l1 l2=?
;if(rowsB.Count<=0)discard rowA ;elseoutput rowA and rowsB ;}
join操作有两个输⼊，上⾯例⼦中tableA是outer input，⽤于外层循环；tableB是inner input，⽤于循环内部。下⾯针对执⾏计划描述⼀下SQL Server完成这个操作的具体步骤。 %. ^ g.L
2vt [ AhVA
1.3 查看执⾏计划⽅法
sql优化的几种方式移到⽂章最前⾯。
1.4 执⾏步骤
下 ⾯是⽰例SQL的执⾏计划图。 nested loop操作的右边，位于上⾯的是outer input，位于下⾯的是inner input。你不能够根据join中哪个表出现在前⾯来确定outer input和inner input关系，⽽必须从执⾏计划中来确定，因为SQL Server会⾃动选择哪个作为inner input。
a) 对tableA执⾏Table Scan操作。这个操作的输⼊是tableA表中的数据，这些数据位于磁盘上，操作过程中被加载到内存；输出是符合条件的记录集，将作为b)的outer input。在这个操作中，l1=?的条件会被使⽤。
b) 执⾏上⾯伪代码描述的nested loop操作。对a)中的每个输出记录，执⾏步骤c)。
c) 对tableB执⾏Clustered Index Seek操作。这个操作是在nested loop循环⾥⾯执⾏的，输⼊是tableB表的聚集索引数据。它使⽤l1和l2=?这两个条 件，从tableB的聚集索引中选择符合条件的结果。
d) 构造返回结果集。从nested loop的输出中，整理出select中指定的字段，构造最终输出结果集。
1.5 进阶说明
上⾯例⼦对inner input使⽤的是聚集索引，下⾯看⼀下⾮聚集索引的情况，加强对执⾏计划的理解、分析能⼒。
把tableB col1上的主键修改为⾮聚集⽅式，⽰例的SQL语句执⾏计划如下：
图2
前 ⾯三个执⾏步骤a)、b)、 c)跟1.4中⼀样，有⼀点需要注意的是，步骤c)是执⾏Index Seek操作，它跟Clustered Index Seek有区别。聚集索引的根节点是每⼀条实际数据记录，⽽⾮聚集索引的根节点是对聚集索引根结点键值的引⽤（如果表存在聚集索引），或者是对实际数据记 录rowid的引⽤（指没有聚集索引的表，这种表称为heap表）。Clustered Index Seek执⾏之后，实际的物理数据记录已经被加载到内存中，⽽Index Seek操作之后，并没有加载实际的物理数据记录，⽽只是⾮聚集索引的根结点数据，其中只包含了索引字
段数据以及引⽤的聚集索引键值或者rowid。 SQL Server在这个步骤中使⽤⾮聚集索引根结点数据中的索引字段值，与outer input中的记录（rowA）关联字段进⾏匹配，判断是否是符合条件的结果，如
果是，则将⾮聚集索引根结点数据结构保存到nested loop操作的输
出数据结构中，并且会创建⼀个书签（Bookmark），指⽰在必要的时候需要根据这个书签去获取引⽤的数据。
d) 执⾏Bookmark Lookup操作。nested loop操作的输出是⼀个内存数据结构，在从这个内存数据结构中整理出整个查询语句的输出结果集之前，需要处理前⾯的书签引⽤问题，Bookmark Lookup操作就是根据书签中引⽤的聚集索引键值或者rowid获取具体记录数据。
e) Filter过滤操作。回顾前⾯⼏个操作，在执⾏nested loop时只是使⽤⾮聚集索引的索引字段（l1）跟outer input的关联字段进⾏匹配，到⽬前为⽌还没有使⽤l2=?这个条件，这个操作就是使⽤l2=?对 Bookmark Lookup的输出进⾏过滤。
看 的仔细的⼈到这⾥后可能会有⼏个疑问，1. l2=?怎么没有⼀个Filter操作？2. 在1.4中为什么没有出现Filter操作？解释如下：1. 在tableA上⾯执⾏的是Table Scan操作，是直接对每条实际数据进⾏扫描，在这个扫描过程中可以使⽤l2=?这个条件进⾏过滤，避免⼀个额外的Filter操作。
⿏标移动到Table Scan操作上，从提⽰信息的参数（Argument）⾥⾯可以看到l2=?的条件已经被运⽤上了。2. 前⾯说过，聚集索引的根节点是实际数据记录，执⾏Clustered Index Seek的时候，
最终也是扫描到了实际数据记录，在这个过程中运⽤l2=?这个条件，同样避免⼀个额外的Filter操作。这就是 1.4中没有Filter操作的原因。
f) 构造返回结果集。跟1.4步骤d)⼀样。
1.6 nested loop使⽤条件
任何⼀个join操作，如果满⾜nested loop使⽤条件，查询优化过程中SQL Server就会对nested loop的成本（I/O成本、CPU成本等）进⾏评估，基于评估结果确定是否使⽤这种join⽅式。
使⽤nested loop⽅式的条件是：a) outer input的记录数不⼤，最好是在1000-2000以下，⼀般超过3000就很难说了，基本不⼤会选择nested loop。b) 作为inner input的表中，有可⽤于这个查询的索引。
这 是因为outer input记录数不⼤，意味着外层循环次数⽐较⼩；inner input上有可⽤的索引，意味着在循环⾥⾯搜索inner input表中是否存在匹配的记录时，效率会很⾼，哪怕inner input表实际记录数有⼏百万。基于这两个条件，nested loop的执⾏效率⾮常⾼，在三种join⽅式⾥⾯，是内存和CPU消耗最少的⼀种（不合理的强制指定nested loop⽅式除外）。
关 于使⽤条件另外的说明：outer input的记录数，并不是指outer input表中实际记录数，例如⽰例SQ
L中，如果tableA在col2上有维护统计信息（存在col2的索引或者是单独维护的统计信息），并且 l2=?的条件值符合SARG（可搜索参数）形式，那么查询编译时刻SQL Server就能够利⽤统计信息和条件值评估出符合条件的记录数，查询执⾏时刻符合条件l2=?的记录才被⽤于外层循环。inner input表中有可⽤的索引，是指inner input表中⽤于和outer input表关联的字段（⼀个或多个字段）能够命中某个索引（这些字段的部分或者全部出现在某个索引字段的前⾯）。
符 合上⾯的条件，也不是说SQL Server 100%就会选择nested loop。因为SQL Server的查询优化器是基于成本评估的，如果其它⽅案评估出的成本胜过这个，SQL Server会选择其它的join⽅式。举个例⼦，如果inner input上符合条件的索引是⾮聚集索引，这样SQL Server可能需要⼀个额外的Bookmark Lookup操作获取实际记录数据，如果inner input表数据量⾮常⼤，索引碎⽚程度很⾼等情况，可能导致Bookmark Lookup成本⾮常⾼，SQL Server会尝试其它join⽅案的评估选择。
1.7 强制指定nested loop⽅式
使 ⽤loop关键字实现，例如 tableA inner loop join tableB，将强制SQL Server使⽤nested loop⽅式执⾏这个join操作。或者使⽤option选项，例如tableA inner join tableB option(loop join)　nested loop算法有它适⽤的范围，在这个范围之内效率是最⾼的，超出这个范围效率反⽽很差，除⾮你有⼗分的把握，不要随意强制指定join⽅式。
接下来就不再象上⾯这样详细的讲述了。
2. merge join
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的记录预先读出来放⼊内存临时表中，⽐从原数据页或磁盘读取要快。
merge join操作本⾝是⾮常快的，但是merge join前进⾏的排序可能会相当耗时（SQL Server最消耗内存和CPU的操作，⼀个是⼤数据排序，⼀个是⼤数据的hash运算，这都是指查询计划⾥⾯的Sort以及Hash相关的操作，例如 hash join、使⽤hash算法实现的Distinct操作等，⽽不是指你的SQL中order by关键字），尤其是对数据量⾮常⼤的记录集，因此导致使⽤merge join的查询成本变得⾮常⾼。对于数据量⾮常⼤的表，如果merge join的关联字段可以使⽤聚集索引，merge join是最快的Join⽅法之⼀。因此优化⽅案是在表结构设计层⾯良好的设计关联关系和表的索引结构，SQL语句充分利⽤索引，尽可能减少merge join前的排序操作，减少Bookmark Lookup操作。
⼀ 般情况下，如果⽆法满⾜nested loop条件，会考虑对merge join⽅法的评估。merge join的选择，主要是考虑两个输⼊的数据量，以及分别对应于关联字段是否能够命中索引。例如tableA join tableB，关联字段在两个表中都能命中索引，数据量超过了nested loop的选择范围，则会考虑使⽤merge join⽅法。当然，如果tableA和tableB的数据量过⼤导致评估出来的成本过⾼，则会放弃merge join⽽评估hash join了。 ~2 $`$RkZv
g&xw)W9p
使⽤inner merge join或者option(merge join)强制使⽤merge join⽅法。
3. hash join
hash join有两个输⼊：build input（也叫做outer input）和probe input（也叫做inner input），不仅⽤于inner/left/right join 等，象union/group by等也会使⽤hash join进⾏操作，在group by中build input和probe input都是同⼀个记录集。
同nested loop，在执⾏计划中build input位于上⽅，probe input位于下⽅。
hash join操作分两个阶段完成：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，以查匹配的记录。
关 于hash算法的细节，可以查看数据结构的⼀些资料。hash算法主要是⽤于⼤数据量的搜索，为了避免每次都象merge join⼀样在全部的数据中进⾏搜索匹配，通过合适的 hash函数，先给要搜索的数据根据hash key建⽴hash值作为索引，在搜索时，先通过hash 值定位到⼀个较⼩的搜索范围，然后在这个范围中搜索匹配符合条件的结果，以提⾼效率。
SQL Server将数据量较⼩的表作为build input，尽量使根据build input构造的hash table能够完全放在内存中，这样probe阶段的匹配操作就完全是在内存中进⾏，这样的hash join叫做In-Memory Hash Join。
如 果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算法。
伴 随着⼤数据的hash join运算，还会有standard external merge sorts、multiple merge levels、multiple partitioning steps、multiple partitioning levels，SQL Server还可能会使⽤Recursive Hash Join等算法或其它的优化⼿段。
hash join⼀般都⽤于⼤数据量的操作，例如join中某个表的数据达到⼀定程度或者⽆法⼀次加载到内存，另外如果你的关联字段在两个join表中都不能够命 中索引，也是使⽤hash join来处理。因此⼀般情况下，hahs join处理代价⾮常⾼，是数据库服务器内存和CPU的头号杀⼿之⼀，尤其是涉及到分区（数据量太⼤导致内存不够的情况，或者并发访问很⾼导致当前处理线 程⽆法获得⾜够的内存，那么数据量不是特⼤的情况下也可能需要进⾏分区），为了尽快的完成所有的分区步骤，将使⽤⼤量异步的I/O操作，因此期间单⼀⼀个 线程就可能导致多个磁盘驱动器出于忙碌状态，这很有可能阻塞其它线程的执⾏。
使⽤inner hash join或者option (hash join)强制使⽤hash join⽅法。
建议
三 种join⽅法，都是拥有两个输⼊。优化的基本原则：1. 避免⼤数据的hash join，尽量将其转化为⾼效的merge join、nested loop join。可能使⽤的⼿段有表结构设计、索引调整设计、SQL优化，以及业务设计优化。例如冗余字段的运⽤，将统计分析结果⽤service定期跑到静态 表中，适当的冗余表，使⽤AOP或类似机制同步更新等。2. 尽量减少join两个输⼊端的数据量。这⼀点⽐较常犯的⽑病是，条件不符合SARG（光这⼀点就有很多⾼超的技巧可以发挥），在⼦查询内部条件给的不充分 （SQL过于复杂情况下SQL Server查询优化器经常犯傻，写在⼦查询外部的条件不会被⽤在⼦查询内部，影响⼦查询内部的效率或者是跟⼦查询再join时候的效率）。另外也是设 计、业务端尽量限制这两个输⼊的数据量了。
关于业务设计⽅⾯的优化，参考以前写的⼀篇post：系统分析设计 ⼀个JOIN问题解决⽅案的感想 重视业务分析设计。
补充：关于SQL Server 2005
⼤致看了下SQL Server 2005，执⾏计划的显⽰确实有⼀些不⼀样，但主要部分或者说原理上是差不多的，不会有多少偏差。上⾯的⽰例SQL，在tableB上⾯使⽤⾮聚集索引时，SQL Server 2005的执⾏计划图如下：
图3
⼀ 个主要的不同点是SQL Server 2000下⾯Bookmark Lookup操作，在2005下⾯显⽰成⼀个RID Lookup操作 + ⼀个Nested Loops操作实现，其实这也是很好理解的，可以说这样显⽰执⾏计划更合理⼀点，让你⼀看到这个操作，就知道它是通过⼀个循环机制到tableB中获取实 际数据。
另 外⼀点是，将⿏标移动到执⾏计划的图标上⾯后，弹出的提⽰信息的⼀些改变，例如2005⾥⾯会显⽰每个操作的输出列表（output list），⽽我上⾯的⽂章中基本都使⽤“输出数据结构”这样⼀个词汇在表达。通过查看output list，你更能明⽩RID Lookup（Bookmark Lookup）这样的操作存在的理由了。
最后，2005⾥⾯可以将图形显⽰的执⾏计划保存下来，以后可以打开再以图形⽅式进⾏查看分析，这个在2000下⾯是不⾏
的，2000只能保存执⾏计划的⽂本。这样⼀些⼩功能对于分析SQL性能⾮常有⽤，在图形界⾯上的分析更直观。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。