Optimizie MySQL query: col_name IN (val1, ..., valN)

Question

I had posted a question about mysql equality range optimization here. At this post, I want to discuss about why mysql optimizer is too bad for this type of query: col_name IN (val1, ..., valN).

My table:
alert_user(id, user_id, source_id, start_time, is_read, ...)

Indexes:
idx_user_start(user_id, start_time)
idx_user_read_start(user_id, is_read, start_time)
idx_user_source_start(user_id, source_id, start_time)
idx_user_read_source_start(user_id, is_read, source_id, start_time)

Records: 30M
Records of user_id 1: 6M

1. Query 1

SELECT id, source_id, is_read, start_time
FROM alert_user
WHERE user_id = 1 AND source_id IN (3, 48)
ORDER BY start_time DESC LIMIT 100;

Run: 170s

• access_type: index
• key: idx_user_start
• key_length: 12

{
    "query_block": {
        "select_id": 1,
        "cost_info": {
            "query_cost": "1316696.93"
        },
        "ordering_operation": {
            "using_filesort": false,
            "table": {
                "table_name": "alert_user",
                "access_type": "index",
                "possible_keys": [
                    "idx_user_source_start",
                    "idx_user_start",
                    "idx_user_read_start",
                    "idx_user_read_source_start"
                ],
                "key": "idx_user_start",
                "used_key_parts": [
                    "user_id",
                    "start_time"
                ],
                "key_length": "12",
                "rows_examined_per_scan": 314,
                "rows_produced_per_join": 2540666,
                "filtered": "4.57",
                "backward_index_scan": true,
                "cost_info": {
                    "read_cost": "46363.53",
                    "eval_cost": "254066.68",
                    "prefix_cost": "1316696.93",
                    "data_read_per_join": "193M"
                },
                "used_columns": [
                    "id",
                    "user_id",
                    "is_read",
                    "start_time",
                    "source_id"
                ],
                "attached_condition": "((`test2`.`alert_user`.`user_id` = 1) and (`test2`.`alert_user`.`source_id` in (3,48)))"
            }
        }
    }
}

2. Query 2

SELECT id, source_id, is_read, start_time
FROM alert_user use index (idx_user_source_start)
WHERE (user_id = 1 AND source_id IN (3, 48))
ORDER BY start_time DESC LIMIT 100;

Run: 3s

• access_type: range
• key: idx_user_source_start
• key_length: 12

{
    "query_block": {
        "select_id": 1,
        "cost_info": {
            "query_cost": "2142293.68"
        },
        "ordering_operation": {
            "using_filesort": true,
            "table": {
                "table_name": "alert_user",
                "access_type": "range",
                "possible_keys": [
                    "idx_user_source_start"
                ],
                "key": "idx_user_source_start",
                "used_key_parts": [
                    "user_id",
                    "source_id"
                ],
                "key_length": "12",
                "rows_examined_per_scan": 1826304,
                "rows_produced_per_join": 1826304,
                "filtered": "100.00",
                "index_condition": "((`test2`.`alert_user`.`user_id` = 1) and (`test2`.`alert_user`.`source_id` in (3,48)))",
                "using_MRR": true,
                "cost_info": {
                    "read_cost": "1959663.28",
                    "eval_cost": "182630.40",
                    "prefix_cost": "2142293.68",
                    "data_read_per_join": "139M"
                },
                "used_columns": [
                    "id",
                    "user_id",
                    "is_read",
                    "start_time",
                    "source_id"
                ]
            }
        }
    }
}

3. Query 3
I deleted 2 indexes which contain is_read, and run query

SELECT id, source_id, is_read, start_time
FROM alert_user
WHERE (user_id = 1 AND source_id IN (3, 48))
ORDER BY start_time DESC LIMIT 100;

Run: < 1s

• access_type: ref
• key: idx_user_start
• key_length: 4

{
    "query_block": {
        "select_id": 1,
        "cost_info": {
            "query_cost": "1903471.80"
        },
        "ordering_operation": {
            "using_filesort": false,
            "table": {
                "table_name": "alert_user",
                "access_type": "ref",
                "possible_keys": [
                    "idx_user_source_start",
                    "idx_user_start"
                ],
                "key": "idx_user_start",
                "used_key_parts": [
                    "user_id"
                ],
                "key_length": "4",
                "ref": [
                    "const"
                ],
                "rows_examined_per_scan": 11740588,
                "rows_produced_per_join": 2348117,
                "filtered": "20.00",
                "backward_index_scan": true,
                "cost_info": {
                    "read_cost": "729413.00",
                    "eval_cost": "234811.76",
                    "prefix_cost": "1903471.80",
                    "data_read_per_join": "179M"
                },
                "used_columns": [
                    "id",
                    "user_id",
                    "is_read",
                    "start_time",
                    "source_id"
                ],
                "attached_condition": "(`test2`.`alert_user`.`source_id` in (3,48))"
            }
        }
    }
}

Mysql uses 3 different execution strategies for the above 3 queries. All are slow. I know 2 methods to optimize the above query:

• Use UNION (< 400ms)
• Use Lateral JOIN (< 400ms)

However, I still have to hint mysql use index idx_user_source_start. Maybe creating many indexes makes mysql cannot choose the optimal index.

Second, I feel a bit tired because I have to rewriting SQL to UNION when query contain IN (val1, val2,...).

