Optimizing Pagination in PostgreSQL: OFFSET/LIMIT vs. Keyset

#postgres #pagination #database

Retrieving data efficiently is key to building optimized backends. Today, we discuss two approaches to scanning records in a table and why keyset pagination might help reduce the database CPU spikes you might notice whenever your long-running job reads all records in a table.

Imagine this: Your backend service has a daily job that fetches all users on the platform in a paginated way to perform some processing. What processing it does is not relevant for this discussion; we will only focus on how all users are fetched. It can use OFFSET/LIMIT-based pagination or keyset pagination to fetch these records.

-- Fetch the first 100 users
SELECT * FROM users ORDER BY id LIMIT 100 OFFSET 0;

-- Fetch the next 100 users
SELECT * FROM users ORDER BY id LIMIT 100 OFFSET 100;

-- Fetch the subsequent 100 users
SELECT * FROM users ORDER BY id LIMIT 100 OFFSET 200;

[users table ordered by id]
| id  | name     | ... |
|-----|----------|-----|
| 1   | Alice    |     |
| 2   | Bob      |     |
| ... | ...      |     |
| 100 | Hannah   |     |
| 101 | Ian      |     |
| 102 | Jane     |     |
| ... | ...      |     |
| 1000| Zach     |     |

Pagination using OFFSET/LIMIT:

Page 1 (OFFSET 0, LIMIT 100):
Fetches rows with id 1 to 100.

Page 2 (OFFSET 100, LIMIT 100):
Fetches rows with id 101 to 200.

Page 3 (OFFSET 200, LIMIT 100):
Fetches rows with id 201 to 300.

... and so on until all users are processed.

While this is a simplistic way to read through all the records, as the number of records in the table increases, so will the offset value. The database then must scan and discard more rows before reaching the desired page, leading to slower queries. In my professional experience, I’ve observed that when the database retrieves a large number of pages to access a specific result (by discarding preceding pages), this pattern can lead to a noticeable spike in CPU usage of the database instance.

This can also be exacerbated by the fact that, more often than not, we end up fetching all users in a loop (due to the nature of jobs that process data in bulk), resulting in multiple CPU-intensive queries one after another.

Let’s see how we can solve this problem using keyset pagination.

Keyset Pagination, offers an efficient alternative for navigating through large datasets. Instead of skipping a number of rows, it uses a reference point (a key) from the last retrieved row to fetch the next set of records.

How Keyset Pagination Works
Using the users table, we can paginate by continuously querying for users with an id greater than the last processed id.

-- Fetch the first 100 users
SELECT * FROM users WHERE id > 0 ORDER BY id ASC LIMIT 100;

-- Assume the last id from the previous batch is 100
-- Fetch the next 100 users
SELECT * FROM users WHERE id > 100 ORDER BY id ASC LIMIT 100;

-- If the last id is 200
SELECT * FROM users WHERE id > 200 ORDER BY id ASC LIMIT 100;

[users table ordered by id]
| id  | name     | ... |
|-----|----------|-----|
| 1   | Alice    |     |
| 2   | Bob      |     |
| ... | ...      |     |
| 100 | Hannah   |     |
| 101 | Ian      |     |
| 102 | Jane     |     |
| ... | ...      |     |
| 1000| Zach     |     |

Pagination using Keyset:

Page 1 (id > 0, LIMIT 100):
Fetches rows with id 1 to 100.

Page 2 (id > 100, LIMIT 100):
Fetches rows with id 101 to 200.

Page 3 (id > 200, LIMIT 100):
Fetches rows with id 201 to 300.

... and so on until all users are processed.

Let’s compare the EXPLAIN ANALYZE output of both queries to see which one is better.

For page 1:

explain analyse SELECT * FROM users ORDER BY id LIMIT 100 OFFSET 0;
                                                            QUERY PLAN                                                            
----------------------------------------------------------------------------------------------------------------------------------
 Limit  (cost=0.29..26.50 rows=100 width=348) (actual time=0.031..0.070 rows=100 loops=1)
   ->  Index Scan using users_pkey on users  (cost=0.29..2571.39 rows=9807 width=348) (actual time=0.030..0.058 rows=100 loops=1)
 Planning Time: 3.365 ms
 Execution Time: 0.125 ms
(4 rows)


explain analyse SELECT * FROM users WHERE id > 0 ORDER BY id ASC LIMIT 100;
                                                            QUERY PLAN                                                            
----------------------------------------------------------------------------------------------------------------------------------
 Limit  (cost=0.29..64.93 rows=100 width=348) (actual time=0.023..0.058 rows=100 loops=1)
   ->  Index Scan using users_pkey on users  (cost=0.29..2113.49 rows=3269 width=348) (actual time=0.022..0.044 rows=100 loops=1)
         Index Cond: (id > 0)
 Planning Time: 0.235 ms
 Execution Time: 0.084 ms

Not much difference, right? Let’s see what increasing offsets can do to the execution time. Also, keep an eye on the actual number of rows being fetched.

For page 201:

explain analyse SELECT * FROM users ORDER BY id LIMIT 100 OFFSET 20000;
                                                             QUERY PLAN                                                             
------------------------------------------------------------------------------------------------------------------------------------
 Limit  (cost=710.69..714.24 rows=100 width=42) (actual time=5.760..5.783 rows=100 loops=1)
   ->  Index Scan using users_pkey on users  (cost=0.29..1776.29 rows=50000 width=42) (actual time=0.033..4.911 rows=20100 loops=1)
 Planning Time: 0.096 ms
 Execution Time: 5.810 ms
(4 rows)


explain analyse SELECT * FROM users WHERE id > 20000 ORDER BY id ASC LIMIT 100;
                                                            QUERY PLAN                                                            
----------------------------------------------------------------------------------------------------------------------------------
 Limit  (cost=0.29..4.10 rows=100 width=42) (actual time=0.040..0.069 rows=100 loops=1)
   ->  Index Scan using users_pkey on users  (cost=0.29..1148.42 rows=30122 width=42) (actual time=0.038..0.058 rows=100 loops=1)
         Index Cond: (id > 20000)
 Planning Time: 2.370 ms
 Execution Time: 0.100 ms

As the offset increases, the OFFSET/LIMIT-based query has to read through more rows, thus fetching more pages, which results in increased execution time. On the other hand, the keyset pagination query always utilizes the index to fetch the required page.

We can also use keyset pagination when designing our APIs. For example, rather than accepting a limit and offset as API parameters, we can instead build something like this:

GET /api/users?limit=100&after_id=200

The only cons of using keyset pagination over OFFSET/LIMIT-based pagination include the lack of random access to a page and the need to keep track of the state (i.e., up to which ID we have fetched records).

In summary, OFFSET/LIMIT pagination is easy to implement but becomes inefficient with large tables. Keyset pagination offers a more efficient alternative by using indexed keys to fetch records directly. Despite requiring state management and lacking random page access, its efficiency benefits make keyset pagination the better choice for processing substantial amounts of data in backend services and APIs.