MySQL chooses a slow execution plan for selecting rows by range condition with ORDER BY, LIMIT and OFFSET clauses

Question

I have a table "client_data" with 2 indexes:

1. CLIENT_USER_CREATED (CLIENT, USER, CREATED)
2. CLIENT_CREATED (CLIENT, CREATED)

The primary key is (ID, CLIENT, CREATED)

The table is partitioned by range on CREATED column by months: p202009, p202010, p202011, p202012, p202101, etc. Each partition has around 40M rows. The entire table has more than 1B rows.

I have a query:

SELECT * FROM client_data p
WHERE p.CLIENT IN (1001) AND p.CREATED >= '2020-10-01 00:00:00'
ORDER BY p.CREATED DESC
LIMIT 100 OFFSET 400

When I run the query with LIMIT and OFFSET, MySQL uses the first index, which is not optimal (takes 3 sec).

When I run the same query without OFFSET, MySQL uses the second index, which is optimal (takes 5 ms).

Here are the plans (classic + tree views):

-- the "bad" CLIENT_USER_CREATED index is used
EXPLAIN SELECT * FROM client_data p WHERE p.CLIENT IN (1001) AND p.CREATED >= '2020-10-01 00:00:00' ORDER BY p.CREATED DESC LIMIT 100 OFFSET 400
id;select_type;table;partitions;type;possible_keys;key;key_len;ref;rows;filtered;Extra
1   SIMPLE  p   p202010,p202011,p202012,p202101,p202102,p202103,p202104,p202105,p202106,p202107,p202108,p202109,p202110,p202111,p202112,p202201,p202202,p202203,p202204,p202205,p202206,p202207,p202208,p202209,p202210,p202211,p202212,p202301,p202302,p202303,p202304,p202305,p202306,p202307,p202308,p202309,p202310,p202311,p202312,pmax    ref CLIENT_CREATED,CLIENT_USER_CREATED  CLIENT_USER_CREATED 4   const   657814  50.0    Using index condition; Using filesort

-> Limit/Offset: 100/400 row(s)  (cost=690705 rows=100) (actual time=3330..3331 rows=100 loops=1)
    -> Sort: p.CREATED DESC, limit input to 500 row(s) per chunk  (cost=690705 rows=657814) (actual time=3325..3331 rows=500 loops=1)
        -> Index lookup on p using CLIENT_USER_CREATED (CLIENT=1001), with index condition: (p.CREATED >= TIMESTAMP'2020-10-01 00:00:00')  (cost=690705 rows=657814) (actual time=0.0653..2477 rows=365293 loops=1)

-- force using "good" CLIENT_CREATED index
EXPLAIN SELECT * FROM client_data p USE INDEX (CLIENT_CREATED) WHERE p.CLIENT IN (1001) AND p.CREATED >= '2020-10-01 00:00:00' ORDER BY p.CREATED DESC LIMIT 100
id;select_type;table;partitions;type;possible_keys;key;key_len;ref;rows;filtered;Extra
1   SIMPLE  p   p202010,p202011,p202012,p202101,p202102,p202103,p202104,p202105,p202106,p202107,p202108,p202109,p202110,p202111,p202112,p202201,p202202,p202203,p202204,p202205,p202206,p202207,p202208,p202209,p202210,p202211,p202212,p202301,p202302,p202303,p202304,p202305,p202306,p202307,p202308,p202309,p202310,p202311,p202312,pmax    range   CLIENT_CREATED  CLIENT_CREATED  9       607747  100.0   Using index condition; Backward index scan

-> Limit: 100 row(s)  (cost=729297 rows=100) (actual time=1.16..2.75 rows=100 loops=1)
    -> Index range scan on p using CLIENT_CREATED over (CLIENT = 1001 AND '2020-10-01 00:00:00' <= CREATED) (reverse), with index condition: ((p.CLIENT = 1001) and (p.CREATED >= TIMESTAMP'2020-10-01 00:00:00'))  (cost=729297 rows=607747) (actual time=1.16..2.74 rows=100 loops=1)

-- the "good" CLIENT_CREATED index is used after I remove OFFSET
EXPLAIN analyze SELECT * FROM client_data p WHERE p.CLIENT IN (1001) AND p.CREATED >= '2020-10-01 00:00:00' ORDER BY p.CREATED DESC LIMIT 100
id;select_type;table;partitions;type;possible_keys;key;key_len;ref;rows;filtered;Extra
1   SIMPLE  p   p202010,p202011,p202012,p202101,p202102,p202103,p202104,p202105,p202106,p202107,p202108,p202109,p202110,p202111,p202112,p202201,p202202,p202203,p202204,p202205,p202206,p202207,p202208,p202209,p202210,p202211,p202212,p202301,p202302,p202303,p202304,p202305,p202306,p202307,p202308,p202309,p202310,p202311,p202312,pmax    range   CLIENT_CREATED,CLIENT_USER_CREATED  CLIENT_CREATED  9       607747  100.0   Using index condition; Backward index scan

