MySQL Bugs: #8036: Bad optimization of ORDER BY ... LIMIT 1 if one table is MyISAM, another InnoDB

Bug #8036	Bad optimization of ORDER BY ... LIMIT 1 if one table is MyISAM, another InnoDB
Submitted:	20 Jan 2005 10:12	Modified:	29 Jan 2005 2:16
Reporter:	Nick Peterson	Email Updates:
Status:	Verified	Impact on me:	None
Category:	MySQL Server: Optimizer	Severity:	S3 (Non-critical)
Version:	4.0.18, 4.1.10, 5.1.52	OS:	FreeBSD (Free BSD 4.5, Linux)
Assigned to:		CPU Architecture:	Any

Description:
I have changed type of table from MyISAM to InnoDB, the select query increese up to 10X times, 

QUERY: select * from t1, t2 WHERE t1.name = t2.id ORDER by t1.name DESC LIMIT 10; 

when I have make the FLUSH of that table - all bacame fine (fast ~ 0.01 s)

When i have shutdown the mysql (with mysqladmin) and making the same query, the select query increese up to 10X times.

How to repeat:
When i have shutdown the mysql (with mysqladmin) and making the same query, the select query increese up to 10X times.

innodb is running slow (after shutdown) untill i make 'flush'

Can you submit a dump of the tables involved (preference as
attached file in the Files tab here) ?

Thanks in advance.

Nick,

please print

EXPLAIN SELECT ...;

in the fast case and the slow case.

Regards,

Heikki

<b>InnoDB stranges</b>

<pre>
at first 'documents' and 'companies' are MyISAM

<b>1.</b>
It is with MyISAM table;
mysql> SELECT d.date FROM companies c, documents d WHERE c.cmid = d.cmid ORDER by d.docid DESC LIMIT 1;
+------------+
| date       |
+------------+
| 2005-01-10 |
+------------+
1 row in set (0.02 sec)
mysql> explain SELECT d.date FROM companies c, documents d WHERE c.cmid = d.cmid ORDER by d.docid DESC LIMIT 1 ;
+-------+-------+---------------+---------+---------+--------+-------+-------------+
| table | type  | possible_keys | key     | key_len | ref    | rows  | Extra       |
+-------+-------+---------------+---------+---------+--------+-------+-------------+
| d     | index | cmid          | PRIMARY |       4 | NULL   | 22931 |             |
| c     | ref   | cmid          | cmid    |       4 | d.cmid |     1 | Using index |
+-------+-------+---------------+---------+---------+--------+-------+-------------+
2 rows in set (0.00 sec)

<b>2.</b>
After :: ALTER TABLE `documents` TYPE = INNODB;
now 'documents' is InnoDB and 'companies' is MyISAM
mysql> SELECT d.date  FROM companies c,documents d WHERE c.cmid = d.cmid ORDER by d.docid DESC LIMIT 1 ;
+------------+
| date       |
+------------+
| 2005-01-10 |
+------------+
1 row in set (0.00 sec)

mysql> explain SELECT d.date  FROM companies c,documents d WHERE c.cmid = d.cmid ORDER by d.docid DESC LIMIT 1 ;
+-------+-------+---------------+---------+---------+--------+-------+-------------+
| table | type  | possible_keys | key     | key_len | ref    | rows  | Extra       |
+-------+-------+---------------+---------+---------+--------+-------+-------------+
| d     | index | cmid          | PRIMARY |       4 | NULL   | 22251 |             |
| c     | ref   | cmid          | cmid    |       4 | d.cmid |     1 | Using index |
+-------+-------+---------------+---------+---------+--------+-------+-------------+
2 rows in set (0.00 sec)

<b>3.</b>
It is<font color=red> after shutdowning mysql</font>; (type of table are the same as in /2/)
mysql> SELECT d.date  FROM companies c,documents d WHERE c.cmid = d.cmid ORDER by d.docid DESC LIMIT 1 ;
+------------+
| date       |
+------------+
| 2005-01-10 |
+------------+
1 row in set <font color=red>(0.83 sec)</font>

mysql> explain SELECT d.date  FROM companies c,documents d WHERE c.cmid = d.cmid ORDER by d.docid DESC LIMIT 1 ;
+-------+-------+---------------+------+---------+--------+------+----------------------------------------------+
| table | type  | possible_keys | key  | key_len | ref    | rows | Extra                                        |
+-------+-------+---------------+------+---------+--------+------+----------------------------------------------+
| c     | index | cmid          | cmid |       4 | NULL   |  924 | Using index; Using temporary; Using filesort |
| d     | ref   | cmid          | cmid |       4 | c.cmid |   15 |                                              |
+-------+-------+---------------+------+---------+--------+------+----------------------------------------------+
2 rows in set (0.00 sec)

