7 ms·

Do not use a page argument for pagination. If you have another process/client concurrently adding/removing items, then some items will be returned twice, and ot

Do not use a page argument for pagination. If you have another process/client concurrently adding/removing items, then some items will be returned twice, and others will never be returned. It is better to use, for example, the ID of the last returned item as a starting point for the next query.

kaoD 6y ago
As a user I expect that to happen. Cursors on the other hand are awful for getting to arbitrary pages, they are mostly useful for "More" links as on HN or Reddit. It's a trade-off.
- felixfbecker 6y ago
  Cursors are also the only reliable option for supporting programatic usage for automation use cases.
- masklinn 6y ago
  I’d say they’re right: cursors are way better for an API. Pages are way better for a person. This here is about an API.
  - matt-attack 6y ago
    Well good luck giving your users direct page access when your API only supports cursors.
  - tstrimple 6y ago
    How often do people really jump to an arbitrary page? I'd say filtering / searching capabilities are far more important for users than paging.
    - _nothing 6y ago
      It depends? If I'm looking for a new desk on IKEA's online catalog then I care more about filtering/searching, but if I'm reading through a conversation on a forum and want to be able to link to certain sections then I want that paginated.
      - tshaddox 6y ago
        But even for the latter case, surely you're not specifically interested in a specific page called "page 50" but rather you're interested in items satisfying some predicate (like "posts from 2 weeks ago") or locations respective to the entire list (like "halfway through the list"), and it would be much better if the user interface supported those sorts of navigation.
  - gls2ro 6y ago
    Here I think it makes sense to split the API in two classes: 1. APIs consumed by other backends lets call them API2B 2. APIs consumed by frontends lets call them API2C In this case cursors are better for API2B but not for API2C as in case of API2C most users expect to be able to jump directly to a specific page. At least when I am designing an API i take different decisions based on this split. For example in case of API2C I always want to see FE design even if I work on backend.
- tshaddox 6y ago
  The notion of "page" really only applies as an arbitrary interface division to make performance predictable. The same book could be published in different form factors such that there's no real meaning to a specific page number. There's no "turn your bibles to page 112." That's even more clearly true when the data itself is changing over time, such that even the first thing on the first page is changing over time. Thus using page numbers is probably a pretty poor proxy for what you're actually trying to do when you say "getting to arbitrary pages." Presumably you are wanting to skip to a specific place in the list, perhaps specified as a percentage ("take me halfway through the list") or as some predicate on the data ("take me to items from 2 weeks ago"). APIs should provide ways of expressing these specific places in a list, instead of requiring you to either guess page numbers or do extra work to calculate them.
  - kaoD 6y ago
    Isn't that just pagination with a different granularity? You'd still present the user with a set of results (a "page") and would let them seek forwards/backwards to the adjacent subsets of results. AFAICT cursors can't support this. And even if you go halfways into the list you can't display all subsequent items, so you'd still have to paginate in some way. The page metaphor is there for a good reason.
    - tshaddox 6y ago
      There are two concepts here. One is simply the idea of a service returning only some portion of the items in a list for each request. That notion almost always exists simply for practical reasons: to bound the performance for retrieving, formatting, transferring, and consuming the list. I have no problem with that. The other concept is using an actual page number to make requests, e.g. requesting {page: 1} and then subsequently requesting {page: 2}. This concept is the one I was claiming is less desirable than some alternatives. As for cursors, I don't see any reason why you couldn't make requests like {listPosition: "50%"} or {createdBefore: "2020-02-15"} and then still use cursors in the response to request the previous or next page. (Those two examples probably aren't actually good API naming conventions, but it should demonstrate the idea.)
dec0dedab0de 6y ago
i prefer an offset, then a crawling client can pad their requests and remove anything with a duplicate id.
- ngrilly 6y ago
  That solves the problem of items added concurrently (by deduplicating them) but that doesn't solve the problem of removed items.
  - dec0dedab0de 6y ago
    The only thing that completely solves for removed items is constantly polling, or setting up a webhook/callback of some kind. Padding the offset would solve for the problem mentioned where deleting an item would mean some non deleted items are not included in the paging results because they got moved up a page after that page was requested, but before the next page was requested. For example If I request 100 items at a time but set my offset to be 90 more than what i have received so far, i can expect my response to have duplicates, if it does not then i know my offset was not padded enough and i can request from a different offset. Of course you would adjust the numbers based on knowledge of the data. Edit: If you used the ID of the last item instead of an offset, then you could get errors if your last item is in fact the one that was deleted.
    - ngrilly 6y ago
      Your padding + deduplication solution is nice. > Edit: If you used the ID of the last item instead of an offset, then you could get errors if your last item is in fact the one that was deleted. If the items are sorted by ID, then we use the ID of the last item x. But for example if they are sorted by timestamp, then we use the timestamp of the last item (and maybe the ID to break ties). Then it doesn't matter if the last item is still there or not. We are only considering values before or after depending on the sort order.
profquail 6y ago
You can also use SQL:2011 "System-Version Tables" (a.k.a. temporal databases) supported in most of the major RDBMSs now. You'd just need to keep track of a timestamp when you started querying/paginating and include it as part of the SQL query, which'll give clients a consistent view even if the database is being concurrently modified.
- Scarbutt 6y ago
  temporal databases) supported in most of the major RDBMSs now. Which ones?
  - mgkimsal 6y ago
    I'm only aware of SQL Server (2016), Oracle and MariaDB supporting temporal tables, and... having dived in to them, they can certainly add some complexity to your data and queries. Would be happy to learn of more - had to do some digging on this in late 2019 for a PostgreSQL project, but there's nothing native or 'standard' for pg at that point in time.
    - dragonwriter 6y ago
      It's in progress: https://commitfest.postgresql.org/32/2316/ https://commitfest.postgresql.org/32/2316/
      - mgkimsal 6y ago
        Thanks!
