为什么MAX()函数比ORDER BY ... LIMIT 1慢100倍？

Question

为什么MAX()函数比ORDER BY ... LIMIT 1慢100倍？

9

我有一个名为foo的表格，其中包含20个其他列，包括bar、baz和quux。在baz和quux上都建有索引。该表格共有约50万行。

以下两个查询为什么速度相差如此之大？查询A只需要0.3秒，而查询B需要28秒。 查询A：

select baz from foo
    where bar = :bar
    and quux = (select quux from foo where bar = :bar order by quux desc limit 1)

解释，说明

id  select_type table   type    possible_keys   key     key_len ref     rows    Extra
1   PRIMARY     foo     ref     quuxIdx         quuxIdx 9       const   2       "Using where"
2   SUBQUERY    foo     index   NULL            quuxIdx 9       NULL    1       "Using where"

查询 B

select baz from foo
    where bar = :bar
    and quux = (select MAX(quux) from foo where bar = :bar)

解释，说明

id  select_type table   type    possible_keys   key     key_len ref     rows    Extra
1   PRIMARY     foo     ref     quuxIdx         quuxIdx 9       const   2       "Using where"
2   SUBQUERY    foo     ALL     NULL            NULL    NULL    NULL    448060  "Using where"

我使用的是MySQL 5.1.34版本。

- Viktor Dahl

“LiMIT 1” 的意思是只取一行并停止，对吗？查询 B 的时间复杂度为 O(n*m)。 - jondinham

2

@PaulDinh 看起来两个查询结果都是相同的，很可能与操作顺序有关，在第一种情况下，它按 quux 进行排序，并从结果中搜索搜索栏（快速），在第二个查询中，它从未排序的表中搜索搜索栏（需要检查整个表），然后进行排序以找到最大值。 - zb'

@Viktor，你能否展示以下内容：解释选择 foo 表中 baz 字段，其中 bar = :bar 并且 quux 等于 (选取 foo 表中 quux 字段，其中 quux=MAX(quux) 且 bar = :bar ) 的查询语句解释选择 foo 表中 baz 字段，其中 bar = :bar 并且 quux 等于 (选取 foo 表中 quux 字段，其中 quux=MAX(quux) 且 bar = :bar limit 1 ) 的查询语句 - zb'

@eicto：对你的评论点赞，但我想澄清一件事：查找未索引列的最大值不需要O(n log(n))排序。可以通过扫描表格一次并记住所见到的最高值来在O(n)时间内完成。 - Mark Byers

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Mark Byers · Accepted Answer

你应该在 (bar, quux) 上添加索引。

没有这个索引，MySQL 无法有效地执行查询，因此必须从各种低效的查询计划中选择。在第一个示例中，它扫描了 quux 索引，并查找原始表中对应的 bar 值。这需要检查每行两次，但它运气很好，找到了具有正确 bar 值的行，所以扫描可以停止。这可能是因为你搜索的 bar 值经常出现，所以幸运的机会非常高。因此，它只需检查少量行即可找到匹配项，即使每行检查时间是两倍，但检查的只有少量行，总体上也实现了巨大的节省。由于索引上没有 bar，MySQL 事先不知道值 :bar 是否频繁出现，因此它无法知道这个查询是否快速。

在第二个示例中，它使用不同的计划，始终扫描整个表格。每行直接从表格中读取，而没有使用索引。这意味着每行读取都很快，但由于你有很多行，总体上很慢。如果没有任何行与:bar 匹配，则此查询计划将更快。但是，如果大约 1% 的行具有所需的 bar 值，则使用此查询计划将比上面的计划慢（非常）约 100 倍。由于你没有在 bar 上添加索引，MySQL 无法事先知道这一点。

你也可以只添加缺失的索引，然后两个查询都会运行得更快。