mysql - Condition on joined table faster than condition on reference

Question

I have a query involving two tables: table A has lots of rows, and contains a field called b_id, which references a record from table B, which has about 30 different rows. Table A has an index on b_id, and table B has an index on the column name.

My query looks something like this:

SELECT COUNT(A.id) FROM A INNER JOIN B ON B.id = A.b_id WHERE (B.name != 'dummy') AND <condition>;

With condition being some random condition on table A (I have lots of those, all exhibiting the same behavior).

This query is extremely slow (taking north of 2 seconds), and using explain, shows that query optimizer starts with table B, coming up with about 29 rows, and then scans table A. Doing a STRAIGHT_JOIN, turned the order around and the query ran instantaneously.

I'm not a fan of black magic, so I decided to try something else: come up with the id for the record in B that has the name dummy, let's say 23, and then simplify the query to:

SELECT COUNT(A.id) FROM A WHERE (b_id != 23) AND <condition>;

To my surprise, this query was actually slower than the straight join, taking north of a second.

Any ideas on why the join would be faster than the simplified query?

UPDATE: following a request in the comments, the outputs from explain:

Straight join:

+----+-------------+-------+--------+-----------------+---------+---------+---------------+--------+-------------+
| id | select_type | table | type   | possible_keys   | key     | key_len | ref           | rows   | Extra       |
+----+-------------+-------+--------+-----------------+---------+---------+---------------+--------+-------------+
|  1 | SIMPLE      | A     | ALL    | b_id            | NULL    | NULL    | NULL          | 200707 | Using where |
|  1 | SIMPLE      | B     | eq_ref | PRIMARY,id_name | PRIMARY | 4       | schema.A.b_id |     1  | Using where |
+----+-------------+-------+--------+-----------------+---------+---------+---------------+--------+-------------+

No join:

+----+-------------+-------+------+---------------+------+---------+------+--------+-------------+
| id | select_type | table | type | possible_keys | key  | key_len | ref  | rows   | Extra       |
+----+-------------+-------+------+---------------+------+---------+------+--------+-------------+
|  1 | SIMPLE      | A     | ALL  | b_id          | NULL | NULL    | NULL | 200707 | Using where |
+----+-------------+-------+------+---------------+------+---------+------+--------+-------------+

UPDATE 2: Tried another variant:

SELECT COUNT(A.id) FROM A WHERE b_id IN (<all the ids except for 23>) AND <condition>;

This runs faster than the no join, but still slower than the join, so it seems that the inequality operation is responsible for part of the performance hit, but not all.

score 4 · Accepted Answer

如果您使用的是 MySQL 5.6 或更高版本，那么您可以询问查询优化器它在做什么；

SET optimizer_trace="enabled=on";

## YOUR QUERY 
SELECT COUNT(*) FROM transactions WHERE (id < 9000) and user != 11;
##END YOUR QUERY

SELECT trace FROM information_schema.optimizer_trace;

SET optimizer_trace="enabled=off";

您几乎肯定需要参考 MySQL 参考Tracing the Optimizer和The Optimizer中的以下部分

查看第一个解释，查询似乎更快，可能是因为优化器可以使用 tableB来过滤到基于连接所需的行，然后使用外键获取 table 中的行A。

在解释中，有趣的是这一点；只有一行匹配，它正在使用schema.A.b_id. A实际上，这是对我认为性能差异所在的行进行预过滤。

   | ref           | rows   | Extra       |
   | schema.A.b_id |     1  | Using where |

因此，与查询一样，这一切都归结为索引——或者更准确地说是缺少索引。仅仅因为您在各个字段上都有索引，并不一定意味着这些索引适合您正在运行的查询。

基本规则：如果EXPLAIN没有说Using Index那么你需要添加一个合适的索引。

查看解释输出，具有讽刺意味的是，每行的最后一件事是有趣的。即Extra

在第一个例子中，我们看到

