MySQL8.0的反连接

作者：Guilhem Bichot 译：徐轶韬

在MySQL 8.0.17中，我们在TPC-H基准测试中观察到一个特定的查询。该查询的执行速度比MySQL 8.0.16快20％。这项改进的原因是实施了“ antijoin”优化。

“优化器现在将NOT IN （子查询），NOT EXISTS（子查询），IN（子查询）IS NOT TRUE或 EXISTS（子查询）IS NOT TRUE的WHERE条件在内部转换为反联接，从而删除子查询。”

在这篇博文里，我将解释该优化的作用，并提供性能相关的数字。

该优化适用于以下问题：

• “对象存在于当前集合中而不在其他集合”
• “这个季度没有购买订单的客户”
• “今年没有通过考试的学生”
• “过去三年没有进行身体检查的患者”。

在SQL中，通常会转换为以下形式的查询：

如果使用这种形式的查询，该语句的优化潜力非常小。我们必须读取patients表中的每条记录，并检查每条记录是否存在于子查询。我们需要对子查询进行多次评估计算，因为它的WHERE子句取决于patients.patient_id，它随patients的每条记录而变化（我们称为“相关子查询”）。

优化此查询的第一步是打破顶部查询和子查询之间的界限，将后者有效地合并到前者中，从而产生：

这个新查询使用antijoin运算符; 就像join运算符一样，但它不查找匹配记录，而是查找不匹配的记录；精确地来说，它从左侧选择记录，而右侧没有与ON条件匹配的记录。

MySQL可以选择两种策略来评估计算反连接。

“First Match”策略：从patients那里读取记录，在exams找到匹配，如果没有匹配，则发出patients 记录；这等同于我们保留了子查询。

“Materialization”策略：观察ON子句中存在三个子条件，其中只有一个取决于patients。因此，MySQL可以自动构建一个临时表tmp，该表由与前两个子条件（type 和date）匹配的exams 记录构成；类似于下图：

然后MySQL自动在tmp.patient_id上添加索引，并执行以下操作：从patients读取一条记录，使用该索引在tmp中查找匹配项，如果没有匹配项，则发出patients记录。

与“First Match”相比，此策略可能会具有优势，因为：

• 它只读取一次exams （构建tmp）
• tmp的记录可能少于exams 的记录，因此在tmp中探查的速度比在exams 中要快
• 通过在tmp上建立的索引来进行探测，而exams 本身可能没有索引。

但是，构建tmp可能会花费大量的前期成本：MySQL需要分配内存来存储其记录（如果有很多记录，甚至可能分配磁盘空间），还需要时间将记录写入tmp。因此，这两种策略中哪一种更好取决于实际情况。幸运的是，MySQL有一个基于成本的优化器，它将考虑两种不同的策略，根据表中记录的数量，条件的选择性，索引的可用性来计算其成本，并选择成本最低的策略。

到目前为止，我们已经了解到，通过对两种执行策略（而不是一种）之间进行基于成本的选择，反连接优化可以加快查询速度。

但是，如果我们使用两个以上的表，则必须做更多的事情。因此，我将使用之前提到的TPC-H 的DBT-3实现，查询号为21。

在此查询中，我们有四个表，并且在WHERE子句中还有两个子查询。第一个是EXISTS类型，MySQL将其视为半连接（MySQL 5.6中引入的优化）。第二个子查询的类型为NOT EXISTS，因此可以作为反连接进行处理。子查询因此合并到了顶部查询中，FROM子句现在看起来像：

这是我们理解antijoin转换的另一个关键优势的地方：因为它的ON条件仅取决于l1和l3，因此只要保持其位置在l1之后，antijoin运算符就可以在FROM子句中的任何位置左右移动。最佳位置取决于l3中的记录数（此数字越大，评估计算反连接的成本就越高），并且取决于反连接条件的选择性。代价高昂的操作符应该推迟运行，可以使更多记录被之前的操作符删除;另一方面，如果该操作符非常有选择性，则应该尽早运行，以尽快消除大量的记录。因此，没有简单的答案，必须进行成本计算和比较。MySQL的基于成本的优化器将考虑访问表的不同顺序，并选择成本最低的表。

有一个明显的异议。有人可能会说：“不需要使用反联接运算符，MySQL可以保留子查询，而不合并它，并在最佳位置（在读取l1，orders或nation…之后）进行评估，按你说的做基于成本的选择”。

但是，请记住，MySQL会在优化顶部的查询之后才会优化子查询。当它在优化顶部查询，想知道应将NOT EXISTS（subquery）条件附加到哪个表上时，它既不知道子查询的成本，也不知道NOT EXISTS的选择性。因此，优化器假设NOT EXISTS（subquery）是“透明的”：它不花费任何成本，并且选择性为100％。这不是最佳方式。但是请注意，如果MySQL 先优化子查询后再优化顶部查询，这个问题将得以解决，但又会出现另一个问题，因为有时执行不可合并子查询的最佳策略取决于对其进行评估计算的次数，只有我们已经对顶部查询进行优化后才能知道。因此，有时依赖关系是从上到下，有时是从下到上，通常是……两种都有。

将子查询合并到一个反连接中，我们可以避免这个问题：我们将所有表放到一个计划阶段，这种计划可以做出明智的选择。

让我们通过TPC-H来说明这一点。

创建表之后，运行查询号21。它发出100条记录，但是我们更关心它的执行时间：

现在，再次运行此查询，但是使用了一个提示来禁用反连接优化，从而将NOT EXISTS保留为子查询，以模拟MySQL 8.0.17之前的情况。提示与禁用半连接的提示相同（NO_SEMIJOIN），NOT EXISTS（SELECT / * + NO_SEMIJOIN（）* / …）。

现在执行时间为：

我们可以看到，antijoin优化节省了15秒，即增加了19％

这是带有反连接的良好执行计划，如EXPLAIN FORMAT = TREE所示（反连接位于第5行）：

这是没有antijoin的不好的（相反，它在第16行仍然有一个子查询）：

在不好的情况下，我们可以看到在读取l1之后对NOT EXISTS进行了评估计算。而在好的情况下，我们可以看到它在最后进行了评估计算（l3是最后一个表），运行速度更快，显然这是一个更明智的选择。

顺便说一句，我们可以看到已经用“First Match”处理了反连接，因为在“Nested loop anti-join”节点中没有提及内部临时表。

现在该回顾一下。我们了解了反连接优化：

1. 适用于NOT EXISTS，NOT IN（子查询）
2. 允许MySQL的计划者选择策略（First Match或Materialization）
3. MySQL的计划者可以选择更多的表顺序。

感谢您使用MySQL！