13 ms·

API pagination design

353 points by fagnerbrack 6y ago

awwnaw 6y ago
Are you a python dev? No, let me guess, rust. 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?
Centigonal 6y ago
I've worked with APIs (mainly based on ElasticSearch backends) that implement something like this pattern. There, the "cursor" is called a "ScrollId." Here's what that looks like in ES: https://www.elastic.co/guide/en/elasticsearch/client/java-rest/master/java-rest-high-search-scroll.html 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.
- blueline 6y ago
  Elastic search now recommends using “search_after” instead of scrolling for deep pagination, although mechanically they’re pretty similar to use
  - Centigonal 6y ago
    Thanks for the heads-up!
  - dmitryminkovsky 6y ago
    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.
  - Andys 6y ago
    Yeah - search_after is the stateless version
- Andys 6y ago
  Also, they have a concurrent version called "Sliced Scroll" which lets you do multi-threaded fetch in N streams, each with their own cursor.
dudul 6y ago
> 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.
- vbezhenar 6y ago
  Yep, just inverse your conditions and sorting and you’ve got previous page.
- and0x000 6y ago
  This. 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.
amelius 6y ago
How long will the cursor be valid?
- dmitryminkovsky 6y ago
  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: https://github.com/hasura/graphql-engine/issues/141#issuecomment-406006229 https://github.com/hasura/graphql-engine/issues/141#issuecom... or https://stackoverflow.com/questions/38017054/mysql-cursor-based-pagination-with-multiple-columns https://stackoverflow.com/questions/38017054/mysql-cursor-ba...
  - dmlittle 6y ago
    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. [1] https://www.elastic.co/guide/en/elasticsearch/reference/current/search-search.html https://www.elastic.co/guide/en/elasticsearch/reference/curr...
    - dmitryminkovsky 6y ago
      Yep, that’s the case if you use the scroll parameter, but their search_after API is not stateful and that’s the sort of thing this article is about.
hirundo 6y ago
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. If I missed a decent solution, please tell.
- vbezhenar 6y ago
  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.
- dudul 6y ago
  All the columns you order by should be part of your cursor value, and the id can be used to tie break non unique columns.
- simonw 6y ago
  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. 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_keys https://latest.datasette.io/fixtures/compound_three_primary_... The code is pretty complicated - mostly here: https://github.com/simonw/datasette/blob/0.53/datasette/views/table.py#L535-L594 https://github.com/simonw/datasette/blob/0.53/datasette/view...
et1337 6y ago
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. Cursors elegantly sidestep these issues.
- contravariant 6y ago
  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.
  - dharmab 6y ago
    If you care about that kind of guarantee you might want to keep a connection open and stream new updates.
    - rualca 6y ago
      > 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. https://developer.mozilla.org/en-US/docs/Web/HTTP/Conditional_requests https://developer.mozilla.org/en-US/docs/Web/HTTP/Conditiona...
  - ajitid 6y ago
    > use a more streamable format than JSON Did you mean we should stream data over WebSocket or use HTTP/2 or do we need to do something different altogether?
eatonphil 6y ago
Keyset pagination is described in a few places online in detail. The one that comes to mind is in Use the Index, Luke [0]. [0] https://use-the-index-luke.com/no-offset https://use-the-index-luke.com/no-offset
- lenkite 6y ago
  One cannot go to an arbitrary page with this method - doesn't it destroy use-ability quite a bit ?
  - rossmohax 6y ago
    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.