|  1 | SIMPLE      | A     | .... Using where |
|  1 | SIMPLE      | B     | ...  Using where |

这两种使用 where都不好；理想情况下至少有一个，最好两者都应该说使用索引

当你这样做

SELECT COUNT(A.id) FROM A WHERE (b_id != 23) AND <condition>;

并查看使用 where然后您需要在执行表扫描时添加索引。

例如，如果你做了

EXPLAIN SELECT COUNT(A.id) FROM A WHERE (Id > 23)

你应该看到使用 where；使用索引（这里假设Id是主键并且有索引）

如果您随后在末尾添加了一个条件

EXPLAIN SELECT COUNT(A.id) FROM A WHERE (Id > 23) and Field > 0

并查看使用 where然后您需要为这两个字段添加索引。仅仅在一个字段上有一个索引并不意味着 MySQL 将能够在跨多个字段的查询期间使用该索引 - 这是查询优化器内部将决定的事情。我不完全确定内部规则；但通常添加一个额外的索引来匹配查询会有很大帮助。

所以添加一个索引（在上面查询中的两个字段上）：

ALTER TABLE `A` ADD INDEX `IndexIdField` (`Id`,`Field`)

应该更改它，以便在基于这两个字段进行查询时有一个索引。

我已经在我的一个有表的数据库上尝试过Transactions这个User。

我将使用此查询

EXPLAIN SELECT COUNT(*) FROM transactions WHERE (id < 9000) and user != 11;

在两个字段上不带索引运行：

PRIMARY,user    PRIMARY 4   NULL    14334   Using where

然后添加一个索引：

ALTER TABLE `transactions` ADD INDEX `IndexIdUser` (`id`, `user`);

然后再次进行相同的查询，这次

PRIMARY,user,Index 4    Index 4 4   NULL    12628   Using where; Using index

这次它使用了索引——结果会快很多。

从@Wrikken 的评论 - 还要记住，我没有准确的架构/数据，所以一些调查需要对架构进行假设（这可能是错误的）

SELECT COUNT(A.id) FROM A FORCE INDEX (b_id)

would perform at least as good as 

SELECT COUNT(A.id) FROM A INNER JOIN B ON A.b_id = B.id.

如果我们查看 OP 中的第一个 EXPLAIN，我们会看到查询有两个元素。参考 *eq_ref* 的EXPLAIN文档，我可以看到这将根据这种关系定义要考虑的行。

解释输出的顺序并不一定意味着它先做一个，然后再做另一个；这只是选择执行查询的内容（至少据我所知）。

由于某种原因，查询优化器决定不使用索引b_id- 我在这里假设由于查询，优化器决定执行表扫描会更有效。

第二个解释让我有点担心，因为它没有考虑 ; 上的索引b_id。可能是因为AND <condition>（被省略了，所以我猜测它可能是什么）。当我尝试使用索引时，b_id它确实使用了索引；但是一旦添加了条件，它就不会使用索引。

所以，做的时候

  SELECT COUNT(A.id) FROM A INNER JOIN B ON A.b_id = B.id.

这一切都向我表明，PRIMARY 索引B是速度差异的来源；我假设因为schema.A.b_id在说明中该表上有一个外键；这必须是比索引更好的相关行集合b_id- 因此查询优化器可以使用这种关系来定义要选择的行 - 并且因为主索引比二级索引更好，所以从中选择行会更快B 然后使用关系链接来匹配 A 中的行。

score 2 · Accepted Answer

我在这里没有看到任何奇怪的行为。您需要了解 MySQL 如何使用索引的基础知识。这是我通常推荐的一篇文章：MySQL 使用索引的 3 种方式。

观察人们写这样的东西总是很有趣WHERE (B.name != 'dummy') AND <condition>，因为这AND <condition>可能是 MySQL 优化器选择特定索引的原因，并且没有正当理由将查询的性能与另一个查询的性能进行比较WHERE b_id != 23 AND <condition>，因为这两个查询通常需要不同的索引才能表现良好。

