public class MergeJoin
{
// Assume that left and right are already sorted
public static Relation Sort(Relation left, Relation right)
{
Relation output = new Relation();
while (!left.IsPastEnd() && !right.IsPastEnd())
{
if (left.Key == right.Key)
{
output.Add(left.Key);
left.Advance();
right.Advance();
}
else if (left.Key < right.Key)
left.Advance();
else //(left.Key > right.Key)
right.Advance();
}
return output;
}
}
代码1.Merge Join的C#代码表示
因此，通常来说Merge Join如果输入两端有序，则Merge Join效率会非常高，但是如果需要使用显式Sort来保证有序实现Merge Join的话，那么Hash Join将会是效率更高的选择。但是也有一种例外，那就是查询中存在order by,group by,distinct等可能导致查询分析器不得不进行显式排序，那么对于查询分析器来说，反正都已经进行显式Sort了,何不一石二鸟的直接利用Sort后的结果进行成本更小的MERGE JOIN？在这种情况下，Merge Join将会是更好的选择。
另外，我们可以由Merge Join的原理看出，当连接条件为不等式(但不包括!=)，比如说> < >=等方式时，Merge Join有着更好的效率。
下面我们来看一个简单的Merge Join,这个Merge Join是由聚集索引和非聚集索引来保证Merge Join的两端有序，如图10所示。
图10.由聚集索引和非聚集索引保证输入两端有序
当然，当Order By,Group By时查询分析器不得不用显式Sort,从而可以一箭双雕时，也会选择Merge Join而不是Hash Join,如图11所示。
图11.一箭双雕的Merge Join
哈希匹配(Hash Join)哈希匹配连接相对前面两种方式更加复杂一些，但是哈希匹配对于大量数据，并且无序的情况下性能均好于Merge Join和Loop Join。对于连接列没有排序的情况下(也就是没有索引)，查询分析器会倾向于使用Hash Join。
哈希匹配分为两个阶段,分别为生成和探测阶段，首先是生成阶段，第一阶段生成阶段具体的过程可以如图12所示。
图12.哈希匹配的第一阶段
图12中，将输入源中的每一个条目经过散列函数的计算都放到不同的Hash Bucket中，其中Hash Function的选择和Hash Bucket的数量都是黑盒，微软并没有公布具体的算法，但我相信已经是非常好的算法了。另外在Hash Bucket之内的条目是无序的。通常来讲，查询优化器都会使用连接两端中比较小的哪个输入集来作为第一阶段的输入源。
