Add pagination to /matches

[cortsf]

Describe your idea, in simple words.

Add limit or proper pagination parameters to the /matches endpoint.

Why is it a good idea?

It would allow us to index an oracle. We only need the most recent values.

Are you willing to work on it yourself?

Probably. We are looking to pick a chain indexer for our project without having to extend it if possible.

[KtorZ]

Here are some thoughts regarding pagination:

• Pagination is usually tricky on collections that are not immutable. This is the case for matches, and especially recent matches which can potentially be rolled back. A client could be send page=n, only to discover later that page=n has completely changed.

• Pagination demands a stable ordering, which is now implemented since Ensure stable ordering of results within a same slot / block #65. This was the first step towards a working pagination system. Results are now properly ordered by slot-no -> transaction-index -> output -> index.

• A naive pagination with a fixed hard limit would likely not play well. For example: return results by batch of 50. The reason it doesn't work well is because from a database perspective, it breaks the data at arbitrary points and we can't properly leverage database indexes for the query. To know where the next batch is, the database still has to construct a temporary binary tree with all the results, and slice the corresponding batch from it. As such, pagination would provide almost no performance benefits (except maybe the time needed to serialized the data). It would however provide some convenience for clients.

• Rather, providing a pagination by slot-no would be interesting for multiple reasons:

  • It allows to leverage compound indexes, resulting in very efficient queries that can directly filter on both patterns and pagination criteria.

  • It offers meaningful boundaries for client applications which likely have knowledge of when some event happened; for example, when waiting on a particular UTxO after having submitted a transaction.

  • It can be combined with extra headers X-First-Block-Header-Hash and X-Last-Block-Header-Hash that can be used to validate the sub-chains given by the slot range. This is particularly useful to ensure data integrity from the client-side as now, client can verify that the next batch they receive is indeed a continuation of the previous batch (header hashes should match). Imagine the following scenario:

    • client asks for the range (slot=100, slot=200]
    • server returns data
    • node adopts a new fork of the chain, reverting data from slot=150 and onwards.
    • client asks for the range (slot=200, slot=300]
    • server returns data

    Now, the client isn't aware of the chain switch and think it has a correct version of the data but half of the data from its first batch has maybe been invalidated. If the server was providing block header hashes of the interval boundary, the client could, on the second request verify that the starting header match the previous last header: it wouldn't and it would know it needs to fetch the previous range again.

  • The only "downside" I see with this approach is that it doesn't necessarily gives clients fixed-size pages. Yet, pages are bounded, because blocks are themselves ultimately bounded in size. So it is still possible for clients to fetch pages with a worse-case heuristic to make sure they do not go over their capacity.

[xray-robot]

What is your idea? Provide a use case.

We would like to have pagination, as it will allow to manage requests and know in advance approximately how much data will be transferred.

As a draft, I might suggest:

• Request headers:
  Passing the Prefer: count=estimated parameter to the headers will instruct the database to get the number of records and Range: 0-9 will specify which range to select (but the results will be cut off by --pageSize argument, see below)
• Response headers:
  Returns Content-Range: 0-9/3182

That's how it's done in PostgREST: https://api.koios.rest/#overview--pagination-offsetlimit

It might also be worth adding offset and limit arguments to the endpoint, for quick access to pagination.
It is also necessary to have a startup argument --pageSize 1000 (or something), to set the default value of the maximum page size.

Why is it a good idea?

Tracking and managing long-running requests. It will also prevent malicious requests to public APIs (we plan to make a free public Kupo cluster, with Cloudflare WAF on top of it, but long-running queries will put a heavy load on it, even to server fails).

[xray-robot]

The pagination by slot-number is available for a few releases already. I am however trying things out regarding internal query ordering to possibly speed up paginated requests even more. At the moment, pagination happens after the main query on matches.

I read what you wrote above. I would like to know if it is possible to implement at least --pageSize, to limit and offset the output? And to preserve the integrity of the response data use X-First-Block-Header-Hash and X-Last-Block-Header-Hash as you described.

[KtorZ]

It is not possible to have these values in the Header because Kupo only knows about them once the query is done. The server actually streams results from the database, and thus it must have already sent the headers by the time it starts steaming the body. So technically speaking, by the time you send the headers, you don't know yet what the last block header is.

Now, that's the slightly dismissive answer. The more realistic one is, it's possible if I adjust the way responses are fetched from the database. In particular in the presence of a limit or offset.

If the number of results is limited, then it's arguably safe to collect all results in memory and only then, serialise them down to clients. This would allow knowing where the request ends.

[KtorZ]

Note also that I have somehow developed an aversion of "limit", "offset" and "page" etc. as query parameters.

I am quite keen on having proper HTTP Range on the JSON items. So one can limit the results by lines. I don't think we need any extra header for data consistency as the existing one will do. If the X-Most-Recent-Checkpoint hasn't changed then the ranged results haven't changed either. Otherwise, it'll depends how far in the past are results; but anything within the last 36h must potentially be refetched on a tip change.

[xray-robot]

I didn't realize that Kupo broadcasts data "in real time". I thought the response data was fully retrieved from the database and only then sent to the client.

My suggestion is to somehow granularize heavy queries. In this case it is easier to manage the load on the server, but there is a question whether it will reduce the load, because you will have to get the entire requested collection first and then separate to pages - although the sqlite should somehow optimize it.

In the current implementation Kupo is good as a data source for further caching, perhaps my wishes should be as a separate tool on top of Kupo... And I'm describing "another db-sync", but apparently that's not what you want from Kupo, so I see your point. 😇

[xray-robot]

Anyway, if you have the vision and desire to add a pagination mode for Kupo (I/O optimized), that would be great for some client-server use cases.

[KtorZ]

When it comes to heavy queries (and actually even small ones, but it's a lot more visible on heavy ones); there's nothing more efficient than streaming. Largest queries I've seen on Kupo on a pruned database can yield more than 400k rows, so several hundred MB of data. Kupo is now down to ~5s on those; I am not saying that's as low as we can get but it's pretty close I think.

Getting everything into RAM first and then serialising it won't be faster because of the idle time we spend building the data in memory, then serialising it and then freeing the massive amount of memory allocated for this. So it can only harm performances and, will require a large amount of memory that is currently close to zero.

Nevertheless, there's a point about small queries; and a Range-based pagination seems like a low hanging fruit that's relatively elegant and efficient so, why not.