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

[1 Dec 2016 2:40] Manuel Ung
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".
[1 Dec 2016 4:25] Umesh Shastry
Hello Manuel,

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

Thanks,
Umesh
[1 Dec 2016 8:46] Øystein Grøvlen
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)
[1 Dec 2016 22:22] Manuel Ung
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).
[2 Dec 2016 8:50] Øystein Grøvlen
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.
[2 Dec 2016 9:07] Manuel Ung
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.