-> Limit: 100 row(s)  (cost=1.33e+6 rows=100) (actual time=86.3..87.5 rows=100 loops=1)
    -> Index range scan on p using CLIENT_CREATED over (CLIENT = 1001 AND '2020-10-01 00:00:00' <= CREATED) (reverse), with index condition: ((p.CLIENT = 1001) and (p.CREATED >= TIMESTAMP'2020-10-01 00:00:00'))  (cost=1.33e+6 rows=607747) (actual time=86.3..87.5 rows=100 loops=1)

The CLIENT column has around 1000 uniq values.

The version of MySQL is 8.0.33.

I wonder why MySQL does not use an optimal index for the query, which satisfies the leftmost prefix requirement, searching for only one CLIENT, and sorting by the second index field then.

Answer 1

Here is an idea

Without changing the query, hide the index

ALTER TABLE client_data ALTER INDEX CLIENT_USER_CREATED INVISIBLE;

Try out your queries for a while. If all your queries behave properly, then go drop the index (OPTIONALLY).

ALTER TABLE client_data DROP INDEX CLIENT_USER_CREATED;

If you have queries with CLIENT and USER in your WHERE clauses, then keep the index. You will have to make the index visible again with

ALTER TABLE client_data ALTER INDEX CLIENT_USER_CREATED VISIBLE;

You should add the index hints as BillKarwin already suggested.

As to why LIMIT changes the explain plan CLIENT_USER_CREATED when OFFSET is introduced, here is my insane rant.

INSANE RANT

Personally, I have always been under the impression that the order of the indexes matter to an EXPLAIN plan when LIMIT and OFFSET enter the mix.

Please run SHOW CREATE TABLE client_data\G

If CLIENT_USER_CREATED appears in the table schema after CLIENT_CREATED, there is a great chance CLIENT_CREATED would be chosen (the first index it sees) to do an index scan cut short by LIMIT.

If CLIENT_USER_CREATED appears in the table schema before CLIENT_CREATED, then introducing OFFSET would check for the CLIENT=1001 after performing a backward traversal (on the first index it sees), searching for 1001 before generating later p[arts of the explain plan.

If you are doing pagination, please consider refactoring your query using OFFSET against the ID rather than the other columns.

Please consider my insane rant as a disclaimer.

Answer 2

I assume you are using PARTITIONing because you will remove 'old' rows? (This is about the only use for Partitioning.) Removing partitioning would lead to a different set of index suggestions.

I realize that you will probably reject my suggestions as too invasive in the table and the code. But here goes anyway.

The tip-off that performance is bad is having all the partitions mentioned in the partitions column.

Probably most of your queries involve WHERE CLIENT IN (...)? Is id used for anything other than having a PRIMARY KEY?

PRIMARY KEY(client, created),
INDEX(id)

would (perhaps) make the data clustered in a more efficient way for this, and probably other, queries.

As for OFFSET -- It is problematic due to skipping/duplicating rows, and due to being slow when the offset is high. A more efficient way to code things is to "remember where you left off". See Pagination . (Caveat: It may not apply well to your situation.)

As for "why"... MySQL's Optimizer has always been somewhat blind to LIMIT and its mate OFFSET. It's as if it ignores them when deciding how to perform the query.

What happens when you mave multiple clients in IN? I suspect things get worse. The solution may be to use UNION:

( SELECT * FROM client_data p
    WHERE p.CLIENT = 1001 AND p.CREATED >= '2020-10-01 00:00:00'
    ORDER BY p.CREATED DESC
    LIMIT 500    -- 400+100
) UNION ALL
( SELECT * FROM client_data p
    WHERE p.CLIENT = 987 AND p.CREATED >= '2020-10-01 00:00:00'
    ORDER BY p.CREATED DESC
    LIMIT 500    -- 400+100
)
ORDER BY p.CREATED DESC    -- yes, repeated
LIMIT 100 OFFSET 400       -- different

If the table has some big columns (TEXT, etc), consider doing a "lazy load":

SELECT r.*                      -- just 100 rows
    FROM client_data AS r
    JOIN (
        ... SELECT id FROM ...  -- 400+100 rows
         ) as q  USING(id)

And then make sure the EXPLAIN says "Using index", which means that the INDEX is "covering".