The Dangers of OFFSET With MySQL

Christian Emmer

Jul 28, 2022 · 15 min read

Large limit offsets degrade the performance of most databases, but it is especially egregious in MySQL.

The problem, with a clustered index

To illustrate the problem, let's create a simple table and fill it with 1,000,000 rows of non-trivial size:

CREATE TABLE messages
(
    id      SERIAL PRIMARY KEY,
    message TEXT NOT NULL
);

INSERT INTO messages (message)
SELECT 'Lorem ipsum dolor sit amet, consectetur adipiscing elit. Integer aliquam ornare velit, auctor tempus erat ultrices ut. Phasellus ac nibh ante. Morbi consectetur, lorem in pulvinar tincidunt, augue est cursus ipsum, sed dapibus neque sapien id libero. Donec id felis sem. Morbi quis mi turpis. Nam viverra felis ac ex convallis, in congue nunc ultrices. Curabitur rutrum, lorem sit amet vulputate ultricies, velit odio ultrices dui, sed volutpat lorem felis vitae nibh. Vestibulum ante ipsum primis in faucibus orci luctus et ultrices posuere cubilia curae; Aenean orci mi, consectetur sed turpis sed, consequat tempor nisi. Cras id venenatis mi. Sed cursus in eros sit amet interdum.'
FROM (SELECT 1
      FROM (SELECT 0 AS n UNION SELECT 1 UNION SELECT 2 UNION SELECT 3 UNION SELECT 4 UNION SELECT 5 UNION SELECT 6 UNION SELECT 7 UNION SELECT 8 UNION SELECT 9) a
         , (SELECT 0 AS n UNION SELECT 1 UNION SELECT 2 UNION SELECT 3 UNION SELECT 4 UNION SELECT 5 UNION SELECT 6 UNION SELECT 7 UNION SELECT 8 UNION SELECT 9) b
         , (SELECT 0 AS n UNION SELECT 1 UNION SELECT 2 UNION SELECT 3 UNION SELECT 4 UNION SELECT 5 UNION SELECT 6 UNION SELECT 7 UNION SELECT 8 UNION SELECT 9) c
         , (SELECT 0 AS n UNION SELECT 1 UNION SELECT 2 UNION SELECT 3 UNION SELECT 4 UNION SELECT 5 UNION SELECT 6 UNION SELECT 7 UNION SELECT 8 UNION SELECT 9) d
         , (SELECT 0 AS n UNION SELECT 1 UNION SELECT 2 UNION SELECT 3 UNION SELECT 4 UNION SELECT 5 UNION SELECT 6 UNION SELECT 7 UNION SELECT 8 UNION SELECT 9) e
         , (SELECT 0 AS n UNION SELECT 1 UNION SELECT 2 UNION SELECT 3 UNION SELECT 4 UNION SELECT 5 UNION SELECT 6 UNION SELECT 7 UNION SELECT 8 UNION SELECT 9) f) temp;

Because id is the primary key it becomes the InnoDB table's clustered index . Like all other InnoDB b-tree indexes , clustered indexes will store values that are close together value-wise on the same page on disk. But clustered indexes are special because they also store the rest of the row's data alongside it in the same page. So when you query a row by its clustered index, InnoDB will look for the b-tree leaf that contains that value, and then it's inexpensive to read the rest of the row data. This helps provide some disk I/O optimization when querying rows in a range because many of them will be stored in the same pages.

The table ended up with about 741MB of data:

mysql> SELECT round((data_length + index_length) / 1024 / 1024) AS `Size (MB)`
       FROM information_schema.tables
       WHERE table_name = 'messages';

+-----------+
| Size (MB) |
+-----------+
|       741 |
+-----------+
1 row in set (0.01 sec)

Note: we need a table of some significant size like this in order to illustrate the performance degradation of OFFSET. Having a table with only a single numeric primary key column won't highlight the issues as well.

Now let's measure how long it takes to select a single row at a time at various offsets:

mysql> SELECT * FROM messages ORDER BY id LIMIT 1;
1 row in set (0.00 sec)

mysql> SELECT * FROM messages ORDER BY id LIMIT 1 OFFSET 10;
1 row in set (0.00 sec)

mysql> SELECT * FROM messages ORDER BY id LIMIT 1 OFFSET 100;
1 row in set (0.00 sec)

