Bug #117085 Performance issue with Multi-Valued Index and ORDER BY DESC LIMIT (Reads more data than expected)
Submitted: 31 Dec 2024 8:50 Modified: 14 Mar 20:44
Reporter: Eunbin Baek Email Updates:
Status: Closed Impact on me:
None 
Category:MySQL Server: Optimizer Severity:S5 (Performance)
Version:8.0.40 OS:Any
Assigned to: CPU Architecture:x86
Tags: DESC, multi-valued index, regression

[31 Dec 2024 8:50] Eunbin Baek 
Description:
In version 8.0.40, a performance issue occurs when using a Multi-Valued Index with an ORDER BY DESC and LIMIT clause in a query, specifically when the value specified in the LIMIT clause is greater than the actual number of result rows.

This appears to be caused by the following changes introduced in version 8.0.40.
==============================================================================
A query using a greater-than (>) or less-than (<) comparison with a multi-valued index executed much more slowly than the same query using an equality (=) comparison with the same index. (Bug #104897, Bug #33334911)
==============================================================================

Specifically, the changes to the Field_typed_array::key_cmp function in the sql/field.cc file seem to be the cause. Previously, when a key value did not match, the function returned -1. However, after this patch in version 8.0.40, it now always returns 1.

This also affects the following two functions, causing them to fail in correctly identifying the end point of an index scan.
- sql/key.cc :: int key_cmp(KEY_PART_INFO *key_part, const uchar *key, uint key_length)
- sql/range_optimizer/reverse_index_range_scan.cc :: int ReverseIndexRangeScanIterator::cmp_prev(QUICK_RANGE range_arg)

How to repeat:
You can reproduce the issue by importing the attached SQL file and then executing the following query.

>> 8.0.39 (Fast Case)
mysql> select * from t1 where 50 member of (ids->'$[*]') and id < 4098 order by id desc limit 10;
+------+------+----------+------+
| id   | col1 | col2     | ids  |
+------+------+----------+------+
| 4097 | 2522 | 52d799a8 | [50] |
| 4096 | 5874 | 52d79930 | [50] |
| 4095 | 2283 | 52d798b8 | [50] |
| 4094 | 5179 | 52d797fa | [50] |
| 4093 | 1205 | 52d794c6 | [50] |
+------+------+----------+------+
5 rows in set (0.00 sec)

mysql> show status like '%Handler%';
+----------------------------+-------+
| Variable_name              | Value |
+----------------------------+-------+
| Handler_commit             | 1     |
| Handler_delete             | 0     |
| Handler_discover           | 0     |
| Handler_external_lock      | 2     |
| Handler_mrr_init           | 0     |
| Handler_prepare            | 0     |
| Handler_read_first         | 0     |
| Handler_read_key           | 1     |
| Handler_read_last          | 0     |
| Handler_read_next          | 0     |
| Handler_read_prev          | 5     |
| Handler_read_rnd           | 0     |
| Handler_read_rnd_next      | 0     |
| Handler_rollback           | 0     |
| Handler_savepoint          | 0     |
| Handler_savepoint_rollback | 0     |
| Handler_update             | 0     |
| Handler_write              | 6     |
+----------------------------+-------+

>> 8.0.40 (Slow Case)
mysql> select * from t1 where 50 member of (ids->'$[*]') and id < 4098 order by id desc limit 10;
+------+------+----------+------+
| id   | col1 | col2     | ids  |
+------+------+----------+------+
| 4097 | 2522 | 52d799a8 | [50] |
| 4096 | 5874 | 52d79930 | [50] |
| 4095 | 2283 | 52d798b8 | [50] |
| 4094 | 5179 | 52d797fa | [50] |
| 4093 | 1205 | 52d794c6 | [50] |
+------+------+----------+------+
5 rows in set (3.46 sec)

mysql> show status like '%Handler%';
+----------------------------+--------+
| Variable_name              | Value  |
+----------------------------+--------+
| Handler_commit             | 1      |
| Handler_delete             | 0      |
| Handler_discover           | 0      |
| Handler_external_lock      | 2      |
| Handler_mrr_init           | 0      |
| Handler_prepare            | 0      |
| Handler_read_first         | 0      |
| Handler_read_key           | 1      |
| Handler_read_last          | 0      |
| Handler_read_next          | 0      |
| Handler_read_prev          | 400005 |
| Handler_read_rnd           | 0      |
| Handler_read_rnd_next      | 131009 |
| Handler_rollback           | 0      |
| Handler_savepoint          | 0      |
| Handler_savepoint_rollback | 0      |
| Handler_update             | 0      |
| Handler_write              | 531014 |
+----------------------------+--------+

Suggested fix:
Please ensure that the changes are revised to work seamlessly with the related code.
[31 Dec 2024 8:51] Eunbin Baek 
This is the test data for reproducing the issue.

Attachment: mvi_test.sql (application/octet-stream, text), 15.10 MiB.
[31 Dec 2024 9:28] MySQL Verification Team 
Hello Eunbin Baek,

Thank you for the report and test case.
Verified as described.

-- 8.0.40

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

Copyright (c) 2000, 2024, 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> select * from t1 where 50 member of (ids->'$[*]') and id < 4098 order by id desc limit 10;
+------+------+----------+------+
| id   | col1 | col2     | ids  |
+------+------+----------+------+
| 4097 | 2522 | 52d799a8 | [50] |
| 4096 | 5874 | 52d79930 | [50] |
| 4095 | 2283 | 52d798b8 | [50] |
| 4094 | 5179 | 52d797fa | [50] |
| 4093 | 1205 | 52d794c6 | [50] |
+------+------+----------+------+
5 rows in set (2.15 sec)

mysql> select * from t1 where 50 member of (ids->'$[*]') and id < 4098 order by id desc limit 10;
+------+------+----------+------+
| id   | col1 | col2     | ids  |
+------+------+----------+------+
| 4097 | 2522 | 52d799a8 | [50] |
| 4096 | 5874 | 52d79930 | [50] |
| 4095 | 2283 | 52d798b8 | [50] |
| 4094 | 5179 | 52d797fa | [50] |
| 4093 | 1205 | 52d794c6 | [50] |
+------+------+----------+------+
5 rows in set (2.04 sec)

mysql> select * from t1 where 50 member of (ids->'$[*]') and id < 4098 order by id desc limit 10;
+------+------+----------+------+
| id   | col1 | col2     | ids  |
+------+------+----------+------+
| 4097 | 2522 | 52d799a8 | [50] |
| 4096 | 5874 | 52d79930 | [50] |
| 4095 | 2283 | 52d798b8 | [50] |
| 4094 | 5179 | 52d797fa | [50] |
| 4093 | 1205 | 52d794c6 | [50] |
+------+------+----------+------+
5 rows in set (2.03 sec)

mysql> select * from t1 where 50 member of (ids->'$[*]') and id < 4098 order by id desc limit 10;
+------+------+----------+------+
| id   | col1 | col2     | ids  |
+------+------+----------+------+
| 4097 | 2522 | 52d799a8 | [50] |
| 4096 | 5874 | 52d79930 | [50] |
| 4095 | 2283 | 52d798b8 | [50] |
| 4094 | 5179 | 52d797fa | [50] |
| 4093 | 1205 | 52d794c6 | [50] |
+------+------+----------+------+
5 rows in set (2.03 sec)

-- 8.0.39

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

Copyright (c) 2000, 2024, 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> select * from t1 where 50 member of (ids->'$[*]') and id < 4098 order by id desc limit 10;
+------+------+----------+------+
| id   | col1 | col2     | ids  |
+------+------+----------+------+
| 4097 | 2522 | 52d799a8 | [50] |
| 4096 | 5874 | 52d79930 | [50] |
| 4095 | 2283 | 52d798b8 | [50] |
| 4094 | 5179 | 52d797fa | [50] |
| 4093 | 1205 | 52d794c6 | [50] |
+------+------+----------+------+
5 rows in set (0.00 sec)
.
.
+------+------+----------+------+
5 rows in set (0.00 sec)
+------+------+----------+------+
5 rows in set (0.00 sec)
+------+------+----------+------+
5 rows in set (0.00 sec)

regards,
Umesh
[14 Mar 20:44] Jon Stephens 
Documented fix as follows in the MySQL 8.0.42, 8.4.5, and 9.3.0 changelogs:

    A negative impact in performance was observed when using a
    multivalued index with ORDER BY DESC and LIMIT in a query, where
    the value specified by LIMIT was greater than the number of rows
    actually in the result.

    Regression of BUG#104897, BUG#33334911.

Closed.