Offset pagination and its problems

You may have seen requests looking like https://api.example.com/posts?limit=10&offset=50. This is offset pagination. We are saying skip 50 rows and give me the next 10.

SELECT * FROM posts
LIMIT 10 OFFSET 50  -- "skip 50, give me next 10"

Problems with this approach:

Database must scan through all 50 rows to skip them
Gets slower as offset increases (page 1000 means scanning 1000 rows!)
Can miss/duplicate records if new posts are added while paginating
Still has to sort everything first

PS. It's still useful when you want to show page results and items wouldn't update too often e.g. booking system search results. Because the experience of having pages here is more natural and desired to users.

Cursor pagination and its benefits

Cursor pagination is when you provide a cursor parameter to the API. This cursor is the last item seen in the previous page (id of the last item). The API then uses this cursor to figure out where to start the next page from. Stripe for example uses this e.g. with starting_after parameter.

Looks like this: https://api.example.com/posts?starting_after=1000, 1000 being the id of the last item in the previous page.

SELECT * FROM posts
WHERE id < 1000    -- Last ID user saw
ORDER BY id DESC   -- Newest first (5,4,3,2,1)
LIMIT 10;

Why it's better:

Uses PRIMARY KEY index (comes free with table)
Can jump directly to ID 1000 in index
Consistent performance regardless of page depth
No missed/duplicated records
Works great with AUTO_INCREMENT ids since they're:
- Monotonic (always increasing)
- Map to creation order
- Already indexed

Response example:

// Request
GET /api/posts?limit=10  // First page
GET /api/posts?cursor=1000&limit=10  // Next pages (1000 = last seen id)

// Response
{
  "posts": [...],
  "hasMore": true,
  "nextCursor": "990"  // ID of last item in this page
}

990 because sorted DESC. Larger ids would mean newer posts.

Ordering

DESC = highest to lowest (5,4,3,2,1) = newest first
ASC = lowest to highest (1,2,3,4,5) = oldest first

How is sorting efficient?

The key is that we're using the PRIMARY KEY index, which is already sorted!

Think of an index like a pre-sorted phone book:

PRIMARY KEY index is already stored like:
id: 1 -> data
id: 2 -> data
id: 3 -> data
id: 4 -> data
id: 5 -> data

When we say:

WHERE id < 1000
ORDER BY id DESC

The database:

Goes to index (already sorted!)
Finds position of id 1000
Walks backwards through the index (for DESC)
Takes 10 items

Efficient Pagination notes

Comments

More from this blog

Become a cracked product engineer today

Bipedal, humanoid, and the words for creature shapes in games

Lerp and smoothstep, what they actually do

IK and FK, what they actually are

How to make your textures fast on the GPU

Ordering

How is sorting efficient?

Command Palette

Comments

More from this blog

Offset pagination and its problems

Cursor pagination and its benefits

Ordering

How is sorting efficient?