mysql> SELECT * FROM messages ORDER BY id LIMIT 1 OFFSET 1000;
1 row in set (0.00 sec)

mysql> SELECT * FROM messages ORDER BY id LIMIT 1 OFFSET 10000;
1 row in set (0.01 sec)

mysql> SELECT * FROM messages ORDER BY id LIMIT 1 OFFSET 100000;
1 row in set (0.68 sec)

mysql> SELECT * FROM messages ORDER BY id LIMIT 1 OFFSET 500000;
1 row in set (4.01 sec)

mysql> SELECT * FROM messages ORDER BY id LIMIT 1 OFFSET 999999;
1 row in set (6.40 sec)

Note: your timings are likely to vary, but they should have a similar exponential growth. The timings in this article are from the MySQL v8.0.29 Docker image. See "Creating a MySQL Playground in Docker" for instructions on using it.

Creating a MySQL REPL Playground in Docker

Apr 27, 2022 · 4 min read

It's helpful to have local throwaway environments for rapid development, especially with databases, and creating one for MySQL is a snap with Docker.

The difference in query time with offsets up through 10,000 is negligible, but once we get close to 100,000 the performance penalty becomes clear.

The problem, with a secondary index

What happens if we create that same table with an extra column that has a secondary index , and then fill that column with random numbers that won't match the clustered index's ordering:

CREATE TABLE messages
(
    id      SERIAL PRIMARY KEY,
    message TEXT NOT NULL,
    weight  INT  NOT NULL,
    INDEX (weight)
);

INSERT INTO messages (message, weight)
SELECT 'Lorem ipsum dolor sit amet, consectetur adipiscing elit. Integer aliquam ornare velit, auctor tempus erat ultrices ut. Phasellus ac nibh ante. Morbi consectetur, lorem in pulvinar tincidunt, augue est cursus ipsum, sed dapibus neque sapien id libero. Donec id felis sem. Morbi quis mi turpis. Nam viverra felis ac ex convallis, in congue nunc ultrices. Curabitur rutrum, lorem sit amet vulputate ultricies, velit odio ultrices dui, sed volutpat lorem felis vitae nibh. Vestibulum ante ipsum primis in faucibus orci luctus et ultrices posuere cubilia curae; Aenean orci mi, consectetur sed turpis sed, consequat tempor nisi. Cras id venenatis mi. Sed cursus in eros sit amet interdum.'
     , rand() * 2147483647
FROM (SELECT 1
      FROM (SELECT 0 AS n UNION SELECT 1 UNION SELECT 2 UNION SELECT 3 UNION SELECT 4 UNION SELECT 5 UNION SELECT 6 UNION SELECT 7 UNION SELECT 8 UNION SELECT 9) a
         , (SELECT 0 AS n UNION SELECT 1 UNION SELECT 2 UNION SELECT 3 UNION SELECT 4 UNION SELECT 5 UNION SELECT 6 UNION SELECT 7 UNION SELECT 8 UNION SELECT 9) b
         , (SELECT 0 AS n UNION SELECT 1 UNION SELECT 2 UNION SELECT 3 UNION SELECT 4 UNION SELECT 5 UNION SELECT 6 UNION SELECT 7 UNION SELECT 8 UNION SELECT 9) c
         , (SELECT 0 AS n UNION SELECT 1 UNION SELECT 2 UNION SELECT 3 UNION SELECT 4 UNION SELECT 5 UNION SELECT 6 UNION SELECT 7 UNION SELECT 8 UNION SELECT 9) d
         , (SELECT 0 AS n UNION SELECT 1 UNION SELECT 2 UNION SELECT 3 UNION SELECT 4 UNION SELECT 5 UNION SELECT 6 UNION SELECT 7 UNION SELECT 8 UNION SELECT 9) e
         , (SELECT 0 AS n UNION SELECT 1 UNION SELECT 2 UNION SELECT 3 UNION SELECT 4 UNION SELECT 5 UNION SELECT 6 UNION SELECT 7 UNION SELECT 8 UNION SELECT 9) f) temp;

And then run those same performance tests against the secondary index (by using it as our ORDER BY):

mysql> SELECT * FROM messages ORDER BY weight LIMIT 1;
1 row in set (0.00 sec)

mysql> SELECT * FROM messages ORDER BY weight LIMIT 1 OFFSET 10;
1 row in set (0.00 sec)

