Bug #107626 Low limit heuristic used unnecessarily with descending scans
Submitted: 21 Jun 2022 19:19 Modified: 24 Aug 2023 21:48
Reporter: Manuel Ung Email Updates:
Status: Closed Impact on me:
None 
Category:MySQL Server: Optimizer Severity:S3 (Non-critical)
Version:8.0.29 OS:Any
Assigned to: CPU Architecture:Any

[21 Jun 2022 19:19] Manuel Ung 
Description:
The low limit heuristic is only useful if the current best plan does not provide index order. The code attempts to account for this by calling test_if_order_by_key, and skipping the heuristic if the plan already provides correct order. However, it does not work well for ORDER BY DESC.

The problem is that if we detect a a descending scan, we will call `is_reverse_sorted_range ` on the range plan to see if it provides reverse order. However, at this point in optimization, range plans are always forwards sorted because `test_quick_select` always returns forwards sorted range plans, and reversing them is one of the final steps of optimization.

How to repeat:
Check plan/trace to confirm that low limit heuristic is used.

Clearly, key(j, i) is a better key since it fits the query shape exactly. 

create table t (i int primary key,  j int, key(j, i)) engine=innodb;
insert into t (WITH RECURSIVE a (i) AS ( SELECT 0  union all SELECT i+1  from a where i < 9  ), b (i) AS  (SELECT x.i + y.i * 10 + z.i * 100 + w.i * 1000 +  v.i * 10000 FROM a x, a y, a z, a w, a v) SELECT b.i, 1 from b order by i);
analyze table t;
set optimizer_trace='enabled=on';
explain select * from t where j = 1 and i <= 10000  order by i desc limit 1;
select * from information_schema.optimizer_trace;

Suggested fix:
Instead of checking is_reverse_sorted_range after running test_if_order_by_key in the make_join_query_block function, use reverse_sort_possible instead.
[22 Jun 2022 5:48] MySQL Verification Team 
Hello Manuel Ung,

Thank you for the report and feedback.

regards,
Umesh
[22 Jun 2022 5:49] MySQL Verification Team 
- 8.0.29

bin/mysql -uroot -S /tmp/mysql.sock
Welcome to the MySQL monitor.  Commands end with ; or \g.
Your MySQL connection id is 7
Server version: 8.0.29 MySQL Community Server - GPL

Copyright (c) 2000, 2022, Oracle and/or its affiliates.

Oracle is a registered trademark of Oracle Corporation and/or its
affiliates. Other names may be trademarks of their respective
owners.

Type 'help;' or '\h' for help. Type '\c' to clear the current input statement.

mysql> use test
Reading table information for completion of table and column names
You can turn off this feature to get a quicker startup with -A

Database changed
mysql>
mysql> create table t (i int primary key,  j int, key(j, i)) engine=innodb;
Query OK, 0 rows affected (0.02 sec)

mysql> insert into t (WITH RECURSIVE a (i) AS ( SELECT 0  union all SELECT i+1  from a where i < 9  ), b (i) AS  (SELECT x.i + y.i * 10 + z.i * 100 + w.i * 1000 +  v.i * 10000 FROM a x, a y, a z, a w, a v) SELECT b.i, 1 from b order by i);
Query OK, 100000 rows affected (0.68 sec)
Records: 100000  Duplicates: 0  Warnings: 0

mysql> analyze table t;
+--------+---------+----------+----------+
| Table  | Op      | Msg_type | Msg_text |
+--------+---------+----------+----------+
| test.t | analyze | status   | OK       |
+--------+---------+----------+----------+
1 row in set (0.01 sec)

mysql> set optimizer_trace='enabled=on';
Query OK, 0 rows affected (0.00 sec)