ccleve 6y ago
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.
- yencabulator 6y ago
  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`.
  - ccleve 6y ago
    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.
- deleted 6y ago
  [deleted]
- dudul 6y ago
  This is not about database cursors.
- crb002 6y ago
  You could enable a batch hint in the API. The server has the option to allocate a cursor if one is available. Best of both worlds.
dmitryminkovsky 6y ago
The Use The Index Luke material about this is essential background reading, but in terms of actually implementing: My favorite SQL implementation of cursor-based keyset pagination can be found on this Hasura issue: https://github.com/hasura/graphql-engine/issues/141 https://github.com/hasura/graphql-engine/issues/141, specifically this comment: https://github.com/hasura/graphql-engine/issues/141#issuecomment-406006229 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-based-pagination-with-multiple-columns/38017813 https://stackoverflow.com/questions/38017054/mysql-cursor-ba...
- altdatathrow 6y ago
  fyi that mysql multiple column answer is incorrect, mysql does indeed support row/tuple comparisons [1]: > 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.html https://dev.mysql.com/doc/refman/8.0/en/comparison-operators...
  - djeiasbsbo 6y ago
    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...
    - rossmohax 6y ago
      Maybe WHERE NOT EXIST (SELECT ...) can help?
      - boudin 6y ago
        I think the question was about excluding columns, not rows. I don't know any way to do that personally.
briandilley 6y ago
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): https://gist.github.com/briandilley/a0715f9f85b632b7080f8921d87ce520 https://gist.github.com/briandilley/a0715f9f85b632b7080f8921...
ucarion 6y ago
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. [1]: https://www.hyrumslaw.com/ https://www.hyrumslaw.com/
- alexchamberlain 6y ago
  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.
chrismorgan 6y ago
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 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.)
- lenkite 6y ago
  This approach still requires a full table scan right ?
  - chrismorgan 6y ago
    No: it becomes just an added `WHERE id >= anchor` constraint, which with the usual indexes is cheap.
knlam 6y ago
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)
- mewpmewp2 6y ago
  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.
atom_arranger 6y ago
I'm a fan of the "GraphQL Cursor Connections Specification", which could be applied even if not using GraphQL: https://relay.dev/graphql/connections.htm https://relay.dev/graphql/connections.htm
- jiji33i 6y ago
  "If all you have is a hammer, everything looks like a nail." 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?
  - atom_arranger 6y ago
    No, and yes.
  - Can_Not 6y ago
    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.
AlexITC 6y ago
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.
novia 6y ago
I've been hitting paginated page limits. Why even bother to offer a paginated version if you can't grab an arbitrary page?
- yoz-y 6y ago
  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.
pkd 6y ago
Several recommendations on this thread have led me to buy the SQL Performance Explained book.
- deleted 6y ago
  [deleted]
User23 6y ago
I'm pretty sure pagination APIs are the result of people who haven't ever read Stevens writing services.
- mmkos 6y ago
  Can you elaborate? I tried looking it up but nothing meaningful comes up.
  - User23 6y ago
    The TCP book. As in Transmission Control Protocol and it solves the problem way better than any of the janky hacks called pagination.
- deleted 6y ago
  [deleted]
sb8244 6y ago
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).
boulos 6y ago
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”. [1] https://google.aip.dev/158 https://google.aip.dev/158
- deleted 6y ago
  [deleted]
- graderjs 6y ago
  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"
  - knorker 6y ago
    It's definitely not new, but worth repeating. But yes, I'm surprised it would show up on hackerNEWS.
  - boulos 6y ago
    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.
    - graderjs 6y ago
      It seems to me you might have meant to reply to another comment. This is not an "exception to 'you should offer cursors'" this is offering cursors.
momokoko 6y ago
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.
- dub 6y ago
  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-Sizing https://github.com/brettwooldridge/HikariCP/wiki/About-Pool-... dives into that.
- growse 6y ago
  > 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.
- swyx 6y ago
  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?
pram 6y ago
Is an auto increment sequential number good enough for a 'cursor' or is there something I'm missing here.
- knorker 6y ago
  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))
deleted 6y ago
[deleted]
blackrock 6y ago
When you got your JSON data in nested form, with arrays. How do you flatten it, for storage in the database? Do you create sub tables to handle the arrays?
croes 6y ago
What if your id column uses GUIDs?
- knorker 6y ago
  How do you mean that it changes the proposition?
  - croes 6y ago
    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?
    - knorker 6y ago
      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".
gandutraveler 6y ago
Cursor or pointer works well if the pagination request are in the same user session. However cursors can't be used to deep linking in urls and when the data is dynamic.
vincnetas 6y ago
I think author misses crucial point while using OFFSET. At least postgres doc has this to say (https://www.postgresql.org/docs/13/queries-limit.html https://www.postgresql.org/docs/13/queries-limit.html) When using LIMIT, it is important to use an ORDER BY clause that constrains the result rows into a unique order. Otherwise you will get an unpredictable subset of the query's rows. You might be asking for the tenth through twentieth rows, but tenth through twentieth in what ordering? The ordering is unknown, unless you specified ORDER BY. And looks like pagination queries provided by author do not take sorting in to account, which means that items on page 100 will be with id greater than 10000, but in undefined order. explain analyze select id from product where id > 10000 limit 100
02020202 6y ago
i use page and limit(per page). anything else is just over-engineering. kiss the yagni.
notretarded 6y ago
Implying that anyone goes further than page 1. Put a notification on the page "your search query returned too many results, please refine your criteria"
flqn 6y ago
In addition to using cursors or whatever pagination method suits your backend in query params, it's also a good idea to include pagination URLs in the response itself if you can. Greatly simplifies what the client has to do and reduces coupling since now the client doesn't need to care what your query param structure is
montoro 6y ago
Great article! I wrote something similar, includind a playground which serves as a benchmark to compare the various pagination options: https://www.samu.space/api-pagination/ https://www.samu.space/api-pagination/
mewpmewp2 6y ago
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 easily act out binary search to find what they are looking for in an ordered list of items. 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.
- deleted 6y ago
  [deleted]
- cj 6y ago
  A while ago, github replaced the pagination on their commits page to be based on a git commit ID instead of a page number. After that change, it made it a lot more difficult to find the oldest commit in a large repo - frustrating. That said, I think the percent of average ability internet users (ie. people visiting an ecommerce shop) will virtually never attempt to navigate by changing values in a query string param. High scores on a gaming forum, maybe more likely. Either way, if users need the ability to jump through pages, I would hope that would be exposed in a UI rather than expecting people to edit the URL directly.
  - mewpmewp2 6y ago
    Yeah, it's best if it's possible to do it both ways. With url and also by clicking links and maybe even add a select/input to go to certain page. If you look at any e-commerce systems, ranging from WooCommerce to Shopify, Amazon and Walmart, I think they all use pagination. Some Amazon pages do have infinite scroll however I have also been frustrated without having the ability to quickly go through commits... Or I think releases for that matter? For instance, browsing through tags/release versions, which should be a very valid use-case in my opinion also uses cursor based navigation.
ChrisMarshallNY 6y ago
I like the idea of a "cursor," or some kind of appointed "variable." It has the potential to become complex, so I would assume it was an "also" capability, as opposed to an "instead of" capability. I like the idea of a "range" syntax ("[X..<Y], [X...Y], [X<..Y], [X<.<Y], etc). When I write APIs, server performance isn't really an issue for me. Most of the performance bottleneck, in my experience, is data transfer, so being able to optimize that, pays the greatest dividends. Also, making the API easy to understand, and express semantically, is important.
EugeneOZ 6y ago
I’ve spent more time reading this article, than this approach could save in practice if we accumulate all the saved milliseconds.
- Abimelex 6y ago
  wow having this kind of mindset would probably have left us in the stone age.
lkbm 6y ago
I tried running their exact example queries, since I conveniently have a >100k row PostgreSQL table available of the same name. (> 100k rows) The first (offset) was indeed on the order of 5x slower, but I suspect what the author saw with a 40ms to a 0.1ms time difference was that it wasn't pre-warmed first run. For me, with offset, the FIRST run was 25ms, but subsequet runs are around 2-3ms. For `id > 10000`, it was under 0.05ms. It's also very odd that they don't do an `order by`. This seems important. Default ordering is semi-stable. It'll tend not to change, but it can at any point. Benchmarking without that may be misleading.
callesgg 6y ago
I think is better to not use pagination at all. Design your api or page so that you receive all or more entries than you could possibly need. If the user wants them all pagination is just in the way. If the user does not want them all give them as many as they are likely to be able to handle.
- hellcow 6y ago
  "Woah, our database is slowing to a crawl, requests are deadlocked everywhere. Yeah, some asshole is hitting GET /messages and pulling 2TB in a single request again." "Surely that's what he wanted."
  - callesgg 6y ago
    Given that is what the person is doing, that is likly what they are trying to do. Most of the times when I do things, I do it cause I want to do it, not cause I did an opsie.
    - scrollaway 6y ago
      "let's allow users to DOS us in a single request if they want to" is not an acceptable design decision, I'm sure you are aware of that.
      - callesgg 6y ago
        Most services don’t handle ddos amounts of data, a few 1000 rows of data is fine. Don’t design like you are Twitter if you are not. It is a waste of man hours. If I as a client need 10 000 rows of data that is what I will ask for either in one request or in a 100 consecutive.
- Can_Not 6y ago
  This is terrible advice, sending the client as little as reasonably possible (therefore use pagination) is the most sane, performant, affordable, and secure default assumption. Any rails/laravel/feathersjs style framework have multiple types of pagination built in for free.
nareshb513 6y ago
I have implented such a work in my initial career days like 15 yrs back there i have implemented first, previous,next, last no goto page number. It works for multiple columns in the order by. The trick is to swith the order by in reverse and limit the results to page size, this way we get results in reverse orde but while returning just send them.in the reverse order.... The assumption is to include the primary key as mandatory order by at the end implicitly. This makes a lot easy in other situations like if mulitple pages of records found with same value.. etc...
Abimelex 6y ago
thats how firebase does it. It's quite impossible to have proper pagination on realtime results, that's why I believe they used this approach: https://firebase.google.com/docs/firestore/query-data/query-cursors https://firebase.google.com/docs/firestore/query-data/query-...
abhishekjha 6y ago
Can somebody elaborate on what the last paragraph means? If I have a limit of count per page and I know which page I am based on URL I can always generate a prev/next page link. I guess it is pointing out that limit/offset needs be used in such a case. How did reddit do it in terms or pagination? Such a large website wouldn’t survive on limit/offset.
ivoecpereira 6y ago
I have written about this as well[1] and even built a Github PoC about it comparing both approaches regarding speed[2] but one of the main flaws is the lack of a deeper consideration for sorting and filtering examples and impact demonstration. Will look into adding more detail about that in an addendum. [1] https://medium.com/swlh/why-you-shouldnt-use-offset-and-limit-for-your-pagination-4440e421ba87?source=friends_link&sk=2dafef5c1fb698e2f7884bf5e8149b37 https://medium.com/swlh/why-you-shouldnt-use-offset-and-limi... [2] https://github.com/IvoPereira/Efficient-Pagination-SQL-PoC https://github.com/IvoPereira/Efficient-Pagination-SQL-PoC
sonthonax 6y ago
This is one of those obvious things that people have a blockheaded aversion towards. In every job I’ve consulted on, there has been a component where pagination is the bottleneck. And it’s rarely where pagination could be useful (like a static list of products). I typically see it when someone builds an aggregating (and aggravating) microservice that pulls all of the data from another service; that blocks the entire database. Perhaps it’s the world of ‘Django developers’ I find myself in. But the fact this simple design pattern reaches the front page of Hackernews worries me. I’ve personally had backend developers give confused looks and diatribes about simplicity when I’ve suggested this approach. Frontend developers frequently give the greatest resistance, which I think is because they most often act in concert with product managers who are welded to certain UX idioms that they chose without fully imagining the engineering consequences of. One approach which I try to push people towards is fetching a big list (N≈5000) and paginating it however the UX designer wants. The response of the big list should be sparse, that is without including additional fields that aren’t displayed by the front end (and fetching more data when the user navigates). You’ll frequently get puzzled looks suggesting this, but benchmarks will usually show that fetching 5000 rows and a small number of columns takes a few milliseconds, and can be serialised into 150kb. On balance it ends up being faster: as you’ll get fewer network requests; fewer round trips to the database; fewer fetches; and less time spend serialising (which is a major bottleneck itself that Python developers ignore).
- raihansaputra 6y ago
  Sometimes it's the case of overoptimising/early optimization too. BE doesn't want to create another endpoint with simplified fields, FE being overly concerned with size of JSON responses over the wire / being processed client side (while the image for each item is not optimized themselves). Thanks for sharing the Big N approach, I have to try that.

353 points by fagnerbrack 6y ago

Are you a python dev? No, let me guess, rust. 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?

Centigonal 6y ago

I've worked with APIs (mainly based on ElasticSearch backends) that implement something like this pattern. There, the "cursor" is called a "ScrollId." Here's what that looks like in ES: https://www.elastic.co/guide/en/elasticsearch/client/java-rest/master/java-rest-high-search-scroll.html 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.

blueline 6y ago
Elastic search now recommends using “search_after” instead of scrolling for deep pagination, although mechanically they’re pretty similar to use
- Centigonal 6y ago
  Thanks for the heads-up!
- dmitryminkovsky 6y ago
  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.
- Andys 6y ago
  Yeah - search_after is the stateless version
Andys 6y ago
Also, they have a concurrent version called "Sliced Scroll" which lets you do multi-threaded fetch in N streams, each with their own cursor.

dudul 6y ago

> 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.

vbezhenar 6y ago
Yep, just inverse your conditions and sorting and you’ve got previous page.
and0x000 6y ago
This. 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.

amelius 6y ago

How long will the cursor be valid?

dmitryminkovsky 6y ago
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: https://github.com/hasura/graphql-engine/issues/141#issuecomment-406006229 https://github.com/hasura/graphql-engine/issues/141#issuecom... or https://stackoverflow.com/questions/38017054/mysql-cursor-based-pagination-with-multiple-columns https://stackoverflow.com/questions/38017054/mysql-cursor-ba...
- dmlittle 6y ago
  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. [1] https://www.elastic.co/guide/en/elasticsearch/reference/current/search-search.html https://www.elastic.co/guide/en/elasticsearch/reference/curr...
  - dmitryminkovsky 6y ago
    Yep, that’s the case if you use the scroll parameter, but their search_after API is not stateful and that’s the sort of thing this article is about.

hirundo 6y ago

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. If I missed a decent solution, please tell.

vbezhenar 6y ago
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.
dudul 6y ago
All the columns you order by should be part of your cursor value, and the id can be used to tie break non unique columns.
simonw 6y ago
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. 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_keys https://latest.datasette.io/fixtures/compound_three_primary_... The code is pretty complicated - mostly here: https://github.com/simonw/datasette/blob/0.53/datasette/views/table.py#L535-L594 https://github.com/simonw/datasette/blob/0.53/datasette/view...

et1337 6y ago

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. Cursors elegantly sidestep these issues.

contravariant 6y ago
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.
- dharmab 6y ago
  If you care about that kind of guarantee you might want to keep a connection open and stream new updates.
  - rualca 6y ago
    > 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. https://developer.mozilla.org/en-US/docs/Web/HTTP/Conditional_requests https://developer.mozilla.org/en-US/docs/Web/HTTP/Conditiona...
- ajitid 6y ago
  > use a more streamable format than JSON Did you mean we should stream data over WebSocket or use HTTP/2 or do we need to do something different altogether?

eatonphil 6y ago

Keyset pagination is described in a few places online in detail. The one that comes to mind is in Use the Index, Luke [0]. [0] https://use-the-index-luke.com/no-offset https://use-the-index-luke.com/no-offset

lenkite 6y ago
One cannot go to an arbitrary page with this method - doesn't it destroy use-ability quite a bit ?
- rossmohax 6y ago
  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.

ccleve 6y ago

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.

yencabulator 6y ago
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`.
- ccleve 6y ago
  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.
