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: 31 Dec 2024 9:28
• Reporter: Eunbin Baek
• Status: Verified
• Category: MySQL Server: Optimizer
• Severity: S5 (Performance)
• Version: 8.0.40
• OS: Any
• 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