Naac 6y ago
What does Hackernews use in this case?
- weaksauce 6y ago
  from what I can tell, every item in the hackernews data set is a monotonically increasing integer id and comments/posts are not fundamentally treated differently. for instance your comment is 26227524 and the parent post is 26225373 edit: hacker news pagination is not high priority apparently since they just use the easiest way with p= some number.
  - TameAntelope 6y ago
    It's okay for a submission to show up twice/not show up at all on a single page view of HN, so I can see why it wouldn't be a priority.
  - mewpmewp2 6y ago
    For forum like UI it is better to have numbered pages in ny opinion.
slt2021 6y ago
you can return urls that guarantee proper pagination with your response, if the output is more than the limit. this way you can incorporate your logic (id of the last returned item is a starting point) in pagination and make sure as your API evolves, client applications pagination logic doesn't have to change as long as you provide proper pagination links for example GET /customer/1/orders/ response: {'orders': [order1, order2, order3], 'navigation': { 'firstpage': '/get/customer/1/orders/', 'nextpage': '/get/customer/1/orders/?query=orderId^GT4', 'lastpage': '/get/customer/1/orders/?query=orderId^GT990', 'totalrows': 1000 } GT means greater than
lhorie 6y ago
If items get returned twice while iterating, then I know something got added. Manga websites do this and it's a nice unintended feature. Slicing by ID is how Github does commit history and it drives me nuts that I can't jump several pages, for example, to see when the first commit was, or to guess whereabouts some commit is given a known time range. IDs make it impossible to do anything but iterate step by step. I much prefer an interface that exposes: a) how many items exist in total b) which offset it's starting from c) how many items in the slice Then if I want a slice from 300-8000th items, I can type exactly that in the URL. Yes, I understand this will render a huge page, just let me do it the one time so I won't be spamming your server with requests over the next hour trying to find something while fighting against bad UX.
- ngrilly 6y ago
  > If items get returned twice while iterating, then I know something got added. Fair point. I agree, that's a nice side effect. But what if you're looking at page 1, and an item is removed from that page? Then you'll never see the first item at page 2, because it's now the last on page 1. > Then if I want a slice from 300-8000th items, I can type exactly that in the URL. That's a nice feature. But it can put a lot of load on your backend if you paginate over 10 of thousands of items.
  - lhorie 6y ago
    > an item is removed How common are concurrent removals in practice though? I can't think of a single instance off the top of my head where this is problematic and you can't just go back to the previous page if you're really paranoid or confused that something is "missing" > it can put a lot of load on your backend if you paginate over 10 of thousands of items Look at it in aggregate. Fiddling w/ URL params to paginate (instead of clicking pagination links) is a power user move. If I want the date of first commit in a repo, I'll only look at the last page (vs paging through the entire history). For guessing, I can click a page, and if I went too far, binary search from there (again, vs linear search). Etc. Even for the most degenerate use case (e.g. some jerk trying to crawl over the entire dataset), the load is smaller with a single request than the overhead of multiple requests. Paginating is not an appropriate mitigation strategy against this type of traffic, and you arguably can implement detection/caching/blocking mechanisms much more easily for naive huge queries than if you need to differentiate regular traffic from bots.