mysql> explain select * from t where j = 1 and i <= 10000  order by i desc limit 1;
+----+-------------+-------+------------+-------+---------------+---------+---------+------+-------+----------+----------------------------------+
| id | select_type | table | partitions | type  | possible_keys | key     | key_len | ref  | rows  | filtered | Extra                            |
+----+-------------+-------+------------+-------+---------------+---------+---------+------+-------+----------+----------------------------------+
|  1 | SIMPLE      | t     | NULL       | range | PRIMARY,j     | PRIMARY | 4       | NULL | 18960 |    10.00 | Using where; Backward index scan |
+----+-------------+-------+------------+-------+---------------+---------+---------+------+-------+----------+----------------------------------+
1 row in set, 1 warning (0.00 sec)
[22 Jun 2022 5:50] MySQL Verification Team 
-
mysql> select * from information_schema.optimizer_trace\G
*************************** 1. row ***************************
                            QUERY: explain select * from t where j = 1 and i <= 10000  order by i desc limit 1
                            TRACE: {
  "steps": [
    {
      "join_preparation": {
        "select#": 1,
        "steps": [
          {
            "expanded_query": "/* select#1 */ select `t`.`i` AS `i`,`t`.`j` AS `j` from `t` where ((`t`.`j` = 1) and (`t`.`i` <= 10000)) order by `t`.`i` desc limit 1"
          }
        ]
      }
    },
    {
      "join_optimization": {
        "select#": 1,
        "steps": [
          {
            "condition_processing": {
              "condition": "WHERE",
              "original_condition": "((`t`.`j` = 1) and (`t`.`i` <= 10000))",
              "steps": [
                {
                  "transformation": "equality_propagation",
                  "resulting_condition": "((`t`.`i` <= 10000) and multiple equal(1, `t`.`j`))"
                },
                {
                  "transformation": "constant_propagation",
                  "resulting_condition": "((`t`.`i` <= 10000) and multiple equal(1, `t`.`j`))"
                },
                {
                  "transformation": "trivial_condition_removal",
                  "resulting_condition": "((`t`.`i` <= 10000) and multiple equal(1, `t`.`j`))"
                }
              ]
            }
          },
          {
            "substitute_generated_columns": {
            }
          },
          {
            "table_dependencies": [
              {
                "table": "`t`",
                "row_may_be_null": false,
                "map_bit": 0,
                "depends_on_map_bits": [
                ]
              }
            ]
          },
          {
            "ref_optimizer_key_uses": [
              {
                "table": "`t`",
                "field": "j",
                "equals": "1",
                "null_rejecting": true
              }
            ]
          },
          {
            "rows_estimation": [
              {
                "table": "`t`",
                "range_analysis": {
                  "table_scan": {
                    "rows": 100464,
                    "cost": 10104.8
                  },
                  "potential_range_indexes": [
                    {
                      "index": "PRIMARY",
                      "usable": true,
                      "key_parts": [
                        "i"
                      ]
                    },
                    {
                      "index": "j",
                      "usable": true,
                      "key_parts": [
                        "j",
                        "i"
                      ]
                    }
                  ],
                  "best_covering_index_scan": {
                    "index": "j",
                    "cost": 10086.5,
                    "chosen": true
                  },
                  "setup_range_conditions": [
                  ],
                  "group_index_range": {
                    "chosen": false,
                    "cause": "not_group_by_or_distinct"
                  },
                  "skip_scan_range": {
                    "potential_skip_scan_indexes": [
                      {
                        "index": "PRIMARY",
                        "usable": false,
                        "cause": "query_references_nonkey_column"
                      },
                      {
                        "index": "j",
                        "usable": false,
                        "cause": "prefix_not_const_equality"
                      }
                    ]
                  },
[22 Jun 2022 5:50] MySQL Verification Team 
"analyzing_range_alternatives": {
                    "range_scan_alternatives": [
                      {
                        "index": "PRIMARY",
                        "ranges": [
                          "i <= 10000"
                        ],
                        "index_dives_for_eq_ranges": true,
                        "rowid_ordered": true,
                        "using_mrr": false,
                        "index_only": false,
                        "in_memory": 1,
                        "rows": 18960,
                        "cost": 1901.09,
                        "chosen": true
                      },
                      {
                        "index": "j",
                        "ranges": [
                          "j = 1 AND i <= 10000"
                        ],
                        "index_dives_for_eq_ranges": true,
                        "rowid_ordered": false,
                        "using_mrr": false,
                        "index_only": true,
                        "in_memory": 1,
                        "rows": 10001,
                        "cost": 1004.32,
                        "chosen": true
                      }
                    ],
                    "analyzing_roworder_intersect": {
                      "usable": false,
                      "cause": "too_few_roworder_scans"
                    }
                  },
                  "chosen_range_access_summary": {
                    "range_access_plan": {
                      "type": "range_scan",
                      "index": "j",
                      "rows": 10001,
                      "ranges": [
                        "j = 1 AND i <= 10000"
                      ]
                    },
                    "rows_for_plan": 10001,
                    "cost_for_plan": 1004.32,
                    "chosen": true
                  }
                }
              }
            ]
          },
          {
            "considered_execution_plans": [
              {
                "plan_prefix": [
                ],
                "table": "`t`",
                "best_access_path": {
                  "considered_access_paths": [
                    {
                      "access_type": "ref",
                      "index": "j",
                      "chosen": false,
                      "cause": "range_uses_more_keyparts"
                    },
                    {
                      "rows_to_scan": 10001,
                      "filtering_effect": [
                      ],
                      "final_filtering_effect": 1,
                      "access_type": "range",
                      "range_details": {
                        "used_index": "j"
                      },
                      "resulting_rows": 10001,
                      "cost": 2004.42,
                      "chosen": true
                    }
                  ]
                },
                "condition_filtering_pct": 100,
                "rows_for_plan": 10001,
                "cost_for_plan": 2004.42,
                "chosen": true
              }
            ]
          },
          {
            "attaching_conditions_to_tables": {
              "original_condition": "((`t`.`j` = 1) and (`t`.`i` <= 10000))",
              "attached_conditions_computation": [
                {
                  "table": "`t`",
                  "rechecking_index_usage": {
                    "recheck_reason": "low_limit",
                    "limit": 1,
                    "row_estimate": 10001,
                    "range_analysis": {
                      "table_scan": {
                        "rows": 100464,
                        "cost": 35164.4
                      },
                      "potential_range_indexes": [
                        {
                          "index": "PRIMARY",
                          "usable": true,
                          "key_parts": [
                            "i"
                          ]
                        },
                        {
                          "index": "j",
                          "usable": false,
                          "cause": "not_applicable"
                        }
                      ],
                      "best_covering_index_scan": {
                        "index": "j",
                        "cost": 10086.5,
                        "chosen": true
                      },
[22 Jun 2022 5:50] MySQL Verification Team 
"setup_range_conditions": [
                      ],
                      "group_index_range": {
                        "chosen": false,
                        "cause": "cannot_do_reverse_ordering"
                      },
                      "skip_scan_range": {
                        "chosen": false,
                        "cause": "cannot_do_reverse_ordering"
                      },
                      "analyzing_range_alternatives": {
                        "range_scan_alternatives": [
                          {
                            "index": "PRIMARY",
                            "ranges": [
                              "i <= 10000"
                            ],
                            "index_dives_for_eq_ranges": true,
                            "rowid_ordered": true,
                            "using_mrr": false,
                            "index_only": false,
                            "in_memory": 1,
                            "rows": 18960,
                            "cost": 1901.09,
                            "chosen": true
                          }
                        ]
                      },
                      "chosen_range_access_summary": {
                        "range_access_plan": {
                          "type": "range_scan",
                          "index": "PRIMARY",
                          "rows": 18960,
                          "ranges": [
                            "i <= 10000"
                          ]
                        },
                        "rows_for_plan": 18960,
                        "cost_for_plan": 1901.09,
                        "chosen": true
                      }
                    }
                  }
                }
              ],
              "attached_conditions_summary": [
                {
                  "table": "`t`",
                  "attached": "((`t`.`j` = 1) and (`t`.`i` <= 10000))"
                }
              ]
            }
          },
          {
            "optimizing_distinct_group_by_order_by": {
              "simplifying_order_by": {
                "original_clause": "`t`.`i` desc",
                "items": [
                  {
                    "item": "`t`.`i`"
                  }
                ],
                "resulting_clause_is_simple": true,
                "resulting_clause": "`t`.`i` desc"
              }
            }
          },
          {
            "reconsidering_access_paths_for_index_ordering": {
              "clause": "ORDER BY",
              "steps": [
              ],
              "index_order_summary": {
                "table": "`t`",
                "index_provides_order": true,
                "order_direction": "desc",
                "index": "PRIMARY",
                "plan_changed": false
              }
            }
          },
          {
            "finalizing_table_conditions": [
              {
                "table": "`t`",
                "original_table_condition": "((`t`.`j` = 1) and (`t`.`i` <= 10000))",
                "final_table_condition   ": "((`t`.`j` = 1) and (`t`.`i` <= 10000))"
              }
            ]
          },
          {
            "refine_plan": [
              {
                "table": "`t`"
              }
            ]
          },
          {
            "considering_tmp_tables": [
            ]
          }
        ]
      }
    },
    {
      "join_explain": {
        "select#": 1,
        "steps": [
        ]
      }
    }
  ]
}
MISSING_BYTES_BEYOND_MAX_MEM_SIZE: 0
          INSUFFICIENT_PRIVILEGES: 0
1 row in set (0.00 sec)
[24 Aug 2023 21:48] Jon Stephens 
Documented fix as follows in the MySQL 8.0.35 and 8.3.0 changelogs:

    The low limit heuristic did not work well for ORDER BY DESC due
    to choosing the wrong index.

Closed.
[8 Sep 2023 20:50] Jon Stephens 
Documented fix as follows in the MySQL 8.0.35 and 8.2.0 changelogs:

    The low limit heuristic did not work well for ORDER BY DESC due
    to choosing the wrong index.

Closed.