Keyset pagination for performance in Rest API - Deep Dive

Overview - Keyset pagination for performance

What is it?

Keyset pagination is a method to split large lists of data into smaller parts for easier viewing or processing. Instead of counting pages, it uses a unique marker from the last item seen to fetch the next set. This approach helps avoid slow database queries when dealing with big data. It is often used in web APIs to deliver data efficiently.

Why it matters

Without keyset pagination, systems often use page numbers which can cause slow responses and inconsistent results when data changes. This can frustrate users waiting for data or cause errors in applications. Keyset pagination solves this by making data retrieval faster and more reliable, improving user experience and system performance.

Where it fits

Learners should first understand basic pagination and database queries. After mastering keyset pagination, they can explore cursor-based APIs, infinite scrolling, and advanced database indexing techniques.

Mental Model

Core Idea

Keyset pagination fetches the next data chunk by remembering the last item's unique key instead of counting pages.

Think of it like...

Imagine reading a book with a bookmark. Instead of counting pages to find where you left off, you just open the book where the bookmark is and continue reading.

┌───────────────┐
│ Data List     │
├───────────────┤
│ Item 1        │
│ Item 2        │
│ ...           │
│ Item N (last) │ ← Use this item's key as marker
└───────────────┘
       ↓
Fetch next items where key > last item's key

Build-Up - 7 Steps

1

Foundation

Understanding basic pagination

Concept: Learn how simple pagination splits data into pages using page numbers and limits.

In basic pagination, you ask for page 1, page 2, etc., each with a fixed number of items. For example, page 1 returns items 1-10, page 2 returns 11-20, and so on. This uses SQL queries with OFFSET and LIMIT to skip and fetch data.

Result

You get a fixed number of items per page, but queries slow down as page numbers grow.

Knowing how basic pagination works helps you see why it becomes inefficient with large data sets.

2

Foundation

Problems with offset pagination

Concept: Discover why using OFFSET in queries can cause slow performance and inconsistent data.

OFFSET makes the database skip rows before returning results. For large offsets, this means scanning many rows, which is slow. Also, if data changes between requests, page contents can shift, causing duplicates or missing items.

Result

Pagination becomes slow and unreliable as data grows or changes.

Understanding these problems motivates the need for a better pagination method.

3

Intermediate

Introducing keyset pagination concept

Concept: Learn how keyset pagination uses the last seen item's unique key to fetch the next set.

Instead of OFFSET, keyset pagination uses a WHERE clause to get items with keys greater than the last item's key. For example, if the last item's ID was 100, the next query fetches items with ID > 100, ordered by ID, limited to the page size.

Result

Queries run faster because the database uses indexes efficiently and avoids scanning skipped rows.

Knowing that keyset pagination uses a marker instead of counting rows explains why it is faster and more stable.

4

Intermediate

Implementing keyset pagination in REST APIs

🤔Before reading on: Do you think the client or server should track the last item's key for pagination? Commit to your answer.

Concept: Understand how REST APIs pass the last item's key as a cursor to fetch the next page.

