Paginating Hundreds of Millions of Rows in MySQL

As the company's business grew, so did our data volume. MySQL is a free, community-driven open-source database, and if you want to paginate through millions of rows with it, relying on limit alone just doesn't cut it. That's not a knock on MySQL — with its pluggable storage engine architecture, it covers the vast majority of application needs, and managing 100 TB with MySQL is entirely feasible. How you use it, however, is another matter.

Pagination is table stakes for pretty much every admin list page. When the data is small, any implementation works; the problems only surface once the table grows to a few million rows: the first few pages return in milliseconds, later pages get slower and slower, and the last few pages may simply time out. This post documents the deep pagination problem I ran into on our company's billing table, and how I optimized it step by step.

Why limit gets slow

limit accepts one or two numeric arguments, which must be integer constants. With two arguments, the first specifies the offset of the first returned row and the second specifies the maximum number of rows to return.

The key is how the offset is implemented: MySQL cannot "jump" to row 100,000. It has to read all of the preceding offset rows and throw them away, returning only the final few. In other words, limit 100000, 20 actually reads 100,020 rows. If the selected columns aren't in the index, every one of those rows also requires a lookup back into the clustered index via the primary key, and the more rows you read, the more that cost gets amplified.

With offsets under 100k, limit performance is just about tolerable, but as the offset grows, performance falls off a cliff.

Our billing table had reached 2.3 million rows in a single table. Paginating to the last page with limit could easily take 20 seconds or more. The exact timing of course depends on indexes, column count, data contents, and query conditions.

Locate primary keys with a subquery first

To fix the pagination performance, my approach was: use a subquery to fetch only the primary key ids first, then use those ids to fetch the full rows.

-- The subquery fetches only the primary key id, with the where conditions
-- It can be satisfied entirely from the index, no row lookups needed
select id from table limit 100000,20

(Include the where conditions in the subquery.)

Since the primary key id is already the primary index, the limit runs very fast. Adding the filter columns to a composite index is what makes the improvement really substantial. The reason this step is fast: when selecting only id, the whole query can be completed within the index; each index record is tiny, so for the same offset scan the IO cost is far lower than scanning full rows.

But add sorting and performance drops sharply again — from what I observed, sorting 300k rows by id or timestamp takes 1–2 seconds.

The best approach is to abandon the limit offset entirely and use where id > xxx to locate the target starting position much faster, then sort and take 20 rows with limit. This comfortably handles millions of rows. This pattern is commonly called cursor pagination (or keyset pagination): each time you turn a page, you carry over the id of the last row on the previous page, and where id > xxx locates the starting point directly in the index. No matter which page you're on, you only ever scan about 20 rows. The trade-off is that you can only page sequentially — no jumping to arbitrary pages — which makes it a good fit for feeds and exports.

Fetch full rows by id list

First query out the ids you need, then run an unconditioned in idList query:

-- Step two: fetch the full columns using the id list from step one
-- No where conditions; keep the ordering as-is
select columns from table where id in (idList)

(No conditions; keep the ordering if there is one — sorting doesn't matter here because the data set is already tiny, so even an external sort is fast.)

When fetching the list, all you need is where id in (...). All the other conditions were already applied during the select-id step, so the row fetch needs no conditions at all — but do keep the ordering.

This makes paginated queries extremely fast, and if the list has few columns, you can build a covering index and go even faster. In practice, list pages often have 10 or 20+ columns, and indexing all of them is a bad idea: the index would be huge, and inserts and updates would slow down maintaining it, potentially hurting the table overall. So query design means balancing column count, sort order, number of conditions, index type, and which columns to index.

Joins are basically off the table at this data scale — prefer denormalized columns instead. On large tables, a join means every row of the driving table performs a lookup against the driven table, and the amplification becomes severe as data grows. Duplicating commonly joined columns into the main table trades one extra write for one fewer join on every read — usually a good deal for read-heavy list scenarios.

Verify the execution plan with explain

Optimization isn't a matter of gut feeling — after changing a SQL statement, check the execution plan to confirm.

Run the query through explain to see how it executes: whether it uses an index, which index type, whether row lookups happen, the estimated scanned rows, and other key information. Master these and your database performance improves in a meaningful way.

-- Prefix the query with explain to see the execution plan
-- Focus on type (index access type), key (index actually used),
-- rows (estimated rows scanned), and Extra (Using index = covering index)
explain select id from table where conditions limit 100000,20;

In testing, this pagination scheme handles 1 million rows at 20 per page well within 1 second — around 600 ms per request.

Beyond a single table

Pagination optimization solves single-table query performance, but the table keeps growing, so the architecture needs an escape hatch prepared in advance.

If a single table exceeds 5 million rows, it's time to consider horizontal sharding.

At the business logic level, to increase single-database throughput, consider read/write splitting: writes to the primary, reads from replicas, possibly multiple replicas.

Split databases vertically along business lines, and separate hot data from cold data when allocating server resources.

Pitfalls and caveats

1. The subquery approach assumes the where-clause columns have a suitable composite index. Otherwise the select-id step itself degrades into a full table scan and the optimization is wasted.

2. Cursor pagination with where id > xxx requires the sort key to be monotonic and unique. If you sort by timestamp and timestamps have duplicates, paging can skip or repeat rows — the usual fix is a composite sort on (timestamp, id).

3. The in (idList) length equals the page size — 20 is fine. Don't generalize this pattern to passing thousands of ids at once.

4. The rows value from explain is an estimate and can be off when table statistics are stale. When in doubt, cross-check with the slow query log and actual execution times.

tip

Before changing pagination SQL in production, verify the execution plan against realistic data volumes on a replica or a test database. Deep pagination problems simply don't reproduce on small data sets.

Wrapping up

The root cause of slow deep pagination is that limit offsets must scan and discard rows one by one, and the cost grows with the data. The fix is to make the scan happen over the smallest possible data set: locate primary keys within the index first, then fetch full rows; and drop the offset entirely in favor of cursor pagination where you can. After the change, use explain to verify the indexes are actually being used. When a single table can no longer keep up, move on to architectural measures: sharding, read/write splitting, and hot/cold data separation.