/query paginates with no sort, so page boundaries rest on MongoDB natural order #300

Activity

1. thehabes

   added a parent issue on Sep 3, 2026

   • Make paged reads on /query and /search honest and self-describing #299
2. thehabes commented on Sep 10, 2026

   

   thehabes

   on Sep 10, 2026

   MemberAuthor

   More actions

   explain() evidence: no blocking in-memory sort

   Run 2026-09-10 against the dev collection, read-only. MongoDB 8.0.32, annotationStore.alpha, 463,284 documents. Indexes present: _id_, slug, prime, target_1, target.id_1, target.@id_1, target.source_1, target.source.id_1, target.source.@id_1.

   This is the acceptance criterion asking for explain() output before merging.

   Query plans

   executionStats at limit=100&skip=1000, each shape with and without .sort({ _id: 1 }).

   Query body	Sort	Stages	Docs examined	ms
   {"@type":"oa:Annotation"}	no	LIMIT <- SKIP <- COLLSCAN	1,102	1
   {"@type":"oa:Annotation"}	yes	LIMIT <- SKIP <- FETCH <- IXSCAN	108,676	226
   {"type":"Annotation"}	no	LIMIT <- SKIP <- COLLSCAN	378,517	280
   {"type":"Annotation"}	yes	LIMIT <- SKIP <- FETCH <- IXSCAN	23,202	50
   {"__rerum.APIversion":{"$exists":true}}	no	LIMIT <- SKIP <- COLLSCAN	357,024	272
   {"__rerum.APIversion":{"$exists":true}}	yes	LIMIT <- SKIP <- FETCH <- IXSCAN	1,699	3
   {"__rerum.generatedBy":"<a real agent>"}	no	LIMIT <- SKIP <- COLLSCAN	357,073	285
   {"__rerum.generatedBy":"<a real agent>"}	yes	LIMIT <- SKIP <- FETCH <- IXSCAN	1,753	4
   {"__rerum.isReleased":""}	no	LIMIT <- SKIP <- COLLSCAN	357,024	283
   {"__rerum.isReleased":""}	yes	LIMIT <- SKIP <- FETCH <- IXSCAN	1,699	4

   No SORT stage appears in any of the ten plans. With the sort in place the planner stops doing a collection scan and walks the _id index instead, so the ordering is satisfied by the index rather than by a blocking in-memory sort. That is the outcome this issue was checking for, and it clears the concern about trading a latent correctness problem for a real performance one.

   The alternative compound index discussed at the bottom of this issue is not needed.

   Latency against depth

   Timings above are single-shot and noisy. These are medians of three runs at limit=100, which is what the timing claims should rest on.

   Query body	skip	No sort	With sort
   {"@type":"oa:Annotation"}	0	47 ms	114 ms
   {"@type":"oa:Annotation"}	1,000	44 ms	282 ms
   {"@type":"oa:Annotation"}	10,000	45 ms	299 ms
   {"@type":"oa:Annotation"}	50,000	74 ms	390 ms
   {"@type":"oa:Annotation"}	99,000	106 ms	494 ms
   {"__rerum.APIversion":{"$exists":true}}	0	336 ms	70 ms
   {"__rerum.APIversion":{"$exists":true}}	1,000	318 ms	43 ms
   {"__rerum.APIversion":{"$exists":true}}	10,000	320 ms	59 ms
   {"__rerum.APIversion":{"$exists":true}}	50,000	380 ms	154 ms
   {"__rerum.APIversion":{"$exists":true}}	99,000	414 ms	260 ms

   Four of the five shapes tested get faster with the sort, because an index scan beats a collection scan on a selective predicate. The exception is {"@type":"oa:Annotation"}, which gets slower at every depth and tops out at 494 ms at skip=99000. Those documents are sparse in _id order, so the index scan examines 108,676 keys to fill a page of 100 while the collection scan finds matches densely packed near the start of natural order.

   That worst case sits at the top of the 340-445 ms band already recorded for /query on #309, so it is not a new performance regime. It is worth knowing that the shape most likely to be slower is a common one.

   Mixed _id types

   All three BSON types coexist on dev, as this issue predicted.

   _id type	Count
   objectId	348,898
   string	107,959
   object (embedded)	6,427

   BSON orders string before embedded object before objectId, so an ascending _id sort produces three contiguous blocks in that order. Across the whole collection the transitions land at index 107,959 and 114,386, both just past the skip ceiling of 100,000. A filtered query reaches them sooner: {"@type":{"$exists":true}} crosses at 25,149 and 31,576.

   Confirming the earlier note on this thread: the order is total and complete, but it is not oldest-to-newest and should not be documented as if it were.

   Tiling verification

   Five limit=100 pages equal one limit=500 request, same records in the same order, no repeats. Checked at the driver and again through the running endpoint.

   Window	Where	Result
   skip=2000, {"__rerum.APIversion":{"$exists":true}}	endpoint	identical, no repeats
   skip=99000, same body	driver	identical, no repeats
   string to object transition, skip=107709	driver	identical, no repeats
   object to objectId transition, skip=114136	driver	identical, no repeats
   string to object transition, skip=24899, {"@type":{"$exists":true}}	endpoint	identical, no repeats
   object to objectId transition, skip=31326, same body	endpoint	identical, no repeats

   Repeating a request returns the same page.

   A trap for anyone re-verifying this

   Do not key records on @id when checking dev for duplicates. The 500-record window at skip=31326 of {"@type":{"$exists":true}} contains 36 distinct documents that all carry the same stored @id:

   http://165.134.105.29/annotationstore/annotation/[object Object]
   

   That string is baked into the stored data. It is a v0 write that concatenated an embedded-object _id into a URL, not anything the current code does and not a paging fault. The documents are genuinely distinct, and tiling is correct once records are keyed on their content. It is a cousin of the _id.toString() bug in #307, but that one is a live dedup key in /search while this one is dead data already on disk.

   Worth its own issue if nobody has filed it. It means those 36 records are not addressable by their own @id.

   Status

   Implemented on 301-limit-skip in #310: .sort({ _id: 1 }) on POST /query (controllers/crud.js) and HEAD /query (controllers/history.js), plus the ordering guarantee written into public/API.html. Full suite passes at 238 tests. The OpenAPI half of the last acceptance criterion is still open and belongs with #305.

   Remaining caveat unchanged from the issue body: result order changes for every existing /query client, so this wants a soak on dev.