deleted 6y ago
[deleted]
dudul 6y ago
This is not about database cursors.
crb002 6y ago
You could enable a batch hint in the API. The server has the option to allocate a cursor if one is available. Best of both worlds.

dmitryminkovsky 6y ago

The Use The Index Luke material about this is essential background reading, but in terms of actually implementing: My favorite SQL implementation of cursor-based keyset pagination can be found on this Hasura issue: https://github.com/hasura/graphql-engine/issues/141 https://github.com/hasura/graphql-engine/issues/141, specifically this comment: https://github.com/hasura/graphql-engine/issues/141#issuecomment-406006229 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-based-pagination-with-multiple-columns/38017813 https://stackoverflow.com/questions/38017054/mysql-cursor-ba...

altdatathrow 6y ago
fyi that mysql multiple column answer is incorrect, mysql does indeed support row/tuple comparisons [1]: > 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.html https://dev.mysql.com/doc/refman/8.0/en/comparison-operators...
- djeiasbsbo 6y ago
  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...
  - rossmohax 6y ago
    Maybe WHERE NOT EXIST (SELECT ...) can help?
    - boudin 6y ago
      I think the question was about excluding columns, not rows. I don't know any way to do that personally.

briandilley 6y ago

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): https://gist.github.com/briandilley/a0715f9f85b632b7080f8921d87ce520 https://gist.github.com/briandilley/a0715f9f85b632b7080f8921...