<b>4.</b>
It is after :: flush table documents;
(type of tables are the same as in /2/ and /3/)
mysql> SELECT d.date  FROM companies c,documents d WHERE c.cmid = d.cmid ORDER by d.docid DESC LIMIT 1 ;
+------------+
| date       |
+------------+
| 2005-01-10 |
+------------+
1 row in set (0.00 sec)

mysql> explain SELECT d.date  FROM companies c,documents d WHERE c.cmid = d.cmid ORDER by d.docid DESC LIMIT 1 ;
+-------+-------+---------------+---------+---------+--------+-------+-------------+
| table | type  | possible_keys | key     | key_len | ref    | rows  | Extra       |
+-------+-------+---------------+---------+---------+--------+-------+-------------+
| d     | index | cmid          | PRIMARY |       4 | NULL   | 18056 |             |
| c     | ref   | cmid          | cmid    |       4 | d.cmid |     1 | Using index |
+-------+-------+---------------+---------+---------+--------+-------+-------------+
2 rows in set (0.00 sec)
</pre>

This problem bacame until to make <font color=green>'flush table documents;'</font> after shutdowning the mysql

Nick,

I am able to repeat the problem with 4.1.10. FLUSH TABLE did not seem to have any effect here, but the optimization is grossly wrong if one table is MyISAM and another InnoDB. Instead of just fetching that one row, MySQL does a filesort!

If both tables are InnoDB, then the optimization is ok. The same if both tables are MyISAM.

Thank you for the bug report,

Heikki

mysql> show create table a1;
+-------+-----------------------------------------------------------------------
--------------------------------------------------------------------------------
--------------------------------------------------------------------------------
--------------------------------------------------------------------------------
-------------------------------------------------------+
| Table | Create Table

                                                       |
+-------+-----------------------------------------------------------------------
--------------------------------------------------------------------------------
--------------------------------------------------------------------------------
--------------------------------------------------------------------------------
-------------------------------------------------------+
| a1    | CREATE TABLE `a1` (
  `a` int(11) NOT NULL default '0',
  `b` int(11) default NULL,
  `c` char(255) default NULL,
  `d` char(255) default NULL,
  `e` char(255) default NULL,
  `f` char(255) default NULL,
  `g` char(255) default NULL,
  PRIMARY KEY  (`a`),
  UNIQUE KEY `i1` (`b`),
  UNIQUE KEY `i2` (`b`),
  KEY `c` (`c`(50))
) ENGINE=MyISAM DEFAULT CHARSET=latin1 |
+-------+-----------------------------------------------------------------------
--------------------------------------------------------------------------------
--------------------------------------------------------------------------------
--------------------------------------------------------------------------------
-------------------------------------------------------+
1 row in set (0.00 sec)

mysql> show create table a2;
+-------+-----------------------------------------------------------------------
--------------------------------------------------------------------------------
--------------------------------------------------------------------------------
--------------------------------------------------------------------------------
-------------------------------------------------------+
| Table | Create Table

                                                       |
+-------+-----------------------------------------------------------------------
--------------------------------------------------------------------------------
--------------------------------------------------------------------------------
--------------------------------------------------------------------------------
-------------------------------------------------------+
| a2    | CREATE TABLE `a2` (
  `a` int(11) NOT NULL default '0',
  `b` int(11) default NULL,
  `c` char(255) default NULL,
  `d` char(255) default NULL,
  `e` char(255) default NULL,
  `f` char(255) default NULL,
  `g` char(255) default NULL,
  PRIMARY KEY  (`a`),
  UNIQUE KEY `i1` (`b`),
  UNIQUE KEY `i2` (`b`),
  KEY `c` (`c`(50))
) ENGINE=InnoDB DEFAULT CHARSET=latin1 |
+-------+-----------------------------------------------------------------------
--------------------------------------------------------------------------------
--------------------------------------------------------------------------------
--------------------------------------------------------------------------------
-------------------------------------------------------+
1 row in set (3.68 sec)

mysql> describe select * from a1, a2 where a1.b = a2.b order by a2.a limit 1;
+----+-------------+-------+------+---------------+------+---------+-----------+
------+---------------------------------+
| id | select_type | table | type | possible_keys | key  | key_len | ref       |
 rows | Extra                           |
+----+-------------+-------+------+---------------+------+---------+-----------+
------+---------------------------------+
|  1 | SIMPLE      | a1    | ALL  | i1,i2         | NULL |    NULL | NULL      |
 8631 | Using temporary; Using filesort |
