Bug #77439 ORDER BY creates temporary tables when implicit order is declared explicitly
Submitted: 22 Jun 2015 18:00 Modified: 23 Jun 2015 13:34
Reporter: Domas Mituzas Email Updates:
Status: Verified Impact on me:
None 
Category:MySQL Server: Optimizer Severity:S4 (Feature request)
Version:all of them OS:Any (really all of them)
Assigned to: CPU Architecture:Any

[22 Jun 2015 18:00] Domas Mituzas
Description:
There're many cases in MySQL where ORDER BY will destroy query plans, even if underlying execution is already implicitly providing ordered data (i.e. reads on an index come out ordered)

This means that even if there're no major obstacles to execute query efficiently, ORDER BY decides that it needs to materialize full dataset on temporary table before returning it (or even worse, tiny subset of it) to the client.

We were doing workarounds all over around since the early ages of MySQL, the fact that this is still an issue is very saddening. 

How to repeat:
mysql> create table a1 (a int, b int, primary key (a,b));
Query OK, 0 rows affected (0.34 sec)

mysql> create table a2 (a int, b int, primary key (a,b));
Query OK, 0 rows affected (0.37 sec)

mysql> insert into a1 values (1,2),(1,3),(1,4),(2,4),(2,5),(2,6);
Query OK, 6 rows affected (0.05 sec)
Records: 6  Duplicates: 0  Warnings: 0

mysql> insert into a2 values (2,1),(2,2),(4,1),(4,2),(6,1),(6,2);
Query OK, 6 rows affected (0.10 sec)
Records: 6  Duplicates: 0  Warnings: 0

mysql> explain select * from a1 join a2 on a1.b=a2.a;
+----+-------------+-------+-------+---------------+---------+---------+-----------+------+-------------+
| id | select_type | table | type  | possible_keys | key     | key_len | ref       | rows | Extra       |
+----+-------------+-------+-------+---------------+---------+---------+-----------+------+-------------+
|  1 | SIMPLE      | a1    | index | NULL          | PRIMARY | 8       | NULL      |    6 | Using index |
|  1 | SIMPLE      | a2    | ref   | PRIMARY       | PRIMARY | 4       | test.a1.b |    1 | Using index |
+----+-------------+-------+-------+---------------+---------+---------+-----------+------+-------------+
2 rows in set (0.00 sec)

mysql> explain select * from a1 join a2 on a1.b=a2.a order by a1.a, a1.b, a2.a, a2.b;
+----+-------------+-------+-------+---------------+---------+---------+-----------+------+----------------------------------------------+
| id | select_type | table | type  | possible_keys | key     | key_len | ref       | rows | Extra                                        |
+----+-------------+-------+-------+---------------+---------+---------+-----------+------+----------------------------------------------+
|  1 | SIMPLE      | a1    | index | NULL          | PRIMARY | 8       | NULL      |    6 | Using index; Using temporary; Using filesort |
|  1 | SIMPLE      | a2    | ref   | PRIMARY       | PRIMARY | 4       | test.a1.b |    1 | Using index                                  |
+----+-------------+-------+-------+---------------+---------+---------+-----------+------+----------------------------------------------+
2 rows in set (0.00 sec)

mysql> 

Suggested fix:
optimize ORDER BY properly.
[23 Jun 2015 13:34] Sinisa Milivojevic
This is indeed a deficiency, but it is not a bug. However, this is a feature request in the optimizer domain that would be very much welcome.

Verified.
[2 Sep 2016 13:42] Morgan Tocker
Just a quick note that this is an InnoDB-specific optimization (which is fine).  NDB for example will not guarantee order here.