Building APIs: A Comparison Between Cursor and Offset Pagination?
I have been mostly relying on offsets for implementing paging. It is more straightforward in implementation but I find cursor based pagination more intuitive in usage; plus it has better support for real-time data but on the negative side you are forced to use infinite scroll which is not always the best solution.
I was curious if anybody has any experience with these two approaches in their projects? And what are some other advantages and disadvantages on this? [1]
[1] I wrote this piece a while back but was thinking of updating it further: https://betterprogramming.pub/building-apis-a-comparison-between-cursor-and-offset-pagination-88261e3885f8
26 comments
[ 2.8 ms ] story [ 72.6 ms ] threadIf you're using a cursor, you should be iterating the entire (or at least most of) the result set over the course of the connection. I wouldn't think they're appropriate to API's, because maintaining the cursor state between requests sounds painful.
Offset is the only way to paginate arbitrarily sorted data sets, unless you plan on going hard on indexing. The performance falls off as the offset grows. You'll also have issues with apparent 'duplicates' between pages.
Keyset pagination is preferred if the data is usually sorted in one way. Most infinite scrolling falls into this category. Each row has a unique 'counter', which is (usually) monotonic. To skip pages, filter rows whose counter is later than the last row in the current page. This is fast and has no duplicates. However, your sorting options are constrained, as you must have an index for each sort option.
Keyset and offset can be combined to eliminate the duplication defect of offset alone. The performance issue will still be there. This becomes an engineering decision - in most use cases, the large offset perf hits don't really happen (aside from abuse, which almost always happens).
I’m guessing this is the meaning the OP was referring to.
You're not forced to. You could instead Show "8964 Results Total: Previous 100 | Next 100 ... Last 100" which in practice is the same as pagination.
Sure the user can't click in the MIDDLE of the page set, but what kind of a use case is that, anyway.
Anyway, cursor offsets are fundamentally O(1), and offsets are fundamentally O(N) where N is the offset. As a younger programmer, I used to wonder what is this algorithmic magic the database uses, so it knows how to compute offset 10000 without sorting and looking at the first 10000 values I sort by. Well? No magic, it just hustles through it and delivers. But slowly.
Let's say we want to offer the user 5 pages, 100 records per page:
prev (7) | next (9) | 10 | 11 | 12 | 13 | 14 | ... | last
If you click "13", you'd need to query with cursor for page 9 (i.e. id > last rec of page 8) , and offset 400 limit 100.
This way offset never get gigantic, because if you show up to 5 pages to the user, you need to offset up to 5 * 100 records at a given time (combined with the cursor).
The thing is, the cursor is a lookup on an indexed sorted index, it's O(log N), it's effectively free already. And we add the cost of materializing the slice (if even just in memory), and introducing the potential of DoS-ing our server with this temporary state if we're not careful.
insert into temp select id, date from tbl where id >= c_id and date >= c_date order by date desc, id desc limit 500
I don't see doing any offset over the whole dataset.
> And we add the cost of materializing the slice (if even just in memory)
The alternative is to transfer 400 full rows of data that will be used just to compute pages.
> and introducing the potential of DoS-ing our server with this temporary state if we're not careful.
I don't see any DoS vector specific to this but I'd be thrilled to learn of one.
So you pick 500 keys and put them into a temp table. Then what? You still have to show a page that's 100 of those 500 keys.
> The alternative is to transfer 400 full rows of data that will be used just to compute pages.
The alternative is the hybrid cursor+offset approach, which doesn't transfer 400 full rows of anything.
> I don't see any DoS vector specific to this but I'd be thrilled to learn of one.
I generate enough sessions to fill your RAM with temp tables.
I don't need to use offset. I can use limit. And also, offset in 500 rows dataset never was a problem.
> I generate enough sessions to fill your RAM with temp tables.
o_O These tables contain only keys. In your approach you're going to have 500 keys in memory as well. Moreover, I'm not wasting resources by transferring them in my application. I'm in fact saving resources. You're making things up.
EDIT: Are you arguing about performance impact of scanning 500 rows vs 100 rows (though I don't understand your approach either, you're skipping - scanning - 400 rows as well)? The problem of paging is scanning whole dataset.
So let's focus on the main issue I spotted:
> In your approach you're going to have 500 keys in memory as well.
That's not true at all. At no point I have 500 of anything in memory. So there's some big misunderstanding here about what I propose (and hence how it compares with your alternative).
If you want to go over my original comments again and ask questions to understand the concept, I'm at your service.
Cursor+offset doesn't scan the whole dataset, and saving subsets in temp tables doesn't improve on it (i.e. temp tables make things slower). But I'm not sure where we misunderstand each other.
1. You start at the cursor.
2. You offset at most 400 records from the cursor.
3. You read 100 records.
The first point means you don't scan the whole dataset. The second point means for the next 5 pages you offset max 400 records. The third point means you read nothing, except what you want to display immediately.
It's also sometimes called keyset pagination - there's a good article about that here: https://use-the-index-luke.com/no-offset
I implemented it in https://datasette.io - it's quite tricky to build if you want to support arbitrary sort orders.
Cursor based pagination is way better, since the backend aggregation bucket size is capped by the page size times the number of nodes used for a distributed sort (essentially you aggregate on page sized priority queues, one per node, and then aggregate them).
Cursor ($ID:$DATE) = "123:2012-01-01"
Query: select * from tbl where id >= $ID and date >= $DATE limit 100
Two things that come to mind:
1. Depending on the technology there may be alternatives: https://www.citusdata.com/blog/2016/03/30/five-ways-to-pagin...
2. There may be ways to provide pagination through filtering instead of offsetting
Probably most common ordering on big resultsets are either by time (eg. emails) or alphabetic (eg. a dictionary).
When searching in a dictionary you do a binary search followed by page navigation when close: open it approximatively where you think the target word might be, then jump in the appropriate direction a number of times then go page by page until the target is found. If you have tabs to jump to the appropriate starting letter or group of starting letters that can be implemented as filtering but the UI can look like pagination.When going through pages of emails, to the user, jumping through pages or jumping through days may be the same thing.
This of course means pages may no longer be the same length.
Infinite scrolling is a poor UI for multiple reasons and it is an antagonistic UI (you don't want users to browse long datasets so you make it HARD). A determined user will just generate more requests. Instead of making it hard to explore a dataset, make it easy. Make it intuitive to filter and make it easy to reverse the ordering (costs nothing for the DB).
If you only provide one ordering and infinite scrolling, the only effect is frustration, broken scroll wheels, and plenty of requests. An example of this is FB Messenger. You can only scroll or search by words. So if I don't remember keywords, just the approximate time and I have confidence I can reach the chat then the only way is to scroll and scroll. Compare Telegram which lets you filter by date.