ucarion 6y ago

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. [1]: https://www.hyrumslaw.com/ https://www.hyrumslaw.com/

alexchamberlain 6y ago
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.

chrismorgan 6y ago

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 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.)

lenkite 6y ago
This approach still requires a full table scan right ?
- chrismorgan 6y ago
  No: it becomes just an added `WHERE id >= anchor` constraint, which with the usual indexes is cheap.

knlam 6y ago

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)

mewpmewp2 6y ago
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.

atom_arranger 6y ago

I'm a fan of the "GraphQL Cursor Connections Specification", which could be applied even if not using GraphQL: https://relay.dev/graphql/connections.htm https://relay.dev/graphql/connections.htm

jiji33i 6y ago
"If all you have is a hammer, everything looks like a nail." 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?
- atom_arranger 6y ago
  No, and yes.
- Can_Not 6y ago
  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.

AlexITC 6y ago

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.

novia 6y ago

I've been hitting paginated page limits. Why even bother to offer a paginated version if you can't grab an arbitrary page?

yoz-y 6y ago
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.

pkd 6y ago

Several recommendations on this thread have led me to buy the SQL Performance Explained book.

deleted 6y ago
[deleted]

User23 6y ago

I'm pretty sure pagination APIs are the result of people who haven't ever read Stevens writing services.

