数据库性能优化JOIN方法说明(2)

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 on tableA.col1=tableB.col1 where tableA.col2=? and tableB.col2=?tableA中没有建立任何索引，tableB中在col1上有建立一个主键（聚集索引）。

1.2 算法伪代码描述

    foreach rowA in tableA where tableA.col2=?{search rowsB from tableB where tableB.col1=rowA.col1 and tableB.col2=? ;if(rowsB.Count<=0)discard rowA ;elseoutput rowA and rowsB ;}

join操作有两个输入，上面例子中tableA是outer input，用于外层循环；tableB是inner input，用于循环内部。下面针对执行计划描述一下SQL Server完成这个操作的具体步骤。

1.3 查看执行计划方法

移到文章最前面。

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。在这个操作中，tableA.col1=?的条件会被使用。

b) 执行上面伪代码描述的nested loop操作。对a)中的每个输出记录，执行步骤c)。

c) 对tableB执行Clustered Index Seek操作。这个操作是在nested loop循环里面执行的，输入是tableB表的聚集索引数据。它使用tableB.col1=rowA.col1和tableB.col2=?这两个条件，从tableB的聚集索引中选择符合条件的结果。

d) 构造返回结果集。从nested loop的输出中，整理出select中指定的字段，构造最终输出结果集。

1.5 进阶说明

上面例子对inner input使用的是聚集索引，下面看一下非聚集索引的情况，加强对执行计划的理解、分析能力。

把tableB col1上的主键修改为非聚集方式，示例的SQL语句执行计划.

前面三个执行步骤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时只是使用非聚集索引的索引字段（tableB.col1）跟outer input的关联字段进行匹配，到目前为止还没有使用tableB.col2=?这个条件，这个操作就是使用tableB.col2=?对Bookmark Lookup的输出进行过滤。

看的仔细的人到这里后可能会有几个疑问，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操作的原因。

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表中实际记录数，例如示例SQL中，如果tableA在col2上有维护统计信息（存在col2的索引或者是单独维护的统计信息），并且tableA.col2=?的条件值符合SARG（可搜索参数）形式，那么查询编译时刻SQL Server就能够利用统计信息和条件值评估出符合条件的记录数，查询执行时刻符合条件tableA.col2=?的记录才被用于外层循环。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方式。

接下来就不再象上面这样详细的讲述了。