Paginating Requests in APIs (2020)
ignaciochiazzo.medium.com
ignaciochiazzo.medium.com
I don't think I've used offsets in APIs for at least 10 years. Lightly-obfuscated cursor tokens are one of the first things I build in web projects and that's usually less than an hour's work.
If you _really_ need the ability to drop the needle in your dataset with pagination, design your system to use pseudo-pagination where you approximate page-to-record mappings and generate cursors to continue forward or backward from that point.
If you're dealing with very small datasets, its fine. I'm an average person using average APIs, which means that when I see offset-based pagination, it's usually on a service deployed and used by a lot of people.
Unsurprisingly, the offset based APIs often include some other arbitrary limit like "offset limited to 10k" or something silly but understandable if you've built an API used by thousands of people before, or understand how databases work.
They're also often superseded by betters APIs that actually allow you to page the entire result set. Then you have a deprecated API that you either support forever or annoy users by turning it off.
So yes, if you are building something non-internal/pet project, limit/offset is probably the mark of the novice.
Can you explain why offsets would never be a suitable solution? Is there a clear explanation as to why?
I understand how cursors are superior in some cases. But what if you have a site which paginates static data? Offsets would allow you to cache the results easily, overcoming any performance concerns (which would be irrelevant if the dataset was small anyway), providing a better user experience (and developer experience due to simpler implementation details) overall.
I can see that it would be a novice move if you’ve got staggering amounts of records that take a while to query. But that’s actually pretty rare in my experience.
Limit/offset is usually (though not always, as you point out) egregious for anything more than hobbies or small projects. But, I am biased as when I build APIs, I definitely expect some amount of traffic/volume/tuple count, and offset/limit will not do.
Be very careful with timestamp or auto-increment id pagination too. These don't necessarily become visible in the same order since the id or timestamp is generated before the transaction commits unless your database has some specific way of ensuring otherwise.
We use an auto-increment id, and lock inserts on the related account (which always limits the scope of the query).
The only other (stateless) way I can think of is to somehow fiddle with transaction numbers linked to commit order.
In traditional databases, the number linked to the commit order is usually the LSN (Log Sequence Number), which is an offset into the transaction log. Unfortunately, you can't figure that out until your transaction commits, so you can't use it during the transaction.
A hypothetical database where you could see your own LSN from within a transaction would require transaction commit order to be pre-determined at that point. An unrelated transaction with a lower LSN would block your transaction from committing.
In non-traditional databases, this could work differently. E.g. in kafka you can see your partition offsets during a transaction and messages in that partition will become visible in offset-order. The tradeoff is that this order doesn't correspond to global transaction commit order and readers will block waiting for uncommitted transactions (and all the other things about kafka too).
Duplicates or missed entries in the result set are the most likely outcome of offset-based pagination.
?startWith=<item_id>&sortBy=<alpha|datetimedesc|whatever>Skipping forward by date, by username, or even by concept might make long threads much quicker to scan through and understand.
If you want to jump ahead in the results, that is fundamentally unstable though.
1. Accept that the results will be unstable as the underlaying set changes. Pagination may either miss or double-include items unpredictably.
2. Store an intermediate result set guaranteed to remain stable for the necessary duration. This will provide stable pagination, at the cost of solving cache-expiry problems.
3. Use or build a version-controlled data store. I don't know of anything in common use, but there is likely something available. This is similar to #2, but moves the work from the application into the data-storage layer. You then paginate against a set version of the data. Imagine something similar to Immutable, but with expiry for unreachable nodes.
Unsure what #3 looks like at scale.
In my professional experience, lots of devs will implement fetching APIs and not consider pagination, and then when the responses start growing (testing data, use, whatever), user experience sucks. Pagination should be a default API design for anything returning an unbounded list of items.
But in the case of GraphQL, like I may get an incomplete list, or I may get a complete list that will have some fields with missing data, or some combination of both, going down deep depending on the structure of the query. I don't see a clear way to request the missing data without duplicating part of what I already have, and I don't see a clear way to combine the results.
But I may be missing something about GraphQL or something about the tools that makes this simple.
For example something like this:
{
users(first: 10000, after: "cursor123") {
edges {
cursor
node {
id
name
friends(first: 10000, after: "cursor235") {
edges {
cursor
node {
id
name
}
}
}
}
}
}
}That said, paginating multiple resources on the same page is still going to be complicated.
Probably the nicest way to expose this that fits contemporary sensibilities would be as a lazy sequence that does sensible prefetching and asks the server for more data as it’s iterated through.
There's no worry about wasting a full request on the last page with a single item. In fact there's no worry about round trips at all, it's just a matter of buffer back pressure that communicates the need for more or less.
Hmm, when you think about it, its a pretty good way to go.
Isn't this an accurate description of cursor-based pagination? You can have the server hold the cursor and associate a request for the next page based on the client ID (like in the PostgreSQL wire protocol), or you can make the flow stateless (at the network level) by handing the client a ticket for the next page.
I see you mentioned gRPC streams in a sibling comment, which are a great alternative to REST-based pagination, but they are highly stateful! Streams are built into the protocol, so a generic gRPC client will handle most of the state juggling that would have been your responsibility with a REST client.
We're also talking about APIs in general, not just http REST.
>It's still multiple requests on a streaming API
Perhaps, but the requests can be pipelined. You don't need to wait for the response to complete before asking for more.
gRPC is able to offer powerful streaming abstractions because it utilizes HTTP/2 streams, which are cursor based rather than strictly connection oriented. The state is still there; it's just a protocol-level abstraction rather than an application-level abstraction.
> Perhaps, but the requests can be pipelined. You don't need to wait for the response to complete before asking for more.
That sort of defeats the purpose of grpc flow control, doesn't it?
Why do you say that? I don't know the full implementation details themselves but generally there's no reason you can't safely ask for even more after having asked and consumed some. If you have a buffer of M bytes and ask for M, then consume N, you could immediately ask for N more without waiting to receive all of the original M.
Although, I wasn't speaking about gRPC in that case though. I'm not sure how exactly gRPC achieves back pressure. I was only speaking abstractly about a pipelined call vs many pages. You seemed to claim that multiple requests was a requirement.
But fine, ignoring gRPC, you could possibly tune your stack such that normal http calls achieve back pressure from network stacks and packet loss. Http is built on top of TCP streams, after all. That doesn't make it inherently stateful does it?
Going all the way back, I still think its fair to say that a streaming response with backpressure can be stateless and without multiple requests. If you want to argue that multiple packets or TCP signals are needed then perhaps so, but I think that's a far cry from the many separate requests a paginated call requires and I dont think its accurate enough to conflate them.
I think we're saying the same thing but using different formulations. If you send an HTTP request for a list with 20 items, then get back a response with 10 items and a link for the next page, that is essentially the same as cosuming 20 items over a stream with flow control. The point of returning a cursor in the response and having the client send a new request for the next page is to support a stateful stream over a stateless protocol. In neither case are you waiting for the response to be complete before processing items, since your message indicates that "complete" here means the full result set has been sent to the client.
> But fine, ignoring gRPC, you could possibly tune your stack such that normal http calls achieve back pressure from network stacks and packet loss. Http is built on top of TCP streams, after all. That doesn't make it inherently stateful does it?
That's pretty much how streaming responses are implemented in TCP-based protocols (like the SQL query APIs exposed by Postgres or MySQL). TCP connections can be terminated for unrelated reasons, which is why you don't see this pattern very often in recent protocols. When a TCP connection is dropped and restarted due to, say, network congestion, you have to restart the paginated operation from the head of the list. H2 (and, vicariously, gRPC) streams are built to be more resilient to network noise.
But to answer your question, yes, that pattern is inherently stateful. Pagination has to be, since the server has to know what the client has seen in order to prepare the next batch of results. You can manage this state at the protocol level (with streams), or you can push it to the application level (with cursor tokens embedded in the messages exchanged). The streaming approach requires a stateful server and client, whereas the application-level approach only requires a stateful client.
A paged response needs to sync state across many machines. As you have said, you need a clientID, a cursor reference, or a sticky session. That's not nothing.
I think they're inherently different approaches.
OK, I think this is what I was misunderstanding in your comments above. You can keep pagination state in a distributed store, but it's not necessary. The implementations I've seen and worked with have all embedded all the information needed to generate the next page of results in the cursor token itself. Kind of like with a JWT or TLS session ticket, there's no need to sync pagination state or use sticky sessions. That approach also provides some resilience in case the server that generated the previous page of results becomes unreachable (something that the client needs to handle by restarting pagination if pagination state is just held in memory by the server keeping the stream connection open).
gRPC's streaming API is a good example. It has backpressure built in and you just need to configure the buffer sizes. Clients just consume items off the stream and async writes will suspend as needed.
Or are you focusing more on the backend machine to machine case? In that case, some kind of automatic prefetching, lazy loading/yield setup sounds pretty nice if that's abstracted away when you want to iterate over a large dataset from a separate resource server. It's not a pattern I've used before, mainly because it's not often that one server wants to know everything that another server has.
1. You could save the order under a token and iterate respective to that saved order, only showing the data for the ids that were originally included. 2. Instead of continuing from a page count show the next amount. Any mutation before that point will be invisible without having to store the original result list (only ids).
You'd need some mechanism to delete the temporary table after a time, of course, but I imagine this is not uncommon.
Another method would be having a last-modified timestamp on every row in the DB; then you could select records at or before the initial query time. Seems like overkill just for this one purpose, but I imagine it might be generally useful information to have in the DB.
(1) Don't solve the problem, trust the user to figure it out. This is the default (update rows and if the data updates underneath someone then tough) and it works in 95%? of cases or so. Works poorly when computers consume your results.
(2) Versioning tables! Forget updates let's just insert all the things!
SELECT * FROM projectVersions
NATURAL JOIN (SELECT projectKey, MAX(created) AS created
FROM projectVersions
WHERE created <= :time GROUP BY projectKey) AS latest
Deletion is somewhat finnicky here, soft-deletion works just fine as-is but hard deletion brings back issues from issue (1) again. The bigger problem is that if a "project" is a big record then you start copying all this data and your DB grows huge.
(3) Snapshots + Diffs! The previous storage concern can be alleviated by only updating the whole record (a new "snapshot") after 10-20 diffs are recorded, otherwise just store the diff. It's O(1) if you ensure a constant max of diffs... If referential integrity via foreign key constraints is really important to you, the most extreme version of this is a table structure,
snapshotId
[ projectSnapshots ] <----------- [ projectPrimaryContactDiffs ]
\ |
\ | contactId
\ primaryContactId V
-------------------------> [ contacts ]
Other variations of this have extra diff columns sitting on `projectSnapshots` allowing you to change things, possibly just one column which is JSON, etc. ... there are tradeoffs on how available you need the versioned data to be to your database itself for DB queries.
(4) Graph databases. The most extreme form of (3) where we abandon snapshots: maybe every row in some table represents a diff for some column at some time! This ultimately creates a graph database, sentences or "facts" ("Horn clauses") are recorded "at time T, the [subject] [verb]ed such-and-so [object]," you store "record/fieldName/fieldValue" tuples. Sometimes you can also include an integer index to +1 assert or -1 retract facts--queries then sum over the facts, when you find values that are not 0 or 1 you can guess that a _merge conflict_ happened.
(5) Give up and do functional programming :) What this means is, if all of your records are immutable then you get time persistence for free, and you often don't need to copy data as in (2) because you can use structural sharing. The flip side is that everything needs to be accessed by _pointers_ rather than _indexes_, or else whatever is indexed needs to be copied, which can get expensive.
It's worth giving a story for why you would do this. You say up-front, "I want the ability to version a list of Resources for this Project, just like the other fields in my Project Snapshot. When you look at the Project at version 53, you should see the resources that were in that project."
Well, you start with Resources that point to a Project Snapshot or so, but whenever you generate a new Project Snapshot you find yourself copying a bunch of Resources, even when the resources haven't been updated. You maybe insert a ProjectResources many-to-many table, but you're still inserting a bunch into that many-to-many table even when the resources haven't been updated.
The FP instinct comes in when you say "I will have Projects have a reference to a ResourceList and store the reference to that ResourceList, so that I don't have to do this copying when I don't update the resources." Now the arrow has been (somewhat) inverted, Projects point at Resources (somewhat) rather than Resources pointing at Projects. Problem solved, sort of:
[ projectSnapshot ] ----> [ resourceList ] <--- [ resourceListItem ]
/
[ resource ] <-----------
The story is that working backwards you say "ok I'm going to bound their update so each of their updates only inserts, like, 50 ResourceListItem records max," so now you have some notion of a ResourceListPages table, the resource belongs to a page of 50 or so resources in the ResourceList... except now you're still inserting 1,000 pages when you reconstruct every ResourceList. It got way better but it's still not scaling. In desperation you reach for a recursive structure and write out this comment in some source code, haha:
/**
* A ResourceList of order 0 is a page of up to 50 Resources which
* foreign-key to it, for balancing reasons we store here a "count" of how
* many Resource records point to it.
*
* A ResourceList of order N > 0 is a collection of pointers to up to 8
* ResourceLists of order N-1, called subList1, subList2, ... subList8,
* and the count is the sum of counts of all of the sublists.
*/
In the same way, asking for counts may or may not be a quick answer, depending on both the table structure and the query being performed. Query the number of customers who started this year, on a table indexed by start date, and it's incredibly cheap. If that same table is only indexed by last name, then counts become more expensive. I'd say that the advice to return the counts has an implicit addendum to make sure that your database is appropriately indexed such that your typical queries are cheap to perform.
Meanwhile I can only think of one use case for pagination with exact row counts – a user facing application. If you're preallocating storage you can get by with an estimate. If you're consuming an API and want something from near the end you can flip the sort order.
There is no single universal row count that the database could cache, so it must
scan through all rows counting how many are visible. Performance for an exact
count grows linearly with table size.
But now we come to a quirk, SELECT COUNT(DISTINCT n) FROM items will not use
the index even though SELECT DISTINCT n does. As many blog posts mention (“one
weird trick to make postgres 50x faster!”) you can guide the planner by rewriting
count distinct as the count of a subquery
https://wiki.postgresql.org/wiki/Index-only_scans#Is_.22coun...
It says that index only scans can be used with predicates and less often without predicates, though in my experience I've seen the index often used even without predicates.
Index-only scans are opportunistic, in that they take advantage of a pre-existing
state of affairs where it happens to be possible to elide heap access. However,
the server doesn't make any particular effort to facilitate index-only scans,
and it is difficult to recommend a course of action to make index-only scans
occur more frequently, except to define covering indexes in response to a
measured need
Index-only scans are only used when the planner surmises that that will reduce the
total amount of I/O required, according to its imperfect cost-based modelling. This all
heavily depends on visibility of tuples, if an index would be used anyway (i.e. how
selective a predicate is, etc), and if there is actually an index available that could
be used by an index-only scan in principle.
The "shortcuts" you're thinking of may be from the MyISAM storage engine days. Since MyISAM doesn't have transactions or MVCC, it can maintain a row count for the table and just return that. But MyISAM is generally not used for the past decade (or more), as it just isn't really suitable for storing data that you care about.
Storage engines with transactions cannot just store a row count per table because the accurate count always depends on your transaction's isolated snapshot.
Do you really need to paginate millions of rows and count them? Can you distribute the database and parallelize counting? Can you save counts somewhere else? Can you use estimates?
I wonder how do Big Co solve this counting problem.
That said I'm not sure if everyone agrees on that definition, from what I know people do consider keyset pagination and cursor pagination to basically mean the same thing.
HashIds is a popular solution if those columns are numerical or can be represented numerically (e.g. timestamp).
We use a cursor that combines the sort key and normally the ID as a secondary sort and pointer value, otherwise you can’t paginate through data where the sort column has duplicates. We don’t really do much to obfuscate these, but we don’t document the structure and people who try to tweak the values won’t get far.
But in most SQL databases, cursors are something you implement and parse at the application layer, and translate to a WHERE clause on the (hopefully indexed) column you're ordering on. That turns the O(N) "OFFSET" into a O(log(n)) index seek.
That said, they tend to live only as long as the db connection (with some exceptions), so yeah you need some application work to make it sane.
Making the implementation details of pagination unimportant to the API layer the user uses.
Imagine a table with the following schema/data: id=1,created_at='2022-28-05T18:00Z' id=2,created_at='2022-28-05T18:00Z' id=3,created_at='2022-28-05T18:00Z'
To retrieve articles in order of descending creation time, our sort order would be: created_at DESC, id DESC
The last item in the ORDER BY query should be a unique key to ensure we have consistent ordering across multiple queries. We must also ensure all supported sort columns have an INDEX for performance reasons.
Assume our application returns one article at a time, we have already retrieved the first article in the result set. Our cursor must include information for that last records ORDER BY values, e.g. serialize('2022-28-05T18:00Z,3'), for example purposes I will use base64, so our cursor is MjAyMi0yOC0wNVQxODowMFosMw==.
When the user requests the next set of results, they will supply the cursor and it will be used to construct a WHERE (AND) expression: created_at < '2022-28-05T18:00Z' OR (created_at = '2022-28-05T18:00Z' AND id < 3)
So our query for the next set of results would be: SELECT * FROM articles WHERE (created_at < '2022-28-05T18:00Z' OR (created_at = '2022-28-05T18:00Z' AND id < 3) ORDER BY created_at DESC, id DESC LIMIT 1
For queries with more than 2 sort columns the WHERE expression will slightly increase in complexity but it need only be implemented once. If the sort order direction is flipped, make sure to adjust the comparator appropriately, e.g. for 'DESC' use '<' and for 'ASC' use '>'.
I'm not complaining since this is also what I usually do, I'm just wondering of theres more to it.
* data of the record may have been updated, but if there are 1,000 records total, paginating in either direction will always return those same 1,000 records regardless of insertion/deletion.
- Filter by created_at <= time the endpoint first returned a result.
- Utilize soft deletes, where deleted_at IS NULL OR deleted_at < time the endpoint first returned a result.
Any keys allowed to be used in the ORDER BY query should also be immutable.
The relevant one is https://google.aip.dev/158, which recommends cursor-based pagination and covers different pagination use-cases, including:
- support for different sort orders - mentioned in article as weakness of keyset pagination
- support for skipping results - mentioned as a weakness of cursor-based pagination
- why to use opaque page tokens
Also I'll add that if you support a pagination API that accepts args (e.g. to filter on different dimensions) you should include a hash of the args in the opaque next page token, and fail the call if the args change. This prevents some nonsense scenarios where you started paging by scanning index A but the user switched filters such that you'd instead scan index B, but you don't have the key for that column.
> Request messages for collections should define a string page_token field, allowing users to advance to the next page in the collection.
> * If the user changes the page_size in a request for subsequent pages, the service must honor the new page size.
> * The user is expected to keep all other arguments to the RPC the same; if any arguments are different, the API should send an INVALID_ARGUMENT error.
> Many APIs store page tokens in a database internally. In this situation, APIs may expire page tokens a reasonable time after they have been sent, in order not to needlessly store large amounts of data that is unlikely to be used. It is not necessary to document this behavior.
I have done this with both Postgres/S3 and Redshift/S3 backends and presigned URLs and looks like I could do it with Snowflake too.
I wrote the post when I was investigating cursor-based pagination, which I had to implement at Shopify. We decided to use Cursor-based pagination since offset performance wasn't good enough. The larger the offset, the slower the query.
We decided to add the cursors to the LINK header page of each request response. The header contains two URLS: the previous and next page.
We saw a tremendous impact! In some cases, iterating over the pages sequentially using Cursor was much faster than sending parallel requests using Page-based pagination.
I built a library where you can compare the performance of Cursor vs Offset for a Shopify Store iterating on specific resources. This helped validate the approach at Shopify and prove to partners that it was worth migrating to Cursors!
More information here https://twitter.com/IgnacioChiazzo/status/153071174122657382...
Another solution or optimization I've seen is in forum software, where if a user executes a search, the IDs of the search results are copied into a "search results" table with the equivalent of a session ID; that way, the data remains stable between paging, and the data set over which pagination has to be done (e.g. via offset/limit) is very small; joins can be used to link to the items in question in the search results (e.g. posts, threads), or all the items that need to be shown in the paginated search results can be copied over to the ephemeral search results table.
And of course, since it's ephemeral and memory is cheap these days, the whole search result can be cached in server-side memory.
And while I really like keyset pagination, it is annoying to implement in some cases. If your sorting column is not unique you need to sort by multiple columns. And that is really annoying and less efficient if you don't have row value comparisons. And not all databases and especially not all ORMs support those. I'm still waiting on EF Core support here, it looks a bit like this might happen but it's not certain yet.
Maybe the actual key value is stored server side for obfuscation/optimization reasons?
Some other problems that crop up:
- A lot of websites expect to serve most results from cache, and to only hit the DB a minority of the time, but to get your hands on a real DB cursor you'd have to hit the DB every time.
- Not all DB's support moving cursors backwards. Maybe most of them don't? I'm not sure.
- Open DB connections are usually a somewhat limited resource.
Why is it more efficient than key set pagination? According to this article https://archive.ph/2021.04.30-125536/https://medium.com/swlh... the only difference is that the value of the key is encoded to allow the implementation to change
According to other commenters cursor based is the same as key-set, but without exposing the internal format in the public API, so it can be implemented as easily as taking a reversible “hash” of a last seen index and the sort order.
Lazides comment suggests some DBs let you expose the cursor which I haven't heard of before. But I agree with you unless what lazide said exists.
IMO, the performance would come down to the underlying database query: you could get faster key-set in some cases, and faster cursor based in others if the query was hitting a good index and using fewer joins. Both approaches, "key set" and "cursor based" let you search based off index, so I don't see how one could be inherently faster?
or for forwards-compatibility.
This certainly doesn’t seem to be the case. Take viewing this very website, for example… are you suggesting that most people want to see all posts of all time, rather than just the first page or two? Paging is used extensively for feeds, and feeds are crazy common these days, and people rarely want to see all posts ever on a feed.
If I ask a SDK to get me 100 items but internally it returns only 50 before needing to make another call with a marker or cursor It would be nice if the SDK had an option to handle this for me (possibly exposing cursors still for those who really want it).
In pseudo-Python:
def get_stuff():
url = "https://example.org/api.php"
while url:
response = requests.get(url)
yield from response.json()
url = parse_link(response.headers["link"]).next
for item in get_stuff():
print(item)Perhaps, “token-based” pagination would be a better term?
Let's do it. When I was first learning about it, I wondered how the concept related to database cursors, if at all.
It's really just a pointer to the next item at its most simple. But it really is just any opaque blob. Maybe you want it to be a jwt/encrypted blob with a request counter so you can track request usage by specific accounts (along with the pointer). jk that's probably a terrible idea (too entangled). Idk, just came up with it. Point is, you could do something like that, it's just a blob opaque to the client.
So I like "token-based pagination".
"A microdata architecture – a variant of the data-oriented architecture structural style – arranges data as a collection of loosely-coupled data. In a microdata architecture, data are fine-grained and the relations are lightweight."
Likely most experienced data architects are now laughing at what a dumb idea the above is. That's the same reaction I had when I first heard of microservices - "that's obviously a bad idea; ppl aren't that dumb", I thought.
It seems like we don’t have the ability to do “all things in moderation” as an industry very well. We’re in constant search of The Silver Bullet, that if we just apply it, will… buy the world a coke and live in perfect harmonies or something. And we go through the cycle again and again and again.
[1] https://developers.intercom.com/intercom-api-reference/refer...
Huh? The client can ask the server to generate a new cursor, any desired amount of items ahead in the list.
I respond:
[
"items": [ {...}, {...}, {...}, ... ],
"next_cursor": "77963b7a"
]
i.e. this forum, HN. If there were ten pages of comments, going from page 1 to page 2, or vice versa is trivial with a "after" or "before" query. But what about jumping directly to page 3 without previously visiting pages 2 or 4?
So far I've implemented a hybrid... pages still exist, but next and previous page (the most common actions) are cursor.
Is there a better way?
You can then do some cool things, especially if your objects are evenly distributed and especially if you don't need exact page sizes or can over-query and hide them as needed.
If you then know the approximate frequency of objects, you can then map some linear scaling to an approximate range of ULIDs. Basically German tank problem in reverse.
In general a user doesn't want to find "page 3", they are looking for a record that has certain characteristics. They shouldn't need to think about pages, just search terms.
If any row is inserted anywhere before the page you requested, you'll see some other item twice (once at the end of the previous page, then again at the top of the next page). Similarly if any item was removed, you'll skip over some other item when paginating due to every page shifting by one.
1. Do you really need to have page numbers and if so, when?
2. Do I really need to skip pages or go to arbitrary one and if so, when?
3. Can't I just show you first N rows forever, and demand that you limit results by tweaking your filter? What is the N I would allow this.
4. When do I show the count of items, and when not?
6. Do I need an estimate or precise count?
7. Shouldn't I just infinite scroll up to some N? How does that limit the user, can he skip some pages in that way or what happens when he back and forth from the item details to the results list?
8. How big are those lists? Do they grow forever and if so, is it frequent or not? How many new items you expect per year? Do users always need to use filter or they need a "gimme everything" case? Can we delegate to client some of the pagination?
Depending on answers to those questions (and more), we can determine technology behind. We know that COUNT(*) is expensive and that OFFSET sucks, but we also know that it might not matter at all in some cases (premature optimization) and it might be deal breaker in others.
And then if you want to pull down the entire result set, you end up drinking it through a coffee stir, and it takes an absurd number of usually serialized calls. Latency kills. 100 calls later and you've downloaded a whopping "big data" level of 3 MiB. That would have fit just fine in 1, maybe 3 API calls.
By far the worst offender I've run across is Azure's Container Registry, where a combination of ridiculously high latency and small page size results in something like 3 MiB of container metadata taking like 5 minutes to fetch. I remember bug reporting it (won't Fix! gaaaahh) and IIRC, we computed the overall throughput to be ~56 kbps.
I've really struggled with Haskell's lack of support of pagination, and worked on at least two "inner-source" libraries that offer what the author is calling "Key Set" or limit/offset and Cursor Based as Servant combinators.
What I've found, is that "Key Set" is much more ergonomic for library authors to implement, if they have to write the database/sql calls themselves, although "Cursor Based" is technically more efficient.
It's my opinion that the standard, out of the box behavior for an endpoint should be to paginate every single endpoint that returns a list of results, but in order to do that easily you'll need some framework support. More mature frameworks have this right now, and IMO this is one of the weak points in using a less supported language like Haskell. You'll either have to roll your own solution, or rely on spotty library support that does that pagination operation in CPU.
One year ago I had to design an API [0] for paginated nodes which also allows nested nodes. Overall there would be more than 100.000 nodes in the database.
On the UI side there would be a tree table to display the nodes. First you would fetch page 0 with 100 nodes and from there you could either perform a paginated fetch for the next page (page 1) or a nested fetch for page 0 for one of the initially fetched nodes. So essentially the API allows paginated and nested fetches where each nested fetch would be a paginated fetch too.
We used cursor based pagination, because there would be added and deleted nodes eventually in a collaborative environment. It was definitely a fun challenge!
https://phauer.com/2018/web-api-pagination-timestamp-id-cont...
In their case, they went with a "pageToken" variable which is basically a cursor.
The API has been around for years.
The biggest drawback is that the expectation is still that data would be valid concatenated, so (for example) multiple results would be expressed as multiple JSON values concatenated together, rather than entries in a single array.
Also article states a con of Keyset is you can't use an offsets. Technically you can, just the same a pagin (WHERE ID > X ORDER BY ID LIMIT Y OFFSET Z)??
Once you're doing REST instead of just "somewhat sane JSON responses" then the response has self-descriptive elements, including links to related resources. And importantly, URLs for older resources become static very, very quickly. Not unlike the internals of subversion or git.
The trick there is to realize that O(1) = O(2). If you're trying to show 25 items per page, you do not need a query that returns the most recent 25 items. That creates a situation where every single interaction is distinct from every other interaction.
Asking for 25 results and everything newer than that is barely more complicated than pagination already is.
so one query returns an approximate cardinality of the result set or a partition count based on approximate size of the result set and a fixed request response size.
the second to n queries are gets, but the gets include the partition count and the partition requested. the server uses a hashing scheme to either reduce the input data used for the construction of the response or filtering of the response itself.
use of numerical partition ids and hashing allows for the response to maintain consistency over time as well as pushing of the sharding/selection scheme as deep as necessary into the data layer to avoid scalability issues.
requests that are too big are cancelled and given abuse points.
Isn't that the point of all pagination, regardless of how it's implemented?
You can also limit page size and accomplish the same thing.
For user-facing apps, you’ve failed pretty hard already if users can’t find what they need on the first page or so.
If your offsets are big enough for this to matter, I’d rather spend time on why users are so many pages in to the data than optimizing the performance of later pages.
(Processing clients, on the other hand, should query for what they need. Processing in batches may make sens, so there cursor- or what they call keyset-based “pagination” makes good sense. Though in the case of processing clients, I wouldn’t call it “pagination”… it’s more like batches. I’ve mainly used “kelset-based” pagination for processing events, which can alleviate some of the “cons”.)