Pagination Strategies

How to return a large, changing list one page at a time: why offsets slow down and shift, how keyset queries with a tiebreaker fix both, what goes into an opaque page token, and how to handle totals, previous pages and sharded search.

Overview

Pagination means returning a long list a page at a time: a feed, search results, an order history, an export. Every list endpoint needs it from the first release; Google's API guidelines point out that adding it later breaks clients that expected the whole list.

There are two families. Offset pagination says 'skip N rows, then give me 20'. Keyset pagination (also called seek or cursor pagination) says 'give me 20 rows that come after this one'. Offsets are simple and allow jumping to page 50, but they slow down as pages get deeper, and they repeat or skip items when the list changes between requests. Keysets cost the same on every page and stay correct under inserts, but cannot jump.

The API Design chapter introduces cursor pagination for a REST endpoint. This chapter goes underneath it: the exact SQL, the tiebreaker, what a page token contains, going backwards, totals, and paging through a sharded search index.

What you will be able to do

  • Explain, with numbers, why deep offset pages are slow and why they repeat items.
  • Write a correct keyset query for a sort on a non-unique column, and the index that serves it.
  • Design an opaque page token: what it holds, how it is checked, and when it expires.
  • Serve a previous page, a has-more flag and a total without scanning the whole table.
  • Choose a pagination scheme for a feed, an admin table, a search page and a bulk export.

Key concepts

  • Offset and limit
  • Keyset (seek) pagination
  • Tiebreaker column
  • Row value comparison
  • Opaque page tokens
  • Limit plus one
  • Previous page
  • Total counts
  • search_after and PIT

Interview questions

  • Why does offset pagination get slower on deeper pages?
  • Write a keyset query for a feed sorted by created_at, where created_at is not unique.
  • What problems does offset pagination cause when data changes during paging?
  • What would you put in a page token, and how do you protect it?
  • How do you show a total count on a table with 500 million rows?
  • How do you implement a previous-page button with keyset pagination?
  • How do you page deeply through Elasticsearch results?

Sign up free to read the full topic

More System Design topics

Start free on Cariara · Coding problems · System design studio