您应该了解的一件事是，MySQL 喜欢相等比较，而不喜欢范围条件和不等比较。指定正确的值通常比使用范围条件或指定!=值更好。

所以，让我们比较一下这两个查询。

直接连接

对于 A.id 顺序中的每一行（这是主键并且是聚集的，即数据按其顺序存储在磁盘上）从磁盘中获取该行的数据以检查是否<condition>满足您的要求和 b_id，然后（我重复对于每个匹配的行）为 b_id 找到适当的行，进入磁盘，获取 b.name，将其与“虚拟”进行比较。即使这个计划根本没有效率，你的 A 表中只有 200000 行，所以它看起来相当高效。

没有直接连接

对于表 B 中的每一行比较名称是否匹配，查看 A.b_id 索引（显然按 b_id 排序，因为它是一个索引，因此包含随机顺序的 A.ids），并且对于每个 A.id给定的 A.b_id 在磁盘上找到相应的 A 行以检查<condition>，如果它与计数 id 匹配，否则丢弃该行。

如您所见，第二个查询花费了这么长时间，这并不奇怪，您基本上强制 MySQL 随机访问 A 表中的几乎每一行，在第一个查询中，您按照存储顺序读取 A 表磁盘。

没有连接的查询根本不使用任何索引。它实际上应该与使用直接连接的查询大致相同。我的猜测是b_id!=23and的顺序<condition>很重要。

UPD1：您是否仍然可以将未加入的查询的性能与以下内容进行比较：

SELECT COUNT(A.id)
FROM A
WHERE IF(b_id!=23, <condition>, 0);

UPD2：您在 EXPLAIN 中没有看到索引这一事实并不意味着根本没有使用任何索引。一个索引至少是用来定义读取顺序的：当没有其他有用的索引时，通常是主键，但是，正如我上面所说，当有相等条件和对应的索引时，MySQL 会使用该索引. 因此，基本上，要了解使用了哪个索引，您可以查看输出行的顺序。如果顺序与主键相同，则没有使用索引（即使用了主键索引），如果行的顺序被打乱 - 则涉及其他一些索引。

在您的情况下，对于大多数行来说，第二个条件似乎是正确的，但仍然使用索引，即让 b_id MySQL 以随机顺序进入磁盘，这就是它慢的原因。这里没有黑魔法，第二个条件确实会影响性能。

score 0 · Accepted Answer

这个问题的答案其实是算法设计的一个非常简单的结果：

这两个查询之间的主要区别在于合并操作。

在我讲算法之前，我会提到合并操作提高性能的原因。合并提高了性能，因为它减少了聚合的整体负载。这是一个迭代与递归的问题。在迭代类比中，我们只是循环遍历整个索引并计算匹配项。在递归的类比中，我们正在分而治之（可以这么说）；或者换句话说，我们正在过滤我们需要计算的结果，从而减少我们实际需要计算的数字量。

以下是关键问题：

为什么归并排序比插入排序快？
合并排序总是比插入排序快吗？

让我们用一个比喻来解释：

假设我们有一副扑克牌，我们需要将数字为 7、8 和 9 的扑克牌的数量相加（假设我们事先不知道答案）。

假设我们决定采用两种方法来解决这个问题：

我们可以一只手拿着牌，一张一张地把牌移到桌子上，边走边数。
我们可以将卡片分为两组：黑色套装和红色套装。然后我们可以对其中一个组执行步骤 1，并将结果重用于第二组。

如果我们选择选项 2，那么我们将问题一分为二。因此，我们可以计算匹配的黑卡并将数字乘以 2。换句话说，我们正在重用查询执行计划中需要计数的部分。当我们事先知道卡片是如何排序的（又名“聚集索引”）时，这种推理尤其有效。数一半的牌显然比数一整副牌要少得多。