The server returns data plus a cursor (like last item's ID). The client sends this cursor in the next request to get the following items. This keeps pagination stateless and efficient. Example URL: /items?after=100&limit=10

Result

Clients can navigate pages smoothly without heavy server load or inconsistent data.

Knowing how cursors work in APIs helps design scalable and user-friendly data navigation.

5

Intermediate

Handling sorting and multiple keys

🤔Before reading on: Can keyset pagination work with sorting on multiple columns? Commit to yes or no.

Concept: Learn how to paginate when sorting by more than one column using composite keys.

When sorting by multiple columns, the cursor includes all sorted columns. For example, if sorting by date and ID, the cursor might be (date, ID). The query uses WHERE (date, ID) > (last_date, last_id) to fetch next items. This keeps order consistent and pagination correct.

Result

Keyset pagination supports complex sorting without losing performance or correctness.

Understanding composite keys in pagination unlocks advanced data navigation scenarios.

6

Advanced

Dealing with deletions and data changes

🤔Before reading on: Do you think keyset pagination can handle data deletions without issues? Commit to yes or no.

Concept: Explore how keyset pagination behaves when data is added or removed during navigation.

Keyset pagination is stable for new data added after the cursor but can skip or repeat items if data before the cursor is deleted or updated. To handle this, APIs may include timestamps or versioning, or refresh cursors periodically to avoid confusion.

Result

Pagination remains mostly consistent, but developers must plan for edge cases with changing data.

Knowing the limits of keyset pagination with dynamic data helps build robust applications.

7

Expert

Optimizing keyset pagination with database indexes

🤔Before reading on: Is it enough to have any index for keyset pagination to be fast? Commit to yes or no.

Concept: Understand how proper indexing supports fast keyset pagination queries.

Keyset pagination relies on indexes matching the sorting and filtering keys. For example, if paginating by (date, ID), a composite index on (date, ID) is needed. Without correct indexes, queries degrade to full scans. Database explain plans help verify index usage.

Result

With proper indexes, keyset pagination queries run in milliseconds even on large tables.

Knowing how indexes interact with pagination queries is crucial for real-world performance tuning.

Under the Hood

Keyset pagination works by using the database's ability to quickly find rows greater than a given key using indexes. Instead of skipping rows, it uses a WHERE clause with comparison operators on the key columns. The database uses B-tree or similar indexes to jump directly to the starting point, then reads the next rows in order. This avoids scanning or counting skipped rows, reducing CPU and IO load.

Why designed this way?

Traditional offset pagination was simple but inefficient for large datasets. Keyset pagination was designed to leverage database indexes for speed and consistency. It trades the convenience of page numbers for performance and stability, especially important for real-time or large-scale applications.

┌───────────────┐
│ Client Request│
│ with cursor   │
└──────┬────────┘
       │
       ▼
┌───────────────┐
│ Server Query  │
│ WHERE key > X │
│ ORDER BY key  │
│ LIMIT N       │
└──────┬────────┘
       │
       ▼
┌───────────────┐
│ Database uses │
│ index to jump │
│ to key X+1    │
└──────┬────────┘
       │
       ▼
┌───────────────┐
│ Returns next  │
│ N items + new │
│ cursor        │
└───────────────┘

Myth Busters - 4 Common Misconceptions

Quick: Does keyset pagination allow jumping directly to page 10 without fetching pages 1-9? Commit to yes or no.

Common Belief: Keyset pagination lets you jump to any page number directly like offset pagination.

Reality: Keyset pagination does not support jumping to arbitrary pages because it relies on the last seen key, not page numbers.

Why it matters: Expecting random page access can lead to wrong API designs and user confusion.

Quick: Is keyset pagination always faster than offset pagination regardless of data size? Commit to yes or no.

Common Belief: Keyset pagination is always faster than offset pagination no matter what.

Reality: For very small datasets or first pages, offset pagination can be just as fast or faster. Keyset pagination shines with large data and deep pages.

Why it matters: Choosing keyset pagination blindly can add complexity without benefit for small data.

Quick: Can keyset pagination handle sorting by non-unique columns without extra keys? Commit to yes or no.

Common Belief: You can paginate by any column alone, even if it has duplicates, without issues.

Reality: Sorting by non-unique columns requires adding a unique tie-breaker key to avoid skipping or repeating items.

Why it matters: Ignoring this causes missing or duplicated data in pagination results.

Quick: Does keyset pagination guarantee perfect consistency if data changes during navigation? Commit to yes or no.

Common Belief: Keyset pagination always returns consistent results even if data is added or deleted during paging.

Reality: It improves consistency but cannot guarantee perfect stability if data changes before the cursor.

Why it matters: Assuming perfect consistency can cause bugs or user confusion in dynamic data environments.

Expert Zone

1

Keyset pagination requires careful cursor encoding and decoding to avoid exposing internal database keys directly to clients.

2

Composite keys for sorting must match index order exactly to maintain query performance and correctness.

3

APIs often combine keyset pagination with caching or snapshotting to handle data changes gracefully.

When NOT to use

Avoid keyset pagination when users need random access to arbitrary pages or when data sets are very small. In those cases, offset pagination or simple list fetching is simpler and sufficient.

Production Patterns

In production, keyset pagination is used in social media feeds, messaging apps, and large product catalogs. It is combined with cursor tokens encoded as opaque strings and integrated with API rate limiting and caching layers.

Connections

Cursor-based navigation in databases

Keyset pagination builds on the idea of cursors to track position in data streams.

Understanding database cursors helps grasp how keyset pagination maintains state without offsets.

Infinite scrolling in user interfaces

Keyset pagination is often the backend technique powering infinite scroll features.

Knowing keyset pagination explains why infinite scroll can load data smoothly without delays.

Supply chain logistics tracking

Both track progress by a unique marker rather than counting steps.

Recognizing this pattern in logistics helps appreciate keyset pagination as a general progress-tracking method.

Common Pitfalls

#1 Using OFFSET with large page numbers causing slow queries

Wrong approach:

SELECT * FROM items ORDER BY id LIMIT 10 OFFSET 1000000;

Correct approach:

SELECT * FROM items WHERE id > last_seen_id ORDER BY id LIMIT 10;

Root cause:

Misunderstanding that OFFSET skips rows inefficiently instead of using indexed keys.

#2 Paginating by a non-unique column without tie-breaker causing duplicates

Wrong approach:

SELECT * FROM items WHERE date > '2023-01-01' ORDER BY date LIMIT 10;

Correct approach:

SELECT * FROM items WHERE (date, id) > ('2023-01-01', last_id) ORDER BY date, id LIMIT 10;

Root cause:

Ignoring that sorting columns must uniquely identify rows to avoid repeated or missing items.

#3 Exposing raw database keys as cursors to clients

Wrong approach:

Returning cursor=12345 directly in API responses.

Correct approach:

Encoding cursor as opaque string like cursor=eyJpZCI6MTIzNDV9 (base64 JSON).

Root cause:

Not considering security and abstraction best practices for API design.

Key Takeaways

Keyset pagination improves performance by using the last item's unique key instead of page numbers.

It avoids slow database scans caused by OFFSET, making it ideal for large or changing datasets.

Keyset pagination requires careful handling of sorting keys and cursor encoding for correctness and security.

It does not support jumping to arbitrary pages but enables smooth, consistent navigation through data.

Proper database indexing is essential to unlock the full speed benefits of keyset pagination.

Practice

1. What is the main advantage of using keyset pagination over traditional offset-based pagination in REST APIs?

easy

A. It requires less server memory by caching all pages in advance.

B. It allows jumping to any page number directly without sequential access.

C. It improves performance by avoiding slow offset queries on large datasets.

D. It automatically sorts data in descending order without extra code.

Solution

1. Step 1: Understand offset-based pagination issues

   Offset pagination uses a page number and offset, which becomes slow on large datasets because the database must skip many rows.

2. Step 2: Recognize keyset pagination benefits

   Keyset pagination uses a fixed key (like an ID) to fetch the next set of rows, avoiding the costly skip operation and improving performance.

3. Final Answer:

   It improves performance by avoiding slow offset queries on large datasets. -> Option C

4. Quick Check:

   Keyset pagination = better performance [OK]

Hint: Keyset uses keys, not offsets, for faster queries [OK]

Common Mistakes:

• Thinking keyset allows random page jumps
• Assuming keyset caches all data
• Believing keyset changes sort order automatically

2. Which of the following is the correct SQL snippet to implement keyset pagination for a table users ordered by id?

easy

A. SELECT * FROM users ORDER BY id LIMIT 10 OFFSET 20;

B. SELECT * FROM users WHERE id > 20 ORDER BY id LIMIT 10;

C. SELECT * FROM users WHERE id = 20 ORDER BY id LIMIT 10;

D. SELECT * FROM users ORDER BY id DESC LIMIT 10 OFFSET 20;

Solution

1. Step 1: Identify keyset pagination syntax

   Keyset pagination uses a WHERE clause with a key (like id > last_seen_id) and a LIMIT to fetch the next page.

2. Step 2: Analyze each option

   SELECT * FROM users WHERE id > 20 ORDER BY id LIMIT 10; uses WHERE id > 20 with ORDER BY id LIMIT 10, which matches keyset pagination logic.

3. Final Answer:

   SELECT * FROM users WHERE id > 20 ORDER BY id LIMIT 10; -> Option B

4. Quick Check:

   Keyset uses WHERE key > last_key [OK]

Hint: Keyset uses WHERE with key comparison, not OFFSET [OK]

Common Mistakes:

• Using OFFSET instead of WHERE for pagination
• Using equality (=) instead of greater than (>)
• Not ordering results by the key column

3. Given this REST API endpoint using keyset pagination:

GET /items?last_id=50&limit=5

And the database table items with IDs: [45, 47, 50, 52, 55, 60, 65], what will be the IDs returned by this request?

medium

A. [52, 55, 60, 65]

B. [45, 47, 50, 52, 55]

C. [52, 55, 60, 65, 70]

D. [51, 52, 53, 54, 55]

Solution

1. Step 1: Understand keyset pagination with last_id=50

   The API returns items with IDs greater than 50, limited to 5 results.

2. Step 2: Select IDs greater than 50 from the list

   IDs greater than 50 are [52, 55, 60, 65]. There are only 4 such items, so all are returned.

3. Final Answer:

   [52, 55, 60, 65] -> Option A

4. Quick Check:

   IDs > 50 limited to 5 = [52, 55, 60, 65] [OK]

Hint: Return items with ID > last_id, up to limit [OK]

Common Mistakes:

• Including items with ID equal to last_id
• Using offset instead of key comparison
• Assuming IDs are continuous numbers

4. You have this SQL query for keyset pagination:

SELECT * FROM orders WHERE order_date > '2024-01-01' ORDER BY order_date LIMIT 10;

But it returns duplicate rows when new orders are added. What is the likely cause?

medium

A. Ordering by a non-unique column causing duplicates

B. LIMIT value is too high causing repeats

C. Missing OFFSET clause to skip duplicates

D. Using > instead of >= in WHERE clause

Solution

1. Step 1: Identify ordering column uniqueness

   Ordering by order_date alone can cause duplicates if multiple rows share the same date.

2. Step 2: Understand keyset pagination requirements

   Keyset pagination requires ordering by a unique column or combination to avoid duplicates and missing rows.

3. Final Answer:

   Ordering by a non-unique column causing duplicates -> Option A

4. Quick Check:

   Order by unique key to avoid duplicates [OK]

Hint: Order by unique keys to prevent duplicates [OK]

Common Mistakes:

• Thinking OFFSET fixes duplicates
• Using >= instead of > causes duplicates
• Assuming LIMIT controls duplicates

5. You want to implement keyset pagination on a REST API that returns products sorted by price ascending, then by id ascending to break ties.
Which SQL WHERE clause correctly fetches the next page after last product with price=100 and id=50?

hard

A. WHERE price > 100 OR id > 50

B. WHERE price >= 100 AND id > 50

C. WHERE price > 100 AND id > 50

D. WHERE price > 100 OR (price = 100 AND id > 50)

Solution

1. Step 1: Understand multi-column keyset pagination

   When ordering by multiple columns, the WHERE clause must handle the first column and then the second to break ties.

2. Step 2: Analyze the correct condition

   The correct condition is price > 100 OR (price = 100 AND id > 50) to get all rows with higher price or same price but higher id.

3. Final Answer:

   WHERE price > 100 OR (price = 100 AND id > 50) -> Option D

4. Quick Check:

   Multi-column keyset uses OR + AND for tie-break [OK]

Hint: Use OR with AND to handle multi-column keys [OK]

Common Mistakes:

• Using AND instead of OR for first column
• Ignoring tie-break column in WHERE clause
• Using >= instead of > causing duplicates