mysql> SELECT * FROM messages ORDER BY weight LIMIT 1 OFFSET 100;
1 row in set (0.01 sec)

mysql> SELECT * FROM messages ORDER BY weight LIMIT 1 OFFSET 1000;
1 row in set (0.05 sec)

mysql> SELECT * FROM messages ORDER BY weight LIMIT 1 OFFSET 10000;
1 row in set (0.34 sec)

mysql> SELECT * FROM messages ORDER BY weight LIMIT 1 OFFSET 100000;
1 row in set (10.85 sec)

mysql> SELECT * FROM messages ORDER BY weight LIMIT 1 OFFSET 500000;
1 row in set (12.00 sec)

mysql> SELECT * FROM messages ORDER BY weight LIMIT 1 OFFSET 999999;
1 row in set (13.65 sec)

The performance hit is noticeably worse. All the offsets of 100,000 or more rows take more than double the time when compared to the clustered index.

The explanation

MySQL's official documentation doesn't have much on the topic, but MariaDB's page on Pagination Optimization has some:

MariaDB has to find all [OFFSET+LIMIT] rows, step over the first [OFFSET], then deliver the [LIMIT] for that distant page.

Reading the entire table, just to get a distant page, can be so much I/O that it can cause timeouts... or it can interfere with other activity, causing other things to be slow.

Most popular articles on the internet describe this process as needing to "fetch" (from disk) all rows up to and including our result set, and then discard all but our results. Given that vague explanation, it makes sense why ordering on a clustered index would perform better, rows will be near each other on disk.

The use cases

This begs the question: why would you ever query with an offset of 100,000 or more? Here are a few use cases:

Websites that allow paginating a large data set:

Search engine results from billions of crawled web pages
Product search results from a very large product catalog
Displaying a list of some users for a social website, ordered by some ranking

Processing every item in a large set, either individually or in batches:

Sending an email to every registered user
Back-filling every row in a table with some information
Calling some external RPC for every row in a table

The pagination use cases are likely ordering by a secondary index, but even ordering by the clustered index will cause performance issues like we saw above.

None of these query patterns pose problems when first getting started with an empty database, they only become a problem when the data set becomes large. But the available solutions aren't difficult, so you should think about them from the start.

Note: it's worth stating that if you're ordering by a non-monotonically-increasing set of columns that you will have issues with inconsistent reads with OFFSET, regardless of the offset amount. Another reason to avoid OFFSET entirely.

Solution 1: cursor-based pagination

Cursor-based pagination, the "seek" method, keyset pagination - call it what you want, the idea is that you use the results from one query to help fetch the next or previous page. With this method we lose the ability to seek to arbitrary pages in our dataset, but that's likely acceptable for the real world use cases above.

Let's query for the first page of results from the second messages table with the secondary index from above - but the weight column isn't unique, and we need to ensure deterministic ordering, so we have to have a secondary ordering by the id column:

mysql> SELECT id
            , weight
       FROM messages
       ORDER BY weight, id
       LIMIT 10;

+--------+--------+
| id     | weight |
+--------+--------+
| 460554 |   3278 |
| 688311 |   7084 |
| 655956 |   7238 |
|  45815 |   7282 |
|  72018 |   9218 |
| 944968 |  11198 |
| 336739 |  11440 |
| 378072 |  12188 |
| 555292 |  12584 |
| 570261 |  12628 |
+--------+--------+
10 rows in set (0.00 sec)

We can use the last row from the results to query the next page:

mysql> SELECT id
            , weight
       FROM messages
       WHERE weight > 12628
          OR (weight = 12628 AND id > 570261)
       ORDER BY weight, id
       LIMIT 10;

+--------+--------+
| id     | weight |
+--------+--------+
| 701828 |  12980 |
| 969784 |  13970 |
| 827037 |  16192 |
| 171493 |  17776 |
| 506882 |  19514 |
|  18733 |  20746 |
| 202076 |  23078 |
| 768782 |  31196 |
| 675765 |  33418 |
| 956891 |  34210 |
+--------+--------+
10 rows in set (0.00 sec)

And if we wanted to go back a page then we can use the first result from that second page:

mysql> SELECT id
            , weight
       FROM messages
       WHERE weight < 12980
          OR (weight = 12980 AND id < 701828)
       ORDER BY weight, id
       LIMIT 10;

