Hacker News Reader

Comment by terandle | Hacker News Reader

Wish this article would have gone into details about how cursor based pagination is actually implemented. Like they did for the other options by showing SQL. Is this something the database engine has to provide support for?

View on HN

Check https://use-the-index-luke.com/no-offset as a better reference.

But in most SQL databases, cursors are something you implement and parse at the application layer, and translate to a WHERE clause on the (hopefully indexed) column you're ordering on. That turns the O(N) "OFFSET" into a O(log(n)) index seek.

Many databases have actual cursor implementations which are transactional. That means you’ll get a consistent view at the point in time you created the cursor.

That said, they tend to live only as long as the db connection (with some exceptions), so yeah you need some application work to make it sane.

How is a cursor different from key set in that case?

It's not in that case, cursors can be implemented however you want though. Its an abstraction, that prevents you from having to change the schema of the API when you change the implementation.

You can do something like the following in application code.

Imagine a table with the following schema/data: id=1,created_at='2022-28-05T18:00Z' id=2,created_at='2022-28-05T18:00Z' id=3,created_at='2022-28-05T18:00Z'

To retrieve articles in order of descending creation time, our sort order would be: created_at DESC, id DESC

The last item in the ORDER BY query should be a unique key to ensure we have consistent ordering across multiple queries. We must also ensure all supported sort columns have an INDEX for performance reasons.

Assume our application returns one article at a time, we have already retrieved the first article in the result set. Our cursor must include information for that last records ORDER BY values, e.g. serialize('2022-28-05T18:00Z,3'), for example purposes I will use base64, so our cursor is MjAyMi0yOC0wNVQxODowMFosMw==.

When the user requests the next set of results, they will supply the cursor and it will be used to construct a WHERE (AND) expression: created_at < '2022-28-05T18:00Z' OR (created_at = '2022-28-05T18:00Z' AND id < 3)

So our query for the next set of results would be: SELECT * FROM articles WHERE (created_at < '2022-28-05T18:00Z' OR (created_at = '2022-28-05T18:00Z' AND id < 3) ORDER BY created_at DESC, id DESC LIMIT 1

For queries with more than 2 sort columns the WHERE expression will slightly increase in complexity but it need only be implemented once. If the sort order direction is flipped, make sure to adjust the comparator appropriately, e.g. for 'DESC' use '<' and for 'ASC' use '>'.

Isn't that basically just a trivial extension of what they article calls "keyset based pagination"?

I'm not complaining since this is also what I usually do, I'm just wondering of theres more to it.

Oftentimes under the hood, cursor based paging IS keyset paging. The difference is that the keyset is obfuscated, which can allow the implementation to change without changing the API call.

Makes total sense. It also seems trivially automatable on the surface. Echoing GP: Is this an existing DBMS feature? If not, why not?

How do you handle removal?

I haven't had a need to implement this but something like the following should work to provide the same* records regardless of insertion/deletion.

* data of the record may have been updated, but if there are 1,000 records total, paginating in either direction will always return those same 1,000 records regardless of insertion/deletion.

- Filter by created_at <= time the endpoint first returned a result.

- Utilize soft deletes, where deleted_at IS NULL OR deleted_at < time the endpoint first returned a result.

Any keys allowed to be used in the ORDER BY query should also be immutable.

Some database engines will support Cursors like this, but from what I can gather Cursor based navigation is a wrapper around KeySet or page navigation, but base64 encoded parameters.

Making the implementation details of pagination unimportant to the API layer the user uses.

No need for anything special, you would just query with something like "SELECT whatever FROM Table WHERE cursor>value ORDER BY cursor LIMIT n". Obviously there needs to be an index over the columns of the cursor, but any reasonable engine should allow you to add that effortlessly.

The complication comes from having a cursor over results that are sorted on multiple columns. It's not incredibly difficult to implement, but it can certainly be annoying to do, especially if you want to support before+after cursor as well.

Reply on news.ycombinator.com