MySQL Bugs: #115523: MySQL cannot choose the correct index when considering ORDER BY

Bug #115523	MySQL cannot choose the correct index when considering ORDER BY
Submitted:	5 Jul 9:55	Modified:	11 Jul 10:48
Reporter:	ksql- team	Email Updates:
Status:	Verified	Impact on me:	None
Category:	MySQL Server: Optimizer	Severity:	S4 (Feature request)
Version:	8.0	OS:	Any
Assigned to:		CPU Architecture:	Any
Tags:	INDEX, Optimizer, order by, reconsidering_access_paths_for_index_ordering

Description:
If during the filter phase the optimizer selects a composite index that might be used for sorting, it will not look for a more suitable composite index during the ORDER BY phase, even if it finds that the chosen index does not actually support sorting. Additionally, when the field that needs to be sorted has a single-column index, the optimizer always considers this single-column index as the best index for sorting because it assumes that the data distribution is uniform. However, in most real-world scenarios, this is not the case, resulting in a significant discrepancy between the optimizer's estimated cost for this index and the actual cost.

Given a simple table design：
CREATE TABLE `test` (
  `id` int NOT NULL AUTO_INCREMENT,
  `a` int DEFAULT NULL,
  `b` int DEFAULT NULL,
  `c` int DEFAULT NULL,
  `d` int DEFAULT NULL,
  `e` int DEFAULT NULL,
  PRIMARY KEY (`id`),
  KEY `idx_c` (`c`),
  KEY `idx_a_b_c` (`a`,`b`,`c`),
  KEY `idx_a_b` (`a`,`b`),
  KEY `idx_a_c` (`a`,`c`)
) ENGINE=InnoDB EFAULT CHARSET=utf8mb4 COLLATE=utf8mb4_unicode_ci；

Insert some data and make the data follow a non-uniform distribution similar to the one below：
+------------+-----+-----+-----+-----+-----+
| id         | a   | b   | c   | d   | e   |
+------------+-----+-----+-----+-----+-----+
| 1-1000     | 1   | ... | 100 | ... | ... |
+------------+-----+-----+-----+-----+-----+
| 1001-2000  | 2   | ... | 100 | ... | ... |
+------------+-----+-----+-----+-----+-----+
| 2001-3000  | 3   | ... | 99  | ... | ... |
+------------+-----+-----+-----+-----+-----+
| 3001-4000  | 4   | ... | 99  | ... | ... |
+------------+-----+-----+-----+-----+-----+
| ...        | ... | ... | ... | ... | ... |
+------------+-----+-----+-----+-----+-----+
|96001-97000 | 97  | ... | 52  | ... | ... |
+------------+-----+-----+-----+-----+-----+
|97001-98000 | 98  | ... | 52  | ... | ... |
+------------+-----+-----+-----+-----+-----+
|98001-99000 | 99  | ... | 51  | ... | ... |
+------------+-----+-----+-----+-----+-----+
|99001-100000| 100 | ... | 51  | ... | ... |
+------------+-----+-----+-----+-----+-----+

Now we have a query need to be executed: “select * from test where a = '99' order by c desc limit 1；”
Obviously, choosing the index idx_a_c is the best option, as we only need to access a single record, whereas choosing the index idx_c would almost require scanning the entire table to find the correct record.Surprisingly, MySQL ended up choosing the index idx_c.
mysql> explain SELECT * FROM test WHERE a = 99 ORDER BY c DESC LIMIT 1;
+----+-------------+-------+------------+-------+---------------------------+-------+---------+------+------+----------+----------------------------------+
| id | select_type | table | partitions | type  | possible_keys             | key   | key_len | ref  | rows | filtered | Extra                            |
+----+-------------+-------+------------+-------+---------------------------+-------+---------+------+------+----------+----------------------------------+
|  1 | SIMPLE      | test  | NULL       | index | idx_a_b_c,idx_a_c,idx_a_b | idx_c | 5       | NULL |   99 |     1.00 | Using where; Backward index scan |
+----+-------------+-------+------------+-------+---------------------------+-------+---------+------+------+----------+----------------------------------+
1 row in set, 1 warning (0.02 sec)

