高效SQL查询之索引（VI）

我们先看 NestedLoop 和 MergeJoin 的算法（以下为引用，见 RicCC 的《 通往性能优化的天堂 - 地狱 JOIN 方法说明 》 ):
==================================
NestedLoop:
   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 ;
    else
        output rowA and rowsB ;
    }
MergeJoin:
两个表都按照关联字段排序好之后， merge join 操作从每个表取一条记录开始匹配，如果符合关联条件，则放入结果集中；否则，将关联字段值较小的记录抛弃，从这条记录对应的表中取下一条记录继续进行匹配，直到整个循环结束。
==================================
我们通过最简单的情况来计算 NestedLoop 和 MergeJoin 的消耗：
两张表 A 、 B ，分别有 m 、 n 行数据（ m < n ），占用基础表物理存储空间分别为 a 、 b 页，聚集索引树非叶节点都是两层（一层根节点，一层中间级节点）， A 、 B 的聚集索引建在 A.col1 、 B.col1 上。一条查询语句：
select A.col1, B.col2 from A inner join B where A.col1 = B.col1 。
执行 NestedLoop 操作 ：
A 作为 outer input ， B 作为 inner input 时： A 带来的 IO 为 a ；每次通过 clustered index seek 执行内部循环，花费 3( 一个根节点、一个中间集结点、一个叶节点。当然也可能直接从根节点就拿到要的数据，我们只考虑最坏的情况），这样执行整个嵌套循环过程消耗 IO 为 a + 3*m 。如果 B 作为 inner input ， A 作为 outer input 分析类似。
执行 MergeJoin :
MergeJoin 要把 A 、 B 两张表做个 Scan ，然后进行 Merge 操作。所以 A 、 B 分别带来 IO 为 a + b 就是总的逻辑 IO 开销。
从上述分析来看，若 a + 3*m << a + b ，即 3*m << b ，那么 NestedLoop 性能是极佳的。当然，我们比较 A 表的行和 B 表所占数据页大小看上去有点夸张，但是量化分析确实如此。在这里，我们没有计算 NestedLoop 和 MergeJoin 本身的 cpu 计算开销，特别是后者，这部分并不能完全忽略，但是也来得有限。
OK ，现在我们试图执行实际的语句验证我们的观点，看看能发现什么。