STAC: Pagination with index and offset

[sanzog03]

Description:

To list out the entire collection items, the current STAC implementation has pagination via next. The API does offer limit query params to limit the number of items returned. This does allow us to query through all the items in the collection; however, we are always limited by the previous request's response to get the next (no parallelization to get all the items).

Proposal:

Instead of just having next with a limit for pagination, it would be great to have a limit with the offset. This would allow us to make parallel requests, hence highly optimizing the response time.

[slesaad]

@anayeaye @smohiudd no rush, but it'd be great to have this feature. Some of the viz tools we have need us to get all the STAC items, which takes a significant amount of time (especially because using a larger limit fails the request, so we have to use a smaller limit value).

[anayeaye]

We do currently use limit/offset pagination for our collection search and I * think * it could be pretty simple to add it for item search.

[bitner]

This is not actually easy. The issue with offset/limit pagination in most databases including postgres is that each successive offset still needs to scan through ALL previous records, so while offset 0 limit 100 is extremely fast, offset 100 limit 100 may take twice as long, offset 1000 limit 100 may take 10 times as long to return. This is exactly why we use keyset pagination so that successive pages can use an index to quickly get to the next page data .

[anayeaye]

@ividito had some good ideas on improving scalability. I would paraphrase that as using temporal or spatial batching in the items requests to parallelize requests client side but maybe he can better explain

[ividito]

I would paraphrase that as using temporal or spatial batching in the items requests to parallelize requests client side but maybe he can better explain

What I had in mind was essentially a version of "keyset with estimated bookmarks" from https://www.citusdata.com/blog/2016/03/30/five-ways-to-paginate/

Essentially, using available STAC metadata, we can estimate the indexed properties of the underlying items and construct parallel queries instead of sequentially reading everything in one batch. Spatial or temporal batching could be good enough here, or we could figure out a more efficient method for a specific use case.

[bitner]

this is basically what pgstac does behind the scenes to optimize the complicated filter sorted by time use case. let's plan to chat next week, there might be some things we can expose from pgstac (outside of the stac specification) to help with this use case

[smohiudd]

@slesaad is this still something we need to address?

[slesaad]

would definitely be valuable if you guys have the time. is not high priority tho