+--------+--------+
| id     | weight |
+--------+--------+
| 460554 |   3278 |
| 688311 |   7084 |
| 655956 |   7238 |
|  45815 |   7282 |
|  72018 |   9218 |
| 944968 |  11198 |
| 336739 |  11440 |
| 378072 |  12188 |
| 555292 |  12584 |
| 570261 |  12628 |
+--------+--------+
10 rows in set (0.00 sec)

This method would also work well for date columns, such as fetching a page of users by their registration date.

There are a few limits to this method, however:

Your data must be able to be deterministically sorted
You can't seek to an arbitrary page, you have to have the results from a sibling page
You lose the ability to easily know if a next or previous page exists

MariaDB's page on Pagination Optimization has some clever tricks on getting around some of these limits.

Solution 2: Deferred joins

From the official MySQL documentation on secondary indexes :

In InnoDB, each record in a secondary index contains the primary key columns for the row, as well as the columns specified for the secondary index. InnoDB uses this primary key value to search for the row in the clustered index.

In other words, every secondary index in InnoDB is a "covering" index that includes the primary key's columns, similar to multiple-column indexes .

So when we ORDER BY weight, MySQL will:

Scan the secondary index on weight for all values. Those values will be contained in index records that also contain all the values from the row's clustered index columns (just id in this case).
Then use the clustered index column values (again, just id in this case) to look up the row's data from the clustered index record.

From above, we know that InnoDB will fetch all the column data requested for OFFSET + LIMIT rows and then throw away OFFSET of those. The reason the high-offset queries above are slow is that the secondary index on weight doesn't include all the column data we're requesting, InnoDB has to fetch the rest from the clustered index.

If we only wanted the primary key then the lookup is much faster because the query is only returning columns "covered" in the secondary index:

mysql> SELECT id FROM messages ORDER BY weight LIMIT 1 OFFSET 999999;
1 row in set (0.14 sec)

If we move our OFFSET clause to a subquery that doesn't need to look up any data in the clustered index then we can reduce the overall work and minimize wasted effort. We can then use the results of that subquery to quickly look up the rows in the clustered index:

mysql> SELECT * FROM messages ORDER BY weight LIMIT 1 OFFSET 100000;
1 row in set (10.85 sec)

mysql> SELECT *
       FROM messages
                INNER JOIN (SELECT id
                            FROM messages
                            ORDER BY weight
                            LIMIT 1 OFFSET 100000) AS tmp USING (id)
       ORDER BY weight;
1 row in set (0.02 sec)

This solution won't scale as well as cursor-based pagination, but it might be acceptable if your dataset won't easily support cursors.

Comparison to PostgreSQL

Most relational databases suffer from some performance hit with OFFSET, PostgreSQL included, but it's not nearly as bad as MySQL.

If we create a similar table and fill it with similar data:

CREATE TABLE messages
(
    id      SERIAL PRIMARY KEY,
    message TEXT
);

INSERT INTO messages (message)
SELECT 'Lorem ipsum dolor sit amet, consectetur adipiscing elit. Integer aliquam ornare velit, auctor tempus erat ultrices ut. Phasellus ac nibh ante. Morbi consectetur, lorem in pulvinar tincidunt, augue est cursus ipsum, sed dapibus neque sapien id libero. Donec id felis sem. Morbi quis mi turpis. Nam viverra felis ac ex convallis, in congue nunc ultrices. Curabitur rutrum, lorem sit amet vulputate ultricies, velit odio ultrices dui, sed volutpat lorem felis vitae nibh. Vestibulum ante ipsum primis in faucibus orci luctus et ultrices posuere cubilia curae; Aenean orci mi, consectetur sed turpis sed, consequat tempor nisi. Cras id venenatis mi. Sed cursus in eros sit amet interdum.'
FROM generate_series(1, 1000000);

We can see the 999,999 row offset isn't great, but it's far better than MySQL:

postgres=# \timing
Timing is on.

postgres=# SELECT * FROM messages LIMIT 1;
Time: 0.801 ms

postgres=# SELECT * FROM messages LIMIT 1 OFFSET 10000;
Time: 3.086 ms

postgres=# SELECT * FROM messages LIMIT 1 OFFSET 999999;
Time: 235.581 ms

databases mysql

Discuss