先前的外连接禁止内连接消除

Question

概要：如果逻辑树中较早存在未消除的外连接，则可以逻辑消除的内连接将被保留。为什么？

示例在 AdventureWorks2008R2 及更高版本中运行。我添加了跟踪标志来提供连续树和规则的整体上下文。

第一个例子，对于上下文：

• Product在简化过程中消除了左连接（连接表中不需要数据并且引用的值是唯一的）。
• SalesOrderDetail然后在连接崩溃期间消除内部连接，即启发式连接重新排序（连接表中不需要数据，引用者不可为空，并且强制执行 FK）

SELECT sod.SalesOrderDetailID
FROM Sales.SalesOrderDetail AS sod
    LEFT JOIN Production.Product AS p -- Eliminated during simplification (Rule: RedundantLOJN)
        ON p.ProductID = sod.ProductID
    JOIN Sales.SalesOrderHeader AS soh -- Eliminated during join collapse. (Annotated by TF 8619)
        ON soh.SalesOrderID = sod.SalesOrderID
OPTION (RECOMPILE, QUERYTRACEON 8619, QUERYTRACEON 8621, QUERYTRACEON 8606, QUERYTRACEON 3604);

然而，在第二个示例中，可以从逻辑上消除与 SalesOrderHeader 的连接，但事实并非如此。

• 保留左连接，因为需要来自 的数据Product。在逻辑树中，此连接被定义为在不消除的连接之前。
• 后续的加入SalesOrderHeader可以在逻辑上被消除，因为先前的加入不能使消除要求无效：非空引用 + FK 完整性。

SELECT p.Name
FROM Sales.SalesOrderDetail AS sod
    LEFT JOIN Production.Product AS p
        ON p.ProductID = sod.ProductID
    JOIN Sales.SalesOrderHeader AS soh -- Logically eligible for elimination.
        ON soh.SalesOrderID = sod.SalesOrderID
OPTION (RECOMPILE, QUERYTRACEON 8619, QUERYTRACEON 8621, QUERYTRACEON 8606, QUERYTRACEON 3604);

最后，成功消除了连接的三个变体。

在查询文本中，在问题连接之后放置外部连接会更改逻辑树。逻辑含义不变，但内连接不再将外连接作为逻辑树中的后代。

笔记！一个罕见的例子，在 SQL Server 中，查询中连接语句的顺序会影响查询计划

SELECT p.Name
FROM Sales.SalesOrderDetail AS sod
    JOIN Sales.SalesOrderHeader AS soh -- Eliminated during join collapse. (Annotated by TF 8619)
        ON soh.SalesOrderID = sod.SalesOrderID
    LEFT JOIN Production.Product AS p
        ON p.ProductID = sod.ProductID
OPTION (RECOMPILE, QUERYTRACEON 8619, QUERYTRACEON 8621, QUERYTRACEON 8606, QUERYTRACEON 3604);

如果将第一个连接更改为内部连接，则成功消除第二个连接。

SELECT p.Name
FROM Sales.SalesOrderDetail AS sod
    JOIN Production.Product AS p
        ON p.ProductID = sod.ProductID
    JOIN Sales.SalesOrderHeader AS soh -- Eliminated during join collapse. (Annotated by TF 8619)
        ON soh.SalesOrderID = sod.SalesOrderID
OPTION (RECOMPILE, QUERYTRACEON 8619, QUERYTRACEON 8621, QUERYTRACEON 8606, QUERYTRACEON 3604);

此外，作为解决方案，我们可以将第二个连接更改为外部连接：

SELECT p.Name
FROM Sales.SalesOrderDetail AS sod
    LEFT JOIN Production.Product AS p
        ON p.ProductID = sod.ProductID
    LEFT JOIN Sales.SalesOrderHeader AS soh -- Eliminated during simplification (Rule: RedundantLOJN)
        ON soh.SalesOrderID = sod.SalesOrderID
OPTION (RECOMPILE, QUERYTRACEON 8621, QUERYTRACEON 8606, QUERYTRACEON 3604);

结论

上面的例子似乎证明了外连接可能会阻止后续的内连接消除，尽管它在逻辑上是可能的。

我的推测是，促进内连接消除的属性（非空引用、FK 完整性）不会传播到外连接运算符的输出属性。

谁能确认真正的原因是什么？

这里的要点是，如果您创建利用连接消除来优化计划的多用途视图，您需要了解这种交互，并可能修改连接以避免在执行期间进行不必要的工作。

Answer 1

