MySQL Bugs: #54808: Optimizer use REF joins where it should use EQ

Bug #54808	Optimizer use REF joins where it should use EQ_REF
Submitted:	25 Jun 2010 13:42	Modified:	3 Dec 2013 12:47
Reporter:	Ole John Aske	Email Updates:
Status:	Closed	Impact on me:	None
Category:	MySQL Server: Optimizer	Severity:	S3 (Non-critical)
Version:	5.1.47, 5.5.6-m3	OS:	Any
Assigned to:		CPU Architecture:	Any

Description:
If there are multiple (unique) indexes available, which more or less match the join condition, the optimizer may fail to select the proper index which may offer an EQ_REF join. 

Instead it looks like it pick the first index it finds which may only partially match the join condition. This has the effect that a less optimal REF jointype is used instead of the more optimal EQ_REF.

How to repeat:
drop table t3;
create table t3 (a3 int not null, b3 int not null, c3 int not null, d3 int not null,
 primary key(a3)) engine = myisam;
create unique index ix1 on t3(b3,c3);
create unique index ix2 on t3(b3,d3);

insert into t3 values (0x1f, 0x2f, 1, 0x1f);
insert into t3 values (0x2f, 0x3f, 2, 0x2f);
insert into t3 values (0x3f, 0x1f, 3, 0x3f);

explain
select * 
  from t3 as X JOIN t3 as Y using(b3,d3);

+----+-------------+-------+------+---------------+------+---------+-----------------+------+-------------+
| id | select_type | table | type | possible_keys | key  | key_len | ref             | rows | Extra       |
+----+-------------+-------+------+---------------+------+---------+-----------------+------+-------------+
|  1 | SIMPLE      | X     | ALL  | ix1,ix2       | NULL | NULL    | NULL            |    3 |             |
|  1 | SIMPLE      | Y     | ref  | ix1,ix2       | ix1  | 4       | spj_myisam.X.b3 |    1 | Using where |
+----+-------------+-------+------+---------------+------+---------+-----------------+------+-------------+
2 rows in set (0.01 sec)

Optimizer consider both index ix1 and ix2 when joining table Y. Instead of using 
ix2(b3,d3) which completely match the join condition, it instead select ix1(b3,c3) which is only a partial match. This result in a 'ref' join where it could have used an 'eq_ref'

If we then drop the ix1 index we get the expected join plan:

mysql> drop index ix1 on t3;
Query OK, 3 rows affected (0.07 sec)
Records: 3  Duplicates: 0  Warnings: 0

mysql> explain
    -> select *
    ->   from t3 as X JOIN t3 as Y using(b3,d3);
+----+-------------+-------+--------+---------------+------+---------+---------------------------------+------+-------+
| id | select_type | table | type   | possible_keys | key  | key_len | ref                             | rows | Extra |
+----+-------------+-------+--------+---------------+------+---------+---------------------------------+------+-------+
|  1 | SIMPLE      | X     | ALL    | ix2           | NULL | NULL    | NULL                            |    3 |       |
|  1 | SIMPLE      | Y     | eq_ref | ix2           | ix2  | 8       | spj_myisam.X.b3,spj_myisam.X.d3 |    1 |       |
+----+-------------+-------+--------+---------------+------+---------+---------------------------------+------+-------+
2 rows in set (0.00 sec)

If we create ix2 before ix1 the optimizer will also choose ix2. It looks like the optimizer does a 'first fit' instead of 'best fit' when choosing indexes for  join exeution :-o

Verified just as described, also - with current mysql_trunk from bzr:

valeriy-kravchuks-macbook-pro:trunk 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 1
Server version: 5.5.6-m3-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> drop table t3;
ERROR 1051 (42S02): Unknown table 't3'
mysql> create table t3 (a3 int not null, b3 int not null, c3 int not null, d3 int not null,
    ->  primary key(a3)) engine = myisam;
Query OK, 0 rows affected (0.06 sec)

mysql> create unique index ix1 on t3(b3,c3);
Query OK, 0 rows affected (0.24 sec)
Records: 0  Duplicates: 0  Warnings: 0

mysql> create unique index ix2 on t3(b3,d3);
Query OK, 0 rows affected (0.11 sec)
Records: 0  Duplicates: 0  Warnings: 0

mysql> 
mysql> insert into t3 values (0x1f, 0x2f, 1, 0x1f);
Query OK, 1 row affected (0.00 sec)

mysql> insert into t3 values (0x2f, 0x3f, 2, 0x2f);
Query OK, 1 row affected (0.00 sec)

mysql> insert into t3 values (0x3f, 0x1f, 3, 0x3f);
Query OK, 1 row affected (0.00 sec)

mysql> 
mysql> explain
    -> select * 
    ->   from t3 as X JOIN t3 as Y using(b3,d3);
+----+-------------+-------+------+---------------+------+---------+-----------+------+-------------+
| id | select_type | table | type | possible_keys | key  | key_len | ref       | rows | Extra       |
+----+-------------+-------+------+---------------+------+---------+-----------+------+-------------+
|  1 | SIMPLE      | X     | ALL  | ix1,ix2       | NULL | NULL    | NULL      |    3 |             |
|  1 | SIMPLE      | Y     | ref  | ix1,ix2       | ix1  | 4       | test.X.b3 |    1 | Using where |
+----+-------------+-------+------+---------------+------+---------+-----------+------+-------------+
2 rows in set (0.05 sec)

mysql> drop index ix1 on t3;
Query OK, 3 rows affected (0.06 sec)
Records: 3  Duplicates: 0  Warnings: 0

mysql> explain select *    from t3 as X JOIN t3 as Y using(b3,d3);
+----+-------------+-------+--------+---------------+------+---------+---------------------+------+-------+
| id | select_type | table | type   | possible_keys | key  | key_len | ref                 | rows | Extra |
+----+-------------+-------+--------+---------------+------+---------+---------------------+------+-------+
|  1 | SIMPLE      | X     | ALL    | ix2           | NULL | NULL    | NULL                |    3 |       |
|  1 | SIMPLE      | Y     | eq_ref | ix2           | ix2  | 8       | test.X.b3,test.X.d3 |    1 |       |
+----+-------------+-------+--------+---------------+------+---------+---------------------+------+-------+
2 rows in set (0.01 sec)

mysql> create unique index ix1 on t3(b3,c3);
Query OK, 3 rows affected (0.40 sec)
Records: 3  Duplicates: 0  Warnings: 0

mysql> explain select *    from t3 as X JOIN t3 as Y using(b3,d3);
+----+-------------+-------+--------+---------------+------+---------+---------------------+------+-------+
| id | select_type | table | type   | possible_keys | key  | key_len | ref                 | rows | Extra |
+----+-------------+-------+--------+---------------+------+---------+---------------------+------+-------+
|  1 | SIMPLE      | X     | ALL    | ix2,ix1       | NULL | NULL    | NULL                |    3 |       |
|  1 | SIMPLE      | Y     | eq_ref | ix2,ix1       | ix2  | 8       | test.X.b3,test.X.d3 |    1 |       |
+----+-------------+-------+--------+---------------+------+---------+---------------------+------+-------+
2 rows in set (0.01 sec)

P.S. I remember some older bug reports that proved index creation order matters :(

triage: setting to SRMRTBD should be considered with new optimizer features

Noted in 5.7.4 changelog.

The optimizer could choose ref access over eq_ref access when cost of
a nonunique access was evaluated before cost of a unique index.