|  1 | SIMPLE      | a2    | ref  | i1,i2         | i2   |       5 | test.a1.b |
    1 | Using where                     |
+----+-------------+-------+------+---------------+------+---------+-----------+
------+---------------------------------+
2 rows in set (2.69 sec)

mysql> alter table a1 type = innodb;
Query OK, 8631 rows affected, 1 warning (6.63 sec)
Records: 8631  Duplicates: 0  Warnings: 0

mysql> describe select * from a1, a2 where a1.b = a2.b order by a2.a limit 1;
+----+-------------+-------+-------+---------------+---------+---------+--------
---+------+-------------+
| id | select_type | table | type  | possible_keys | key     | key_len | ref
   | rows | Extra       |
+----+-------------+-------+-------+---------------+---------+---------+--------
---+------+-------------+
|  1 | SIMPLE      | a2    | index | i1,i2         | PRIMARY |       4 | NULL
   | 6718 |             |
|  1 | SIMPLE      | a1    | ref   | i1,i2         | i1      |       5 | test.a2
.b |    1 | Using where |
+----+-------------+-------+-------+---------------+---------+---------+--------
---+------+-------------+
2 rows in set (3.90 sec)

mysql> describe select * from a1, a2 where a1.b = a2.b order by a2.a limit 1;
+----+-------------+-------+-------+---------------+---------+---------+--------
---+------+-------------+
| id | select_type | table | type  | possible_keys | key     | key_len | ref
   | rows | Extra       |
+----+-------------+-------+-------+---------------+---------+---------+--------
---+------+-------------+
|  1 | SIMPLE      | a2    | index | i1,i2         | PRIMARY |       4 | NULL
   | 6718 |             |
|  1 | SIMPLE      | a1    | ref   | i1,i2         | i1      |       5 | test.a2
.b |    1 | Using where |
+----+-------------+-------+-------+---------------+---------+---------+--------
---+------+-------------+
2 rows in set (3.04 sec)

If three tables would be InnoDB the problem would be the same as with (MyISAM and InnoDB):
a1 - is InnoBD;a2 - is InnoBD;a3 - is InnoBD;

describe select * from a1, a2, a3 where a1.b = a3.b AND a1.c = a2.c order by a2.c limit 1; # would be without temp file (ok)

describe select * from a1, a2, a3 where a1.b = a3.b AND a1.c = a2.c order by a1.c limit 1; # would be slovly, with temp file (bed)

PS. 
a1 - is MyISAM;a2 - is MyISAM;a3 - is MyISAM;

describe select * from a1, a2, a3 where a1.b = a3.b AND a1.c = a2.c order by a2.c limit 1; # would be without temp file (ok)

describe select * from a1, a2, a3 where a1.b = a3.b AND a1.c = a2.c order by a1.c limit 1; # would be without temp file (ok)

Heikki Tuuri, can you check/test thats with three tables ?

The problem can be easily reproduced in the following way as well:

mysql> CREATE TABLE t1 (
    -> a int NOT NULL DEFAULT '0',
    -> b int,
    -> PRIMARY KEY (a),
    -> UNIQUE KEY i1(b)
    -> ) ENGINE=MyISAM;
Query OK, 0 rows affected (0.09 sec)

mysql> CREATE TABLE t2 (
    -> a int NOT NULL DEFAULT '0',
    -> b int,
    -> PRIMARY KEY (a),
    -> UNIQUE KEY i1(b)
    -> ) ENGINE=MyISAM;
Query OK, 0 rows affected (0.07 sec)

mysql> INSERT INTO t1 VALUES (1,10), (2,20), (3,30);
Query OK, 3 rows affected (0.01 sec)
Records: 3  Duplicates: 0  Warnings: 0

mysql> INSERT INTO t2 VALUES (3,20), (4,30);
Query OK, 2 rows affected (0.00 sec)
Records: 2  Duplicates: 0  Warnings: 0

mysql> EXPLAIN SELECT * FROM t1, t2 WHERE t1.b = t2.b ORDER BY t2.a LIMIT 1;
+----+-------------+-------+------+---------------+------+---------+------+------+---------------------------------+
| id | select_type | table | type | possible_keys | key  | key_len | ref  | rows | Extra                           |
+----+-------------+-------+------+---------------+------+---------+------+------+---------------------------------+
|  1 | SIMPLE      | t2    | ALL  | i1            | NULL | NULL    | NULL |    2 | Using temporary; Using filesort |
|  1 | SIMPLE      | t1    | ALL  | i1            | NULL | NULL    | NULL |    3 | Using where                     |
+----+-------------+-------+------+---------------+------+---------+------+------+---------------------------------+
2 rows in set (0.00 sec)

