为什么更改声明的连接列顺序会引入排序？

Question

我有两个具有相同名称、类型和索引键列的表。其中一个具有唯一的聚集索引，另一个具有非唯一的.

测试设置

设置脚本，包括一些真实的统计数据：

DROP TABLE IF EXISTS #left;
DROP TABLE IF EXISTS #right;

CREATE TABLE #left (
    a       char(4) NOT NULL,
    b       char(2) NOT NULL,
    c       varchar(13) NOT NULL,
    d       bit NOT NULL,
    e       char(4) NOT NULL,
    f       char(25) NULL,
    g       char(25) NOT NULL,
    h       char(25) NULL
    --- and a few other columns
);

CREATE UNIQUE CLUSTERED INDEX IX ON #left (a, b, c, d, e, f, g, h)

UPDATE STATISTICS #left WITH ROWCOUNT=63800000, PAGECOUNT=186000;

CREATE TABLE #right (
    a       char(4) NOT NULL,
    b       char(2) NOT NULL,
    c       varchar(13) NOT NULL,
    d       bit NOT NULL,
    e       char(4) NOT NULL,
    f       char(25) NULL,
    g       char(25) NOT NULL,
    h       char(25) NULL
    --- and a few other columns
);

CREATE CLUSTERED INDEX IX ON #right (a, b, c, d, e, f, g, h)

UPDATE STATISTICS #right WITH ROWCOUNT=55700000, PAGECOUNT=128000;

再现

当我在它们的集群键上连接这两个表时，我期望一对多的 MERGE 连接，如下所示：

SELECT *
FROM #left AS l
LEFT JOIN #right AS r ON
    l.a=r.a AND
    l.b=r.b AND
    l.c=r.c AND
    l.d=r.d AND
    l.e=r.e AND
    l.f=r.f AND
    l.g=r.g AND
    l.h=r.h
WHERE l.a='2018';

这是我想要的查询计划：

（不要在意警告，它们与虚假统计数据有关。）

但是，如果我更改连接中列的顺序，如下所示：

SELECT *
FROM #left AS l
LEFT JOIN #right AS r ON
    l.c=r.c AND     -- used to be third
    l.a=r.a AND     -- used to be first
    l.b=r.b AND     -- used to be second
    l.d=r.d AND
    l.e=r.e AND
    l.f=r.f AND
    l.g=r.g AND
    l.h=r.h
WHERE l.a='2018';

... 有时候是这样的：

Sort 运算符似乎根据连接的声明顺序对流进行排序，即c, a, b, d, e, f, g, h，它向我的查询计划添加了阻塞操作。

我看过的东西

• 我试过将列更改为NOT NULL，结果相同。
• 原始表是用 来创建的ANSI_PADDING OFF，但是用 来创建ANSI_PADDING ON不会影响这个计划。
• 我尝试了一个INNER JOIN而不是LEFT JOIN，没有变化。
• 我在 2014 SP2 Enterprise 上发现了它，并在 2017 Developer（当前的 CU）上创建了一个 repro。
• 删除前导索引列上的 WHERE 子句确实会产生好的计划，但它会影响结果.. :)

最后，我们进入问题

• 这是故意的吗？
• 我可以在不更改查询的情况下消除排序吗（这是供应商代码，所以我真的不想......）。我可以更改表和索引。

Answer 1

这是故意的吗？

是的，这是设计使然。遗憾的是，当 Microsoft 停用 Connect 反馈站点时，此断言的最佳公共资源丢失了，删除了 SQL Server 团队开发人员的许多有用评论。

总之，目前的优化设计不积极争取，以避免不必要的排序本身。这在窗口函数等中最常遇到，但也可以在其他对排序敏感的运算符中看到，特别是对运算符之间的保留排序。

