MySQL Bugs: #84024: Optimizer thinks clustered primary key is not covering

Bug #84024	Optimizer thinks clustered primary key is not covering
Submitted:	1 Dec 2016 2:40	Modified:	2 Dec 2016 9:07
Reporter:	Manuel Ung	Email Updates:
Status:	Verified	Impact on me:	None
Category:	MySQL Server: Optimizer	Severity:	S3 (Non-critical)
Version:	5.7.16, 5.6.34	OS:	Any
Assigned to:		CPU Architecture:	Any

Description:
The optimizer uses covering_keys as a heuristic to check whether to do a table scan or do a ref access in sql_planner.cc. This doesn't work well for clustered primary keys, because it's not in covering_keys, but the cost should be about the same.

How to repeat:
create table t1 (i int primary key, j int, key (j)) engine=innodb;
create table t2 (i int primary key, j int) engine=innodb;
create table t3 (i int, j int, primary key (i)) engine=innodb;
insert into t1 values (1, 1);
insert into t1 select i + 1, j + 1 from t1;
insert into t1 select i + 2, j + 2 from t1;
insert into t1 select i + 4, j + 4 from t1;
insert into t1 select i + 8, j + 8 from t1;
insert into t1 select i + 16, j + 16 from t1;
insert into t1 select i + 32, j + 32 from t1;
insert into t1 select i + 64, j + 64 from t1;
insert into t1 select i + 128, j + 128 from t1;
insert into t1 select i + 256, j + 256 from t1;
insert into t1 select i + 512, j + 512 from t1;
insert into t1 select i + 1024, j + 1024 from t1;
insert into t1 select i + 2048, j + 2048 from t1;
insert into t2 select * from t1;
insert into t3 values (1, 1);
analyze table t1, t2, t3;
explain select t3.j from (t1 left join t2 on t1.i = t2.i) left join t3 on t1.i = t3.i where t1.j > 0 and t1.j < 5000;

Gives you this plan:
id      select_type     table   type    possible_keys   key     key_len ref     rows    Extra
1       SIMPLE  t1      range   j       j       5       NULL    4094    Using where; Using index
1       SIMPLE  t2      eq_ref  PRIMARY PRIMARY 4       test.t1.i       1       Using index
1       SIMPLE  t3      ALL     PRIMARY NULL    NULL    NULL    1       Using where; Using join buffer (Block Nested Loop)

Note that t3 is not using primary key.

Suggested fix:
In sql/sql_planner.cc, do an extra check for s->table->file->primary_key_is_clustered() when evaluating the heuristic "covering_index_better_than_full_scan".

Hello Manuel,

Thank you for the report and test case.
Verified as described with 5.7.16 build.

Thanks,
Umesh

AFAICT, for the given query, the reason table scan is preferred over index look-up is that the table contains only one row.  When there is only a few rows in the table, table scan with join-buffering is probably cheaper than primary index look-ups.  If I increase the number of rows, PK look-ups will be used:

mysql> insert into t3 select i+1, j from t3;
Query OK, 1 row affected (0,00 sec)
Records: 1  Duplicates: 0  Warnings: 0

mysql> insert into t3 select i+2, j from t3;
Query OK, 2 rows affected (0,00 sec)
Records: 2  Duplicates: 0  Warnings: 0

mysql> insert into t3 select i+4, j from t3;
Query OK, 4 rows affected (0,00 sec)
Records: 4  Duplicates: 0  Warnings: 0

mysql> explain select t3.j from (t1 left join t2 on t1.i = t2.i) left join t3 on t1.i = t3.i where t1.j > 0 and t1.j < 5000;
+----+-------------+-------+------------+--------+---------------+---------+---------+---------------+------+----------+--------------------------+
| id | select_type | table | partitions | type   | possible_keys | key     | key_len | ref           | rows | filtered | Extra                    |
+----+-------------+-------+------------+--------+---------------+---------+---------+---------------+------+----------+--------------------------+
|  1 | SIMPLE      | t1    | NULL       | index  | j             | j       | 5       | NULL          | 4096 |   100.00 | Using where; Using index |
|  1 | SIMPLE      | t2    | NULL       | eq_ref | PRIMARY       | PRIMARY | 4       | bug84024.t1.i |    1 |   100.00 | Using index              |
|  1 | SIMPLE      | t3    | NULL       | eq_ref | PRIMARY       | PRIMARY | 4       | bug84024.t1.i |    1 |   100.00 | NULL                     |
+----+-------------+-------+------------+--------+---------------+---------+---------+---------------+------+----------+--------------------------+
3 rows in set, 1 warning (0,00 sec)

Maybe it makes sense? Although consider that:

1. You'll get the more "expensive" plan if you use a covered key instead, so that's kind of strange.
2. In practice, creating the join buffer might be more expensive than rereading the low cardinality t3 table (especially if it's empty).

Hi Manuel,

I can agree that the cost model for join buffering is not perfect.  If so, I think we should improve this model, not rely on heuristics about covering indexes versus table scan.

Improving the cost model would be great if possible.

Changing the heuristic just seemed like an easier/safe workaround since it takes effect on covering keys already.