Mysql - Poor performance of sort by timestamp with limit query

jwaddell
October 14, 2023
277 views
0 votes
2 Answers

I have a simple MySQL table which consists of a primary key ID field, a timestamp (integer) field, and a foreign key ID field (device_id). There are indexes on each of these columns:

mysql> show indexes from device_heartbeats;
+-------------------+------------+------------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
| Table             | Non_unique | Key_name   | Seq_in_index | Column_name | Collation | Cardinality | Sub_part | Packed | Null | Index_type | Comment | Index_comment |
+-------------------+------------+------------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
| device_heartbeats |          0 | PRIMARY    |            1 | id          | A         |     2603552 |     NULL | NULL   |      | BTREE      |         |               |
| device_heartbeats |          1 | IDX...bb8c |            1 | time        | A         |     1573451 |     NULL | NULL   |      | BTREE      |         |               |
| device_heartbeats |          1 | FKb...xi10 |            1 | device_id   | A         |          16 |     NULL | NULL   |      | BTREE      |         |               |
+-------------------+------------+------------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+

The table currently contains about 2.6 million records. Here is the count for each device:

mysql> select device_id, count(device_id) from device_heartbeats group by device_id;
+-----------+------------------+
| device_id | count(device_id) |
+-----------+------------------+
|         1 |           315833 |
|         2 |              589 |
|         3 |           851461 |
|         4 |             2115 |
|         5 |          1104668 |
|         6 |                6 |
|         7 |              409 |
|         8 |              783 |
|         9 |              778 |
|        10 |              772 |
|        11 |              211 |
|        12 |              333 |
|        13 |            57370 |
|        14 |            57121 |
|        15 |           217468 |
|        16 |               58 |
|        17 |               66 |
+-----------+------------------+
17 rows in set (0.26 sec)

I have a query that finds the most recent record using the timestamp field for a particular device_id (850k matching records):

mysql> select * from device_heartbeats where device_id = 3 order by time desc limit 1;
+---------+------------+-----------+
| id      | time       | device_id |
+---------+------------+-----------+
| 2610040 | 1697068792 |         3 |
+---------+------------+-----------+
1 row in set (0.00 sec)

The performance of this query is good, however if I use another device_id (one with only about 2000 records) then the performance is poor:

mysql> select * from device_heartbeats where device_id = 4 order by time desc limit 1;
+-------+------------+-----------+
| id    | time       | device_id |
+-------+------------+-----------+
| 48451 | 1684888379 |         4 |
+-------+------------+-----------+
1 row in set (1.59 sec)

The performance is good for each device_id except for 4 and 5.

What is going on here, and how can I fix it so that the performance is always good?

Answers

The short answer

If you are only interested in the max time for a given device_id, then the lightest/fastest query is simply:

SELECT MAX(time) FROM device_heartbeats WHERE device_id = 3;

with a composite key added:

ALTER TABLE `device_heartbeats`
    DROP INDEX `idx_device_id`,
    ADD INDEX `idx_device_id_time` (`device_id`, `time`);

The long answer

You have not included the EXPLAIN plan for these two queries but we can guess at what is happening with a reasonably high degree of certainty.

If you run your initial GROUP BY query with EXPLAIN you will see something like this:

+----+-------------+-------------------+------------+-------+---------------+---------------+---------+-----+---------+----------+-------------+
| id | select_type | table             | partitions | type  | possible_keys | key           | key_len | ref | rows    | filtered | Extra       |
+----+-------------+-------------------+------------+-------+---------------+---------------+---------+-----+---------+----------+-------------+
| 1  | SIMPLE      | device_heartbeats |            | index | idx_device_id | idx_device_id | 1       |     | 2645572 | 100.00   | Using index |
+----+-------------+-------------------+------------+-------+---------------+---------------+---------+-----+---------+----------+-------------+

This is reasonably quick as the entire query is performed against the index.

With your current single column indices the optimizer is going to have to choose one of them. With your order by time desc limit 1 it is highly likely that it is going to choose the index on time. This is a great choice if there is a recent row for the given device_id, but not so great if it has to scan a large portion of the index and fetch lots of rows.

If you run the EXPLAIN for your query for device_id = 3, you will probably see something like this:

+----+-------------+-------------------+------------+-------+---------------+----------+---------+-----+------+----------+----------------------------------+
| id | select_type | table             | partitions | type  | possible_keys | key      | key_len | ref | rows | filtered | Extra                            |
+----+-------------+-------------------+------------+-------+---------------+----------+---------+-----+------+----------+----------------------------------+
| 1  | SIMPLE      | device_heartbeats |            | index | idx_device_id | idx_time | 8       |     | 8    | 11.70    | Using where; Backward index scan |
+----+-------------+-------------------+------------+-------+---------------+----------+---------+-----+------+----------+----------------------------------+

You will probably see a very similar EXPLAIN for device_id = 4, maybe with a higher but grossly under-estimated row count. The Backward index scan is going backwards through the index on time, reading the corresponding rows from the clustered index (primary key), until it finds a row with device_id = ?. If all the rows for a given device_id are from a "long time ago", it has to fetch a lot of rows. If there is a recent row, it does not have to go very far through the index before finding the first row for the given device_id.

You could force the use of the index on device_id:

