Why is MAX() 100 times slower than ORDER BY ... LIMIT 1?

Question

I have a table foo with (among 20 others) columns bar, baz and quux with indexes on baz and quux. The table has ~500k rows.

Why do the following to queries differ so much in speed? Query A takes 0.3s, while query B takes 28s.

Query A

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

Explain

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"

Query B

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

Explain

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"

I use MySQL 5.1.34.

'LiMIT 1' means taking 1 row and stop, doesn't it? the query B is O(n*m) — jondinham, Oct 17 '12 at 08:43
@PaulDinh seems both queries make same result, most probably that is related to order of operations, in 1st case it sort by quux and search bar from the result (fast) in second query it search bar (need to check whole table) from unsorted and then sort to find max — zb', Oct 17 '12 at 08:46
@Viktor, can you please show `explain select baz from foo where bar = :bar and quux = (select quux from foo where quux=MAX(quux) and bar = :bar )` `explain select baz from foo where bar = :bar and quux = (select quux from foo where quux=MAX(quux) and bar = :bar limit 1 )` — zb', Oct 17 '12 at 08:49
@eicto: +1 to your comment but I want to clarify one thing: Finding the maximum value of an unindexed column does not require a O(n log(n)) sort. It can be done in O(n) time by scanning the table once and remembering the highest value seen. — Mark Byers, Oct 17 '12 at 09:33

Mark Byers · Accepted Answer · 2012-10-17T09:50:59.833

You should add an index on (bar, quux).

Without this index, MySQL can't see how to perform the query efficiently so it has to choose from various inefficient query plans.

In the first example it scans the quux index and for each row found, looks up the corresponding value of bar in the original table. This takes twice as long to check each row, but it gets lucky that a row that has the correct value of bar is near the beginning of its scan and so it can stop. This could be because the value of bar you are searching for occurs frequently, so the chance of being lucky is very high. As a result it may only have to examine a handful of rows before it finds a match, so even though it takes twice as long to check each row, the fact that only a few rows are checked gives a massive overall saving. Since you have no index on bar, MySQL doesn't know in advance that the value :bar occurs frequently so it cannot know that this query will be fast.

In the second example it uses a different plan where it always scans the whole table. Each row is read directly from the table, without usage of an index. This means that each row read is fast, but because you have a lot of rows, it is slow overall. If none of the rows matched on :bar this would be the faster query plan. But if roughly 1% of rows have the desired value of bar, it will be (very) approximately 100 times slower to use this query plan compared to the above plan. Since you have no index on bar, MySQL doesn't know this in advance.

You could also just add the missing index and then both queries will go much faster.

It seems OP asked why the same result have so dramatical difference — zb', Oct 17 '12 at 08:50
so `select quux from foo where quux=MAX(quux) and bar = :bar ` is faster than `select MAX(quux) from foo where bar = :bar` if quux is indexed int and bar is text ? — zb', Oct 17 '12 at 09:04

Why is MAX() 100 times slower than ORDER BY ... LIMIT 1?

1 Answers1

Linked