Add cursor-based continuation to `/query` so paging depth is unbounded and cost is flat

[thehabes]

Status: deferred. This was prototyped on the 302-query-optimization branch and removed before merge, so it can be considered later as its own feature. #302 uses a skip-based rel="next" instead, which is still sent past the skip maximum and answered there with the #301 400. The design and measurements below are what to start from.

Summary

skip cannot page past the configured maximum. Since #301, a request past it is a 400 instead of a repeating page. That is honest, but it also tells a client it may not read past 100000 records, which is a correct contract and a worse one than clients think they have today.

Keyset (cursor) continuation removes the ceiling. /query already sorts on a unique, indexed key since #300, so a cursor is "resume after this _id":

db.find({ "$and": [props, { "_id": { "$gt": lastId } }] }).sort({ _id: 1 }).limit(limit + 1)

Cost is flat with depth, because Mongo seeks the index rather than counting past skip documents. Depth is unbounded, because there is no offset to cap.

skip stays. Decision recorded on the parent thread: keep both modes and document them — skip as the bounded, random-access mode, cursors as the unbounded, sequential one.

Why this matters

It is what makes the skip rejection complete. Rejecting skip > 100000 with no alternative narrows what the API can do. #302's next link now ends a longer walk in that 400, which is honest. A next link that carries a cursor would let the same walk continue, with no change for a client that already follows the link.

Deep skip is expensive even inside the cap. Mongo walks and discards every skipped document. The parent draft measured /query at 340-445 ms across skip=0 through skip=99000, so this is not currently a crisis on /query — but it is linear work that a cursor makes constant, and it is the shape that matters once collections grow.

Clients cannot build a cursor themselves, and should not. idNegotiation() deletes _id from every response body (controllers/utils.js:180) and only reattaches it as id when the @context matches a known mapping. So the server must mint the token and hand it back. That is the right design anyway: an opaque, server-minted token keeps the encoding an implementation detail, and a client that only follows rel="next" needs no code change when the encoding changes.

Proposed design

The token

/query would accept a cursor query parameter. It is opaque to clients and appears only in the server's rel="next" link:

Link: <https://store.rerum.io/v1/api/query?limit=100&cursor=eyJfaWQiOiI2OWU5MTBkZjQ0YWNhMDQxNGMwZWYwMTYifQ>; rel="next"

The token is base64url of a small JSON envelope holding the _id of the last record served: {"_id":"69e910df44aca0414c0ef016"} above.

• Every _id is a string. newID() returns new ObjectId().toHexString(), and every _id on production now and in the future is a string. The dev collection also holds legacy v0 documents whose _id is an ObjectId or an embedded object. That is old bad dev data, and cursor paging would not support it.
• Anything the server did not issue would be a 400, not a guess:
  • a value that is not base64url or not JSON
  • an envelope other than exactly {"_id": …}
  • an _id that is not a string
  • a repeated cursor parameter

The filter

Because every supported _id is a string, "resume after this _id" is a plain $gt in the same order the sort serves:

{ "$and": [props, { "_id": { "$gt": lastId } }] }

The client's filter is combined under $and rather than spread with _id added, so an _id clause in the request body would still apply on cursor pages.

MongoDB comparison operators only match values of the same BSON type as the operand, so a cursor walk would never reach the legacy non-string _id documents on dev. A skip walk still pages into them, so on dev the two modes would differ for a query that matches them. That is expected. If a skip page on dev ends on one, its next link should advance skip instead of carrying a cursor.

Interaction with skip

• cursor and skip together would be a 400, including skip=0. They are two different positioning schemes and combining them has no coherent meaning.
• limit would apply to both modes and be clamped identically.
• Cursor pages would report Pagination-Limit, Pagination-Limit-Max, and Pagination-Skip-Max, but not Pagination-Skip, because no offset was applied and reporting 0 would mislead a client that computes offsets.
• rel="next" on /query would always carry a cursor, including on a page requested by skip, replacing the skip value /query paged responses carry no rel="next", so no client can tell a full page from the last page #302's link carries today. A client that follows the link moves onto the unbounded mode with no change on its side. That transparency is why /query paged responses carry no rel="next", so no client can tell a full page from the last page #302 could ship first.
• skip would keep working, keep its maximum, and be documented as the random-access mode for jumping to a known offset within the cap.