It takes 14 seconds to execute the query using index idx_c.

mysql> SELECT * FROM test WHERE a = 99 ORDER BY c DESC LIMIT 1;
+-------+------+--------+------+--------+--------+
| id    | a    | b      | c    | d      | e      |
+-------+------+--------+------+--------+--------+
| 99000 |   99 | 239947 |   51 | 597204 | 988119 |
+-------+------+--------+------+--------+--------+
1 row in set (14.16 sec)

Now we let MySQL use the index idx_a_c to execute the query.The query time has been reduced by several hundredfold!

mysql> SELECT *  FROM test FORCE INDEX (idx_a_c) WHERE a = 99  ORDER BY c DESC  LIMIT 1;
+-------+------+--------+------+--------+--------+
| id    | a    | b      | c    | d      | e      |
+-------+------+--------+------+--------+--------+
| 99000 |   99 | 239947 |   51 | 597204 | 988119 |
+-------+------+--------+------+--------+--------+
1 row in set (0.03 sec)

How to repeat:
We use sysbench-1.0.17 to create table and import data, the following is the Insert_data.lua script.

-- The beginning of the script.
if sysbench.cmdline.command == nil then
    error("Command is required. Supported commands: run")
end

sysbench.cmdline.options = {
    queries_per_tran = {"Number of queries per transaction", 1},
    num_rows_to_insert = {"Number of rows to insert", 100000},
    skip_trx = {"Do not use BEGIN/COMMIT; Use global auto_commit value", false}
}

function execute_prepare_table()
    drv = sysbench.sql.driver()
    con = drv:connect()

    query = [[CREATE TABLE `test` (
       `id` int NOT NULL AUTO_INCREMENT,
       `a` int DEFAULT NULL,
       `b` int DEFAULT NULL,
       `c` int DEFAULT NULL,
       `d` int DEFAULT NULL,
       `e` int DEFAULT NULL,
       PRIMARY KEY (`id`),
       KEY `idx_c` (`c`),
       KEY `idx_a_b_c` (`a`,`b`,`c`),
       KEY `idx_a_b` (`a`,`b`),
       KEY `idx_a_c` (`a`,`c`)
     ) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4 COLLATE=utf8mb4_unicode_ci
    ]]

    con:query(query)

    con:disconnect()
end

function execute_depopulate_data()
    drv = sysbench.sql.driver()
    con = drv:connect()

    con:query("DROP TABLE test")

    con:disconnect()
end

cursize = 0
function execute_populate_data()
    drv = sysbench.sql.driver()
    con = drv:connect()

    if (cursize == 0) then
       con:bulk_insert_init("INSERT INTO test VALUES")
    end

    for i = 1, sysbench.opt.num_rows_to_insert do
        cursize = cursize + 1

        local a = math.floor((cursize - 1) / 1000) + 1
        local b = sysbench.rand.uniform(1, 1000000)
        local c = 100 - math.floor((cursize - 1) / 2000)
        local d = sysbench.rand.uniform(1, 1000000)
        local e = sysbench.rand.uniform(1, 1000000)

        if (cursize % 5000 == 0) then
            con:bulk_insert_next("(" .. cursize .. "," .. a .. "," .. b .. "," .. c .. "," .. d .. "," .. e ..")")
            con:bulk_insert_done()
            con:bulk_insert_init("INSERT INTO test VALUES")
        else
            con:bulk_insert_next("(" .. cursize .. "," .. a .. "," .. b .. "," .. c .. "," .. d .. "," .. e ..")")
        end
    end

    if (cursize % 5000 == 0) then
        con:bulk_insert_done()
    end

    con:disconnect()
end

sysbench.cmdline.commands = {
    prepare = {execute_prepare_table, sysbench.cmdline.PARALLEL_COMMAND},
    populate = {execute_populate_data, sysbench.cmdline.PARALLEL_COMMAND},
    depopulate = {execute_depopulate_data, sysbench.cmdline.PARALLEL_COMMAND}
}

