AdventureWorks中NOT EXISTS查询执行计划Sort的产生原因

问题背景 #

在AdventureWorks数据库中执行如下NOT EXISTS查询，返回结果符合预期，但执行计划中出现了Sort排序算子：

-- 查询返回9条无对应Product关联的ProductModel记录
select *
from Production.ProductModel
where not exists
(
    select 1
    from Production.Product
    where Production.Product.ProductModelID = Production.ProductModel.ProductModelID
);

对应执行计划截图：

Sort算子产生原因 #

这个排序操作并非来自内层NOT EXISTS子查询本身，是SQL Server优化器选择「Merge Join（合并联接）」实现反半连接匹配时的必要操作：

• Merge Join的工作原理是对两个待联接的数据集做单次顺序扫描，逐行匹配联接键，执行效率很高，但有硬性前提：两个输入数据集必须严格按照联接键（本查询中就是ProductModelID字段）排序。
• 本查询中，参与联接的两个数据集分别来自Production.ProductModel和Production.Product的索引扫描：如果对应索引的排序顺序不满足联接键的排序要求（比如Production.Product的聚集索引排序键是主键ProductID，扫描输出的结果默认按ProductID排列，而非ProductModelID），优化器就会在对应输入流上添加Sort算子，先把数据按ProductModelID排好序，再送入Merge Join算子做匹配。
• 这个Sort完全是为Merge Join服务的，和子查询写法没有直接关联。你可以做个简单验证：给查询加OPTION (HASH JOIN)查询提示强制优化器选择哈希联接，重新生成执行计划就会发现Sort算子完全消失——因为哈希联接不需要输入数据提前排序。

内容的提问来源于stack exchange，提问作者Paritosh