如果我们想再次提高性能，取决于我们数据库的大小，我们甚至可以进一步考虑分为四组（而不是两组）：梅花、方块、红心和黑桃。我们是否要执行此进一步步骤取决于将卡片分类到其他组的开销是否可以通过性能增益来证明。在少量卡片中，性能提升可能不值得为分类到不同组所需的额外开销。随着卡数量的增加，性能增益开始超过间接成本。

这是“算法简介，第 3 版” （Thomas H. Cormen，Charles E. Leiserson，Ronald L. Rivest，Clifford Stein）的摘录：（注意：如果有人能告诉我如何格式化子符号，我将对其进行编辑以提高可读性。）

（另外，请记住“n”是我们正在处理的对象的数量。）

“作为一个例子，在第 2 章中，我们将看到两种排序算法。第一种称为插入排序，对 n 个项目进行排序所需的时间大致等于 c1n2，其中 c1 是一个不依赖于 n 的常数。即，它所花费的时间大致与 n2 成正比。第二种，归并排序，所花费的时间大致等于 c2n lg n，其中 lg n 代表 log2 n，c2 是另一个不依赖于 n 的常数。插入排序通常具有较小的常数因子比归并排序，因此 c1 < c2。我们将看到，常数因子对运行时间的影响远小于对输入大小 n 的依赖。让我们将插入排序的运行时间写为 c1n·n 和归并排序的运行时间为 c2n · lg n。然后我们看到插入排序在其运行时间中的因子为 n，而归并排序的因子为 lg n，它要小得多。（例如，当 n = 1000 时，lg n 约为 10，而当 n 等于 100 万时，lg n 约为 20。）尽管对于较小的输入大小，插入排序通常比归并排序运行得更快，但一旦输入大小 n 变为足够大，合并排序的 lg n 与 n 的优势将超过补偿常数因子的差异。不管 c1 比 c2 小多少，总会有一个交叉点，超过这个点合并排序会更快。”

为什么这是相关的？让我们看看这两个查询的查询执行计划。我们会看到有一个由内连接引起的合并操作。

score 0 · Accepted Answer

可能这应该是评论而不是答案，但它会有点长。

首先，很难相信具有（几乎）完全相同的解释的两个查询以不同的速度运行。此外，如果解释中带有额外行的那一行运行得更快，则这种可能性较小。我想“更快”这个词是这里的关键。

您已经比较了速度（完成查询所需的时间），这是一种非常具有经验的测试方式。例如，您可能不正确地禁用了缓存，这使得比较无用。更不用说<insert your preferred software application here>您在运行测试时可能进行了页面错误或任何其他可能导致查询速度下降的操作。

衡量查询性能的正确方法是基于解释（这就是它存在的原因）

所以最接近我必须回答这个问题的事情是：关于为什么加入比简化查询更快的任何想法？...简而言之，是第 8 层错误。

不过，我确实有其他一些意见，应该考虑到这些意见以加快速度。如果A.id是主键（名称闻起来像），根据您的解释，为什么count(A.id)必须扫描所有行？它应该能够直接从索引中获取数据，但我没有Using index在额外的标志中看到。似乎您甚至没有唯一索引，并且它不是不可为空的字段。这也闻起来很奇怪。确保该字段不为空并且上面有唯一索引，再次运行解释，确认额外的标志包含Using index，然后（正确）计时查询。它应该运行得更快。

另请注意，与我上面提到的相同的性能改进方法是替换count(A.id)为count(*).

只是我的2美分。

score 0 · Accepted Answer

因为 MySQL 不会index!=val在 where 中使用索引。

优化器将通过猜测来决定使用索引。由于“！=”更有可能获取所有内容，因此它会跳过并阻止使用索引来减少开销。（是的，mysql很笨，它不统计索引列）

您可以通过使用执行更快的 SELECT，index in(everything other then val)这样 MySQL 将学会使用索引。

此处显示查询优化器将选择不使用按值索引的示例

mysql - Condition on joined table faster than condition on reference

5 回答 5

Related

Reference