Yet after having run the ANALYZE command for table t1:
mysql> ANALYZE TABLE t1;
+---------+---------+----------+----------+
| Table   | Op      | Msg_type | Msg_text |
+---------+---------+----------+----------+
| test.t1 | analyze | status   | OK       |
+---------+---------+----------+----------+
1 row in set (0.02 sec)

 we have:
mysql> EXPLAIN SELECT * FROM t1, t2 WHERE t1.b = t2.b ORDER BY t2.a LIMIT 1;
+----+-------------+-------+-------+---------------+---------+---------+-----------+------+-------------+
| id | select_type | table | type  | possible_keys | key     | key_len | ref       | rows | Extra       |
+----+-------------+-------+-------+---------------+---------+---------+-----------+------+-------------+
|  1 | SIMPLE      | t2    | index | i1            | PRIMARY | 4       | NULL      |    2 |             |
|  1 | SIMPLE      | t1    | ref   | i1            | i1      | 5       | test.t2.b |    1 | Using where |
+----+-------------+-------+-------+---------------+---------+---------+-----------+------+-------------+
2 rows in set (0.02 sec)

If we define table t1 as an InnoDB table no ANALYZE command is required.

mysql> CREATE TABLE t1 (
    -> a int NOT NULL DEFAULT '0',
    -> b int,
    -> PRIMARY KEY (a),
    -> UNIQUE KEY i1(b)
    -> ) ENGINE=InnoDB;
Query OK, 0 rows affected (0.13 sec)

mysql> CREATE TABLE t2 (
    -> a int NOT NULL DEFAULT '0',
    -> b int,
    -> PRIMARY KEY (a),
    -> UNIQUE KEY i1(b)
    -> ) ENGINE=MyISAM;
Query OK, 0 rows affected (0.06 sec)

mysql> INSERT INTO t1 VALUES (1,10), (2,20), (3,30);
Query OK, 3 rows affected (0.12 sec)
Records: 3  Duplicates: 0  Warnings: 0

mysql> INSERT INTO t2 VALUES (3,20), (4,30);
Query OK, 2 rows affected (0.00 sec)
Records: 2  Duplicates: 0  Warnings: 0

mysql> EXPLAIN SELECT * FROM t1, t2 WHERE t1.b = t2.b ORDER BY t2.a LIMIT 1;
+----+-------------+-------+-------+---------------+---------+---------+-----------+------+--------------------------+
| id | select_type | table | type  | possible_keys | key     | key_len | ref       | rows | Extra                    |
+----+-------------+-------+-------+---------------+---------+---------+-----------+------+--------------------------+
|  1 | SIMPLE      | t2    | index | i1            | PRIMARY | 4       | NULL      |    2 |                          |
|  1 | SIMPLE      | t1    | ref   | i1            | i1      | 5       | test.t2.b |    1 | Using where; Using index |
+----+-------------+-------+-------+---------------+---------+---------+-----------+------+--------------------------+
2 rows in set (0.00 sec)

It happens because:
handler ha_innobase::info sets the value of rec_per_key for index i1 of table t1 equal to 1;
handler ha_myisam::info sets the value of rec_per_key for index i1 of table t1 equal to 1 only after ANALYZE TABLE t1 has been executed.

(Handler ::info is called in at the very beginning of make_join_statistics.)

create database test; use test;
CREATE TABLE tt1 (
a int NOT NULL DEFAULT '0',
b int,
PRIMARY KEY (a),
UNIQUE KEY i1(b)
) ENGINE=MyISAM;

CREATE TABLE tt2 (
a int NOT NULL DEFAULT '0',
b int,
PRIMARY KEY (a),
UNIQUE KEY i1(b)
) ENGINE=MyISAM;

CREATE TABLE tt3 (
a int NOT NULL DEFAULT '0',
b int,
PRIMARY KEY (a),
UNIQUE KEY i1(b)
) ENGINE=MyISAM;

INSERT INTO tt1 VALUES (1,10), (2,20), (3,30);
INSERT INTO tt2 VALUES (3,20), (4,30);
INSERT INTO tt3 VALUES (2,30), (7,10);

CREATE TABLE t1 (
a int NOT NULL DEFAULT '0',
b int,
PRIMARY KEY (a),
UNIQUE KEY i1(b)
) ENGINE=InnoDB;

CREATE TABLE t2 (
a int NOT NULL DEFAULT '0',
b int,
PRIMARY KEY (a),
UNIQUE KEY i1(b)
) ENGINE=InnoDB;

