Pagination
Understanding the cost of large OFFSETs
In the previous chapter, I explained how offset-based pagination works using LIMIT and OFFSET.
In this chapter, I'll explain an important drawback of offset-based pagination when you paginate through a large number of rows.
How much work does the first page require?
Let's first see how much work PostgreSQL does when retrieving the first 100 orders.
Run the following statement:
12345EXPLAIN ANALYZESELECT id, payment_referenceFROM ordersORDER BY idLIMIT 100;You should see an execution plan similar to this:
1234567Limit (cost=0.29..3.92 rows=100 width=17) (actual time=0.100..0.600 rows=100.00 loops=1) Buffers: shared hit=4 -> Index Scan using orders_pkey on orders (cost=0.29..3628.29 rows=100000 width=17) (actual time=0.100..0.400 rows=100.00 loops=1) Index Searches: 1 Buffers: shared hit=4Planning Time: 0.800 msExecution Time: 0.800 msThe id column is the primary key of the orders table. PostgreSQL creates a B-tree index for the primary key, so there is already an index on id called orders_pkey.
A B-tree index keeps its indexed values in sorted order. Since orders_pkey is an index on id, PostgreSQL can scan the index from the smallest id to the largest. This already gives PostgreSQL the order required by ORDER BY id, so it doesn't need to sort the rows separately.
For now, focus on the Index Scan line and, specifically, the rows value inside the actual section:
1actual time=0.100..0.400 rows=100.00 loops=1The rows=100.00 value tells us that the Index Scan produced 100 rows.
Once PostgreSQL had produced those 100 rows, the Limit node had all the rows it needed, so the query could stop.
Therefore, to return the first 100 orders, PostgreSQL only had to retrieve 100 rows through the index scan.
What happens with a large OFFSET?
In the previous query, the Index Scan produced only 100 rows to return the first 100 orders.
Now suppose the user navigates to a much later page, where PostgreSQL needs to skip the first 90,000 orders before returning the next 100.
Let's use EXPLAIN ANALYZE to see how much work PostgreSQL does in that case.
Run the following statement:
123456EXPLAIN ANALYZESELECT id, payment_referenceFROM ordersORDER BY idLIMIT 100OFFSET 90000;You should see an execution plan similar to this:
1234567Limit (cost=3265.49..3269.12 rows=100 width=17) (actual time=49.300..49.400 rows=100.00 loops=1) Buffers: shared hit=922 read=246 -> Index Scan using orders_pkey on orders (cost=0.29..3628.29 rows=100000 width=17) (actual time=0.900..31.500 rows=90100.00 loops=1) Index Searches: 1 Buffers: shared hit=922 read=246Planning Time: 9.600 msExecution Time: 51.300 msAgain, focus on the rows value in the actual section of the Index Scan:
1actual time=0.900..31.500 rows=90100.00 loops=1This time, the Index Scan produced 90,100 rows.
Why?
The query contains:
12OFFSET 90000LIMIT 100Before PostgreSQL can return the 100 rows we want, it first has to move through the 90,000 rows specified by OFFSET. Those rows are skipped. PostgreSQL then returns the next 100 rows.
That is why the Index Scan produced 90,100 rows even though the query returned only 100 rows.
Comparing the two queries
Now compare the actual rows values from the two execution plans.
For the first page:
1Index Scan ... rows=100.00 loops=1For the query with OFFSET 90000:
1Index Scan ... rows=90100.00 loops=1Both queries return only 100 orders, but PostgreSQL performs very different amounts of work:
With no offset, the
Index Scanproduces 100 rows.With
OFFSET 90000, theIndex Scanproduces 90,100 rows.
This is the important drawback of offset-based pagination.
The larger the offset becomes, the more preceding rows PostgreSQL has to process before it can return the rows you requested.
Notice that PostgreSQL uses the orders_pkey index in both queries. The index allows PostgreSQL to retrieve the rows in id order without performing a separate sort, but it does not eliminate the work required by OFFSET.
So even with an index, a large OFFSET can make a pagination query increasingly expensive.
An alternative to large OFFSETs
We have seen that the work required by offset-based pagination increases as the OFFSET becomes larger.
But what if PostgreSQL could start near the rows we want instead of processing all the rows that come before them?
That is the idea behind keyset pagination.
In the next chapter, you will learn how keyset pagination works and compare it with the large-offset query you just analyzed.