cmckn 6y ago
I'd suggest caching the result of a query that could return multiple pages, if consistency is truly important. Otherwise, I don't think it really matters which option you choose, as long as you document the behavior. Edit: obviously the proper impl totally depends on your app. If the result set is enormous, caching doesn't make sense. If it's rapidly changing, pagination probably doesn't make sense. etc, etc.
- ngrilly 6y ago
  But then you need to provide some kind of query ID in the the HTTP request? And if you many concurrent clients, that can be expensive in terms of RAM? If we don't care about added items (they can be deduped client-side), and only care about removed items, maybe the backend can maintain a tombstone timestamp on each deleted item, instead of deleting them, and then the client can provide a "snapshot" timestamp in the query that can be compared with the tombstone timestamp.
  - cmckn 6y ago
    > But then you need to provide some kind of query ID in the the HTTP request? And if you many concurrent clients, that can be expensive in terms of RAM? A query ID is super easy to implement, and yes, for any application you run you have to be aware of the resource requirements. Tune your eviction policy, and this is totally feasible. Deduping and tombstones is messier to implement IMO, and hitting a cached result for the next page (e.g. a redis LIST) is probably less expensive than a "query" (whatever that means for your backend).
- dragonwriter 6y ago
  If consistency is really important, don't paginate on the backend at all. The only way to win is not to play the game. That said, using “page of results preceding <first id if following page>” and “page of results following <last id of preceding page>” reduces obvious pagination artifacts compared to <page number n>. Whether it's better to beat consumers over the head with inconsistency due to concurrent changes probably depends on the application or provide a nearer illusion of consistency probably depends on application domain and use case.

kaoD 6y ago

As a user I expect that to happen. Cursors on the other hand are awful for getting to arbitrary pages, they are mostly useful for "More" links as on HN or Reddit. It's a trade-off.

felixfbecker 6y ago
Cursors are also the only reliable option for supporting programatic usage for automation use cases.
masklinn 6y ago
I’d say they’re right: cursors are way better for an API. Pages are way better for a person. This here is about an API.
- matt-attack 6y ago
  Well good luck giving your users direct page access when your API only supports cursors.
- tstrimple 6y ago
  How often do people really jump to an arbitrary page? I'd say filtering / searching capabilities are far more important for users than paging.
  - _nothing 6y ago
    It depends? If I'm looking for a new desk on IKEA's online catalog then I care more about filtering/searching, but if I'm reading through a conversation on a forum and want to be able to link to certain sections then I want that paginated.
    - tshaddox 6y ago
      But even for the latter case, surely you're not specifically interested in a specific page called "page 50" but rather you're interested in items satisfying some predicate (like "posts from 2 weeks ago") or locations respective to the entire list (like "halfway through the list"), and it would be much better if the user interface supported those sorts of navigation.
- gls2ro 6y ago
  Here I think it makes sense to split the API in two classes: 1. APIs consumed by other backends lets call them API2B 2. APIs consumed by frontends lets call them API2C In this case cursors are better for API2B but not for API2C as in case of API2C most users expect to be able to jump directly to a specific page. At least when I am designing an API i take different decisions based on this split. For example in case of API2C I always want to see FE design even if I work on backend.
