Bug #118960 Sort optimization fails as primary key info in secondary index is not considered after hint-enforced secondary index
Submitted: 9 Sep 2:57 Modified: 9 Sep 7:11
Reporter: Xingyu Yang (OCA) Email Updates:
Status: Verified Impact on me:
None 
Category:MySQL Server: Optimizer Severity:S5 (Performance)
Version:9.2, 8.0, 8.4 OS:Any
Assigned to: CPU Architecture:Any

[9 Sep 2:57] Xingyu Yang 
Description:
A query using a secondary index for sorting does not require a sort operator, but after specifying that secondary index with a hint, a sort operator is needed instead:

mysql> EXPLAIN FORMAT=tree SELECT f1, pk_1, pk_2 FROM t1 WHERE pk_1 = 3 AND f1 = '2000-01-03' ORDER BY pk_2 DESC LIMIT 5;
| -> Limit: 5 row(s)  (cost=0.45 rows=2)
    -> Covering index lookup on t1 using k1 (f1 = TIMESTAMP'2000-01-03 00:00:00', pk_1 = 3) (reverse)  (cost=0.45 rows=2)
 |

mysql> EXPLAIN FORMAT=tree SELECT /*+ INDEX(`t1`@`select#1` `k1`)  */ f1, pk_1, pk_2 FROM t1 WHERE pk_1 = 3 AND f1
 = '2000-01-03' ORDER BY pk_2 DESC LIMIT 5;
| -> Limit: 5 row(s)  (cost=0.45 rows=2)
    -> Sort: t1.pk_2 DESC, limit input to 5 row(s) per chunk  (cost=0.45 rows=2)
        -> Covering index lookup on t1 using k1 (f1 = TIMESTAMP'2000-01-03 00:00:00', pk_1 = 3)  (cost=0.45 rows=2)
 |

How to repeat:
CREATE TABLE t1
(
 pk_1 INT,
 pk_2 INT,
 f1 DATETIME,
 f2 INT,
 PRIMARY KEY(pk_1, pk_2),
 KEY k1(f1),
 KEY k2(f2)
) ENGINE = InnoDB;

INSERT INTO t1 VALUES
(1, 1, '2000-01-01', 1), (1, 2, '2000-01-02', 2), (1, 3, '2000-01-03', 3), (1, 4, '2000-01-04', 4), (1, 5, '2000-01-05', 5),
(2, 1, '2000-01-01', 6), (2, 2, '2000-01-02', 7), (2, 3, '2000-01-03', 8), (2, 4, '2000-01-04', 9), (2, 5, '2000-01-05', 10),
(3, 1, '2000-01-01', 11), (3, 2, '2000-01-02', 12), (3, 3, '2000-01-03', 13), (3, 4, '2000-01-04', 14), (3, 5, '2000-01-05', 15),
(4, 1, '2000-01-01', 16), (4, 2, '2000-01-02', 17), (4, 3, '2000-01-03', 18), (4, 4, '2000-01-04', 19), (4, 5, '2000-01-05', 20),
(5, 1, '2000-01-01', 21), (5, 2, '2000-01-02', 22), (5, 3, '2000-01-03', 23), (5, 4, '2000-01-04', 24), (5, 5, '2000-01-05', 25),
(6, 1, '2000-01-06', 26), (6, 2, '2000-01-06', 27), (6, 3, '2000-01-03', 28), (6, 4, '2000-01-06', 29), (6, 5, '2000-01-06', 30),
(7, 1, '2000-01-06', 31), (7, 2, '2000-01-06', 32), (7, 3, '2000-01-03', 33), (7, 4, '2000-01-06', 34), (7, 5, '2000-01-06', 35),
(8, 1, '2000-01-06', 36), (8, 2, '2000-01-06', 37), (8, 3, '2000-01-03', 38), (8, 4, '2000-01-06', 39), (8, 5, '2000-01-06', 40),
(9, 1, '2000-01-06', 41), (9, 2, '2000-01-06', 42), (9, 3, '2000-01-03', 43), (9, 4, '2000-01-06', 44), (9, 5, '2000-01-06', 45);

