Slow query while selecting a higher offset from millions of rows

Question

I have sort of security log files containing millions of rows. On my current testing I imported the data for one month which is the sum of ~14,000,000 records. The table contains several set of fields including

id for primary key

log_time index

and other 8 columns.

When I perform a select query sorted by log_time with offset of some million, the query gets a lots of time to process.

My Query:

SELECT * FROM securityData ORDER BY log_time LIMIT 5000753, 50;

Explain

mysql> explain SELECT * FROM securityData ORDER BY log_time LIMIT 5000753, 50;
+----+-------------+------------+------+---------------+------+---------+------+---------+----------------+
| id | select_type | table      | type | possible_keys | key  | key_len | ref  | rows    | Extra          |
+----+-------------+------------+------+---------------+------+---------+------+---------+----------------+
|  1 | SIMPLE      | securityData | ALL  | NULL          | NULL | NULL    | NULL | 2664456 | Using filesort |
+----+-------------+------------+------+---------------+------+---------+------+---------+----------------+

Table Details

mysql> explain securityData;

+-----------+-----------------------+------+-----+---------+----------------+
| Field     | Type                  | Null | Key | Default | Extra          |
+-----------+-----------------------+------+-----+---------+----------------+
| id        | bigint(20)            | NO   | PRI | NULL    | auto_increment |
| log_time  | double(18,6) unsigned | NO   | MUL | NULL    |                |
/// more fields
+-----------+-----------------------+------+-----+---------+----------------+

The time of processing go higher and higher when I increase the offset value. I tried in both MyISAM and INNODB

How could I achieve the performance of this query?

Answer 1

You're seeing the intrinsic drawback of OFFSET pagination. Using LIMIT, you force your DB to sort all the records and count them all the way up to your OFFSET base.

Keyset pagination may correspond more closely to your actual needs here and will yield much better performance. As described in the above linked article, simply paginate based on the last key you've seen:

SELECT * 
FROM securityData 
WHERE id > ?last_seen_id
ORDER BY log_time 
LIMIT 50;

This allows your DB to leverage the index over id to directly jump to the first relevant row instead of going through all 5000753 rows preceeding it.

Answer 2

There are two(2) features of this query that makes it struggle:

• SELECT *
• LIMIT

There has to be a temp table that needs to created, loaded, and sorted with all the columns from the securityData table. Doing pagination should not involve all columns from a source table in the very beginning of the query.

What is needed ? Separation of keys for pagination from the gathering of all columns.

STEP 01 : Gather keys for pagination

SELECT id FROM securityData ORDER BY log_time LIMIT 5000753, 50;

STEP 02 : Make that pagination query a subquery

STEP 03 : Join pagination to the securityData table

SELECT B.* FROM
(SELECT id FROM securityData ORDER BY log_time LIMIT 5000753, 50) A
INNER JOIN securityData B USING (id)
ORDER BY B.log_time;

The main idea is to gather just 50 keys into a temp and join back to source table.

This can be very performant regardless what any EXPLAIN plan says. I can say this because almost 6 years ago, I addressed this in a similar post in StackOverflow entitled "Fetching a Single Row from Join Table". I answered it and got nice bounty just by gathering pagination keys first.

My inspiration for rewriting the query this way came from a French Performance Consultant's YouTube Video. Learn form this video and you will never look at pagination the same.

If you decide to paginate this way, please keep any optimizations localized to the subquery. The main point is to collect the keys. Increasing the performance of gathering these keys will increase the whole query's performance.