function thread_init()
    drv = sysbench.sql.driver()
    con = drv:connect()
end

function thread_done()
    con:disconnect()
end

--The end of the script.

Just execute the following two commands in order to import the data into the MySQL database.

sysbench /path/sysbench-1.0/src/lua/insert_data.lua --mysql-host=<your_host> --mysql-port=<your_port> --mysql-user=<your_username> --mysql-password=<your_password> --mysql-db=<your_database> --threads=1 prepare

sysbench /path/sysbench-1.0/src/lua/insert_data.lua --mysql-host=<your_host> --mysql-port=<your_port> --mysql-user=<your_username> --mysql-password=<your_password> --mysql-db=<your_database> --threads=1 populate

After that, you can reproduce this bug using the two queries mentioned in the description.

Suggested fix:

1. Initially, the optimizer thought that the selected index idx_a_b_c might be able to support sorting, so it did not seek a new index. After realizing that idx_a_b_c actually could not support sorting, it still did not look for a more suitable index, such as idx_a_c. I suggest that the optimizer should try to find a more suitable index if it discovers that the chosen index cannot support sorting.

2. The optimizer assumes that the data is uniformly distributed in the “test_if_cheaper_ordering” function,which results in the optimizer's cost estimation for a single index on the sorting field being highly inaccurate, with a significant deviation from the actual situation. I suggest finding ways to make the optimizer more aware of the actual data distribution, at least not defaulting to the assumption that data is uniformly distributed, in order to make more accurate index cost assessments.

Hi Mr. ksql-team,

We do not consider. this as a bug.

However, before closing this report , you could clear out some of the unclear explanation.

Let us first introduce you on how optimisers in the vast majority of RDBMS work. 

Filtering and sorting phase are TOTALLY separated. There are other possible scenarios, with more phases, like in CTE, window functions, nested queries,  etc ......

First of all, the optimiser  is doing ONLY  filtering phse, without any consideration for the following phases. That is how (practically) all optimisers are designed. After filtering phase is over, then sorting phase is done, if required. It is checked whether current selection of index is doing the job or not. Then it chooses the next best option, just for sorting. 

There is no way to merge both phases into one. That goes against the basic premises of the algorithms that relational databases use.

Simply, there are several distinct phases , each optimised on it's own.

If there would arise a possibility of merging the phases, then a completely new Optimiser would have to be designed and implemented.

Hence, based on the above , what you report is not a bug.

Please, let us know if we misunderstood your report. If you are not reporting merging totally distinct and separate phases, please let us know.

Not a bug.

One more , very small, note ......

There are many optimiser hints in our product  .....

Because there is no such thing as a perfect Optimiser in this imperfect world.

Why don't you try USE INDEX or FORCE INDEX ?????

Sorry, my explanation may not have been clear and caused some misunderstanding. Please allow me to explain again.

Firstly, the issue we encountered is that in some scenarios, MySQL adopts the "index" plan, while in reality, using the "ref" plan would be more efficient. The incorrect index choice has resulted in a 400-fold increase in the number of scanned rows.Of course, we can use optimizer hints to select the correct index, but we cannot accurately determine which index should be chosen for every query. This should be the optimizer's job. We believe that we should help the optimizer fix this bug, rather than using optimizer hints to bypass it.

Secondly, fixing this bug does not require designing and implementing an entirely new optimizer. It only requires correcting a minor issue in the optimizer when handling the 'ORDER BY' clause. A little effort goes a long way.

Finally, a perfect optimizer does not truly exist in this world. However, striving to create one is precisely the pursuit of every database professional, isn't it?

Hi Mr. ksql-team,

Thank you for your last comment.

However, we have explained to you the concept that all queries are optimised in several totally distinct phases. And they can NOT be merged.

We do not see that you have addressed this fact.

We are looking forward to your response.

Hi ksql-team,

We have givent it a further thought and decided that your idea makes a proper feature request.

Verified as a feature request.