MySQL Bugs: #117273: some sort is not optimized away by index, if index have part of primary key

Bug #117273	some sort is not optimized away by index, if index have part of primary key
Submitted:	23 Jan 4:13	Modified:	24 Jan 5:10
Reporter:	jia liu	Email Updates:
Status:	Verified	Impact on me:	None
Category:	MySQL Server: Optimizer	Severity:	S5 (Performance)
Version:	8.0.35	OS:	Any
Assigned to:		CPU Architecture:	Any
Tags:	sort index-extensions index

Description:
https://dev.mysql.com/doc/refman/8.0/en/index-extensions.html

as the document says, an secondary  index will contain primary key, and innodb will know and use it. but, if an index contains part of the primary key, it seems not recognized correctly.

How to repeat:
CREATE TABLE `ordertest` (
  `pk1` int NOT NULL,
  `pk2` int NOT NULL,
  `col3` int DEFAULT NULL,
  `col4` int DEFAULT NULL,
  PRIMARY KEY (`pk1`,`pk2`),
  KEY `col3` (`col3`,`pk1`,`col4`),
  KEY `col3_2` (`col3`,`pk1`,`pk2`,`col4`),
  KEY `col3_3` (`col3`,`pk2`,`pk1`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4 COLLATE=utf8mb4_0900_ai_ci;

insert into ordertest values (1,2,3,4);

explain select * from ordertest order by col3,pk1,col4;
+----+-------------+-----------+------------+-------+---------------+------+---------+------+------+----------+-------------+
| id | select_type | table     | partitions | type  | possible_keys | key  | key_len | ref  | rows | filtered | Extra       |
+----+-------------+-----------+------------+-------+---------------+------+---------+------+------+----------+-------------+
|  1 | SIMPLE      | ordertest | NULL       | index | NULL          | col3 | 14      | NULL |    1 |   100.00 | Using index |
+----+-------------+-----------+------------+-------+---------------+------+---------+------+------+----------+-------------+

-- sort is optimized away by index, which is correct

explain select * from ordertest order by col3,pk1,col4,pk2;
+----+-------------+-----------+------------+-------+---------------+------+---------+------+------+----------+-----------------------------+
| id | select_type | table     | partitions | type  | possible_keys | key  | key_len | ref  | rows | filtered | Extra                       |
+----+-------------+-----------+------------+-------+---------------+------+---------+------+------+----------+-----------------------------+
|  1 | SIMPLE      | ordertest | NULL       | index | NULL          | col3 | 14      | NULL |    1 |   100.00 | Using index; Using filesort |
+----+-------------+-----------+------------+-------+---------------+------+---------+------+------+----------+-----------------------------+
explain select * from ordertest order by col3,pk1,col4,pk1,pk2;
+----+-------------+-----------+------------+-------+---------------+------+---------+------+------+----------+-----------------------------+
| id | select_type | table     | partitions | type  | possible_keys | key  | key_len | ref  | rows | filtered | Extra                       |
+----+-------------+-----------+------------+-------+---------------+------+---------+------+------+----------+-----------------------------+
|  1 | SIMPLE      | ordertest | NULL       | index | NULL          | col3 | 14      | NULL |    1 |   100.00 | Using index; Using filesort |
+----+-------------+-----------+------------+-------+---------------+------+---------+------+------+----------+-----------------------------+

-- both of them require an extra sort, which is not match my understanding.

Suggested fix:
I think index col3 stores columns as (col3,pk1,col4,pk2), or I have miss unsterstanding of the make up of sercondary index?

if the secondary index stores as (col3,pk1,col4,pk2) then the second explain's sort is not need.
else if secondary index stores as (col3,pk1,col4,pk1,pk2) then the third explain's sort is not need.

Hi Mr. liu,

Thank you for your bug report.

Your understanding of InnoDB index structure is wrong.

Secondary indices do not contain a primary key, but only a value of the particular primary key entry. Most other databases contain a link to the record position, but InnoDB contains a value of the single  primary key entry.

Not a bug.

> Secondary indices do not contain a primary key, but only a value of the particular primary key entry.

I do not understand what above means.

> CREATE TABLE `ordertest` (
> [...]
>   PRIMARY KEY (`pk1`,`pk2`),
>   KEY `col3` (`col3`,`pk1`,`col4`),
> [...]
>
> I think index col3 stores columns as (col3,pk1,col4,pk2), or I have miss unsterstanding of the make up of sercondary index?

I think jia liu is right here, and...

> explain select * from ordertest order by col3,pk1,col4,pk2;
> +----+-------------+-----------+------------+-------+---------------+------+---------+------+------+----------+-----------------------------+
> | id | select_type | table     | partitions | type  | possible_keys | key  | key_len | ref  | rows | filtered | Extra                       |
> +----+-------------+-----------+------------+-------+---------------+------+---------+------+------+----------+-----------------------------+
> |  1 | SIMPLE      | ordertest | NULL       | index | NULL          | col3 | 14      | NULL |    1 |   100.00 | Using index; Using filesort |
> +----+-------------+-----------+------------+-------+---------------+------+---------+------+------+----------+-----------------------------+

...I was surprised at first that above query would not use the col3 KEY.  I then thought maybe the col3 KEY was not covering for SELECT * and the optimizer would prefer a filesort to PK lookups, and then...

> CREATE TABLE `ordertest` (
>  `pk1` int NOT NULL,
>  `pk2` int NOT NULL,
>  `col3` int DEFAULT NULL,
>  `col4` int DEFAULT NULL,
>  PRIMARY KEY (`pk1`,`pk2`),
> [...]

...I realized the col3 KEY is actually a covering index for the query.  So I would also expect the query to be served from the index, without a filesort.

It would be interesting to see the explain of "select col3,pk1,col4,pk2 from ordertest order by col3,pk1,col4,pk2".  Is it the SELECT * that confuses the optimizer, or is the optimizer actually forgetting that pk2 is appended to the columns of the col3 KEY.

> Not a bug.

So I actually think this is a bug.

Hello jia liu, Jean-François,

Thank you for the report and feedback.

regards,
Umesh