Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Building APIs: A Comparison Between Cursor and Offset Pagination?

news.ycombinator.com

Post reply on HN
Print view View original

11–20 of 27 posts

Re: Building APIs: A Comparison Between Cursor and Offset Pagination?

#11

Post by zeroonetwothree »

slver wrote: post #4

> you are forced to use infinite scroll which is not always the best solution. 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…

It can be useful for time ordered content where you can binary search for the appropriate time. Of course it would be nice if sites let you directly go to a time period but that seems to be nonexistent.

Re: Building APIs: A Comparison Between Cursor and Offset Pagination?

#12

Post by slver »

zeroonetwothree wrote: post #11
slver wrote: post #4

> you are forced to use infinite scroll which is not always the best solution. 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…

It can be useful for time ordered content where you can binary search for the appropriate time. Of course it would be nice if sites let you directly go to a time period but that seems to be nonexistent.

Seems like a "before" and "after" fields would serve users better, but I do understand the use case.

Re: Building APIs: A Comparison Between Cursor and Offset Pagination?

#14

Post by tdeck »

controlledchaos wrote: post #2

When I’ve worked with APIs that implemented pagination using cursors (Square), I really loved the ease of integration with my app. Writing a while loop that checks if the cursor is populated was better/faster than checking if the number of results from the last request was less than the requested number of rows.

I actually built some of those Square APIs! The reason we used cursors was correctness. If new records get added (say, in your transaction history) and you're consuming records newest first, limit+offset pagination will cause the client to miss or double-count some records. That might be OK when a user is scrolling through a listing, but it's a real problem when you're writing an app to compute your sales tax obligation.

Re: Building APIs: A Comparison Between Cursor and Offset Pagination?

#16

Post by inshadows »

ablol wrote: post #15

How does keyset based pagination deal with deletes? If the cursor/current key is deleted you lose your paging state. Or am I wrong?

AFAU you use keyset as upper/lower bounds in your SQL query, so deletion is not problem. Example:

Cursor ($ID:$DATE) = "123:2012-01-01"

Query: select * from tbl where id >= $ID and date >= $DATE limit 100

Re: Building APIs: A Comparison Between Cursor and Offset Pagination?

#17

Post by inshadows »

andrewingram wrote: post #5
ddek wrote: post #3

I've used cursor pagination on daemons doing large batch processing. It worked fine. If 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 g…

Important to call out here, but thanks to GraphQL’s unfortunate habit of using words which already have established meanings, when a lot of people talk about “cursor-based pagination”, they actually mean keyset pagination and not something that requires a server to maintain a stateful cursor. I’m guessing this is the meaning the OP was referring to.

I think it's common to call it cursor regardless of where it's maintained. I agree that it may confuse some people since there are cursors in SQL APIs. But the underlying concept is the same. Keyset does not convey the specific meaning.

Re: Building APIs: A Comparison Between Cursor and Offset Pagination?

#18

Post by inshadows »

slver wrote: post #7
alexchamberlain wrote: post #6

Earlier quoted context omitted.

A skip list would allow a user to skip to the Nth page, but I don't know of any database that offers one in the form of an index.

We can technically offer the users Nth page with cursors+offset hybrid, if we're fine with the computational demands (smaller than pure offset, but bigger than just prev|next|last). 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 lim…

You can also just query 5*100 IDs (keysets actually) and insert them into temporary table, all in a single SQL query, retrieve 100 full records in 2nd query, and get cursors for next/prev pages in third query (I'm not sure about this part, would need some windowing query I guess). It may seem wasteful, but in my experience it's fast (though I don't really have "Big Data" to test on). I do something similar to check if there's next/prev page. Temporary tables in SQLite are session local, deleted on close.

Re: Building APIs: A Comparison Between Cursor and Offset Pagination?

#19

Post by alexvoda »

I think viewing the problem of pagination as a choice between offset and keyset is a limiting mindset.

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.

Re: Building APIs: A Comparison Between Cursor and Offset Pagination?

#20

Post by alexvoda »

alexvoda wrote: post #19

I think viewing the problem of pagination as a choice between offset and keyset is a limiting mindset. 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…

Another positive example is any Discourse based forum which provides a timeline for scrolling. Jumping in the middle of the time interval is not the same as jumping in the middle of the resultset, but it serves the same purpose and is usually closer to what the user actually wants.
Post reply on HN