The labs on this site need JavaScript to run. The same content is written out below.

Learn › Database › SQL

Offset and keyset pagination

Why later pages get slower

A list of posts is shown page by page, newest first. The OFFSET method reads and discards all the rows of the earlier pages before it reaches the page you want. The keyset (cursor) method uses the index to go straight to "right after the last post you saw".

Partly checked against real execution · The content of the results was checked with SQLite, and the number of rows read follows the documentation

Concepts in this lab

Offset-based pagination and keyset (cursor-based) pagination

Offset-based pagination skips a given number of rows from the start and then fetches rows. It gets slower for later pages because all the skipped rows must still be read. Keyset pagination remembers the key value of the last row of the previous page and queries with the condition "after that value". It uses an index to start reading right at that position, so the speed stays constant even for deep pages.

Index

A data structure that keeps the values of specific columns separately, in sorted form, so that the wanted rows of a table can be found quickly. Without one, the whole table must be read to find the rows that match a condition. Reads get faster, but it must also be updated every time data is inserted, updated, or deleted, so it costs write performance and storage space.

B-tree index

The index structure that most relational databases use by default. It is a balanced tree that keeps values sorted, and each node holds many keys, so the height of the tree is low. You can find a value by going down only a few levels from the root. Because the values are sorted, it is used not only for equality lookups but also for range lookups and sorting.

Try these

• Default settings — OFFSET on page 1,000. It reads 20,000 rows and uses only 20.
• The same position with keyset — It reads only the 20 rows it needs.
• OFFSET, page 1 — Early pages are fast with OFFSET too.
• OFFSET, page 10,000 — The number of discarded rows becomes 200,000.
• A new post is added in between (OFFSET) — A post you just saw appears again on the next page.
• A new post is added in between (keyset) — The reference is the post id, so nothing shifts.

Running with the default settings

1. The post table has 1,000,000 posts, and a larger id means a newer post. Page 1,000 is requested with OFFSET 19,980.
2. The database cannot know in advance where the row after the first 19,980 rows is. It starts from the newest post and counts one by one along the index while it reads. It reads 19,980 rows and throws them away.
3. Then it reads the next 20 rows and returns them as the result. The ids run from 980,020 down to 980,001.

Result of this run

• To return 20 rows, it read 20,000 rows and discarded 19,980. The number of discarded rows grows in proportion to the page number. Every time you open a later page, it effectively reads all the earlier rows again.

Code

-- Page 1,000 (id descending = newest first)
SELECT id, title, created_at
  FROM post
 ORDER BY id DESC
 LIMIT 20 OFFSET 19980;

Assumptions of this model

It assumes that 1,000,000 posts are sorted by id and that id has an index (the primary key). That the rows skipped by OFFSET still have to be computed inside the server, so a large OFFSET might be inefficient, is the explanation in the PostgreSQL documentation (LIMIT and OFFSET). The same statement was not found in the MySQL documentation. If the sort key is not id but a column whose values can repeat, such as the creation time, the keyset condition must also include a column whose values do not repeat, as in (creation time, id). The numbers of rows are calculated values and were not measured on a real database. The content of the results was checked on a real SQL engine (SQLite). Both methods returned the same posts for the same page; after one new post was inserted, the first line of the next page with OFFSET was the last post of the previous page again, and with keyset the next post came.

Previous lab: Window functions · Next lab: Views, stored procedures, and triggers