mmkos 6y ago
Can you elaborate? I tried looking it up but nothing meaningful comes up.
- User23 6y ago
  The TCP book. As in Transmission Control Protocol and it solves the problem way better than any of the janky hacks called pagination.
deleted 6y ago
[deleted]

sb8244 6y ago

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).

boulos 6y ago

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”. [1] https://google.aip.dev/158 https://google.aip.dev/158

deleted 6y ago
[deleted]
graderjs 6y ago
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"
- knorker 6y ago
  It's definitely not new, but worth repeating. But yes, I'm surprised it would show up on hackerNEWS.
- boulos 6y ago
  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.
  - graderjs 6y ago
    It seems to me you might have meant to reply to another comment. This is not an "exception to 'you should offer cursors'" this is offering cursors.

momokoko 6y ago

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.

dub 6y ago
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-Sizing https://github.com/brettwooldridge/HikariCP/wiki/About-Pool-... dives into that.
growse 6y ago
> 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.
swyx 6y ago
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?

pram 6y ago

Is an auto increment sequential number good enough for a 'cursor' or is there something I'm missing here.

knorker 6y ago
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))

deleted 6y ago

[deleted]

blackrock 6y ago

When you got your JSON data in nested form, with arrays. How do you flatten it, for storage in the database? Do you create sub tables to handle the arrays?