INSERT INTO t1 VALUES
(11, 1, '2000-01-01', 1), (11, 2, '2000-01-02', 2), (11, 3, '2000-01-03', 3), (11, 4, '2000-01-04', 4), (11, 5, '2000-01-05', 5),
(12, 1, '2000-01-01', 6), (12, 2, '2000-01-02', 7), (12, 3, '2000-01-03', 8), (12, 4, '2000-01-04', 9), (12, 5, '2000-01-05', 10),
(13, 1, '2000-01-01', 11), (13, 2, '2000-01-02', 12), (13, 3, '2000-01-03', 13), (13, 4, '2000-01-04', 14), (13, 5, '2000-01-05', 15),
(14, 1, '2000-01-01', 16), (14, 2, '2000-01-02', 17), (14, 3, '2000-01-03', 18), (14, 4, '2000-01-04', 19), (14, 5, '2000-01-05', 20),
(15, 1, '2000-01-01', 1), (15, 2, '2000-01-02', 2), (15, 3, '2000-01-03', 3), (15, 4, '2000-01-04', 4), (15, 5, '2000-01-05', 5),
(16, 1, '2000-01-06', 6), (16, 2, '2000-01-06', 7), (16, 3, '2000-01-03', 8), (16, 4, '2000-01-06', 9), (16, 5, '2000-01-06', 10),
(17, 1, '2000-01-06', 31), (17, 2, '2000-01-06', 32), (17, 3, '2000-01-03', 33), (17, 4, '2000-01-06', 34), (17, 5, '2000-01-06', 35),
(18, 1, '2000-01-06', 36), (18, 2, '2000-01-06', 37), (18, 3, '2000-01-03', 38), (18, 4, '2000-01-06', 39), (18, 5, '2000-01-06', 40),
(19, 1, '2000-01-06', 1), (19, 2, '2000-01-06', 2), (19, 3, '2000-01-03', 3), (19, 4, '2000-01-06', 4), (19, 5, '2000-01-06', 5);

INSERT INTO t1 VALUES
(21, 1, '2000-01-01', 1), (21, 2, '2000-01-02', 2), (31, 3, '2000-01-03', 3), (41, 4, '2000-01-04', 4), (51, 5, '2000-01-05', 5),
(22, 1, '2000-01-01', 6), (22, 2, '2000-01-02', 7), (32, 3, '2000-01-03', 8), (42, 4, '2000-01-04', 9), (52, 5, '2000-01-05', 10),
(23, 1, '2000-01-01', 11), (23, 2, '2000-01-02', 12), (33, 3, '2000-01-03', 13), (43, 4, '2000-01-04', 14), (53, 5, '2000-01-05', 15),
(24, 1, '2000-01-01', 16), (24, 2, '2000-01-02', 17), (34, 3, '2000-01-03', 18), (44, 4, '2000-01-04', 19), (54, 5, '2000-01-05', 20),
(25, 1, '2000-01-01', 1), (25, 2, '2000-01-02', 2), (35, 3, '2000-01-03', 3), (45, 4, '2000-01-04', 4), (55, 5, '2000-01-05', 5),
(26, 1, '2000-01-06', 6), (26, 2, '2000-01-06', 7), (36, 3, '2000-01-03', 8), (46, 4, '2000-01-06', 9), (56, 5, '2000-01-06', 10),
(27, 1, '2000-01-06', 31), (27, 2, '2000-01-06', 32), (37, 3, '2000-01-03', 33), (47, 4, '2000-01-06', 34), (57, 5, '2000-01-06', 35),
(28, 1, '2000-01-06', 36), (28, 2, '2000-01-06', 37), (38, 3, '2000-01-03', 38), (48, 4, '2000-01-06', 39), (58, 5, '2000-01-06', 40),
(29, 1, '2000-01-06', 1), (29, 2, '2000-01-06', 2), (39, 3, '2000-01-03', 3), (49, 4, '2000-01-06', 4), (59, 5, '2000-01-06', 5);

INSERT INTO t1 SELECT pk_1 + 60, pk_2, f1, f2 FROM t1;
INSERT INTO t1 SELECT pk_1 + 120, pk_2, f1, f2 FROM t1;
INSERT INTO t1 SELECT pk_1 + 240, pk_2, f1, f2 FROM t1;
INSERT INTO t1 SELECT pk_1, pk_2 + 10, f1, f2 FROM t1;

ANALYZE TABLE t1;

