50299.htm

来自「一本很基础的SQL讲解」· HTM 代码 · 共 124 行 · 第 1/2 页

<P>d) 执行Bookmark Lookup操作。nested loop操作的输出是一个内存数据结构，在从这个内存数据结构中整理出整个查询语句的输出结果集之前，需要处理前面的书签引用问题，Bookmark Lookup操作就是根据书签中引用的聚集索引键值或者rowid获取具体记录数据。</P>
<P>e) Filter过滤操作。回顾前面几个操作，在执行nested loop时只是使用非聚集索引的索引字段（tableB.col1）跟outer input的关联字段进行匹配，到目前为止还没有使用tableB.col2=?这个条件，这个操作就是使用tableB.col2=?对Bookmark Lookup的输出进行过滤。</P>
<P>看的仔细的人到这里后可能会有几个疑问，1. tableA.col2=?怎么没有一个Filter操作？2. 在1.4中为什么没有出现Filter操作？解释如下：1. 在tableA上面执行的是Table Scan操作，是直接对每条实际数据进行扫描，在这个扫描过程中可以使用tableA.col2=?这个条件进行过滤，避免一个额外的Filter操作。鼠标移动到Table Scan操作上，从提示信息的参数（Argument）里面可以看到tableA.col2=?的条件已经被运用上了。2. 前面说过，聚集索引的根节点是实际数据记录，执行Clustered Index Seek的时候，最终也是扫描到了实际数据记录，在这个过程中运用tableB.col2=?这个条件，同样避免一个额外的Filter操作。这就是1.4中没有Filter操作的原因。</P>
<P>f) 构造返回结果集。跟1.4步骤d)一样。</P>
<P><STRONG>1.6 nested loop使用条件</STRONG></P>
<P>任何一个join操作，如果满足nested loop使用条件，查询优化过程中SQL Server就会对nested loop的成本（I/O成本、CPU成本等）进行评估，基于评估结果确定是否使用这种join方式。</P>
<P>使用nested loop方式的条件是：a) outer input的记录数不大，最好是在1000-2000以下，一般超过3000就很难说了，基本不大会选择nested loop。b) 作为inner input的表中，有可用于这个查询的索引。</P>
<P>这是因为outer input记录数不大，意味着外层循环次数比较小；inner input上有可用的索引，意味着在循环里面搜索inner input表中是否存在匹配的记录时，效率会很高，哪怕inner input表实际记录数有几百万。基于这两个条件，nested loop的执行效率非常高，在三种join方式里面，是内存和CPU消耗最少的一种（不合理的强制指定nested loop方式除外）。</P>
<P>关于使用条件另外的说明：outer input的记录数，并不是指outer input表中实际记录数，例如示例SQL中，如果tableA在col2上有维护统计信息（存在col2的索引或者是单独维护的统计信息），并且tableA.col2=?的条件值符合SARG（可搜索参数）形式，那么查询编译时刻SQL Server就能够利用统计信息和条件值评估出符合条件的记录数，查询执行时刻符合条件tableA.col2=?的记录才被用于外层循环。inner input表中有可用的索引，是指inner input表中用于和outer input表关联的字段（一个或多个字段）能够命中某个索引（这些字段的部分或者全部出现在某个索引字段的前面）。</P>
<P>符合上面的条件，也不是说SQL Server 100%就会选择nested loop。因为SQL Server的查询优化器是基于成本评估的，如果其它方案评估出的成本胜过这个，SQL Server会选择其它的join方式。举个例子，如果inner input上符合条件的索引是非聚集索引，这样SQL Server可能需要一个额外的Bookmark Lookup操作获取实际记录数据，如果inner input表数据量非常大，索引碎片程度很高等情况，可能导致Bookmark Lookup成本非常高，SQL Server会尝试其它join方案的评估选择。</P>
<P><STRONG>1.7 强制指定nested loop方式</STRONG></P>
<P>使用loop关键字实现，例如tableA inner loop join tableB，将强制SQL Server使用nested loop方式执行这个join操作。或者使用option选项，例如tableA inner join tableB option(loop join)　nested loop算法有它适用的范围，在这个范围之内效率是最高的，超出这个范围效率反而很差，除非你有十分的把握，不要随意强制指定join方式。</P>
<P>接下来就不再象上面这样详细的讲述了。</P>
<P><STRONG>2. merge join</STRONG></P>
<P>merge join第一个步骤是确保两个关联表都是按照关联的字段进行排序。如果关联字段有可用的索引，并且排序一致，则可以直接进行merge join操作；否则，SQL Server需要先对关联的表按照关联字段进行一次排序（就是说在merge join前的两个输入上，可能都需要执行一个Sort操作，再进行merge join）。</P>
<P>两个表都按照关联字段排序好之后，merge join操作从每个表取一条记录开始匹配，如果符合关联条件，则放入结果集中；否则，将关联字段值较小的记录抛弃，从这条记录对应的表中取下一条记录继续进行匹配，直到整个循环结束。&nbsp;</P>
<P>#p#</P>
<P>在多对多的关联表上执行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的记录预先读出来放入内存临时表中，比从原数据页或磁盘读取要快。</P>
<P>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操作。</P>
<P>一般情况下，如果无法满足nested loop条件，会考虑对merge join方法的评估。merge join的选择，主要是考虑两个输入的数据量，以及分别对应于关联字段是否能够命中索引。例如tableA join tableB，关联字段在两个表中都能命中索引，数据量超过了nested loop的选择范围，则会考虑使用merge join方法。当然，如果tableA和tableB的数据量过大导致评估出来的成本过高，则会放弃merge join而评估hash join了。</P>
<P>使用inner merge join或者option(merge join)强制使用merge join方法。</P>
<P><STRONG>3. hash join</STRONG></P>
<P>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都是同一个记录集。</P>
<P>同nested loop，在执行计划中build input位于上方，probe input位于下方。</P>
<P>hash join操作分两个阶段完成：build（构造）阶段和probe（探测）阶段。</P>
<P><STRONG>Build阶段</STRONG></P>
<P>这个阶段主要构造hash table。在inner/left/right join等操作中，表的关联字段作为hash key；在group by操作中，group by的字段作为hash key；在union或其它一些去除重复记录的操作中，hash key包括所有的select字段。</P>
<P>Build操作从build input输入中取出每一行记录，将该行记录关联字段的值使用hash函数生成hash值，这个hash值对应到hash table中的hash buckets（哈希表目）。如果一个hash值对应到多个hash buckts，则这些hash buckets使用链表数据结构连接起来。当整个build input的table处理完毕后，build input中的所有记录都被hash table中的hash buckets引用/关联了。</P>
<P><STRONG>Probe阶段</STRONG></P>
<P>在这个阶段，SQL Server从probe input输入中取出每一行记录，同样将该行记录关联字段的值，使用build阶段中相同的hash函数生成hash值，根据这个hash值，从build阶段构造的hash table中搜索对应的hash bucket。hash算法中为了解决冲突，hash bucket可能会链接到其它的hash bucket，probe动作会搜索整个冲突链上的hash bucket，以查找匹配的记录。&nbsp;</P>
<P>关于hash算法的细节，可以查看数据结构的一些资料。hash算法主要是用于大数据量的搜索，为了避免每次都象merge join一样在全部的数据中进行搜索匹配，通过合适的 hash函数，先给要搜索的数据根据hash key建立hash值作为索引，在搜索时，先通过hash值定位到一个较小的搜索范围，然后在这个范围中搜索匹配符合条件的结果，以提高效率。&nbsp;</P>
<P>SQL Server将数据量较小的表作为build input，尽量使根据build input构造的hash table能够完全放在内存中，这样probe阶段的匹配操作就完全是在内存中进行，这样的hash join叫做In-Memory Hash Join。</P>
<P>如果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算法。</P>
<P>伴随着大数据的hash join运算，还会有standard external merge sorts、multiple merge levels、multiple partitioning steps、multiple partitioning levels，SQL Server还可能会使用Recursive Hash Join等算法或其它的优化手段。</P>
<P>hash join一般都用于大数据量的操作，例如join中某个表的数据达到一定程度或者无法一次加载到内存，另外如果你的关联字段在两个join表中都不能够命中索引，也是使用hash join来处理。因此一般情况下，hahs join处理代价非常高，是数据库服务器内存和CPU的头号杀手之一，尤其是涉及到分区（数据量太大导致内存不够的情况，或者并发访问很高导致当前处理线程无法获得足够的内存，那么数据量不是特大的情况下也可能需要进行分区），为了尽快的完成所有的分区步骤，将使用大量异步的I/O操作，因此期间单一一个线程就可能导致多个磁盘驱动器出于忙碌状态，这很有可能阻塞其它线程的执行。</P>
<P>使用inner hash join或者option (hash join)强制使用hash join方法。</P>
<P><STRONG>建议</STRONG></P>
<P>三种join方法，都是拥有两个输入。优化的基本原则：1. 避免大数据的hash join，尽量将其转化为高效的merge join、nested loop join。可能使用的手段有表结构设计、索引调整设计、SQL优化，以及业务设计优化。例如冗余字段的运用，将统计分析结果用service定期跑到静态表中，适当的冗余表，使用AOP或类似机制同步更新等。2. 尽量减少join两个输入端的数据量。这一点比较常犯的毛病是，条件不符合SARG（光这一点就有很多高超的技巧可以发挥），在子查询内部条件给的不充分（SQL过于复杂情况下SQL Server查询优化器经常犯傻，写在子查询外部的条件不会被用在子查询内部，影响子查询内部的效率或者是跟子查询再join时候的效率）。另外也是设计、业务端尽量限制这两个输入的数据量了。</P>
<P>关于业务设计方面的优化，参考以前写的一篇post：系统分析设计 一个JOIN问题解决方案的感想 重视业务分析设计。</P>
<P><STRONG>补充：关于SQL Server 2005</STRONG></P>
<P>大致看了下SQL Server 2005，执行计划的显示确实有一些不一样，但主要部分或者说原理上是差不多的，不会有多少偏差。上面的示例SQL，在tableB上面使用非聚集索引时，SQL Server 2005的执行计划图如下：</P>
<TABLE class=ln cellSpacing=0 borderColorDark=#ffffff align=center bgColor=#ddddd borderColorLight=#999999 border=1>
<TBODY>
<TR>
<TD bgColor=#ffffff>
<P align=left><IMG src="/files/uploadimg/20070702/1041532.gif"></P></TD></TR>
<TR>
<TD class=it align=middle bgColor=#dddddd>图3</TD></TR></TBODY></TABLE>
<P>一个主要的不同点是SQL Server 2000下面Bookmark Lookup操作，在2005下面显示成一个RID Lookup操作 + 一个Nested Loops操作实现，其实这也是很好理解的，可以说这样显示执行计划更合理一点，让你一看到这个操作，就知道它是通过一个循环机制到tableB中获取实际数据。</P>
<P>另外一点是，将鼠标移动到执行计划的图标上面后，弹出的提示信息的一些改变，例如2005里面会显示每个操作的输出列表（output list），而我上面的文章中基本都使用“输出数据结构”这样一个词汇在表达。通过查看output list，你更能明白RID Lookup（Bookmark Lookup）这样的操作存在的理由了。</P>
<P>最后，2005里面可以将图形显示的执行计划保存下来，以后可以打开再以图形方式进行查看分析，这个在2000下面是不行的，2000只能保存执行计划的文本。这样一些小功能对于分析SQL性能非常有用，在图形界面上的分析更直观。</P>
<P><FONT size=4>【相关文章】</FONT></P>
<UL type=disc>
<LI><A href="http://database.51cto.com/art/200601/20106.htm" target=_blank><U><FONT color=blue>SQL：JOIN之完全用法</FONT></U></A></LI></UL>
<UL type=disc>
<LI><A href="http://www.51cto.com/art/200511/11551.htm" target=_blank><U><FONT color=blue>SQL中的JOIN的简洁解释</FONT></U></A></LI></UL>
<DIV align=right>【责任编辑：<A class=ln href="mailto:[e-mail]">火凤凰</A> TEL：[phone]】</DIV></td>
      </tr>
      <tr>
        <td class="d_font4">&nbsp;</td>
      </tr>
    </table>