五 [译]数据库是如何工作查询管理器( 四 ) _关联

1) 内部和外部联系都计算哈希表
2) 然后将他们放进磁盘
3) 然后逐个桶比较两者的关系(一个用加载到内存，另一个逐行读文件) [原文的意思是外部联系的所有元素哈希值存在一个文件中，逐行读取。通过哈希值可以知道是几号桶，就把桶加载到内存进行对比]
合并关联
合并连接是唯一一种关联可以生成排序结果
注意：在这个简化的合并关联中，不区分内部或外部表;两者都扮演了一样的角色。但实际的实现起来是有不同的，例如，在处理重复项时。
排序
我们已经讲过了合并排序，在这种情况下合并排序是个好的算法（但如果内存足够，就不是最好的）就是数据集是已排序的，举个栗子：
合并关联
这部分非常类似于我们看到的合并排序的合并操作。
但这一次，我们只选择两个关系中相等的元素，而不是从两个关系中挑选每个元素。
这是它的构思：
1) 对比两个关系中当前项(初始的时候两个当前项都是第一个)
2) 如果他们是相等的，就把两个元素放到结果，再比较两个关系的下一个元素
3) 如果不相等，就去对比值最小的那个关系的下个元素(因为下个元素可能能匹配)
4) 重复 1,2,3 直到有个关系到达最后一个元素
这是有效的，因为两个关系都是已排序的，所以你不需要在这些关系中返回。
这算法一个简化版，因为它没有处理数组中有多个相同值的情况（换句话说，多重匹配）。针对这种情况，真实的版本太重复了。这就是我选择简化版的原因。
如果两个关系是已排序的，那么事件负责会是 O(N+M)
如果两个关系都需要排序，那么会加上排序的成本，时间复杂度会是 O(N*Log(N) + M*Log(M))
对计算机科学的Geeks 来讲，这里有一个可能的算法来处理多个匹配（注意：我不是100％肯定我的算法）：
mergeJoin(relation a, relation b)relation outputinteger a_key:=0;integer b_key:=0;while (a[a_key]!=null or b[b_key]!=null)if ( a[a_key] < b[b_key])a_key++;else if (a[a_key] > b[b_key])b_key++;else //Join predicate satisfied//i.e. a[a_key] == b[b_key]//计算与a相关的重复数量integer nb_dup_in_a = 1:while (a[a_key]==a[a_key+nb_dup_in_a])nb_dup_in_a++;//计算与b相关的重复数量integer dup_in_b = 1:while (b[b_key]==b[b_key+nb_dup_in_b])nb_dup_in_b++;//在输出中写下重复项for (int i = 0 ; i< nb_dup_in_a ; i++)for (int j = 0 ; i< nb_dup_in_b ; i++)write_result_in_output(a[a_key+i],b[b_key+j])a_key=a_key + nb_dup_in_a-1;b_key=b_key + nb_dup_in_b-1;end ifend while
哪一个是最好的？
如果存在最佳类型的关联，就不会有那么多种类型。这个问题非常困难，因为有很多因素发挥作用：
1) 有大量的空闲内存：没有足够的内存，你可以和强大的哈希关联说再见了（至少和全在内存中进行散列连接的方式说再见）
2) 2个数据集的大小：举个栗子，如果你有一个非常大的表要关联个小表，嵌套循环关联会比哈希关联快，那是因为哈希关联的创建成本较高。如果你有两个很大的表，那么嵌套查询就比较耗CPU了
3) 索引的存在：如果是两个B+树的索引，最机智的选择当然是合并关联了
4) 如果结果需要排序：即使你正在处理的数据集是没排序的，你可能会想使用成本昂贵的合并关联（用来排序），因为合并关联后结果是有序的，你也可以把它和其他的合并关联连起来用(或者因为使用 ORDER BY/GROUP BY/ 等操作符隐式或显式地要求一个排序结果)
5) 如果关系已经排序：在这种情况下，合并连接是最佳候选
6) 关联的类型: 它是等值连接（即：.col1 = .col2）？它是内关联，外关联，笛卡尔积还是自关联？某些关联在某些情况下无法工作。