Keyset pagination for performance in Rest API - Time & Space Complexity

Time Complexity: Keyset pagination for performance

O(1)

Understanding Time Complexity

When fetching data in pages, how fast the system responds matters a lot. We want to understand how the time to get each page changes as the data grows.

How does using keyset pagination affect the speed compared to other methods?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

GET /items?limit=10&after=12345

// Server query example:
SELECT * FROM items
WHERE id > 12345
ORDER BY id ASC
LIMIT 10;
    

This code fetches the next 10 items after a given ID using keyset pagination.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Database scans starting from a specific key (id > 12345).
• How many times: The database reads only the next 10 rows after the key, no scanning of previous rows.

How Execution Grows With Input

As the total number of items grows, the query still reads only the next 10 items after the last seen ID.

Input Size (n)	Approx. Operations
10	Reads about 10 rows
100	Reads about 10 rows
1000	Reads about 10 rows

Pattern observation: The number of operations stays roughly the same regardless of total data size.

Final Time Complexity

Time Complexity: O(1)

This means the time to fetch a page stays constant no matter how big the data grows.

Common Mistake

[X] Wrong: "Fetching page 100 will take 100 times longer than page 1 because it has to skip all previous items."

[OK] Correct: Keyset pagination uses a key to jump directly to the right spot, so it does not scan or skip all previous items.

Interview Connect

Understanding how keyset pagination keeps queries fast helps you design APIs that scale well. This skill shows you can think about performance as data grows.

Self-Check

"What if we changed the query to use offset-based pagination instead of keyset? How would the time complexity change?"