尽管如此，优化器在避免不必要的排序方面做得很好（在许多情况下），但这种结果通常是由于积极尝试不同的排序组合之外的其他原因造成的。从这个意义上说，与其说是“搜索空间”的问题，不如说是正交优化器功能之间复杂的相互作用，这些功能已被证明可以以可接受的成本提高总体计划质量。

例如，通常可以简单地通过将排序要求（例如顶级ORDER BY）与现有索引进行匹配来避免排序。在您的情况下，这可能意味着添加，ORDER BY l.a, l.b, l.c, l.d, l.e, l.f, l.g, l.h;但这是一种过度简化（并且不可接受，因为您不想更改查询）。

更一般地，每个备忘录组可以与所需的或期望的属性相关联，其可以包括输入排序。如果没有明显的理由强制执行特定命令（例如，为了满足ORDER BY，或确保来自对顺序敏感的物理运算符的正确结果），则涉及“运气”因素。我在避免排序与合并连接连接中写了更多关于它的细节，因为它与合并连接（在联合或连接模式下）有关。其中大部分超出了产品支持的表面积，因此将其视为信息性的，并且可能会发生变化。

在您的特定情况下，是的，您可以按照 jadarnel27 的建议调整索引以避免排序；尽管没有什么理由真正更喜欢这里的合并连接。您还可以OPTION(HASH JOIN, LOOP JOIN)根据您对数据的了解以及最佳、最差和平均情况性能之间的权衡，在不更改查询的情况下使用计划指南提示在散列或循环物理连接之间进行选择。

最后，出于好奇，请注意，可以通过简单的 避免排序ORDER BY l.b，代价是b单独进行多对多合并连接的效率可能较低，并且具有复杂的残差。我提到这主要是为了说明我之前提到的优化器功能之间的交互，以及顶级需求可以传播的方式。

Answer 2

我可以在不更改查询的情况下消除排序吗（这是供应商代码，所以我真的不想......）。我可以更改表和索引。

如果您可以更改索引，则更改索引​​的顺序#right以匹配连接中过滤器的顺序会删除排序（对我而言）：

CREATE CLUSTERED INDEX IX ON #right (c, a, b, d, e, f, g, h)

令人惊讶的是（至少对我而言），这导致两个查询都没有以排序结束。

这是故意的吗？

查看一些奇怪的 trace flags的输出，最终的 Memo 结构有一个有趣的区别：

正如您在顶部的“根组”中看到的那样，两个查询都可以选择使用合并连接作为执行此查询的主要物理操作。

很好的查询

没有排序的连接由组 29 选项 1 和组 31 选项 1 驱动（每个都是对所涉及索引的范围扫描）。它由组 27（未显示）过滤，这是过滤连接的一系列逻辑比较操作。

错误查询

具有排序的那个由这两个组（29 和 31）中的每一个所具有的（新）选项 3 驱动。选项 3 对前面提到的范围扫描的结果执行物理排序（每个组的选项 1）。

为什么？

出于某种原因，在第二个查询中，优化器甚至无法直接使用 29.1 和 31.1 作为合并连接源的选项。否则，我认为它会在其他选项中列在根组下。如果它完全可用，那么它肯定会通过更昂贵的排序操作来选择那些。

我只能得出结论：

• 这是优化器搜索算法中的一个错误（或更可能是一个限制）
  • 将索引和连接更改为只有 5 个键会删除第二个查询的排序（6、7 和 8 个键都具有排序）。
  • 这意味着具有 8 个键的搜索空间非常大，以至于优化器没有时间在非排序解决方案以“找到足够好的计划”的原因提前终止之前将其识别为可行选项
  • 对我来说，连接条件的顺序对优化器的搜索过程影响很大，这对我来说似乎有点麻烦，但实际上这有点超出我的理解
• 排序是必需的，以确保结果的正确性
  • 这似乎不太可能，因为当键较少或以不同顺序指定键时，查询可以在没有排序的情况下运行

希望有人能来解释为什么需要排序，但我认为 Memo 建筑中的差异很有趣，可以作为答案发布。