在基于成本的优化之前执行的许多简化都针对生成的查询（ORM 等）。这些查询通常遵循某种模式并导致逻辑上冗余的投影、选择和连接。

这里需要进行权衡。任何数量的重写和简化在逻辑上都是可能的。每一个都需要根据当前的树进行评估，并在当地情况合适时加以应用。所有这些都需要时间和资源。每个查询都会考虑在基于成本的优化之前运行的规则，即使是那些未优化成本非常低的查询，或者稍后将符合一个简单计划的条件。

出于这些原因，优化器团队谨慎地在此处仅包含成本（实现和运行时）相对较低且适用性较高的规则。

考虑：有些规则比其他规则更难实施。有些评估成本高于潜在收益所证明的价值。由于内部依赖性，有些会在优化器代码的其他地方引入细微的错误。其他的根本不够常见，以至于无法实施它们。还有一些很容易实现，通常足够有用，但当时没有想到，从那以后也没有被要求（足够大声）。例如，使用多列关系连接消除。

与您的问题相关的示例，使用相同的架构：

-- Join eliminated
SELECT SOD.ProductID 
FROM Sales.SalesOrderDetail AS SOD
LEFT JOIN Production.Product AS P
    ON P.ProductID = SOD.ProductID;

-- Join not eliminated projecting from the preserved side of the join
SELECT P.ProductID 
FROM Sales.SalesOrderDetail AS SOD
LEFT JOIN Production.Product AS P
    ON P.ProductID = SOD.ProductID;

尽管我们可能会争论P.ProductID并SOD.ProductID保证逻辑和模式在所有方面都相同，但并没有消除那里的连接。就目前而言，第二个查询中的外连接未转换为内连接，这将允许问题所针对的简化。

同样，这不是因为 SQL Server 优化器开发人员愚蠢或懒惰。这种事情并不常见，值得在每次编译时检查。

一般而言，为了充分利用连接简化和消除，您应该按照逻辑顺序构建书面连接（例如相邻的连接表），并确保满足 Rob Farley 指出的四个条件。

重新排序连接

在某些有限的上下文中，在其他连接周围移动外部连接是可能的，但通常很复杂且昂贵。这些转换很棘手，因此绝大多数此类工作仅限于基于成本的优化的搜索 2（完全优化）阶段。即便如此，在 SQL Server 中研究和/或实现的逻辑可能性相对较少。

在这种转换过程中很容易无意中改变语义。有关一些介绍性讨论，请参阅Jeff Smith 的混合 INNER 和 OUTER 联接时要小心。有关更多技术细节，有大量技术论文，例如César A. Galindo-Legaria (Microsoft) 和 Arnon Rosenthal 的Outerjoin Simplification and Reordering for Query Optimization。

启发式连接重新排序确实在重新组织交叉连接、内连接和外连接方面做出了一些努力，但由于前面提到的所有原因，这些努力都属于轻量级的一端。

我会给你留下这个有趣的重写，它确实允许消除：

SELECT p.[Name]
FROM Production.Product AS P
RIGHT JOIN Sales.SalesOrderDetail AS SOD
JOIN Sales.SalesOrderHeader AS SOH
    ON SOH.SalesOrderID = SOD.SalesOrderID
    ON SOD.ProductID = P.ProductID;

db<>小提琴演示

正如伦纳特所说：

您可能会对以下文章感兴趣：https : //dzone.com/articles/cool-sql-optimizations-that-do-not-depend-on-the-c和https://dzone.com/articles/ cool-sql-optimizations-that-do-not-depend-on-the-c-1它比较了许多 DBMS（sql-server-2014 等）的“代数”优化，这些优化不依赖于成本模型.

除了4. Removing “Silly” Predicates 之外，这些对于 SQL Server 来说大多是准确的，这并不反映 SQL Server 区分EQ（相等，拒绝空值）和IS（空值感知）比较。需要明确的是，SQL Server 确实支持这一点。

Answer 2

是的，在某些情况下，联接消除阶段不会消除应有的消除量。它经常发生在涉及空值的场景中，包括由于左连接而为空的情况。我记得几年前，与 Paul White 讨论过，您可以通过使用明确的“AND SomeJoinColumn IS NOT NULL”（我猜这里是 sod.SalesOrderID）来帮助解决这个问题。我们确信这是一个错误，但它不太可能引起微软的注意，因为它不会影响正确性。我今天不能测试它，但看看它是否有助于消除。我以后可以随时编辑此答案。

哦，当我在 2009 年第一次提出这个问题时，我没有注意到这种行为。当我意识到这一点时，似乎将其纳入我的演示文稿中的边缘案例太多了。