Have anyone faced this problem in MySQL, please share your thoughts.

Answer 1

This index may be faster, but still not 'perfect':

INDEX(user_id, source_id,    -- either order is equally good
      start_time,            -- a range
      is_read)               -- for "covering"

When you add that index, remove any that are a left subset of it, namely idx_user_source_start.

Once you have that index, this will be even faster (at least if the table is 'large'):

( SELECT  id, source_id, is_read, start_time
    FROM  alert_user
    WHERE  user_id = 1
      AND  source_id = 3 
    ORDER BY  start_time DESC
    LIMIT  100
) UNION ALL
( SELECT  id, source_id, is_read, start_time
    FROM  alert_user
    WHERE  user_id = 1
      AND  source_id = 48
    ORDER BY  start_time DESC
    LIMIT  100
)
ORDER BY start_time DESC   -- yes, again
LIMIT 100;

I realize that it may not be practical to break up the IN (or OR) and make UNIONs. But nothing else will be efficiently executed.

Leaving off the is_read will be nearly as good. In either case, it will do 200 fetches, build a temp table (probably in RAM), re-sort and trim down to 100.

If you will be using OFFSET, too, it gets a little trickier: https://mysql.rjweb.org/doc.php/index_cookbook_mysql#or

Case 1 (and subcases)

• The Optimizer usually fails to notice a LIMIT and factor it into picking a plan. More specifically...
• When scanning and filtering and limiting, the 'limit' rows could be in the first few rows scanned, or they could be at the far end of the table.
• When there is a choice between picking an index that handles part of a WHERE but includes the ORDER BY versus handles all of the WHERE and not the ORDER BY, the Optimizer can all-to-easily make the wrong choice.
• IN with multiple values is usually as bad as a "range" -- columns after it in the INDEX are ignored.
• As you observed, a change in the data distribution and/or items in IN can make a big difference in performance. Be aware that the Optimizer does not do adequate research to discover this.
• Avoiding IN (or, OR) by using UNION (as exemplified above) lets more columns of an index be used, even to the point of stopping short of scanning the entire table.

The 'real' answer of how MySQL's Optimizer works is its "cost model". I do not attempt to follow that. (See EXPLAIN FORMAT=JSON and "Optimizer trace".) I try to optimization it by saying "given this template, the Optimizer will usually want INDEX(...). But if that index is not available, here is what it will do with the existing INDEXes. The cost model depends on statistics which are less than perfect. For example, there is no "histogram" indicating that a column has an unbalanced set of values. (MariaDB attempts to do such.)

Answer 2

Thank for your reply. I think that UNION is the most optimal query. If you don't mind, I'd like to discuss about how MySQL chooses the execution plan.

Table alert_user has other columns besides the ones above. As for source_id, here are some examples:

• Source 3 contains data with start_time in [2023-04-01 -> 2023-04-17]
• Source 29 contains data with start_time in [2023-04-01 -> 2023-06-29]
• Source 48 contains data with start_time in [2023-04-01 -> 2023-07-11]

Case 1: When table alert_user only contains 2 indexes idx_user_start and idx_user_source_start

Test 1.1

SELECT id, source_id, is_read, start_time
FROM alert_user
WHERE (user_id = 1 AND source_id IN (3, 29))
ORDER BY start_time DESC LIMIT 100;

MySQL uses idx_user_start (access_type ref), run time is 11s

Query 1.2: Hint MySQL to use index

SELECT id, source_id, is_read, start_time
FROM alert_user USE INDEX (idx_user_source_start)
WHERE (user_id = 1 AND source_id IN (3, 29))
ORDER BY start_time DESC LIMIT 100;

MySQL use idx_user_source_start, run time is 1.7s

Query 1.3

.... source_id IN (3, 48) ...
MySQL use idx_user_start, run time is 0.5s, it runs fast because source 48 has many records recently.

Query 1.4: Hint MySQL to use index

SELECT id, source_id, is_read, start_time
FROM alert_user USE INDEX (idx_user_source_start)
WHERE (user_id = 1 AND source_id IN (3, 48))
ORDER BY start_time DESC LIMIT 100;

MySQL use idx_user_source_start, run time is 3.2s

Query 1.5: The most optimal query

UNION: 0.1s
UNION with index hint (idx_user_source_start): 0.1s

Case 2: When alert_user only contains 4 indexes idx_user_start, idx_user_source_start, idx_user_read_start, idx_user_read_source_start

Test 2.1

SELECT id, source_id, is_read, start_time
FROM alert_user
WHERE (user_id = 1 AND source_id IN (3, 29))
ORDER BY start_time DESC LIMIT 100;

MySQL uses idx_user_start (access_type index), run time has increased to 120s, very slow when compared with query 1.1. I found that mysql plan use access_type is index, different with access_type: ref of query 1.1.

Can you explain to me why MySQL chose the above execution plans.

1. Query 1.1 and 1.2

Why MySQL chose idx_user_start instead of idx_user_source_start

2. Query 1.1 and 2.1

Why is there a difference in access_type strategy ?

3. Is mysql optimizer not smart enough to

• Optimize query IN (val1,..,valN)
• When table has many indexes, mysql failed to choose the correct index. I have to use index hint in other queries
• After much time working with mysql, I came to the conclusion that that it's always better to use UNION and index hint. Do you have the same thoughts ?

Many thanks !