Content #
排序归并算法就是 Sort-Merge Join（SMJ），也被称为 Merge Join。SMJ 可以分为排序和归并两个阶段：
- 第一阶段是排序，就是对 Outer 表和 Inner 表进行排序，排序的依据就是每条记录在连接键上的数值。
- 第二阶段就是归并，因为两张表已经按照同样的顺序排列，所以 Outer 表和 Inner 表各一次循环遍历就能完成比对工作了。
SMJ 就是先要把两个数据集合变成两个数据序列，也就是有序的数据单元，然后再做循环比对。这样算下来，它的计算成本是两次排序再加两次循环。你可能会觉得奇怪，这成本是不是比 NLJ 还要高呀？
是的。所以选择 SMJ 是有前提的，而这个前提就是表的记录本身就是有序的，否则就不划算了。
索引是天然有序的，如果表的连接键刚好是索引列，那么 SMJ 就是三种嵌套循环算法中成本最低的，它的时间复杂度只有 O(m+n)。