Efficient Querier Pagination

[aaronc]

Summary

It has been brought to my attention that the current approach to pagination is inefficient because it still requires the full result set to be retrieved by the querier so it will slow down under really huge result sets.

Proposal

@alpe proposed two approaches here: https://github.com/regen-network/cosmos-modules/pull/63#pullrequestreview-380905827 which I am quoting below

Option A

For the list query pagination we would need some additional query payload

• Limit uint32 - max number of entries, defaults to 20(?) when empty
• After bytes - last element id of the previous result set; not included in the new resultset; can be nil for first page; may need to by type agnostic

Result:

• Data repeated Model(???) - result set
• HasMore bool
• Proof Proof(?)

Option B

Make it easier for clients:

• Limit uint32 - max number of entries, defaults to 20(?) when empty
• Cursor bytes - same idea as After but not type agnostic. Clients would never build it from the result set; can be nil for first page

Result:

• Data repeated Model(???) - result set
• Cursor bytes - can be nil when last page is returned
• HasMore bool - required as there may only be a first page
• Proof Proof(?)

I like option B a bit more now as we would drop the object ID type in the requests and let the client simple return what would be the offset for the next page. All logic, encoding is server side only.

Approach B (adding a type agnostic Cursor field) may be the better approach going forward and would be the approach I recommend as a starting point. Approach A, however, might be easier to adapt to existing query methods without changing the result types (i.e. for #6163).

I would propose this be done from the start for gRPC queriers (#5894).

I would not recommend changing existing querier methods unless clients complain of UX problems in order to not break backwards compatibility of existing clients during the migration to protobuf.

[jgimeno]

@aaronc even type A will change the result type, since we need a way to return the after []byte type. Am I wrong?

The only issue I see maybe is the way pagination will work in CLI command line, maybe is a little bit annoying to provide the last element ID as a param.

[aaronc]

@aaronc even type A will change the result type, since we need a way to return the after []byte type. Am I wrong?

Well ideally that is included as the key of the last item in the result set. But the cleaner way would probably be to include it directly in the result set as Cursor or something.

[jgimeno]

Ok! What we do then about this, I can provide an example on how to do case B in one PR for a specific case, and if we like implement it for all, or we wait to gRPC?

[aaronc]

@jgimeno I think the most bang for the buck will be doing together with gRPC. I have an init PR for bank #5882. I need to update it anyway and can add it there as a starting point. I would also like to update ADR 021 to mention this. Have you read that?

[jgimeno]

Gonna read it. This is the PR your are using right? https://github.com/cosmos/cosmos-sdk/pull/5953

[aaronc]

Yes, that's the init PR

[aaronc]

Here's what I'm thinking, just take Page []byte in the request and return NextPage []byte in the response if there are more pages (nil otherwise).

Ex:

message BalancesRequest {
  bytes address = 1;
  bytes page = 2;
  uint32 limit = 3;
}

message BalancesResponse {
  repeated cosmos_sdk.v1.Coin balances = 1;
  bytes next_page = 2;
}

[jgimeno]

I see, and I think is a good approach, I wonder how user friendly would be this from the point of view of the command line.

Is not the same --page 1 that --page 0x1234567890ABCD but I can't come with other idea that does not need to do a traversal of the full set.

[alexanderbez]

One way would be to support both -- efficient and lazy (current) pagination:

message BalancesRequest {
  bytes address = 1;
  uint32 page = 2;
  bytes page_key = 3;
  uint32 limit = 4;
}

The idea is that a client can either provide page or page_key, where the former would do lazy pagination and the latter would do efficient pagination. In the presence of both, we can either error or pick the efficient path.

[aaronc]

Hmm... I'd rather not complicate things by supporting both options on the querier level. Most usage I imagine will actually be programmatic.

I can't see any other use case beside the CLI, and if we really want to support the simple --page 2 syntax, the client can just inefficiently iterate through result sets itself until it gets to the right page.

[jgimeno]

Yeah, maybe we can just accept this tradeoff.

[jgimeno]

Sorry, I am just thinking, but I see with the approach suggested other problem with the REST.

This approach only allows pagination in a webapp in the style of:

<- prev next ->

Since we always need at least the first call to get the next page key.

So exact paginations on the style of:

1 2 3 4 5 6 ... etc wont be possible without many tricks.

This is just some thoughts, I am not advocating against, just to bring them to the table and have them in mind.

[alexanderbez]

Why is this a tradeoff or complication? It's pretty trivial (if/else check). Clients that don't want to pass around a byte/hex key should not have to.

[jgimeno]

I think what @aaronc says is that from the point of view of the API having two types of pagination is not optimal, not because of the coding complexity but from API design.

[alexanderbez]

Mhhh, I respectfully disagree. Can you please explain how it's non-optimal? The client can choose to use which ever method it wants. One value is omitted over the other.

[jgimeno]

I understand you perfectly, with non optimal I wanted to say that is less simple than having only one way of pagination, which from a client perspective it just makes it a little bit harder but just looking at

uint32 page = 2; bytes page_key = 3;

to understand the difference of both.

Don't get me wrong @alexanderbez! I think is not a bad idea to have both, I did not think about it and I think it helps to bring the --page 1 use case.

Whatever we decide is ok for me. :D

[aaronc]

Maybe it's the right thing to do, I just think it would be simpler if we could avoid it. It's added complexity for every request type and every querier method. I'll see if I can find a simpler way... but maybe there isn't.

[alexanderbez]

ACK whatever you guys wish to go with...

[aaronc]

Did a quick spike on this with for #5975

I think this approach will address both concerns:

https://github.com/cosmos/cosmos-sdk/pull/5953/files#diff-bc1bef9ecc3076635102b2d152b5449c

https://github.com/cosmos/cosmos-sdk/pull/5953/files#diff-8ca04691fa5aa1d8ede405ec840d9f21

Using page numbers can be made more efficient if the iteration only unmarshals the values that are actually going to be returned. The Paginate function linked above just skips unneeded results until it gets to the requested page.

[alpe]

IMHO we should focus on one way to query and keep the api simple and self explaining. Either cursor or pages. The cursor is more efficient on the server side as we would not have to read and skip data. It is also more correct with data being inserted while iterating. An insert before the cursor would not have any effect on the result set and after the cursor would just be appended. On the other hand pages was used before and people would not be forced to a new UX.

Maybe we can learn more about the common client use cases.

[aaronc]

So I'd like us to come to a decision on this either way.

My current proposal as represented in #6353 (specifically https://github.com/cosmos/cosmos-sdk/pull/6353/files#diff-bc1bef9ecc3076635102b2d152b5449c) is to handle both keys as @alpe has suggested or standard limit/offset. I don't think it's that complex to handle both and I think it would account for both:

• users that want the most efficient pagination, and
• users that want to show search paginated search results on a web page like google.

I understand @alpe's concerns about just wanting to support one approach, but at least on the server side we can abstract over the complexity with helper functions. In #6353, I have a helper that works over PrefixStores that should work for most of the cases we have in the SDK.

If we had to choose between one of those approaches, I would advocate for @alpe's more efficient key approach. But if we don't want to have the opinionated either/or battle, I present #6353 as a middle ground.

A few details on the approach in #6353:

• Each request type has a PageRequest page field and each response type has a PageResponse page field
• Either key or offset can be used together with limit. I am choosing offset rather than "page number" because limit/offset is the more common terminology in general.
• When offset is used, count_total can also be set and this will cause the PageResponse to include the total number of results (for web pages that want to show the total number of results and total number of pages).
• PageResponse always returns next_key so that clients can switch to the more efficient key method at any point.

Whether we choose this approach or settle on supporting just one of offset/pagenum or key, I'd prefer to settle on something rather quickly because other than this, gRPC module queriers are unblocked. If we decide on something, I think #6353 can be completed rather quickly and then each gRPC querier will get pagination from the start.

[anilcse]

My current proposal as represented in #6353 (specifically https://github.com/cosmos/cosmos-sdk/pull/6353/files#diff-bc1bef9ecc3076635102b2d152b5449c) is to handle both keys as @alpe has suggested or standard limit/offset. I don't think it's that complex to handle both and I think it would account for both:

+1

6353 seems to be a better approach considering all these points. Querier is blocked on this and we should move quickly. I would advocate to support both for now and handle the complexity with helper function on server side.

We are planning to resume #6353 and start working on querier stuff.

[aaronc]

Any other opinions here? @alexanderbez @jgimeno ?

It we're fine with the dual-approach #6353, it would be great to green-light it and get it moving.

[alexanderbez]

My opinion still stands from my previous comment -- as long as we can support both methods 👍

[aaronc]

Okay great, seems like we're on the same page. Let's move forward with the dual approach in #6353 and we can discuss any details in that PR.

[anilcse]

@aaronc we might need to use page instead of offset. Otherwise the default behaviour to use key over offset (when both are not set) is not possible as offset's default value is 0 and is still a valid offset value. We should not use key by default if the offset is 0

One workaround can be to use end value as offset + limit - 1 inside paginate (https://github.com/cosmos/cosmos-sdk/pull/6452/files#diff-8ca04691fa5aa1d8ede405ec840d9f21R58), but that doesn't look like a standard approach. Any thoughts?

[aaronc]

I don’t understand what the problem is. If offset and key are both unset the behavior should be identical. If key is set and offset is zero we use key. There is no ambiguity. If both offset and key are set there should be a validation error.

[anilcse]

Okay, as discussed over chat, we'll be using offset=1 for first page records

Edit: Sorry about this. It's just a change to the end value when using offset

[anilcse]

@aaronc @alexanderbez @clevinson I suggest we enforce a maxLimit for pagination. If the limit is not set, we will use the maxLimit. Also, we allow users to set limit only under this maxLimit.

We can have a hard coded value of 25 for maxLimit

Any thouthts?

[alexanderbez]

I'm in favor of a max limit, although idk if 25 is the ideal limit. Why not just keep it at 100?

[aaronc]

100 makes sense to me

[anilcse]

Sure, we'll keep the max limit to 100

[anilcse]

@aaronc how do we apply this for custom filtered querying. Lets say for proposals we have proposer, status and depositor filers. If we use the current paginate, we would get results <= limit though we (might) have more results.

I think we can fix this by returning miss or hit/found, a bool value from onResult(). https://github.com/cosmos/cosmos-sdk/pull/6452/files#diff-8ca04691fa5aa1d8ede405ec840d9f21R49 The counter will increase only if it is a hit

But we'll have a problem with offset and it can't be page_number * limit for clients, we might need to add nextOffset but that will look bad.

/cc @alexanderbez @jgimeno @clevinson @alpe

[aaronc]

Addressed in #6452 and #6514