Scope

/query only. HEAD /query is removed by #304 rather than extended. See the note below on /search.

Prototype measurements

Measured on the prototype before it was removed, read-only, against the local pm2 app reading the dev collection (rerum-test):

• Past the skip maximum. Following only rel="next" at limit=500 over {"__rerum.history":{"$exists":true}} walked 102001 records in 205 pages, with no duplicates, and stopped when next was absent.
• Same records as skip. Pages at skip=0, 50000, and 99500 were identical to the same slices of the cursor walk.
• Flat latency. Cursor pages averaged 158 ms at depth 0-10k, 125 ms at 45-55k, 121 ms at 90-100k, and 97 ms past 100k. skip pages on the same query took 149 ms, 224 ms, and 365 ms at skip=0, 50000, and 99500, and cannot go further.
• A token the server did not issue. An ObjectId-shaped cursor, {"_id":{"$oid":"…"}}, was a 400.

Notes

• /search is deliberately excluded. Under the current in-memory paging (controllers/search.js:280), a cursor could only encode an offset into the merged array. Same cost, same ceiling, dressed up as a cursor — worse than not shipping one, because it would advertise a guarantee the implementation does not provide. /search paging is tracked under /search paging is unfinished: cost scales with depth, no rel="next", and pages under-fill #306; revisit a cursor with /search paginates in application memory, so every page costs the server everything up to that page #309, where Atlas Search's own searchAfter / searchSequenceToken paging is the genuine equivalent. Availability on our cluster tier and server version needs confirming before that goes in any plan — do not assume it.
• Depends on /query paginates with no sort, so page boundaries rest on MongoDB natural order #300 (a sort key, closed) and /query paged responses carry no rel="next", so no client can tell a full page from the last page #302 (somewhere to put the token, in place).
• The prototype was small. It added a cursor option to getPagination() that decoded the token, rejected cursor with skip, and skipped reporting Pagination-Skip. It also added a token encode/decode pair in controllers/utils.js, the $and/$gt filter and cursor minting in the /query controller, and a nextCursor input to the rel="next" helper (setNextPageLink() in /query paged responses carry no rel="next", so no client can tell a full page from the last page #302). On the documentation side it added a cursor row and a skip-versus-cursor paragraph in public/API.html, and a PageCursor parameter on /api/query in the OpenAPI contract.
• A keyset cursor is stable under insert in a way skip is not: a document inserted before the cursor position does not shift the remaining pages. Given RERUM's mark-deleted-never-remove policy, this makes cursor walks meaningfully more correct than offset walks over a live collection, which is a second reason to prefer them beyond cost.
• The cursor is not bound to the query it came from. Sending it with a different body means "records matching this body after that _id", which is coherent and harmless.
• A final page still scans to the end of the matching range, because the one-record over-fetch has to prove nothing follows. That is the same work a short final skip page does today.
• This is Query and version endpoints load unbounded results into memory #252's third recommendation. Worth linking there.

Acceptance criteria

• /query accepts an opaque cursor parameter and returns the page following it
• The rel="next" link on /query always carries a cursor, including on a page requested by skip, and a client following only that link pages past the skip maximum and terminates correctly
• Cursor paging returns every matching document exactly once, over string _id values; non-string _id legacy dev data is not supported
• A cursor walk and a skip walk of the same query return the same records in the same order, within the range where skip is legal
• /query latency is flat with respect to depth under cursor paging, measured to the depth skip cannot reach
• A malformed, unparseable, or repeated cursor returns 400, as does a token whose _id is not a string
• cursor combined with skip, including skip=0, returns 400
• An _id clause in the request body still applies on cursor pages
• Cursor pages report Pagination-Limit and both maximums, and no Pagination-Skip
• skip continues to work within its maximum, and both modes are documented in public/API.html and in the OpenAPI contract as a cursor parameter on /api/query