CodePark/ questions / ORMs & the N+1 problem
START PRACTICINGPRACTICE
Backend question · Databases & SQL › ORMs & the N+1 problem

Why does this query get slower on later pages, and how does keyset (cursor) pagination fix it? What does keyset pagination give up?

SELECT * FROM posts
ORDER BY created_at DESC, id DESC
LIMIT 20 OFFSET 100000;

Later pages get slower because OFFSET does not jump to a position. The database must build the first 100,020 rows in order, then throw away 100,000 of them. So each page costs more than the page before it.

Offset pages also shift. If rows are inserted or deleted between two requests, users see duplicates or miss items.

Keyset pagination (also called cursor pagination) fixes this. It remembers the last row of the previous page and asks only for the rows after it:
WHERE (created_at, id) < ($1, $2) ORDER BY created_at DESC, id DESC LIMIT 20
With an index on (created_at, id), the database jumps straight to that position in the index. So every page costs about the same. New rows inserted at the same time do not shift the pages.

What keyset pagination gives up:

  • You cannot jump to a page by number, such as page 37.
  • The sort needs a unique tiebreaker, such as id.
  • The index must match the sort order.
  • The cursor must carry the sort values of the last row.
  • OFFSET reads and throws away all skipped rows, so the cost grows with page depth.
  • Offset pages shift when rows are inserted or deleted.
  • Keyset pagination uses an index to jump to the rows after the last seen sort key.
  • Keyset pagination needs a unique tiebreaker and a matching index.
  • Keyset pagination cannot jump to a random page.