EXPLAIN
SELECT *
FROM device_heartbeats FORCE INDEX (idx_device_id)
WHERE device_id = 3
ORDER BY time DESC
LIMIT 1;

/* Output for device_id = 3 */

+----+-------------+-------------------+------------+------+---------------+---------------+---------+-------+--------+----------+----------------+
| id | select_type | table             | partitions | type | possible_keys | key           | key_len | ref   | rows   | filtered | Extra          |
+----+-------------+-------------------+------------+------+---------------+---------------+---------+-------+--------+----------+----------------+
| 1  | SIMPLE      | device_heartbeats |            | ref  | idx_device_id | idx_device_id | 1       | const | 851461 | 100.00   | Using filesort |
+----+-------------+-------------------+------------+------+---------------+---------------+---------+-------+--------+----------+----------------+

/* Output for `device_id = 4 */

+----+-------------+-------------------+------------+------+---------------+---------------+---------+-------+------+----------+----------------+
| id | select_type | table             | partitions | type | possible_keys | key           | key_len | ref   | rows | filtered | Extra          |
+----+-------------+-------------------+------------+------+---------------+---------------+---------+-------+------+----------+----------------+
| 1  | SIMPLE      | device_heartbeats |            | ref  | idx_device_id | idx_device_id | 1       | const | 2115 | 100.00   | Using filesort |
+----+-------------+-------------------+------------+------+---------------+---------------+---------+-------+------+----------+----------------+

This will be much faster for device_id = 4, as it only has to filesort 2115 rows, but it will be relatively slow for device_id = 4, as it has to filesort 851461 rows.

If you add a composite index (as suggested by Senthil P Nathan in the comments):

ALTER TABLE `device_heartbeats`
    DROP INDEX `idx_device_id`,
    ADD INDEX `idx_device_id_time` (`device_id`, `time`);

/* Output for device_id = 3 */

+----+-------------+-------------------+------------+------+----------------------------------+--------------------+---------+-------+--------+----------+----------------------------------+
| id | select_type | table             | partitions | type | possible_keys                    | key                | key_len | ref   | rows   | filtered | Extra                            |
+----+-------------+-------------------+------------+------+----------------------------------+--------------------+---------+-------+--------+----------+----------------------------------+
| 1  | SIMPLE      | device_heartbeats |            | ref  | idx_device_id,idx_device_id_time | idx_device_id_time | 1       | const | 529656 | 100.00   | Backward index scan; Using index |
+----+-------------+-------------------+------------+------+----------------------------------+--------------------+---------+-------+--------+----------+----------------------------------+

/* Output for device_id = 4 */

+----+-------------+-------------------+------------+------+----------------------------------+--------------------+---------+-------+------+----------+----------------------------------+
| id | select_type | table             | partitions | type | possible_keys                    | key                | key_len | ref   | rows | filtered | Extra                            |
+----+-------------+-------------------+------------+------+----------------------------------+--------------------+---------+-------+------+----------+----------------------------------+
| 1  | SIMPLE      | device_heartbeats |            | ref  | idx_device_id,idx_device_id_time | idx_device_id_time | 1       | const | 5232 | 100.00   | Backward index scan; Using index |
+----+-------------+-------------------+------------+------+----------------------------------+--------------------+---------+-------+------+----------+----------------------------------+

Note the change from Using where; Backward index scan to Backward index scan; Using index.

Because these are now simple index lookups, they should return in < 1ms.

A slightly better option, assuming your table has just the three columns included in your question (id, time, device_id), is to remove the surrogate PK:

ALTER TABLE `device_heartbeats`
    DROP PRIMARY KEY,
    DROP INDEX `idx_device_id_time`,
    DROP COLUMN id,
    ADD PRIMARY KEY (`device_id`, `time`);

- RickJames
- October 14, 2023 at 6:32 am
- 0 votes
0
Sensor data is best done with the PRIMARY KEY starting with the device_id. Start with the thorough discussion by @user1191247, and @Schwern. Now, let me wrap them together with this add-on.

I agree with getting rid of id altogether. But if you cannot trust the times to be unique for each device, then keep the auto_inc id and do this:
```
PRIMARY KEY(device_id, ts, id),
INDEX(id)
```
The PK gives you the "clustering" that benefits many of the likely queries for this kind of data. And it does not really have any adverse impact on INSERTs, despite the inserts being very close to ‘chronological’.

The INDEX(id) is all that is needed to keep AUTO_INCREMENT happy.

The recommended SELECT MAX(ts) FROM device_heartbeats WHERE device_id = 3; will touch only one row, taking only a few milliseconds, even if the necessary block(s) are not cached. The index is "covering" (Explain’s "Using index") and will not need any filesort.

Even this will be nearly instantaneous for getting other columns:
```
SELECT *
    FROM device_heartbeats
    WHERE device_id = 3
    ORDER BY ts DESC
    LIMIT 1;
```
The uneven distribution of device_id values won’t affect these particular queries.

(A side note: If you plan to eventually delete ‘old’ data, I strongly recommend PARTITION BY RANGE. See Partition ).
Login or Signup to reply.

Please signup or login to give your own answer.

Click here to cancel reply.

Mysql – Poor performance of sort by timestamp with limit query

Answers

The short answer

The long answer