CREATE TABLE t3 (
a int NOT NULL DEFAULT '0',
b int,
PRIMARY KEY (a),
UNIQUE KEY i1(b)
) ENGINE=InnoDB;

INSERT INTO t1 VALUES (1,10), (2,20), (3,30);
INSERT INTO t2 VALUES (3,20), (4,30);
INSERT INTO t3 VALUES (2,30), (6,10);

// InnoDB  tables -- works perfect as it must be
mysql> EXPLAIN select * from t1, t2, t3 where t1.b = t3.b AND t1.a = t2.a order by
    -> t2.a limit 1;
+-------+--------+---------------+---------+---------+------+------+----------------------------------------------+
| table | type   | possible_keys | key     | key_len | ref  | rows | Extra                                        |
+-------+--------+---------------+---------+---------+------+------+----------------------------------------------+
| t2    | index  | PRIMARY       | i1      |       5 | NULL |    2 | Using index; Using temporary; Using filesort |
| t3    | index  | i1            | i1      |       5 | NULL |    2 | Using index                                  |
| t1    | eq_ref | PRIMARY,i1    | PRIMARY |       4 | t2.a |    1 | Using where                                  |
+-------+--------+---------------+---------+---------+------+------+----------------------------------------------+
3 rows in set (0.00 sec)

mysql>
mysql> EXPLAIN select * from t1, t2, t3 where t1.b = t3.b AND t1.a = t2.a order by
    -> t1.b limit 1;
+-------+--------+---------------+---------+---------+------+------+----------------------------------------------+
| table | type   | possible_keys | key     | key_len | ref  | rows | Extra                                        |
+-------+--------+---------------+---------+---------+------+------+----------------------------------------------+
| t3    | index  | i1            | i1      |       5 | NULL |    2 | Using index; Using temporary; Using filesort |
| t1    | ref    | PRIMARY,i1    | i1      |       5 | t3.b |    1 | Using where; Using index                     |
| t2    | eq_ref | PRIMARY       | PRIMARY |       4 | t1.a |    1 |                                              |
+-------+--------+---------------+---------+---------+------+------+----------------------------------------------+
3 rows in set (0.00 sec)

// MyISAM  tables -- works perfect as it must be
mysql> EXPLAIN select * from tt1, tt2, tt3 where tt1.b = tt3.b AND tt1.a = tt2.a order by
    -> tt2.a limit 1;
+-------+--------+---------------+---------+---------+-------+------+-------------+
| table | type   | possible_keys | key     | key_len | ref   | rows | Extra       |
+-------+--------+---------------+---------+---------+-------+------+-------------+
| tt2   | index  | PRIMARY       | PRIMARY |       4 | NULL  |    2 |             |
| tt1   | eq_ref | PRIMARY,i1    | PRIMARY |       4 | tt2.a |    1 |             |
| tt3   | ref    | i1            | i1      |       5 | tt1.b |    1 | Using where |
+-------+--------+---------------+---------+---------+-------+------+-------------+
3 rows in set (0.00 sec)

mysql> EXPLAIN select * from tt1, tt2, tt3 where tt1.b = tt3.b AND tt1.a = tt2.a order by
    -> tt1.b limit 1;
+-------+--------+---------------+---------+---------+-------+------+---------------------------------+
| table | type   | possible_keys | key     | key_len | ref   | rows | Extra                           |
+-------+--------+---------------+---------+---------+-------+------+---------------------------------+
| tt3   | ALL    | i1            | NULL    |    NULL | NULL  |    2 | Using temporary; Using filesort |
| tt1   | ref    | PRIMARY,i1    | i1      |       5 | tt3.b |    1 | Using where                     |
| tt2   | eq_ref | PRIMARY       | PRIMARY |       4 | tt1.a |    1 |                                 |
+-------+--------+---------------+---------+---------+-------+------+---------------------------------+
3 rows in set (0.00 sec)

The structure of the tables (MyISAM && InnoDB) are the same, but there is something strange with InnoDB sorting algorithm
It always (in all cases) use 'temporary files' (the opposite do MyISAM)

PS. Analyse and Optimise would not help InnoDB tables.
PSS. Igor Babay :)) (btw., are you russian ?)
thats what you have wrote : 
'It happens because:
handler ha_innobase::info sets the value of rec_per_key for index i1 of table t1
equal to 1;
handler ha_myisam::info sets the value of rec_per_key for index i1 of table t1
equal to 1 only after ANALYZE TABLE t1 has been executed.

(Handler ::info is called in at the very beginning of make_join_statistics.) '
have NOTHING with this problem, ('course it is MyISAM defacto THING).
And we are talking about InnoDB stranges :)

