The APIs I generally work will abstract away most of the scroll context configuration stuff, and just return a page of results, plus the ScrollId for the next page.
Elasticsearch’s search_after is a pleasure to use. So easy especially with nullable fields, where the equivalent SQL can get really, really messy with just a few columns.
Anyway solving something “basic” languages like php or node solved eons ago is a bit lame and silly. “Cursors” and pagination have been solved way before HN’s lame plebe discovered wanna be “software engineering”. Cool stuff for a f(w)aang(k) worker. Ah yeah ai might help lol?
> One deficiency you can see is that it’s impossible to generate a “previous page” link
It is perfectly possible to have a "previous page" link. Your pagination needs to support "before" cursor semantic, allowing a consumer to retrieve the N items before the row identified by the cursor.
It is also possible to create a "next page". You only need to take your current page's last id and use it in your query like "where id > current_last_element_id".
"first page" and "last page" are possible as well, simply do "where id > 0" for first and "where id <= (subselect max id)".
You may need to invert order here and there, but it is perfectly possible to use cursor base pagination in a GUI as long as you don't need to provide jumping to a specific page number.
Indefinitely. It's not the kind of cursor that a database gives out, which is a resource. A cursor in this context is just a pointer to some position in a set of results, something like "all results where date created is greater than $X". For SQL implementations, check out:
It depends on the implementation. For example, the post mentions using Elasticsearch in production "which naturally supports this cursor stuff" but it has a max keep alive context duration of 24 hours[1] by default. This limit can be extended on a cluster level but it's unlikely they have it set to indefinite. Which means that their search context is likely only valid for 24 hours.
I tried to make cursor based pagination work in a GraphQL API over MySQL and failed. The problem was that it had to work for a very wide range of SQL statements, with arbitrary order clause, where clause and at least one join.
Offset pagination works fine in this scenario. But something like `where id > 42 limit 100` fails with an arbitrary sorting order on non-unique columns. All I could do would be to generate the unpaginated result, then find the cursor within it, and take the limit after that. Which is too inefficient to be practical.
You sort by your fields and then by id. You also include those field values along with id into your “cursor”. This is complicated for general case but possible to implement.
I implemented this for Datasette. The key is to use the primary key as a "tie breaker" - so you sort by the specified column first and then by the primary key.
Another reason to use cursors is to avoid the problem of repeated or skipped elements caused by concurrent edits. If you use offsets and you’re on page 10, and someone deletes an item on page 1, the whole list shifts and you can accidentally skip an item on page 11. Likewise if someone adds an item on page 1 and you’re on page 10, one of the page 10 items will also show up on page 11.
Though you can't avoid seeing an item just before it is deleted and skipping an item just before it is created. This isn't a huge problem but does mean that the list you end up with may not be a coherent view of the database. But if you require guarantees like that then you might be better of just using SQL directly.
Or just include everything in a single response, HTTPS was designed to handle arbitrary length payloads if I recall correctly. You might want to use a more streamable format than JSON though.
> If you care about that kind of guarantee you might want to keep a connection open and stream new updates.
You don't need that. You just need to get the collection resource to be cacheable and subsequently track your resources' state with conditional requests.
AFAIK chunked transfer works specifically with HTTP 1.1, think Kubernetes for example uses this with JSON in a few prominent places for things like WATCH. But that setup is hardly ideal for the use case.
I don't think you need to do anything difficult you can just treat it as one big file, pretty sure online radio streams have been using this technique for ages. Though I'm not too sure about the particulars.
This is annoying to do with JSON though because you need to remember to close all your brackets, something like CSV is a lot easier because you can just write the header once and then just stream the data.
Edit: Looks like Python supports this using chunked transfer by simply providing the HTTP request data as an iterator.
Suppose I'm on page 2. If I insert a new element Q and it gets pushed as first then page 1 will have Q A B C D. Now if I go back to page 1, I'll get A B C D E and also a token/pointer to go back one more time only to retrieve Q.
So while cursor solved the issues you mentioned, it still will have this case in which pagination gets broken. I'm interested how we can tackle this.
Ah, I assumed from the topic, term and discussion that this would be implemented via sql cursors. Apparently elastic search has a similar concept - but like sql cursors it cannot be stateless (because you cannot ask for Nth to Mth result of searching the collection as of state Z -if you don't want to capture/supply state Z).
This means any stateless pagination api is fundamentally broken. Please don't make promises you cannot keep.
One way to get around this is to drop the notion of page number. Instead do greater than last element on last page.
But this has the drawback of only working as long as the sorting field doesn't have many duplicates. You have to beware if timestamps are high resolution enough for your application or if you have 100+ entries with same family name.
Usually users are smart(lazy) enough to realize they got more than 100 results and will narrow down the search instead. When was the last time you looked beyond even the first 5 results on google yourself, i'd rather adjust the search term than go to page 2.
If your ability to query can manage sorting on two fields, this can be resolved by sorting on the field first, then the primary key as a secondary field.
If I'm sorting by last name, and I sort by last name, then id, I can save the cursor as last name + id, and be able to continue right where I left off.
Depends how long the cursor is alive. Url containing ?date=lt:2012-12-27 is stateless, user readable and more likely to outlive ?cursorId=xyaxjeasu&page=2.
Now it might not be as accurate as having a cursor but it is a lot easier to implement, and still beats simply ?page=2 without cursor, which is the level you see in most apis today.
The cursor is never invalidated. You can always get a valid response from any cursor, whether the resource exists or was already deleted. That's the whole point of using a cursor.
Perhaps your confusion lies in assuming that a cursor's life cycle is tied to a specific object. It isn't. A cursor means "get me whatever resources would immediately follow this resource". It matters nothing if the cursor exists or not. When you run the query, you will get exactly the resource which would follow the cursor. That's by design.
You use the sort key as the page selector. So if it's cities sorted by name, the query is "give me the first 20 cities with names after 'Constantinople'". If Constantinople gets the works, it doesn't matter, because there are still 20 cities whose names come after that lexicographically.
If it is updated, though (in this case, renamed to Istanbul), it can appear later once again, and newly inserted rows behind "Constantinople" will never appear.
I mean, these problems happen if you use offsets too, and my point is that they don't matter.
The most hardcore solution to those would be pre-computing pages but I doubt it makes sense to bring even more state to the search results.
Yes, pagination over a consistent view is a whole other problem! Either you store search results server side, in which case now you need to think about expiration and running out of space, or you are able to regenerate them on the fly somehow. A database which supports as-of queries might make that quite easy, but not many databases do.
Really? The underlying storage engine of most databases stores all data necessary for an "as of" query. Simply ignore all data pages newer than the timestamp cutoff, and prevent the garbage collection of any page that could be part of such a query.
In fact thats the way [eg. postgres] can do a long-running query on a table that someone else is modifying. You in effect are looking at a snapshot of the table at the moment you started the query, even if it takes an hour to produce all the results.
That's an orthogonal problem that you need to define correctness for your application.
Because LIMIT...OFFSET will also arguably give you the wrong result. E.g. Aa is inserted. The user will see "B" both as the last item on the first page, and the first item on the second page.
Or with your example:
Aa Ab B C
Now "A" is inserted between page loads. The user will never see "A". What's right for your application? Maybe a notification saying "previous pages have gotten new items". Maybe not. It all depends.
Reddit can be annoying if you go page after page. As stories are bumped down you see them again. That, in my opinion, is a bug. But solving it requires something completely different from merely defining page boundaries.
> What if the last element on a page is deleted when you click "next"?
That makes absolutely no difference. You're still querying the database for elements that come after a value from a data type for which there is an order. You don't need that element to exist to run a comparison. For example, consider a timestamp-based query: you don't need an element with that specific date to exist to search for any element whose timestamp was taken after an arbitrary moment.
Another approach to solving this issue is with a temporal database (standardized in SQL:2011); supporting a “valid time” in your query gives your user a consistent view of the database tables even if others are modifying it concurrently. It’s also handy if you want to keep audit records of the database (e.g. so users can see who/when/what changes were made).
token based pagination is how infinity scrolling pages are implemented. It definitely has usability problems, but beyond a certain scale offset based pagination is not viable from a performance point of view, especially if users are given option to chose sorting order.
Cursors are stateful. This greatly complicates the design of the backend.
First, you have to maintain state in some kind of session on the app server.
Second, if you have more than one app server, you'll have to share the sessions across them using Redis or Hazelcast or something.
Third, cursors have to be closed, which means you have to know when the user is done with the result set. This is impossible to know. The user could go to page 2 and then go to lunch. So you have to leave it open for a while, and then have some kind of timeout. Have a lot of users doing the same thing? Memory fills, both on the app server and in the database server.
Fourth, your cursor is going to leave a transaction open, which interferes with updates and all kinds of other things.
Fifth, most users never go to page 2 anyway. They run another search.
Keeping cursors open in a web app is a spectacularly bad idea.
UPDATE -- I am in error. The article does not recommend a normal database cursor. Disregard my comment.
Not that kind of cursor. There is no state on the server / in the database and nothing to close.
> Generally, you have some ordering criteria, for example, product id. In this case, you’ll encode your product id with some reversible algorithm (let’s say hashids). And on receiving a request with the cursor you decode it and generate a query like `WHERE id > :cursor LIMIT 100`.
Oops -- this is embarrassing -- I did not read the article closely. You're right, the article does not recommend using a normal database cursor. Never mind.
Just in case you might be able to help me out.. is there any SQL flavor that supports specifying any except certain columns? For example something like:
SELECT * EXCEPT FOO_ID FROM FOO;
I have always wanted this but have never vome across it...
Thanks for answering! Currently I do use views but it's just something I had wondered about.
I mean, the information from the information_schema must be updated anyway when one deletes a column or table, so I thought maybe a function like that which looks it up could exist.
I will try with PL/pgSQL, have long wanted to familiarise myself with it anyway.
If there's subset of rows you frequently want, you may just be able to define a view and use that. (At one point, I defined a text macro in my terminal to list the fields I usually wanted on our "orders" table.)
That multi column answer doesn't seem to address pagination of queries where some of the columns are in descending order and some aren't.
I implemented a keyset paging library for sqlalchemy which supports this, and found the nicest way to do it is to swap the comparisons for the descending columns. For instance if this is an all-ascending paginated query:
select ... where row(c1, c2, c3) > row(11, 12, 13) order by c1, c2, c3
Then with c2 descending it would look like this:
select ... where row(c1, 12, c3) > row(11, c2, 13) order by c1, c2 desc, c3
Been doing it this way for a while actually. Even when it's used as a limit and offset. I find it's a good way to hide the actual pagination implementation from the client and therefor easy to swap out later without the client changing. Here's an example of a `Pagination` object that I use server side to generate and parse cursors (It's written in Kotlin):
From an API evolution standpoint, cursors are a no-brainer over explicit offsets:
1. Nothing stops you from having your cursors be implemented via a SQL offset under the hood.
2. You can have your cursors be base64 data, and embed a cursor version in the ID. You can use this to change how your pagination works without breaking clients during the transition period. (You'll need to document+enforce a maximum validity for pagination tokens to do this successfully.)
3. You can encrypt your pagination tokens, so clients don't get used to making assumptions about how your pagination works under the hood. (This isn't security by obscurity, it's just defending against Hyrum's Law [1].)
It doesn't cost you much to implement cursors early on, and unlike offsets they will grow with you across the evolution of your API.
We've even used cursors to migrate implementations; in our case, we were migrating from solr5 to solr7. When you started a session, you were allocated to solr5 or solr7 according to the business rules in effect; the solr7 cursors were prefixed with solr7-, so that in subsequent requests we could send you to the same major version. It could work the same way with load balancing too I guess.
Sometimes you want a cursor so you can resume where you left off without worrying about new entries that may have come in which would otherwise mess up your pagination.
Sometimes you want position-based queries, because you explicitly do want everything to be positional.
Sometimes you want to combine the two techniques, e.g. if you jump to the middle of a large, ever-changing list, and then want to retrieve the next batch of results after wherever you happen to be.
I like the design that JMAP ended up with <https://tools.ietf.org/html/rfc8620#page-45>: you can specify a position integer, or an anchor ID and optionally an anchorOffset integer. An anchor is a restricted case of a cursor, being the ID of an entity in the result set rather than an opaque type that could embed other information (such as coroutine addresses, thinking back to the old days of HN), but has the notable advantage of being client-controllable.
(Because JMAP is very much an object synchronisation protocol and not just an API for objects that don’t record their history in any way, like your common-or-garden REST API, this is also paired with change tracking so that you can be notified when the set of entities matching the query changes; this is how Fastmail’s webmail (probably the most-used JMAP client for now) updates its message lists for mailboxes (roughly `Email/query { filter: { inMailbox: inbox } }`) and search results (roughly `Email/query { filter: { text: "foo" } }`). Such a principled approach to changing state is extremely valuable for supporting live updating of a UI, and pretty much essential for offline support.)
Cursor based pagination and offset base pagination are two different approach for different purpose (hence not interchangable).
Cursor based is good when you know exactly where the next page go (Eg: chat message when you want to load previous messages). Offset based is good when you want to browse data randomly (Eg: you want to go to page 10 when you are in page 1)
Yeah, it's usual UX for e-commerce sites for customers to have the possibility to choose which page they want to move to, same with forum threads etc. It gives a much better understanding on how many products there are in total and let's you just find things quicker if filters aren't perfect.
It gives you a great overview on how things are generally priced etc if you order by price.
I mentally filter out "GraphQL spam" with the same rigor and aptitude I mentally filter out "bitcoin spam", but this unsubstantiated ad hominem does nothing to convince me that I'm smart or in-the-right for it.
Having used the keyset pagination for a while, it prevents you from worrying about performance in most cases.
While the post claims that is not possible to go back in the result set, it isn't true but it isn't just that simple, a way being to encode the current and the next pointer in the cursor argument, which can be used to go back, also, I think that you can commonly reverse the ordering and play with the query conditions to go back.
On the other hand, the biggest drawbacks I have experienced is:
- Dealing with a cursor where the item involved is actually deleted before you do the next query, there are many strategies but it is certainly something you need to plan for.
- Building APIs that allow sorting by different arguments in the result, which can get the query conditions tricky easily.
In any case, its always worth exploring this mechanism for people not aware of it.
Depending on the data you are showing there are reasons.
One example is when the results are already ordered by relevance (this might be search matches, proximity, recency). In these cases most everybody will not need to go beyond the first page but you still get the benefit of faster loading and rendering due to reduced amount of data for the first load.
We have explicit cursors and classic pagination in our public facing API. Classic paging is such a thorn in our side, but almost everyone uses it for their v1 unless they ask us for guidance first. We have guides about why pagination is bad, and discourage it in our API rate limits, but it still persists.
Looking back, I would exclude classic pagination from a public API and go full cursor. Possibly include an optional total count that can be requested (counts are expensive in PG though).
Given the confusion over the reuse of the term “cursor”, I prefer the terms we (Google) have settled on for Pagination [1]: page token and page size. It’s often awkward to argue about “really, do I need to support pagination from the outset”, but the examples given in that AIP are from real-world battle scars. Even if you just set the page size to a big number, at least you prepare your callers for “one day, you’ll need to handle this”.
Not contradicting, just adding that GCP (Datastore) has had cursors for at least 8 years. When I came across that using App Engine many years ago I really liked the cursor thing, and it stuck with me. I found it a little funny this article sounded a bit like "Here's this new thing"
Oh, but that’s an “API” for a Database. So that’s a fine exception to “you should offer cursors”, since that’s what you actually intend to present. A more generic API that happens to be backed by a database with a list of things in it, should not reflect the underlying database decisions if it can help it.
This is trumpeted around and actually put into production every once in a while.
The reason opaque pagination is an antipattern is because you can’t optimistically fetch resources.
So your customer, the person that paying you for your product, needs to wait for some number of synchronous reads.
With non-opaque offsets these can be done in parallel. If the typical request requires 4 pages, these can be done 4 at a time and of it is less than 4 pages those can be discarded.
This is a clever hack that ends up being user hostile in actual practice. Remember APIs are designed for the benefit of the consumer vs the benefit of the maintainers.
If the API takes a cursor and a number of items to fetch, the idea of a "page" or how large it is exists entirely on the client. You can fetch 40 results in one query and say it corresponds to the next four "pages", if you're configured to show ten items per page
It seems worth noting a high number of concurrent queries to the same database shard as part of the same overall page load can be very wasteful of CPU as database load increase, due to the cost of context switching. https://github.com/brettwooldridge/HikariCP/wiki/About-Pool-... dives into that.
> So your customer, the person that paying you for your product, needs to wait for some number of synchronous reads.
The customer is not always right.
It's also not clear what the practical issue with sequential requests are? Multiple parallel requests may get caught in a rate limiter, and impose much more work on the backend than a cursor (multiple unnecessarysort/discards). It's not a given that spamming a service gets you all the data any faster than using a cursor.
> With non-opaque offsets these can be done in parallel. If the typical request requires 4 pages, these can be done 4 at a time and of it is less than 4 pages those can be discarded.
If the typical request requires 4 pages, then your page size is suboptimal.
non backend dev here. could someone elaborate what exactly is so opaque about pagination? and what makes offsets less opaque? does this term have meaning I don't know about?
and why does the DB need to wait for some number of synchronous reads?
"offset" can be passed transparently to db to retrieve a range of records while "cursor" is customarily implemented in the API layer. I think that's what "opaque" meant in GP's context.
A starting read is needed to obtain the first cursor, hence the synchronous read.
if you ask for next page of results, with parameters like offset=20&limit=10, then you, as a client, can try to reason and manipulate those parameters. Ask for multiple pages in parallel, ask for offset=18 etc. Make calculations on those parameters.
If you only providing a token, like "next_page=abcdef1234" with some encoded structure, you're limiting your client in what it can actually do, but simultaneously simplify backend architecture and make it more forward compatible with future changes in backend (after all, that next_page token can actually be just an offset and limit encoded)
ah i see so some kind of tradeoff between power to the API consumer vs power to the API maintainer. thank you!
i don't see anyone arguing for "next_page=abcdef1234". realistically it's more like "cursor=abcdef1234&limit=10". slightly less opaque. still your point about asking for multiple pages in parallel still stands.
i think i agree with mostly everyone here in that this is a fine tradeoff to make and so would favor cursors over offsets. (unclear how cursors relate to "keysets")
I think that cursor should be used more with realtime data and more stable data like products in an e-commerce shop should use paginated queries.
There's many UX benefits for paginated queries. It gives customer a clear overview of how many products there are and customer can also navigate faster to get a better understanding of what general prices are. If the table/list doesn't have good filters, customer can find what they are looking for faster too. Same with highscores, forums threads and other similar things. Say you are browsing highscores and you want to see what scores are around 10000th position etc.
As a user I find having only prev/next buttons a bit claustrophobic in this case. I think UX should trump whatever performance gains there are from it.
I think supporting an explicit (large) page size addresses your concern. It’s not that you want to make four separate requests, it’s that you want the backend to give you more than a tiny amount of data. If you’re going to induce you the 400 results of loading on the backend, backend implementators may as well give you all the results in one go (assuming the output fits in whatever request/response limits you have).
I definitely agree that just having opaque page tokens without the ability to say “I want up to 100” leads to needless pain for clients and overall system inefficiency.
As long as it can be used to "seek" directly into where the last page ended.
The problem with offset and limit is that you have to actually find the previous N results in order to get the N+1th. But with a cursor you can just "continue".
(when I say "seek" I mean use indexes. I'm comparing to listing a tar file (requires reading the whole thing to find the file in the middle) vs zipfile (seek to where the file is, and read))
If you order by id as a tie breaker it's guaranteed that ever new inserted row has a higher id than the last id in the dataset.
If the id is a GUID it's possible to add a new row between the paginated API calls with a GUID lower than that of the last received row. Or does the cursor prevent that the new row is skipped?
What if the pagination is by order by id only?
Seems to me that you're assuming that everything should be paginated after being sorted by "ID". Why should it be? The user is not interested in your internal representation. An "ID" does not imply semantic meaning, or ordering, and you should not treat it as such.
If you want to order by creation time, then have a column with creation time. With resolution down to nanoseconds it'll be unique. And if not, well your query should be deterministic and "order by ctime,id".
But the problem is always possible. Doesn't matter what method you use. It applies to OFFSET … LIMIT, guid, name, or ID.
It's up to you to decide what you want the user experience to be if someone is on page 1, presses "next page", but before you click someone deleted the entire first page. And maybe there is no page 2 anymore.
These questions are application dependent, I'd say. And while I may have my opinions on the best way to handle it, it's an orthogonal question to what this article is talking about.
Edit: Oh, and there's GUID type 1, so "GUID" doesn't inherently mean "not sortable".
150 comments
[ 0.19 ms ] story [ 260 ms ] threadHere's what that looks like in ES: https://www.elastic.co/guide/en/elasticsearch/client/java-re...
The APIs I generally work will abstract away most of the scroll context configuration stuff, and just return a page of results, plus the ScrollId for the next page.
Anyway solving something “basic” languages like php or node solved eons ago is a bit lame and silly. “Cursors” and pagination have been solved way before HN’s lame plebe discovered wanna be “software engineering”. Cool stuff for a f(w)aang(k) worker. Ah yeah ai might help lol?
It is perfectly possible to have a "previous page" link. Your pagination needs to support "before" cursor semantic, allowing a consumer to retrieve the N items before the row identified by the cursor.
It is also possible to create a "next page". You only need to take your current page's last id and use it in your query like "where id > current_last_element_id".
"first page" and "last page" are possible as well, simply do "where id > 0" for first and "where id <= (subselect max id)".
You may need to invert order here and there, but it is perfectly possible to use cursor base pagination in a GUI as long as you don't need to provide jumping to a specific page number.
https://github.com/hasura/graphql-engine/issues/141#issuecom...
or
https://stackoverflow.com/questions/38017054/mysql-cursor-ba...
[1] https://www.elastic.co/guide/en/elasticsearch/reference/curr...
Offset pagination works fine in this scenario. But something like `where id > 42 limit 100` fails with an arbitrary sorting order on non-unique columns. All I could do would be to generate the unpaginated result, then find the cursor within it, and take the limit after that. Which is too inefficient to be practical.
If I missed a decent solution, please tell.
I managed to get this working with compound primary keys too: click "next" at the bottom of this page for a demo: https://latest.datasette.io/fixtures/compound_three_primary_...
The code is pretty complicated - mostly here: https://github.com/simonw/datasette/blob/0.53/datasette/view...
Cursors elegantly sidestep these issues.
Or just include everything in a single response, HTTPS was designed to handle arbitrary length payloads if I recall correctly. You might want to use a more streamable format than JSON though.
You don't need that. You just need to get the collection resource to be cacheable and subsequently track your resources' state with conditional requests.
https://developer.mozilla.org/en-US/docs/Web/HTTP/Conditiona...
Did you mean we should stream data over WebSocket or use HTTP/2 or do we need to do something different altogether?
https://msgpack.org/
This is annoying to do with JSON though because you need to remember to close all your brackets, something like CSV is a lot easier because you can just write the header once and then just stream the data.
Edit: Looks like Python supports this using chunked transfer by simply providing the HTTP request data as an iterator.
page 1 elements: A B C D E
page 2 elements: F G H I J
so 5 elements in each page.
Suppose I'm on page 2. If I insert a new element Q and it gets pushed as first then page 1 will have Q A B C D. Now if I go back to page 1, I'll get A B C D E and also a token/pointer to go back one more time only to retrieve Q.
So while cursor solved the issues you mentioned, it still will have this case in which pagination gets broken. I'm interested how we can tackle this.
https://www.postgresql.org/docs/13/sql-declare.html
This means any stateless pagination api is fundamentally broken. Please don't make promises you cannot keep.
For elastic: https://www.elastic.co/guide/en/elasticsearch/reference/curr...
But this has the drawback of only working as long as the sorting field doesn't have many duplicates. You have to beware if timestamps are high resolution enough for your application or if you have 100+ entries with same family name.
Usually users are smart(lazy) enough to realize they got more than 100 results and will narrow down the search instead. When was the last time you looked beyond even the first 5 results on google yourself, i'd rather adjust the search term than go to page 2.
If I'm sorting by last name, and I sort by last name, then id, I can save the cursor as last name + id, and be able to continue right where I left off.
That's the whole point of a cursor, isn't it?
And pagination just means querying the records to return a limited subset.
Now it might not be as accurate as having a cursor but it is a lot easier to implement, and still beats simply ?page=2 without cursor, which is the level you see in most apis today.
The cursor is never invalidated. You can always get a valid response from any cursor, whether the resource exists or was already deleted. That's the whole point of using a cursor.
Perhaps your confusion lies in assuming that a cursor's life cycle is tied to a specific object. It isn't. A cursor means "get me whatever resources would immediately follow this resource". It matters nothing if the cursor exists or not. When you run the query, you will get exactly the resource which would follow the cursor. That's by design.
I mean, these problems happen if you use offsets too, and my point is that they don't matter.
The most hardcore solution to those would be pre-computing pages but I doubt it makes sense to bring even more state to the search results.
Really? The underlying storage engine of most databases stores all data necessary for an "as of" query. Simply ignore all data pages newer than the timestamp cutoff, and prevent the garbage collection of any page that could be part of such a query.
In fact thats the way [eg. postgres] can do a long-running query on a table that someone else is modifying. You in effect are looking at a snapshot of the table at the moment you started the query, even if it takes an hour to produce all the results.
Relevant song: https://youtube.com/watch?v=Z0JhC3LO0-8
2 items per page
first page is A&B. Next query is "WHERE ID>'B'".
What's the problem?
Because LIMIT...OFFSET will also arguably give you the wrong result. E.g. Aa is inserted. The user will see "B" both as the last item on the first page, and the first item on the second page.
Or with your example:
Aa Ab B C
Now "A" is inserted between page loads. The user will never see "A". What's right for your application? Maybe a notification saying "previous pages have gotten new items". Maybe not. It all depends.
Reddit can be annoying if you go page after page. As stories are bumped down you see them again. That, in my opinion, is a bug. But solving it requires something completely different from merely defining page boundaries.
That makes absolutely no difference. You're still querying the database for elements that come after a value from a data type for which there is an order. You don't need that element to exist to run a comparison. For example, consider a timestamp-based query: you don't need an element with that specific date to exist to search for any element whose timestamp was taken after an arbitrary moment.
https://en.wikipedia.org/wiki/SQL:2011
[0] https://use-the-index-luke.com/no-offset
First, you have to maintain state in some kind of session on the app server.
Second, if you have more than one app server, you'll have to share the sessions across them using Redis or Hazelcast or something.
Third, cursors have to be closed, which means you have to know when the user is done with the result set. This is impossible to know. The user could go to page 2 and then go to lunch. So you have to leave it open for a while, and then have some kind of timeout. Have a lot of users doing the same thing? Memory fills, both on the app server and in the database server.
Fourth, your cursor is going to leave a transaction open, which interferes with updates and all kinds of other things.
Fifth, most users never go to page 2 anyway. They run another search.
Keeping cursors open in a web app is a spectacularly bad idea.
UPDATE -- I am in error. The article does not recommend a normal database cursor. Disregard my comment.
> Generally, you have some ordering criteria, for example, product id. In this case, you’ll encode your product id with some reversible algorithm (let’s say hashids). And on receiving a request with the cursor you decode it and generate a query like `WHERE id > :cursor LIMIT 100`.
My favorite SQL implementation of cursor-based keyset pagination can be found on this Hasura issue: https://github.com/hasura/graphql-engine/issues/141, specifically this comment: https://github.com/hasura/graphql-engine/issues/141#issuecom.... Something so elegant about this SQL. I enjoy it a lot.
Also really enjoy this answer about how to implement keyset pagination on multiple columns:
https://stackoverflow.com/questions/38017054/mysql-cursor-ba...
> For row comparisons, (a, b) > (x, y) is equivalent to:
> (a > x) OR ((a = x) AND (b > y))
[1] https://dev.mysql.com/doc/refman/8.0/en/comparison-operators...
SELECT * EXCEPT FOO_ID FROM FOO;
I have always wanted this but have never vome across it...
WHERE NOT EXIST (SELECT ...)
can help?
I don't know any way to do that personally.
Otherwise, dynamic column names (that's your search engine fodder) require introspection…
… coupled with the moral equivalent of PL/pgSQL `execute` (i.e. run-time eval) statement.I mean, the information from the information_schema must be updated anyway when one deletes a column or table, so I thought maybe a function like that which looks it up could exist.
I will try with PL/pgSQL, have long wanted to familiarise myself with it anyway.
If there's subset of rows you frequently want, you may just be able to define a view and use that. (At one point, I defined a text macro in my terminal to list the fields I usually wanted on our "orders" table.)
[1] https://blog.jooq.org/2018/05/14/selecting-all-columns-excep...
I implemented a keyset paging library for sqlalchemy which supports this, and found the nicest way to do it is to swap the comparisons for the descending columns. For instance if this is an all-ascending paginated query:
Then with c2 descending it would look like this:https://gist.github.com/briandilley/a0715f9f85b632b7080f8921...
1. Nothing stops you from having your cursors be implemented via a SQL offset under the hood.
2. You can have your cursors be base64 data, and embed a cursor version in the ID. You can use this to change how your pagination works without breaking clients during the transition period. (You'll need to document+enforce a maximum validity for pagination tokens to do this successfully.)
3. You can encrypt your pagination tokens, so clients don't get used to making assumptions about how your pagination works under the hood. (This isn't security by obscurity, it's just defending against Hyrum's Law [1].)
It doesn't cost you much to implement cursors early on, and unlike offsets they will grow with you across the evolution of your API.
[1]: https://www.hyrumslaw.com/
Sometimes you want position-based queries, because you explicitly do want everything to be positional.
Sometimes you want to combine the two techniques, e.g. if you jump to the middle of a large, ever-changing list, and then want to retrieve the next batch of results after wherever you happen to be.
I like the design that JMAP ended up with <https://tools.ietf.org/html/rfc8620#page-45>: you can specify a position integer, or an anchor ID and optionally an anchorOffset integer. An anchor is a restricted case of a cursor, being the ID of an entity in the result set rather than an opaque type that could embed other information (such as coroutine addresses, thinking back to the old days of HN), but has the notable advantage of being client-controllable.
(Because JMAP is very much an object synchronisation protocol and not just an API for objects that don’t record their history in any way, like your common-or-garden REST API, this is also paired with change tracking so that you can be notified when the set of entities matching the query changes; this is how Fastmail’s webmail (probably the most-used JMAP client for now) updates its message lists for mailboxes (roughly `Email/query { filter: { inMailbox: inbox } }`) and search results (roughly `Email/query { filter: { text: "foo" } }`). Such a principled approach to changing state is extremely valuable for supporting live updating of a UI, and pretty much essential for offline support.)
Cursor based is good when you know exactly where the next page go (Eg: chat message when you want to load previous messages). Offset based is good when you want to browse data randomly (Eg: you want to go to page 10 when you are in page 1)
It gives you a great overview on how things are generally priced etc if you order by price.
https://relay.dev/graphql/connections.htm
Are GraphQL-fans so uncapable you have to put your GraphQL-spamming in every single post? Didn't you learn anything else in your life?
While the post claims that is not possible to go back in the result set, it isn't true but it isn't just that simple, a way being to encode the current and the next pointer in the cursor argument, which can be used to go back, also, I think that you can commonly reverse the ordering and play with the query conditions to go back.
On the other hand, the biggest drawbacks I have experienced is:
- Dealing with a cursor where the item involved is actually deleted before you do the next query, there are many strategies but it is certainly something you need to plan for.
- Building APIs that allow sorting by different arguments in the result, which can get the query conditions tricky easily.
In any case, its always worth exploring this mechanism for people not aware of it.
One example is when the results are already ordered by relevance (this might be search matches, proximity, recency). In these cases most everybody will not need to go beyond the first page but you still get the benefit of faster loading and rendering due to reduced amount of data for the first load.
Looking back, I would exclude classic pagination from a public API and go full cursor. Possibly include an optional total count that can be requested (counts are expensive in PG though).
[1] https://google.aip.dev/158
But yes, I'm surprised it would show up on hackerNEWS.
This is not an "exception to 'you should offer cursors'" this is offering cursors.
The reason opaque pagination is an antipattern is because you can’t optimistically fetch resources.
So your customer, the person that paying you for your product, needs to wait for some number of synchronous reads.
With non-opaque offsets these can be done in parallel. If the typical request requires 4 pages, these can be done 4 at a time and of it is less than 4 pages those can be discarded.
This is a clever hack that ends up being user hostile in actual practice. Remember APIs are designed for the benefit of the consumer vs the benefit of the maintainers.
It seems worth noting a high number of concurrent queries to the same database shard as part of the same overall page load can be very wasteful of CPU as database load increase, due to the cost of context switching. https://github.com/brettwooldridge/HikariCP/wiki/About-Pool-... dives into that.
The customer is not always right.
It's also not clear what the practical issue with sequential requests are? Multiple parallel requests may get caught in a rate limiter, and impose much more work on the backend than a cursor (multiple unnecessarysort/discards). It's not a given that spamming a service gets you all the data any faster than using a cursor.
> With non-opaque offsets these can be done in parallel. If the typical request requires 4 pages, these can be done 4 at a time and of it is less than 4 pages those can be discarded.
If the typical request requires 4 pages, then your page size is suboptimal.
and why does the DB need to wait for some number of synchronous reads?
A starting read is needed to obtain the first cursor, hence the synchronous read.
i don't see anyone arguing for "next_page=abcdef1234". realistically it's more like "cursor=abcdef1234&limit=10". slightly less opaque. still your point about asking for multiple pages in parallel still stands.
i think i agree with mostly everyone here in that this is a fine tradeoff to make and so would favor cursors over offsets. (unclear how cursors relate to "keysets")
As a user I find having only prev/next buttons a bit claustrophobic in this case. I think UX should trump whatever performance gains there are from it.
I definitely agree that just having opaque page tokens without the ability to say “I want up to 100” leads to needless pain for clients and overall system inefficiency.
The problem with offset and limit is that you have to actually find the previous N results in order to get the N+1th. But with a cursor you can just "continue".
(when I say "seek" I mean use indexes. I'm comparing to listing a tar file (requires reading the whole thing to find the file in the middle) vs zipfile (seek to where the file is, and read))
Do you create sub tables to handle the arrays?
If you want to order by creation time, then have a column with creation time. With resolution down to nanoseconds it'll be unique. And if not, well your query should be deterministic and "order by ctime,id".
But the problem is always possible. Doesn't matter what method you use. It applies to OFFSET … LIMIT, guid, name, or ID.
It's up to you to decide what you want the user experience to be if someone is on page 1, presses "next page", but before you click someone deleted the entire first page. And maybe there is no page 2 anymore.
These questions are application dependent, I'd say. And while I may have my opinions on the best way to handle it, it's an orthogonal question to what this article is talking about.
Edit: Oh, and there's GUID type 1, so "GUID" doesn't inherently mean "not sortable".