croes 6y ago

What if your id column uses GUIDs?

knorker 6y ago
How do you mean that it changes the proposition?
- croes 6y ago
  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?
  - knorker 6y ago
    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".

gandutraveler 6y ago

Cursor or pointer works well if the pagination request are in the same user session. However cursors can't be used to deep linking in urls and when the data is dynamic.

vincnetas 6y ago

I think author misses crucial point while using OFFSET. At least postgres doc has this to say (https://www.postgresql.org/docs/13/queries-limit.html https://www.postgresql.org/docs/13/queries-limit.html) When using LIMIT, it is important to use an ORDER BY clause that constrains the result rows into a unique order. Otherwise you will get an unpredictable subset of the query's rows. You might be asking for the tenth through twentieth rows, but tenth through twentieth in what ordering? The ordering is unknown, unless you specified ORDER BY. And looks like pagination queries provided by author do not take sorting in to account, which means that items on page 100 will be with id greater than 10000, but in undefined order. explain analyze select id from product where id > 10000 limit 100

02020202 6y ago

i use page and limit(per page). anything else is just over-engineering. kiss the yagni.

notretarded 6y ago

Implying that anyone goes further than page 1. Put a notification on the page "your search query returned too many results, please refine your criteria"

flqn 6y ago

In addition to using cursors or whatever pagination method suits your backend in query params, it's also a good idea to include pagination URLs in the response itself if you can. Greatly simplifies what the client has to do and reduces coupling since now the client doesn't need to care what your query param structure is

montoro 6y ago

Great article! I wrote something similar, includind a playground which serves as a benchmark to compare the various pagination options: https://www.samu.space/api-pagination/ https://www.samu.space/api-pagination/

mewpmewp2 6y ago

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 easily act out binary search to find what they are looking for in an ordered list of items. 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.

deleted 6y ago
[deleted]
cj 6y ago
A while ago, github replaced the pagination on their commits page to be based on a git commit ID instead of a page number. After that change, it made it a lot more difficult to find the oldest commit in a large repo - frustrating. That said, I think the percent of average ability internet users (ie. people visiting an ecommerce shop) will virtually never attempt to navigate by changing values in a query string param. High scores on a gaming forum, maybe more likely. Either way, if users need the ability to jump through pages, I would hope that would be exposed in a UI rather than expecting people to edit the URL directly.
- mewpmewp2 6y ago
  Yeah, it's best if it's possible to do it both ways. With url and also by clicking links and maybe even add a select/input to go to certain page. If you look at any e-commerce systems, ranging from WooCommerce to Shopify, Amazon and Walmart, I think they all use pagination. Some Amazon pages do have infinite scroll however I have also been frustrated without having the ability to quickly go through commits... Or I think releases for that matter? For instance, browsing through tags/release versions, which should be a very valid use-case in my opinion also uses cursor based navigation.

ChrisMarshallNY 6y ago

I like the idea of a "cursor," or some kind of appointed "variable." It has the potential to become complex, so I would assume it was an "also" capability, as opposed to an "instead of" capability. I like the idea of a "range" syntax ("[X..<Y], [X...Y], [X<..Y], [X<.<Y], etc). When I write APIs, server performance isn't really an issue for me. Most of the performance bottleneck, in my experience, is data transfer, so being able to optimize that, pays the greatest dividends. Also, making the API easy to understand, and express semantically, is important.

EugeneOZ 6y ago

I’ve spent more time reading this article, than this approach could save in practice if we accumulate all the saved milliseconds.

Abimelex 6y ago
wow having this kind of mindset would probably have left us in the stone age.

lkbm 6y ago

I tried running their exact example queries, since I conveniently have a >100k row PostgreSQL table available of the same name. (> 100k rows) The first (offset) was indeed on the order of 5x slower, but I suspect what the author saw with a 40ms to a 0.1ms time difference was that it wasn't pre-warmed first run. For me, with offset, the FIRST run was 25ms, but subsequet runs are around 2-3ms. For `id > 10000`, it was under 0.05ms. It's also very odd that they don't do an `order by`. This seems important. Default ordering is semi-stable. It'll tend not to change, but it can at any point. Benchmarking without that may be misleading.

callesgg 6y ago

I think is better to not use pagination at all. Design your api or page so that you receive all or more entries than you could possibly need. If the user wants them all pagination is just in the way. If the user does not want them all give them as many as they are likely to be able to handle.

hellcow 6y ago
"Woah, our database is slowing to a crawl, requests are deadlocked everywhere. Yeah, some asshole is hitting GET /messages and pulling 2TB in a single request again." "Surely that's what he wanted."
- callesgg 6y ago
  Given that is what the person is doing, that is likly what they are trying to do. Most of the times when I do things, I do it cause I want to do it, not cause I did an opsie.
  - scrollaway 6y ago
    "let's allow users to DOS us in a single request if they want to" is not an acceptable design decision, I'm sure you are aware of that.
    - callesgg 6y ago
      Most services don’t handle ddos amounts of data, a few 1000 rows of data is fine. Don’t design like you are Twitter if you are not. It is a waste of man hours. If I as a client need 10 000 rows of data that is what I will ask for either in one request or in a 100 consecutive.
Can_Not 6y ago
This is terrible advice, sending the client as little as reasonably possible (therefore use pagination) is the most sane, performant, affordable, and secure default assumption. Any rails/laravel/feathersjs style framework have multiple types of pagination built in for free.

nareshb513 6y ago

I have implented such a work in my initial career days like 15 yrs back there i have implemented first, previous,next, last no goto page number. It works for multiple columns in the order by. The trick is to swith the order by in reverse and limit the results to page size, this way we get results in reverse orde but while returning just send them.in the reverse order.... The assumption is to include the primary key as mandatory order by at the end implicitly. This makes a lot easy in other situations like if mulitple pages of records found with same value.. etc...

Abimelex 6y ago

thats how firebase does it. It's quite impossible to have proper pagination on realtime results, that's why I believe they used this approach: https://firebase.google.com/docs/firestore/query-data/query-cursors https://firebase.google.com/docs/firestore/query-data/query-...

abhishekjha 6y ago

Can somebody elaborate on what the last paragraph means? If I have a limit of count per page and I know which page I am based on URL I can always generate a prev/next page link. I guess it is pointing out that limit/offset needs be used in such a case. How did reddit do it in terms or pagination? Such a large website wouldn’t survive on limit/offset.

ivoecpereira 6y ago

I have written about this as well[1] and even built a Github PoC about it comparing both approaches regarding speed[2] but one of the main flaws is the lack of a deeper consideration for sorting and filtering examples and impact demonstration. Will look into adding more detail about that in an addendum. [1] https://medium.com/swlh/why-you-shouldnt-use-offset-and-limit-for-your-pagination-4440e421ba87?source=friends_link&sk=2dafef5c1fb698e2f7884bf5e8149b37 https://medium.com/swlh/why-you-shouldnt-use-offset-and-limi... [2] https://github.com/IvoPereira/Efficient-Pagination-SQL-PoC https://github.com/IvoPereira/Efficient-Pagination-SQL-PoC

sonthonax 6y ago

This is one of those obvious things that people have a blockheaded aversion towards. In every job I’ve consulted on, there has been a component where pagination is the bottleneck. And it’s rarely where pagination could be useful (like a static list of products). I typically see it when someone builds an aggregating (and aggravating) microservice that pulls all of the data from another service; that blocks the entire database. Perhaps it’s the world of ‘Django developers’ I find myself in. But the fact this simple design pattern reaches the front page of Hackernews worries me. I’ve personally had backend developers give confused looks and diatribes about simplicity when I’ve suggested this approach. Frontend developers frequently give the greatest resistance, which I think is because they most often act in concert with product managers who are welded to certain UX idioms that they chose without fully imagining the engineering consequences of. One approach which I try to push people towards is fetching a big list (N≈5000) and paginating it however the UX designer wants. The response of the big list should be sparse, that is without including additional fields that aren’t displayed by the front end (and fetching more data when the user navigates). You’ll frequently get puzzled looks suggesting this, but benchmarks will usually show that fetching 5000 rows and a small number of columns takes a few milliseconds, and can be serialised into 150kb. On balance it ends up being faster: as you’ll get fewer network requests; fewer round trips to the database; fewer fetches; and less time spend serialising (which is a major bottleneck itself that Python developers ignore).

raihansaputra 6y ago
Sometimes it's the case of overoptimising/early optimization too. BE doesn't want to create another endpoint with simplified fields, FE being overly concerned with size of JSON responses over the wire / being processed client side (while the image for each item is not optimized themselves). Thanks for sharing the Big N approach, I have to try that.