EXPLAIN FORMAT=tree SELECT f1, pk_1, pk_2 FROM t1 WHERE pk_1 = 3 AND f1 = '2000-01-03' ORDER BY pk_2 DESC LIMIT 5;
EXPLAIN FORMAT=tree SELECT /*+ INDEX(`t1`@`select#1` `k1`)  */ f1, pk_1, pk_2 FROM t1 WHERE pk_1 = 3 AND f1 = '2000-01-03' ORDER BY pk_2 DESC LIMIT 5;

Suggested fix:
If a secondary index is specified using a hint, the primary key index will not participate in optimization. This causes the primary key part of the secondary index to be overlooked when determining whether the secondary index can be used for sorting.

diff --git a/sql/sql_optimizer.cc b/sql/sql_optimizer.cc
index f4fe4d96e58..cf02bb1e27d 100644
--- a/sql/sql_optimizer.cc
+++ b/sql/sql_optimizer.cc
@@ -7819,14 +7819,23 @@ bool add_key_fields(THD *thd, JOIN *join, Key_field **key_fields,
    1 - Out of memory.
 */
 
-static bool add_key_part(Key_use_array *keyuse_array, Key_field *key_field) {
+static bool add_key_part(Key_use_array *keyuse_array, Key_field *key_field,
+                         Key_use_array *primary_keyuse_array = nullptr) {
   if (key_field->eq_func && !(key_field->optimize & KEY_OPTIMIZE_EXISTS)) {
     const Field *const field = key_field->item_field->field;
     Table_ref *const tl = key_field->item_field->m_table_ref;
     TABLE *const table = tl->table;
 
+    Key_use_array *cur_keyuse_array = keyuse_array;
     for (uint key = 0; key < table->s->keys; key++) {
-      if (!(table->keys_in_use_for_query.is_set(key))) continue;
+      cur_keyuse_array = keyuse_array;
+      if (!(table->keys_in_use_for_query.is_set(key))) {
+        if (key == table->s->primary_key && primary_keyuse_array) {
+          cur_keyuse_array = primary_keyuse_array;
+        } else {
+          continue;
+        }
+      }
       if (table->key_info[key].flags & (HA_FULLTEXT | HA_SPATIAL))
         continue;  // ToDo: ft-keys in non-ft queries.   SerG
 
@@ -7840,7 +7849,7 @@ static bool add_key_part(Key_use_array *keyuse_array, Key_field *key_field) {
                                ~(ha_rows)0,  // will be set in optimize_keyuse
                                key_field->null_rejecting, key_field->cond_guard,
                                key_field->sj_pred_no);
-          if (keyuse_array->push_back(keyuse))
+          if (cur_keyuse_array->push_back(keyuse))
             return true; /* purecov: inspected */
         }
       }
@@ -8430,9 +8439,27 @@ static bool update_ref_and_keys(THD *thd, Key_use_array *keyuse,
   if (query_block->materialized_derived_table_count) {
     if (join->generate_derived_keys()) return true;
   }
+
+  // If a secondary index is specified using a hint, the primary key index will
+  // not participate in optimization. This causes the primary key part of the
+  // secondary index to be overlooked when determining whether the secondary
+  // index can be used for sorting, see test_if_order_by_key().
+  Key_use_array primary_keyuses(thd->mem_root);
   /* fill keyuse with found key parts */
   for (; field != end; field++) {
-    if (add_key_part(keyuse, field)) return true;
+    if (add_key_part(keyuse, field, &primary_keyuses)) return true;
+  }
+
+  // const_key_parts could be used in test_if_order_by_key() even if the primary
+  // index is not used. This is because const_key_parts is used to determine
+  // if a key can be used for sorting, and this information is needed even if
+  // the primary index is not used.
+  for (auto use = primary_keyuses.begin(); use != primary_keyuses.end();
+       ++use) {
+    if (use->val->const_for_execution() &&
+        use->optimize != KEY_OPTIMIZE_REF_OR_NULL) {
+      use->table_ref->table->const_key_parts[use->key] |= use->keypart_map;
+    }
   }
 
   if (query_block->ftfunc_list->elements) {
[9 Sep 2:58] Xingyu Yang 
Fix based on version 9.2.0

(*) I confirm the code being submitted is offered under the terms of the OCA, and that I am authorized to contribute it.

Contribution: 0001-primary-key.patch (application/octet-stream, text), 3.40 KiB.
[9 Sep 4:22] Chaithra Marsur Gopala Reddy 
Thank you for the bug report and test case. Verified as described. And thank you for the contribution.