tshaddox 6y ago
The notion of "page" really only applies as an arbitrary interface division to make performance predictable. The same book could be published in different form factors such that there's no real meaning to a specific page number. There's no "turn your bibles to page 112." That's even more clearly true when the data itself is changing over time, such that even the first thing on the first page is changing over time. Thus using page numbers is probably a pretty poor proxy for what you're actually trying to do when you say "getting to arbitrary pages." Presumably you are wanting to skip to a specific place in the list, perhaps specified as a percentage ("take me halfway through the list") or as some predicate on the data ("take me to items from 2 weeks ago"). APIs should provide ways of expressing these specific places in a list, instead of requiring you to either guess page numbers or do extra work to calculate them.
- kaoD 6y ago
  Isn't that just pagination with a different granularity? You'd still present the user with a set of results (a "page") and would let them seek forwards/backwards to the adjacent subsets of results. AFAICT cursors can't support this. And even if you go halfways into the list you can't display all subsequent items, so you'd still have to paginate in some way. The page metaphor is there for a good reason.
  - tshaddox 6y ago
    There are two concepts here. One is simply the idea of a service returning only some portion of the items in a list for each request. That notion almost always exists simply for practical reasons: to bound the performance for retrieving, formatting, transferring, and consuming the list. I have no problem with that. The other concept is using an actual page number to make requests, e.g. requesting {page: 1} and then subsequently requesting {page: 2}. This concept is the one I was claiming is less desirable than some alternatives. As for cursors, I don't see any reason why you couldn't make requests like {listPosition: "50%"} or {createdBefore: "2020-02-15"} and then still use cursors in the response to request the previous or next page. (Those two examples probably aren't actually good API naming conventions, but it should demonstrate the idea.)

dec0dedab0de 6y ago

i prefer an offset, then a crawling client can pad their requests and remove anything with a duplicate id.

ngrilly 6y ago
That solves the problem of items added concurrently (by deduplicating them) but that doesn't solve the problem of removed items.
- dec0dedab0de 6y ago
  The only thing that completely solves for removed items is constantly polling, or setting up a webhook/callback of some kind. Padding the offset would solve for the problem mentioned where deleting an item would mean some non deleted items are not included in the paging results because they got moved up a page after that page was requested, but before the next page was requested. For example If I request 100 items at a time but set my offset to be 90 more than what i have received so far, i can expect my response to have duplicates, if it does not then i know my offset was not padded enough and i can request from a different offset. Of course you would adjust the numbers based on knowledge of the data. Edit: If you used the ID of the last item instead of an offset, then you could get errors if your last item is in fact the one that was deleted.
  - ngrilly 6y ago
    Your padding + deduplication solution is nice. > Edit: If you used the ID of the last item instead of an offset, then you could get errors if your last item is in fact the one that was deleted. If the items are sorted by ID, then we use the ID of the last item x. But for example if they are sorted by timestamp, then we use the timestamp of the last item (and maybe the ID to break ties). Then it doesn't matter if the last item is still there or not. We are only considering values before or after depending on the sort order.

profquail 6y ago

You can also use SQL:2011 "System-Version Tables" (a.k.a. temporal databases) supported in most of the major RDBMSs now. You'd just need to keep track of a timestamp when you started querying/paginating and include it as part of the SQL query, which'll give clients a consistent view even if the database is being concurrently modified.

Scarbutt 6y ago
temporal databases) supported in most of the major RDBMSs now. Which ones?
- mgkimsal 6y ago
  I'm only aware of SQL Server (2016), Oracle and MariaDB supporting temporal tables, and... having dived in to them, they can certainly add some complexity to your data and queries. Would be happy to learn of more - had to do some digging on this in late 2019 for a PostgreSQL project, but there's nothing native or 'standard' for pg at that point in time.
  - dragonwriter 6y ago
    It's in progress: https://commitfest.postgresql.org/32/2316/ https://commitfest.postgresql.org/32/2316/
    - mgkimsal 6y ago
      Thanks!

Naac 6y ago

What does Hackernews use in this case?

weaksauce 6y ago
from what I can tell, every item in the hackernews data set is a monotonically increasing integer id and comments/posts are not fundamentally treated differently. for instance your comment is 26227524 and the parent post is 26225373 edit: hacker news pagination is not high priority apparently since they just use the easiest way with p= some number.
- TameAntelope 6y ago
  It's okay for a submission to show up twice/not show up at all on a single page view of HN, so I can see why it wouldn't be a priority.
- mewpmewp2 6y ago
  For forum like UI it is better to have numbered pages in ny opinion.