in prevs comment the correct would be: 
// InnoDB  tables -- works non-perfect as it must be
mysql> EXPLAIN select * from t1, t2, t3 where t1.b = t3.b AND t1.a = t2.a order by
    -> t2.a limit 1;
+-------+--------+---------------+---------+---------+------+------+----------------------------------------------+
| table | type   | possible_keys | key     | key_len | ref  | rows | Extra                                        |
+-------+--------+---------------+---------+---------+------+------+----------------------------------------------+
| t2    | index  | PRIMARY       | i1      |       5 | NULL |    2 | Using index; Using temporary; Using filesort |
| t3    | index  | i1            | i1      |       5 | NULL |    2 | Using index                                  |
| t1    | eq_ref | PRIMARY,i1    | PRIMARY |       4 | t2.a |    1 | Using where                                  |
+-------+--------+---------------+---------+---------+------+------+----------------------------------------------+
3 rows in set (0.00 sec)

mysql>
mysql> EXPLAIN select * from t1, t2, t3 where t1.b = t3.b AND t1.a = t2.a order by
    -> t1.b limit 1;
+-------+--------+---------------+---------+---------+------+------+----------------------------------------------+
| table | type   | possible_keys | key     | key_len | ref  | rows | Extra                                        |
+-------+--------+---------------+---------+---------+------+------+----------------------------------------------+
| t3    | index  | i1            | i1      |       5 | NULL |    2 | Using index; Using temporary; Using filesort |
| t1    | ref    | PRIMARY,i1    | i1      |       5 | t3.b |    1 | Using where; Using index                     |
| t2    | eq_ref | PRIMARY       | PRIMARY |       4 | t1.a |    1 |                                              |
+-------+--------+---------------+---------+---------+------+------+----------------------------------------------+
3 rows in set (0.00 sec)

Nick,

Igor is working on this.

The optimization is so totally wrong also in the mixed MyISAM/InnoDB case that it has to be fixed. I hope that will fix also other cases.

Thank you,

Heikki

Thank you for taking the time to write to us, but this is not
a bug. Please double-check the documentation available at
http://www.mysql.com/documentation/ and the instructions on
how to report a bug at http://bugs.mysql.com/how-to-report.php

Additional info:

Hi!

The root of this problem has nothing to do with InnoDB or MyISAM tables, but
instead is how MySQL optimizes a query of this type:

The optimization works basily like this (in this case):