3. thehabes commented on Sep 10, 2026

   

   thehabes

   on Sep 10, 2026

   MemberAuthor

   More actions

   Correction to the explain() figures above

   The table in my earlier comment was measured on the development cluster only, at a single depth. Development turns out to be the pathological case rather than the representative one, so those numbers overstate the cost of the _id sort against production by roughly two orders of magnitude. Corrected figures below.

   The acceptance criterion still holds. No plan contains a blocking in-memory SORT stage, on either cluster. The planner satisfies the ordering from the _id_ index directly. The compound index raised at the bottom of this issue is not required to meet that.

   What I described wrongly

   _id is always indexed and the new plan does use it, as IXSCAN(_id_). The subtlety I missed is that _id_ supplies the order but never the predicate. Neither cluster has an index on @type or type, so those are evaluated in the FETCH stage: every document in _id order is loaded and tested until skip + limit matches accumulate. In every sorted plan docsExamined equals keysExamined, which is the signature of a fetch-and-discard walk.

   The old unsorted plan avoided that by filtering during a COLLSCAN and stopping as soon as the page was full. It was fast because it could quit early, not because collection scans are cheap.

   Why development is the wrong place to measure this

   BSON orders string before object before objectId, and the _id composition of the two collections is opposite:

   _id BSON type	Production	Development
   string	336,789	107,959
   object	0	6,427
   objectId	3	348,898
   total	336,792	463,284

   Development puts a 107,959 document legacy v0 string block at the front of every sorted scan, and that block matches @type: oa:Annotation only 0.4% of the time. So the walk wades through all of it before reaching data that matches: filling skip=1000&limit=100 examines 107,959 string documents for 383 matches, then takes 717 more from the object block, which is exactly the 108,676 keys observed.

   Production has no second block, so that cliff does not exist there.

   Production figures

   explain('executionStats'), limit=100, 336,792 documents. Prevalence is from a 2,000 document random sample.

   Query shape	Prevalence	skip	Unsorted	Sorted	Docs examined	Returned
   {"@type":"oa:Annotation"}	51%	0	16 ms	48 ms	34,313	100
   {"@type":"oa:Annotation"}	51%	1000	16 ms	47 ms	35,343	100
   {"@type":"oa:Annotation"}	51%	50000	43 ms	125 ms	89,732	100
   {"@type":"sc:AnnotationList"}	38%	1000	16 ms	46 ms	35,982	100
   {"@type":"sc:AnnotationList"}	38%	50000	411 ms	525 ms	336,792	0
   {"type":"Annotation"}	1.6%	0	63 ms	167 ms	118,959	100
   {"type":"Annotation"}	1.6%	1000	110 ms	270 ms	181,425	100
   {"@type":"Gloss"}	0.2%	1000	168 ms	441 ms	314,294	100
   {"@type":"Gloss"}	0.2%	50000	225 ms	456 ms	336,792	0

   The ratio is a consistent two to three times, and the worst database time observed is 558 ms. The dominant shape, which is half the collection, costs 48 to 125 ms.

   The rows returning 0 records are requests past the end of the result set, which a client following the documented short-page rule never sends.

   One detail worth keeping: oa:Annotation examines 34,313 documents to return its first 100, despite being 51% of the collection. Lexicographic _id order does cluster by document type on production too. It simply has no separate type block to turn that clustering into a cliff.

   Ordering guarantee

   Page tiling verified through the running app at skip 0, 1000 and 50000 on production: two limit=10 pages tile one limit=20 page exactly, with every record distinct. Verified the same way on development at four depths, including across both BSON type boundaries.

   Where this leaves the change

   The sort is correct and should stay. At production's numbers the cost is an optimisation question for #309 rather than anything blocking.

   If it is worth optimising later, a compound index whose prefix is the predicate and whose next key is _id removes the fetch-and-discard entirely, because an equality match on the prefix leaves the following key already in sorted order:

   db.alpha.createIndex({ "@type": 1, _id: 1 }, { background: true })

   The existing prime index already demonstrates the resulting plan shape, so nothing has to be built to see it:

   LIMIT <- FETCH <- SKIP <- IXSCAN(prime)     1,100 keys examined, 100 documents fetched, 2 ms
   

   SKIP applies to index keys and only the returned documents are fetched.

   Aside, relevant to #307

   Production holds zero documents with an embedded-object _id, against 6,427 on development. The _id.toString() bug tracked there cannot fire in production today.

   All measurements above are reads. Nothing was written and no index was created.
4. thehabes

   closed this as completedin #310on Sep 16, 2026