排序归并连接

定义

排序归并连接(Sort-Merge Join)分两阶段:先将参与连接的两侧数据按连接键排序,再像归并排序的合并步骤那样,用两个指针同步推进匹配相等的键,输出连接结果。

原理与代价

主要代价在排序阶段,内存不足时需外部排序落盘;归并阶段两侧各顺序扫描一遍,I/O 模式友好。当任一侧已有序(如按连接键的索引扫描输出、上游算子已排序)时可跳过排序,此时归并连接非常廉价。

与哈希连接的比较

两者都适合大数据量等值连接。哈希连接通常更快且无需排序;归并连接的优势在于:输出天然按连接键有序(可被上层 ORDER BY、分组复用)、支持部分非等值条件(如范围连接)、内存表现更平稳可预期。优化器会依据代价与顺序属性(interesting order)在两者间选择。

应用

PostgreSQL、Oracle、SQL Server 均实现该算法;在分布式与大数据引擎(如 Spark 的 SortMergeJoin)中,它是超大表之间 shuffle 连接的默认选择之一。