MySQL Bugs: #107292: Index isn't used for order if some primary key columns specified in index

Bug #107292	Index isn't used for order if some primary key columns specified in index
Submitted:	14 May 2022 0:37	Modified:	14 May 2022 13:16
Reporter:	Jayden Navarro	Email Updates:
Status:	Verified	Impact on me:	None
Category:	MySQL Server: Optimizer	Severity:	S5 (Performance)
Version:	8.0.21, 5.7, 8.0	OS:	Any
Assigned to:		CPU Architecture:	Any

Description:
If a secondary index includes a column in the middle of it that is part of a composite primary key, queries that ORDER BY the primary key columns will not use the secondary index for the order and will use filesort. Since secondary indexes can logically be thought of as containing the primary key appended to the end of them, it should be possible for the order to be served by the secondary index without requiring a filesort.

How to repeat:
CREATE TABLE testTable (
  pk1 INT,
  pk2 INT,
  c1 INT,
  c2 INT,
  PRIMARY KEY (pk1, pk2),
  KEY IDX_c1_pk1_c2 (c1, pk1, c2)
) ENGINE=InnoDB;

EXPLAIN SELECT c1
FROM testTable
USE INDEX (IDX_c1_pk1_c2)
WHERE c1 = 0 AND pk1 = 0
ORDER BY c2, pk1, pk2;

******************** 1. row *********************
           id: 1
  select_type: SIMPLE
        table: testTable
   partitions: 
         type: ref
possible_keys: IDX_c1_pk1_c2
          key: IDX_c1_pk1_c2
      key_len: 9
          ref: const,const
         rows: 1
     filtered: 100.00
        Extra: Using index; Using filesort
1 rows in set

-------------------------------------------

The above query should not require a filesort, as the index is logically (c1, pk1, c2, pk1, pk2) which provides the order required by the query (since all secondary indexes include the clustered index columns appended to them). Maybe the redundant pk1 isn't actually included and the logical index is (c1, pk2, c2, pk2), but the same result is seen even if the query is changed to `ORDER BY c2, pk2`.

Suggested fix:
Change the optimizer to recognize that the secondary index provides the order required by this query.

Hello Jayden Navarro,

Thank you for the report and feedback.

regards,
Umesh

1. The optimizer does not build the bitmaps of priamry key parts(set TABLE::const_key_parts bits if key fields are equal to constants in the WHERE condition), when force to use the key `IDX_c1_pk1_c2`.

   JOIN::optimize->make_join_plan->update_ref_and_keys->add_key_part

2. It is failed to sort order by using the key `IDX_c1_pk1_c2`, because the optimizer cann't take advantage of the feature that the storage engine has the primary key as a suffix to the secondary keys(can not skip any primary key parts that are constants in the WHERE clause).

   JOIN::optimize->test_skip_sort->test_if_skip_sort_order->test_if_order_by_key