- Find the optimal way to join the tables
  (Based on index statistics and how the table handlers stores it's data)

- When the join order is defined, check if we can optimise the ORDER BY
  clause by using an index (This can only be done if there is only one table
  in the ORDER BY clause and the table is the first table in the join order
  list)

When one want to do an ORDER BY on the FULL result set, this is usually a good
way to solve the problem.

Even if you have a very small limit of result rows, it's still better to
try to optimise the join instead of sorting a full table and then
reading the rows in order to hope to find the wanted rows. (Even reading rows
in index order may be quite sub-optimal)

As Igor said, the reason for the difference for InnoDB and MyISAM in this case
is that the table handler returns slightly different key-distribution
statistics to the optimiser and this causes the optimiser to choose different
join orders.  As the statistics are 'estimated' is not uncommon that there
may be different join orders for different table handlers or even over time
for small data sets.  (For bigger data sets with big variations the statistics
are usually good enough to allow the optimiser to choose the best join order
and the best indexes)

MySQL does take into consideration that it will be a bit more efficient
to first join the table for which we do an ORDER BY on, but in this case
this extra 'weight' is not enough to always force the right table first.

The optimisation we are not considering for the moment that would help
this particular query is: 

- There is a small limit clause
- We are doing a table or index scan on the first table
- We can use an index to resolve the ORDER BY

in this case we could give the 'first' table a higher priority to ensure
it will be first in the join order.

The drawback with this is that in the case when there is only a few matching
rows (and a lot of row combinations to examine), this may take significantly
more time than the current algoritm.

We are considering this (and other optimisation enhancements) in 5.1

In the mean time, you can help MySQL to solve this by forcing the table you
are doing an ORDER BY on to be first in the join: 

select STRAIGHT JOIN * from t1, t2 WHERE t1.name = t2.id ORDER by t1.name DESC LIMIT 10;

This will force the table order to be t1, t2 and MySQL will solve the query by
scanning the t1.name index backwards.

Some more information how MySQL optimizes ORDER BY can be found at:

http://dev.mysql.com/doc/mysql/en/order-by-optimization.html

by using this knowledge you should be able to 'force' MySQL to solve the query
they way you want...

Regards,
Monty

But, the same query (with the same tables sructures) works differently in MyISAM and in InnoDB. 

Thats strange!!

This is what we have with 5.1.52 today:

macbook-pro:5.1 openxs$ bin/mysql -uroot test
Reading table information for completion of table and column names
You can turn off this feature to get a quicker startup with -A

Welcome to the MySQL monitor.  Commands end with ; or \g.
Your MySQL connection id is 8
Server version: 5.1.52-debug Source distribution

Copyright (c) 2000, 2010, Oracle and/or its affiliates. All rights reserved.
This software comes with ABSOLUTELY NO WARRANTY. This is free software,
and you are welcome to modify and redistribute it under the GPL v2 license

Type 'help;' or '\h' for help. Type '\c' to clear the current input statement.

mysql> create database test2;
Query OK, 1 row affected (0.00 sec)

mysql> use test2;
Database changed
mysql> CREATE TABLE tt1 (
    -> a int NOT NULL DEFAULT '0',
    -> b int,
    -> PRIMARY KEY (a),
    -> UNIQUE KEY i1(b)
    -> ) ENGINE=MyISAM;
Query OK, 0 rows affected (0.08 sec)

mysql> 
mysql> CREATE TABLE tt2 (
    -> a int NOT NULL DEFAULT '0',
    -> b int,
    -> PRIMARY KEY (a),
    -> UNIQUE KEY i1(b)
    -> ) ENGINE=MyISAM;
Query OK, 0 rows affected (0.29 sec)

mysql> 
mysql> CREATE TABLE tt3 (
    -> a int NOT NULL DEFAULT '0',
    -> b int,
    -> PRIMARY KEY (a),
    -> UNIQUE KEY i1(b)
    -> ) ENGINE=MyISAM;
Query OK, 0 rows affected (0.09 sec)

mysql> INSERT INTO tt1 VALUES (1,10), (2,20), (3,30);
Query OK, 3 rows affected (0.00 sec)
Records: 3  Duplicates: 0  Warnings: 0

mysql> INSERT INTO tt2 VALUES (3,20), (4,30);
Query OK, 2 rows affected (0.01 sec)
Records: 2  Duplicates: 0  Warnings: 0

mysql> INSERT INTO tt3 VALUES (2,30), (7,10);
Query OK, 2 rows affected (0.00 sec)
Records: 2  Duplicates: 0  Warnings: 0

mysql> CREATE TABLE t1 (
    -> a int NOT NULL DEFAULT '0',
    -> b int,
    -> PRIMARY KEY (a),
    -> UNIQUE KEY i1(b)
    -> ) ENGINE=InnoDB;
Query OK, 0 rows affected (0.07 sec)

mysql> CREATE TABLE t2 (
    -> a int NOT NULL DEFAULT '0',
    -> b int,
    -> PRIMARY KEY (a),
    -> UNIQUE KEY i1(b)
    -> ) ENGINE=InnoDB;
Query OK, 0 rows affected (0.08 sec)

mysql> CREATE TABLE t3 (
    -> a int NOT NULL DEFAULT '0',
    -> b int,
    -> PRIMARY KEY (a),
    -> UNIQUE KEY i1(b)
    -> ) ENGINE=InnoDB;
Query OK, 0 rows affected (0.10 sec)

mysql> INSERT INTO t1 VALUES (1,10), (2,20), (3,30);
Query OK, 3 rows affected (0.00 sec)
Records: 3  Duplicates: 0  Warnings: 0

mysql> INSERT INTO t2 VALUES (3,20), (4,30);
Query OK, 2 rows affected (0.00 sec)
Records: 2  Duplicates: 0  Warnings: 0

mysql> INSERT INTO t3 VALUES (2,30), (6,10);
Query OK, 2 rows affected (0.01 sec)
Records: 2  Duplicates: 0  Warnings: 0

mysql> analyze table t1,t2,t3;
+----------+---------+----------+----------+
| Table    | Op      | Msg_type | Msg_text |
+----------+---------+----------+----------+
| test2.t1 | analyze | status   | OK       |
| test2.t2 | analyze | status   | OK       |
| test2.t3 | analyze | status   | OK       |
+----------+---------+----------+----------+
3 rows in set (0.00 sec)

mysql> analyze table tt1,tt2,tt3;
+-----------+---------+----------+----------+
| Table     | Op      | Msg_type | Msg_text |
+-----------+---------+----------+----------+
| test2.tt1 | analyze | status   | OK       |
| test2.tt2 | analyze | status   | OK       |
| test2.tt3 | analyze | status   | OK       |
+-----------+---------+----------+----------+
3 rows in set (0.00 sec)

mysql> EXPLAIN select * from t1, t2, t3 where t1.b = t3.b AND t1.a = t2.a order by
    -> t2.a limit 1;
+----+-------------+-------+--------+---------------+---------+---------+------------+------+----------------------------------------------+
| id | select_type | table | type   | possible_keys | key     | key_len | ref        | rows | Extra                                        |
+----+-------------+-------+--------+---------------+---------+---------+------------+------+----------------------------------------------+
|  1 | SIMPLE      | t2    | index  | PRIMARY       | i1      | 5       | NULL       |    2 | Using index; Using temporary; Using filesort |
|  1 | SIMPLE      | t3    | index  | i1            | i1      | 5       | NULL       |    2 | Using index; Using join buffer               |
|  1 | SIMPLE      | t1    | eq_ref | PRIMARY,i1    | PRIMARY | 4       | test2.t2.a |    1 | Using where                                  |
+----+-------------+-------+--------+---------------+---------+---------+------------+------+----------------------------------------------+
3 rows in set (0.00 sec)

The above plan is wrong. I see no reason to use index i1 on column b instead of PRIMARY.

mysql> EXPLAIN select * from t1, t2, t3 where t1.b = t3.b AND t1.a = t2.a order by t1.b limit 1;
+----+-------------+-------+--------+---------------+---------+---------+------------+------+----------------------------------------------+
| id | select_type | table | type   | possible_keys | key     | key_len | ref        | rows | Extra                                        |
+----+-------------+-------+--------+---------------+---------+---------+------------+------+----------------------------------------------+
|  1 | SIMPLE      | t2    | index  | PRIMARY       | i1      | 5       | NULL       |    2 | Using index; Using temporary; Using filesort |
|  1 | SIMPLE      | t1    | eq_ref | PRIMARY,i1    | PRIMARY | 4       | test2.t2.a |    1 |                                              |
|  1 | SIMPLE      | t3    | ref    | i1            | i1      | 5       | test2.t1.b |    1 | Using where; Using index                     |
+----+-------------+-------+--------+---------------+---------+---------+------------+------+----------------------------------------------+
3 rows in set (0.00 sec)

mysql> EXPLAIN select * from tt1, tt2, tt3 where tt1.b = tt3.b AND tt1.a = tt2.a order by tt1.b limit 1;
+----+-------------+-------+--------+---------------+---------+---------+-------------+------+---------------------------------+
| id | select_type | table | type   | possible_keys | key     | key_len | ref         | rows | Extra                           |
+----+-------------+-------+--------+---------------+---------+---------+-------------+------+---------------------------------+
|  1 | SIMPLE      | tt1   | ALL    | PRIMARY,i1    | NULL    | NULL    | NULL        |    3 | Using temporary; Using filesort |
|  1 | SIMPLE      | tt3   | ALL    | i1            | NULL    | NULL    | NULL        |    2 | Using where; Using join buffer  |
|  1 | SIMPLE      | tt2   | eq_ref | PRIMARY       | PRIMARY | 4       | test2.tt1.a |    1 |                                 |
+----+-------------+-------+--------+---------------+---------+---------+-------------+------+---------------------------------+
3 rows in set (0.01 sec)

mysql> EXPLAIN select * from tt1, tt2, tt3 where tt1.b = tt3.b AND tt1.a = tt2.a order by tt2.a limit 1;
+----+-------------+-------+--------+---------------+---------+---------+-------------+------+-------------+
| id | select_type | table | type   | possible_keys | key     | key_len | ref         | rows | Extra       |
+----+-------------+-------+--------+---------------+---------+---------+-------------+------+-------------+
|  1 | SIMPLE      | tt2   | index  | PRIMARY       | PRIMARY | 4       | NULL        |    1 |             |
|  1 | SIMPLE      | tt1   | eq_ref | PRIMARY,i1    | PRIMARY | 4       | test2.tt2.a |    1 |             |
|  1 | SIMPLE      | tt3   | ref    | i1            | i1      | 5       | test2.tt1.b |    1 | Using where |
+----+-------------+-------+--------+---------------+---------+---------+-------------+------+-------------+
3 rows in set (0.00 sec)

Plan with MyISAM tables above is correct.

Hello, I wonder if this optimization was ever attacked. I have a very big problem with dynamic queries generated by my application, where the optimizer should choose the index on columns of the order by, but it won't.

I've created a bug on Percona, before I saw this one: https://bugs.launchpad.net/percona-server/+bug/1131426

Can someone give us more information on the optimization? Using straight join is no good since sometimes the filters are good. It seems the optimizer is not doing a good job at estimating how many rows the joins will bring, and comparing it with an estimate of doing the scan using the order by index.

Also affect 5.5.35 and 5.6.15