MySQL - low performance with WHERE, ORDER BY, LIMIT

Question

I have a very weird issue, and I can't wrap my head around it.

Given a rather big table (~5M transactions).

(1) ⚠️ I am running this query - this wallet has about ~20000 transactions in total:

SELECT
    *
FROM
    transactions AS t
WHERE
    t.created_at > "2023-04-01"
    AND t.created_at < "2023-04-02"
    AND (t.to_wallet_id = 6000
    OR t.from_wallet_id = 6000)
ORDER BY
    t.id DESC
LIMIT 100

This results in 11 rows, taking 9300ms Using EXPLAIN it tells shows that it used the PRIMARY key (id) as index.

(2) ✅ Running the same query with a LIMIT of <=11 results into 934ms execution time.

(3) ✅ Running the query from (1) with FORCE INDEX results into ~100ms execution time.

(4) ✅ Running the query from (1) without ORDER BY results into ~100ms execution time.

(5) ✅ Running the query from (1) with another wallet_id with significantly more overall transactions (~500.000) results into ~900ms execution time.

We have indexes for multiple rows and also multi-column indexes. However, it seems that MySQL is not using them, even though they are showing up in the "possible_keys" field when using EXPLAIN.

But even ignoring this, I am super confused why this particular wallet_id performs so bad, given that it has 10% of the entries of the other wallet_id. Also the fact that setting the LIMIT to a value <= 11 (lower than expected results) is showing the expected performance.

Things I considered already:

• We have indexes for all relevant columns and also some multi-column indexes (in the right order)
• We were on MySQL 5.x -> updated to MySQL 8.x (suspected this might have been the issue)

Answer 1

I assume created_at is the transaction date.

I'd use indices (to_wallet_id, created_at) and (from_wallet_id, created_at).

These indices can also be used to list transactions to OR from an account, in date order, which is a common operation.

(
    SELECT *
    FROM transactions
    WHERE created_at > '2023-04-01'
      AND created_at < '2023-04-02'
      AND to_wallet_id = 6000
    ORDER BY created_at DESC LIMIT 100
    )
UNION ALL
(
    SELECT *
    FROM transactions
    WHERE created_at > '2023-04-01'
      AND created_at < '2023-04-02'
      AND from_wallet_id = 6000
    ORDER BY created_at DESC LIMIT 100
    )
ORDER BY created_at DESC LIMIT 100

The idea here is that with an index on (to_wallet_id, created_at), having an equal WHERE condition on to_wallet_id and a range condition on created_at results in a range index scan, which is very fast. In addition, the index lists rows in created_at order directly, which means the ORDER BY does not result in a sort.

This is like taking a dictionary and looking for all the words starting with a certain letter. If you want the resulting words in alphabetic order, then no further sorting is necessary, because the dictionary already lists them in the order you want.

ORDER BY+LIMIT can be very slow if the database has to fetch and sort many thousands of rows, then only keep the first 100. If the index is used as a substitute for sorting, none of this work needs to be done and the top 100 rows are simply found in the index. When using OFFSET it will have to skip rows, but that still avoids a sort.

On the other hand, if you use ORDER BY id, then it is not possible to obtain the top 100 ids from the index, so a sort will have to be done. Even with a multicolumn index like (from_wallet_id,created_at,id) the rows are not listed in the index in a way that is convenient for avoiding a sort, because for one value of from_wallet_id the index will store them in (created_at,id) order, which is not (id) order. And if you flip the columns, using (from_wallet_id,id,created_at) then the created_at column of this index can no longer be used for the WHERE condition on created_at because it is hidden behind the id column.

Each subselect in the above query gathers the top 100 rows, then the UNION ALL followed by a sort brings them together and returns the final top 100 rows. This sort is unavoidable, but it is done on a dataset of limited size (200 rows) which is fast, unlike the sorts that were avoided in the previous steps, which would have to process all the transactions in the specified date range.

Using this scheme, such a query should take a couple hundred microseconds if no spinning disk IO is involved. A millisecond if you're really unlucky.

Answer 2

I am super confused why this particular wallet_id performs so bad, given that it has 10% of the entries of the other wallet_id. Also the fact that setting the LIMIT to a value <= 11 (lower than expected results) is showing the expected performance.

Mysql has to choose a strategy to search for the rows you want. It can either scan the whole table or use an index. It could choose to use an index where the first column is created_at to filter only the dates you need, and then checking all rows in that range to see if they satisfy the other conditions, then sorting them by id and taking the first 100. (Note that since you need a range of dates and not a single value, every column in the index to the right of created_at cannot be used to restrict the number of rows checked).

Or it can choose to scan the table in descending id order, checking every row to see if it satisfy the WHERE conditions, stopping when it finds 100 rows that satisfy the conditions. Given that you require at maximum 100 results, mysql probably thinks that this second strategy will be faster.

However, after it finds 11 rows that satisfy the conditions, mysql continues to search the whole table for more and ends up scanning all 5M transactions without finding any more.

This is why (2) and (5) run faster: mysql finds the requested number of rows easily and then stops, without the need to search more.

(3) and (4) on the other hand, will not use index on id (because it's forced or because it would not be useful) and will probably use an index on created_at that, given the small date range, will need to check a smaller number of rows.

If you want to speed up the query, bobflux answer is an excellent way to get the best result. Or, if you just need to get a consistent time across all possible wallet_id, you could just change the ORDER BY clause to

ORDER BY created_at DESC

which eliminates the need for the order by id and will have mysql pick an index on created_at

Answer 3

Try to create indices (created_at, to_wallet_id, id) and (created_at, from_wallet_id, id) and use

(
    SELECT *
    FROM transactions
    WHERE created_at > '2023-04-01'
      AND created_at < '2023-04-02'
      AND to_wallet_id = 6000
    ORDER BY id DESC LIMIT 100
    )
UNION ALL
(
    SELECT *
    FROM transactions
    WHERE created_at > '2023-04-01'
      AND created_at < '2023-04-02'
      AND from_wallet_id = 6000
    ORDER BY id DESC LIMIT 100
    )
ORDER BY id DESC LIMIT 100