slt2021 6y ago

you can return urls that guarantee proper pagination with your response, if the output is more than the limit. this way you can incorporate your logic (id of the last returned item is a starting point) in pagination and make sure as your API evolves, client applications pagination logic doesn't have to change as long as you provide proper pagination links for example GET /customer/1/orders/ response: {'orders': [order1, order2, order3], 'navigation': { 'firstpage': '/get/customer/1/orders/', 'nextpage': '/get/customer/1/orders/?query=orderId^GT4', 'lastpage': '/get/customer/1/orders/?query=orderId^GT990', 'totalrows': 1000 } GT means greater than

lhorie 6y ago

If items get returned twice while iterating, then I know something got added. Manga websites do this and it's a nice unintended feature. Slicing by ID is how Github does commit history and it drives me nuts that I can't jump several pages, for example, to see when the first commit was, or to guess whereabouts some commit is given a known time range. IDs make it impossible to do anything but iterate step by step. I much prefer an interface that exposes: a) how many items exist in total b) which offset it's starting from c) how many items in the slice Then if I want a slice from 300-8000th items, I can type exactly that in the URL. Yes, I understand this will render a huge page, just let me do it the one time so I won't be spamming your server with requests over the next hour trying to find something while fighting against bad UX.

ngrilly 6y ago
> If items get returned twice while iterating, then I know something got added. Fair point. I agree, that's a nice side effect. But what if you're looking at page 1, and an item is removed from that page? Then you'll never see the first item at page 2, because it's now the last on page 1. > Then if I want a slice from 300-8000th items, I can type exactly that in the URL. That's a nice feature. But it can put a lot of load on your backend if you paginate over 10 of thousands of items.
- lhorie 6y ago
  > an item is removed How common are concurrent removals in practice though? I can't think of a single instance off the top of my head where this is problematic and you can't just go back to the previous page if you're really paranoid or confused that something is "missing" > it can put a lot of load on your backend if you paginate over 10 of thousands of items Look at it in aggregate. Fiddling w/ URL params to paginate (instead of clicking pagination links) is a power user move. If I want the date of first commit in a repo, I'll only look at the last page (vs paging through the entire history). For guessing, I can click a page, and if I went too far, binary search from there (again, vs linear search). Etc. Even for the most degenerate use case (e.g. some jerk trying to crawl over the entire dataset), the load is smaller with a single request than the overhead of multiple requests. Paginating is not an appropriate mitigation strategy against this type of traffic, and you arguably can implement detection/caching/blocking mechanisms much more easily for naive huge queries than if you need to differentiate regular traffic from bots.

cmckn 6y ago

I'd suggest caching the result of a query that could return multiple pages, if consistency is truly important. Otherwise, I don't think it really matters which option you choose, as long as you document the behavior. Edit: obviously the proper impl totally depends on your app. If the result set is enormous, caching doesn't make sense. If it's rapidly changing, pagination probably doesn't make sense. etc, etc.

ngrilly 6y ago
But then you need to provide some kind of query ID in the the HTTP request? And if you many concurrent clients, that can be expensive in terms of RAM? If we don't care about added items (they can be deduped client-side), and only care about removed items, maybe the backend can maintain a tombstone timestamp on each deleted item, instead of deleting them, and then the client can provide a "snapshot" timestamp in the query that can be compared with the tombstone timestamp.
- cmckn 6y ago
  > But then you need to provide some kind of query ID in the the HTTP request? And if you many concurrent clients, that can be expensive in terms of RAM? A query ID is super easy to implement, and yes, for any application you run you have to be aware of the resource requirements. Tune your eviction policy, and this is totally feasible. Deduping and tombstones is messier to implement IMO, and hitting a cached result for the next page (e.g. a redis LIST) is probably less expensive than a "query" (whatever that means for your backend).
dragonwriter 6y ago
If consistency is really important, don't paginate on the backend at all. The only way to win is not to play the game. That said, using “page of results preceding <first id if following page>” and “page of results following <last id of preceding page>” reduces obvious pagination artifacts compared to <page number n>. Whether it's better to beat consumers over the head with inconsistency due to concurrent changes probably depends on the application or provide a nearer illusion of consistency probably depends on application domain and use case.