System Design HLD-03.02
Pagination patterns
Offset versus cursor (keyset) pagination: why deep offsets get slow, why inserts cause duplicates and skips, and how page tokens fix both.
The big idea
No API can return a million posts in one response. Large collections are split into pagesReturning a large result set in chunks, one page per request, with a way to ask for the next chunk., and the client asks for one page at a time. The obvious way is to number them: "page 3, 20 per page", which the database runs as "skip 40 rows, return 20". It is easy to build and easy to use, and it has two problems that only appear at scale.
First, skipping is not free: to skip 1,000,000 rows the database still walks past them, so deep pages get slower and slower. Second, the data moves while people read it. If new posts arrive at the top while you are on page 1, everything shifts down and page 2 repeats posts you already saw. Cursor paginationPaging by remembering the last item seen, such as its id or timestamp, and asking for items after it, instead of skipping a number of rows. fixes both by remembering where you were, not how far you have scrolled.
Think of reading a long scroll of paper that someone keeps adding to at the top. Counting "I have read 40 lines" breaks as soon as they add a line. Putting your finger on the last line you read does not.
How it works
Step 1: Offset pagination
SELECT * FROM posts ORDER BY created_at DESC LIMIT 20 OFFSET 40; -- page 3
The API exposes it as GET /posts?page=3&per_page=20. Clients can jump to any page and show "page 3 of 50". Under the hood the database must find and discard the first 40 rows before returning 20.
Step 2: Cursor (keyset) pagination
SELECT * FROM posts WHERE id < 1234 ORDER BY id DESC LIMIT 20; -- after post 1234
The client says "give me 20 items after the last one I saw". With an index on id (or created_at, id), the database jumps straight to that point and reads 20 rows, no matter how deep you are:
Step 3: See both problems in code
import sqlite3
db = sqlite3.connect(":memory:")
db.execute("CREATE TABLE posts (id INTEGER PRIMARY KEY, title TEXT)")
db.executemany("INSERT INTO posts VALUES (?, ?)", [(i, f"post {i}") for i in range(1, 101)])
def offset_page(page, size=5):
return [r[0] for r in db.execute(
"SELECT id FROM posts ORDER BY id DESC LIMIT ? OFFSET ?", (size, page * size))]
def cursor_page(after, size=5):
if after is None:
q, args = "SELECT id FROM posts ORDER BY id DESC LIMIT ?", (size,)
else:
q, args = "SELECT id FROM posts WHERE id < ? ORDER BY id DESC LIMIT ?", (after, size)
return [r[0] for r in db.execute(q, args)]
p1_off, p1_cur = offset_page(0), cursor_page(None)
db.execute("INSERT INTO posts VALUES (101, 'new post')") # someone posts while we read
db.execute("INSERT INTO posts VALUES (102, 'another')")
print("offset page 1:", p1_off, " page 2:", offset_page(1))
print("cursor page 1:", p1_cur, " page 2:", cursor_page(p1_cur[-1]))
for name, sql in [("offset", "SELECT id FROM posts ORDER BY id DESC LIMIT 5 OFFSET 50000"),
("cursor", "SELECT id FROM posts WHERE id < 50000 ORDER BY id DESC LIMIT 5")]:
plan = db.execute("EXPLAIN QUERY PLAN " + sql).fetchall()
print(f"{name} plan:", " | ".join(row[-1] for row in plan))Output
offset page 1: [100, 99, 98, 97, 96] page 2: [97, 96, 95, 94, 93]
cursor page 1: [100, 99, 98, 97, 96] page 2: [95, 94, 93, 92, 91]
offset plan: SCAN posts
cursor plan: SEARCH posts USING INTEGER PRIMARY KEY (rowid<?) Two new posts arrived between page 1 and page 2. Offset pagination returned 97 and 96 again, because the whole list shifted down by two. The cursor page continued exactly after 96. The query plans show the cost difference: the offset query scans the table, while the cursor query searches the primary key index.
Step 4: Page tokens
Public APIs usually hide the cursor inside an opaque page tokenAn encoded string returned with each page that the client passes back to get the next page. The server decides what is inside, usually the sort key of the last item.:
{ "data": [ ... ], "next_page_token": "eyJpZCI6MTIzNH0" }
The client sends ?page_token=eyJpZCI6MTIzNH0 for the next page and stops when there is no token. Because the token is opaque, the server can change what is inside it (a timestamp plus id, a shard number) without breaking clients. When sorting by a non-unique column like created_at, include the id as a tie-breaker: WHERE (created_at, id) < (?, ?), or rows with equal timestamps can be skipped.
Try it
Try this:
- With offset, press Next page twice, then New post arrives twice, then Next page again. The new page starts with two posts you already have, marked red.
- Switch to cursor and repeat. No duplicates: the new posts are at the top, behind you.
- Think about a deletion instead of an insertion. With offsets, which way does the list shift, and what does the reader miss?
Going deeper
What cursors give up
Cursor pagination cannot jump to "page 37" or show a total page count cheaply, and it only works along an indexed sort order. That is why infinite-scroll feeds, timelines and API listings use cursors, while admin tables with numbered pages and small data sets often keep offsets. Counting rows for "page 3 of 50" is itself expensive on big tables; many products show "more" instead of a total.
Consistency across pages
Even cursors do not give a frozen snapshot: an item edited between pages may move. If clients need a consistent view, the server can pin a snapshot or a timestamp in the token, at the cost of serving slightly older data. Most feeds accept small inconsistencies in exchange for freshness.
Trade-offs
| Option | Wins when | Loses when |
|---|---|---|
| Offset pagination | Small or slowly changing data, admin tables, jump-to-page UIs | Deep pages on large tables, and data that changes while users read |
| Cursor (keyset) pagination | Feeds, timelines, large APIs: fast at any depth, stable under inserts | Jumping to arbitrary pages and showing total counts |
| Opaque page tokens | Public APIs: the server can change the cursor format freely | Debuggability; clients cannot build or inspect tokens |
Common mistakes
- Using offsets on an infinite feed. Users see duplicates and deep pages time out.
- Sorting a cursor on a non-unique column without a tie-breaker, so items with equal values are skipped or repeated.
- Missing the index on the cursor column, which turns a seek back into a scan.
- Letting clients request unlimited page sizes. Always cap
limit.
Check yourself
-
Why does OFFSET 1000000 get slow?
Show answer
B. The database still has to walk past a million rows before returning the page Offset rows are found and discarded one by one, so the cost grows with the offset.
-
Two posts are added at the top while a user is on page 1 of an offset-paginated feed. What happens on page 2?
Show answer
B. The last two posts of page 1 appear again Everything shifts down by two, so page 2 starts two items earlier than intended.
-
What does a cursor-based request ask for?
Show answer
B. Items after the last item the client saw It continues from a remembered position, such as the last id, using an index.
-
Why include the id when the cursor sorts by created_at?
Show answer
B. As a tie-breaker so items with the same timestamp are not skipped or repeated Without a unique tie-breaker, items sharing a timestamp at a page boundary can be lost or duplicated.
Recap
- Offset pagination skips rows: simple, but slow on deep pages and unstable when data changes.
- Cursor pagination continues after the last item seen, using an index: fast and stable.
- Wrap cursors in opaque page tokens so the server can change them freely.
- Sort cursors on a unique key, or add the id as a tie-breaker.
- Use offsets for small, numbered tables; cursors for feeds and large APIs.
Next up
- Crack the system design round learning path