Description:
See the test case.
How to repeat:
Run the following test case under MySQL test suite:
-- source include/have_innodb.inc
create table t1(id int not null primary key, t2_id int not null, n int not null, key(t2_id)) engine=innodb;
create table t2(id int not null primary key, t3_id int not null, n int not null, key(t3_id)) engine=innodb;
create table t3(id int not null primary key, n int not null) engine=innodb;
--disable_query_log
let $n=64;
begin;
while($n)
{
eval insert into t3 values($n,$n);
dec $n;
}
let $n=2000;
while($n)
{
eval insert into t2 values($n,$n % 64,$n);
eval insert into t1 values($n,$n,$n);
dec $n;
}
commit;
--enable_query_log
explain select * from t1,t2,t3 where t1.t2_id = t2.id and t2.t3_id = t3.id order by t1.id limit 20;
explain select * from t1 force key(primary),t2,t3 where t1.t2_id = t2.id and t2.t3_id = t3.id order by t1.id limit 20;
analyze table t2;
explain select * from t1,t2,t3 where t1.t2_id = t2.id and t2.t3_id = t3.id order by t1.id limit 20;
alter table t2 engine=myisam;
explain select * from t1,t2,t3 where t1.t2_id = t2.id and t2.t3_id = t3.id order by t1.id limit 20;
drop table t1,t2,t3;
It produces the following output:
create table t1(id int not null primary key, t2_id int not null, n int not null, key(t2_id)) engine=innodb;
create table t2(id int not null primary key, t3_id int not null, n int not null, key(t3_id)) engine=innodb;
create table t3(id int not null primary key, n int not null) engine=innodb;
explain select * from t1,t2,t3 where t1.t2_id = t2.id and t2.t3_id = t3.id order by t1.id limit 20;
id select_type table type possible_keys key key_len ref rows Extra
1 SIMPLE t3 ALL PRIMARY NULL NULL NULL 64 Using temporary; Using filesort
1 SIMPLE t2 ref PRIMARY,t3_id t3_id 4 test.t3.id 1
1 SIMPLE t1 ref t2_id t2_id 4 test.t2.id 1
explain select * from t1 force key(primary),t2,t3 where t1.t2_id = t2.id and t2.t3_id = t3.id order by t1.id limit 20;
id select_type table type possible_keys key key_len ref rows Extra
1 SIMPLE t1 index NULL PRIMARY 4 NULL 20
1 SIMPLE t2 eq_ref PRIMARY,t3_id PRIMARY 4 test.t1.t2_id 1
1 SIMPLE t3 eq_ref PRIMARY PRIMARY 4 test.t2.t3_id 1
analyze table t2;
Table Op Msg_type Msg_text
test.t2 analyze status OK
explain select * from t1,t2,t3 where t1.t2_id = t2.id and t2.t3_id = t3.id order by t1.id limit 20;
id select_type table type possible_keys key key_len ref rows Extra
1 SIMPLE t3 ALL PRIMARY NULL NULL NULL 64 Using temporary; Using filesort
1 SIMPLE t2 ref PRIMARY,t3_id t3_id 4 test.t3.id 16
1 SIMPLE t1 ref t2_id t2_id 4 test.t2.id 1
alter table t2 engine=myisam;
explain select * from t1,t2,t3 where t1.t2_id = t2.id and t2.t3_id = t3.id order by t1.id limit 20;
id select_type table type possible_keys key key_len ref rows Extra
1 SIMPLE t1 index t2_id PRIMARY 4 NULL 20
1 SIMPLE t2 eq_ref PRIMARY,t3_id PRIMARY 4 test.t1.t2_id 1
1 SIMPLE t3 eq_ref PRIMARY PRIMARY 4 test.t2.t3_id 1
drop table t1,t2,t3;
As you see, the first query chooses to put t3 first, which results in using a temporary table + file sort, which is completely unnecessary as illustrated by the second query. If we insist on using the primary key in t1, t1 is put first in the join order, and we are able to use the primary key to read the records in the requested order.
As you can see from the subsequent queries, analyzing t2 does not fix the problem. However, making it MyISAM does.
Suggested fix:
A workaround is to use FORCE KEY or STRAIGHT_JOIN to prevent the optimizer from choosing the wrong table order. As to the real fix, I have performed a limited investigation in the code, and from what I was able to gather, best_access_path() does not call test_if_skip_sort_order(), and there appears to be no way for it to know that we have a very good LIMIT clause to reduce the total number of records. If there is a way to take that into account and I missed it, it is obviously doing it wrong in this case.
Description: See the test case. How to repeat: Run the following test case under MySQL test suite: -- source include/have_innodb.inc create table t1(id int not null primary key, t2_id int not null, n int not null, key(t2_id)) engine=innodb; create table t2(id int not null primary key, t3_id int not null, n int not null, key(t3_id)) engine=innodb; create table t3(id int not null primary key, n int not null) engine=innodb; --disable_query_log let $n=64; begin; while($n) { eval insert into t3 values($n,$n); dec $n; } let $n=2000; while($n) { eval insert into t2 values($n,$n % 64,$n); eval insert into t1 values($n,$n,$n); dec $n; } commit; --enable_query_log explain select * from t1,t2,t3 where t1.t2_id = t2.id and t2.t3_id = t3.id order by t1.id limit 20; explain select * from t1 force key(primary),t2,t3 where t1.t2_id = t2.id and t2.t3_id = t3.id order by t1.id limit 20; analyze table t2; explain select * from t1,t2,t3 where t1.t2_id = t2.id and t2.t3_id = t3.id order by t1.id limit 20; alter table t2 engine=myisam; explain select * from t1,t2,t3 where t1.t2_id = t2.id and t2.t3_id = t3.id order by t1.id limit 20; drop table t1,t2,t3; It produces the following output: create table t1(id int not null primary key, t2_id int not null, n int not null, key(t2_id)) engine=innodb; create table t2(id int not null primary key, t3_id int not null, n int not null, key(t3_id)) engine=innodb; create table t3(id int not null primary key, n int not null) engine=innodb; explain select * from t1,t2,t3 where t1.t2_id = t2.id and t2.t3_id = t3.id order by t1.id limit 20; id select_type table type possible_keys key key_len ref rows Extra 1 SIMPLE t3 ALL PRIMARY NULL NULL NULL 64 Using temporary; Using filesort 1 SIMPLE t2 ref PRIMARY,t3_id t3_id 4 test.t3.id 1 1 SIMPLE t1 ref t2_id t2_id 4 test.t2.id 1 explain select * from t1 force key(primary),t2,t3 where t1.t2_id = t2.id and t2.t3_id = t3.id order by t1.id limit 20; id select_type table type possible_keys key key_len ref rows Extra 1 SIMPLE t1 index NULL PRIMARY 4 NULL 20 1 SIMPLE t2 eq_ref PRIMARY,t3_id PRIMARY 4 test.t1.t2_id 1 1 SIMPLE t3 eq_ref PRIMARY PRIMARY 4 test.t2.t3_id 1 analyze table t2; Table Op Msg_type Msg_text test.t2 analyze status OK explain select * from t1,t2,t3 where t1.t2_id = t2.id and t2.t3_id = t3.id order by t1.id limit 20; id select_type table type possible_keys key key_len ref rows Extra 1 SIMPLE t3 ALL PRIMARY NULL NULL NULL 64 Using temporary; Using filesort 1 SIMPLE t2 ref PRIMARY,t3_id t3_id 4 test.t3.id 16 1 SIMPLE t1 ref t2_id t2_id 4 test.t2.id 1 alter table t2 engine=myisam; explain select * from t1,t2,t3 where t1.t2_id = t2.id and t2.t3_id = t3.id order by t1.id limit 20; id select_type table type possible_keys key key_len ref rows Extra 1 SIMPLE t1 index t2_id PRIMARY 4 NULL 20 1 SIMPLE t2 eq_ref PRIMARY,t3_id PRIMARY 4 test.t1.t2_id 1 1 SIMPLE t3 eq_ref PRIMARY PRIMARY 4 test.t2.t3_id 1 drop table t1,t2,t3; As you see, the first query chooses to put t3 first, which results in using a temporary table + file sort, which is completely unnecessary as illustrated by the second query. If we insist on using the primary key in t1, t1 is put first in the join order, and we are able to use the primary key to read the records in the requested order. As you can see from the subsequent queries, analyzing t2 does not fix the problem. However, making it MyISAM does. Suggested fix: A workaround is to use FORCE KEY or STRAIGHT_JOIN to prevent the optimizer from choosing the wrong table order. As to the real fix, I have performed a limited investigation in the code, and from what I was able to gather, best_access_path() does not call test_if_skip_sort_order(), and there appears to be no way for it to know that we have a very good LIMIT clause to reduce the total number of records. If there is a way to take that into account and I missed it, it is obviously doing it wrong in this case.