Sparse vector top-K carries a large fixed per-query cost: 100k tier at 8.94 ms p50 vs 1.45 ms before the 26.8.1 pruning work

[lvca]

Split out of #5388, where it has been an unresolved side thread since the round-1 measurement.

Summary

LSM_SPARSE_VECTOR top-K at the 100k tier costs 8.94 ms p50 where it used to cost 1.45 ms. The regression appeared in the 26.8.1 development line, has not moved since the Block-Max MaxScore work landed (a0a79da51), and is not addressed by the block-payload-copy bound on issue-5388-block-payload-copy, which is worth about -12.5% here.

The 1M tier is fine and improving. This is specifically about small and mid-size corpora, where a fixed per-query cost that is invisible at 1M dominates the measurement.

Timeline (all @tae898's numbers, Big-ANN sparse track, real SPLADE, embedded INT8, settled index, N=5)

build	100k p50	1M p50
dev0 / dev3	1.45 ms	165 ms
dev5 (BMW block-skip)	23.1 ms	166 ms
dev6 (Block-Max MaxScore)	8.94 ms	53.6 ms
dev20 (current line)	8.94 ms	52.49 ms

MaxScore recovered 23.1 -> 8.94 ms and cut 1M by 3.1x, but 100k is still 6.2x its original cost, and two development cycles have not moved it.

Why this is a fixed-cost problem, not a scaling problem

Scaling from 100k to 1M went from 114x per 10x of data on dev0 to 5.9x per 10x now. The corpus-proportional part of the work is in good shape - it is the constant that grew. The dev0 100k number was cheap because the old exhaustive traversal had almost no setup and a tiny corpus finished before setup could matter; today's traversal has real per-query preparation that a 100k corpus cannot amortise.

Candidate contributors, in the order I intend to measure them:

1. Per-query cursor setup. PaginatedSparseVectorEngine.topK opens one merged cursor per query term. A real SPLADE query has 30-120 terms, so anything O(terms) with a meaningful constant is paid 30-120 times before a single posting is scored.
2. MaxScore preparation. Computing per-term sigma, sorting for the promotion order, and building the essential/non-essential partition is O(terms log terms) plus per-term metadata touches, all before the first candidate.
3. Merged-cursor construction across memtable and every active segment, including segments that hold no postings for the term.
4. Block-header and skip-list touches that scale with the index, not with what pruning ends up decoding. At 1M only about a third of blocks get decoded; the rest of the metadata is still walked.
5. Anything O(active segments) per term when the 100k index settles into a different segment count than the 1M one.

Why it matters now

Against the same data and ground truth, Qdrant and Milvus return recall@10 = 1.00 at 2.9 ms and 9.3 ms p50 on the 1M tier. Our exact path is at 52.5 ms. Per-query constants that cost 7.5 ms at 100k are the same constants sitting inside the 1M number, so this is not only about the small tier - it is the cheapest available lever on both.

Scope

• Attribute the 100k per-query cost to specific call sites with a profile at that tier (the existing profile is 1M, where these constants are invisible).
• Remove or amortise whatever is genuinely fixed per query.
• Guard the result with a benchmark that reports a small-corpus tier, so a fixed-cost regression cannot hide behind a healthy 1M number again.

Reporter's harness is staged to re-measure, and the tier builds in seconds.

/cc @tae898

[lvca]

First round is on issue-5467-sparse-fixed-cost, commit e54969230 (branched on top of issue-5388-block-payload-copy, so it carries that fix too). It did not turn out to be a fixed cost at all - the profile pointed somewhere else entirely, and the fix helps every tier rather than just the small one.

What the profile actually said

I built an end-to-end harness through PaginatedSparseVectorEngine.topK on a SPLADE-shaped corpus - 30k vocabulary, ~120 non-zeros per document, queries of 30-120 terms drawn towards the head of the df curve - and profiled the 100k tier, where the constants I suspected should have been visible.

Almost nothing was where I expected:

cost centre	share of query time
essential-term min-heap (siftDown + pushHeap + popHeap)	45.3%
scoreCandidate	13.3%
scan drive loop	22.5%
merged-cursor navigation (seekTo, advance, isTombstone, currentRid)	~15%
block decode, page reads, arraycopy	did not appear

Cursor setup, refreshSegmentsFromFileManager, openMergedCursor and MaxScore preparation together came to under 0.1%. My hypothesis in the issue body - per-query preparation that a small corpus cannot amortise - was simply wrong.

Counters explain the shape. Per query, averaged over 500 queries at 100k:

terms=59  candidates=88,799  scored=87,443  blockSkips=1,357  probes=224,209
heap: pop=245,142  push=245,095  compares=2,749,764  avgHeapSize=48.4

2.75 million position comparisons per query, ~31 per candidate. Each one dereferenced two RID objects reached through two more objects, and the segment cursor allocated a RID for every posting it stepped over. At ~9 ns per comparison that is the query.

What changed

Four changes, none of which alters what the traversal visits or returns:

1. Primitive positions end to end. SourceCursor / DimCursor / PaginatedSegmentDimCursor expose (bucketId, position) directly; the RID is materialised lazily and cached. BmwScorer navigates, compares and seeks on the primitives and builds a RID only for a candidate that survives the aligned-run scan. seekTo / blockMaxAt / blockEndAt gained primitive overloads so the block-max probe allocates nothing.
2. Mirrored heap keys. The scorer keeps positions in flat int[]/long[] arrays indexed by term, refreshed only where a cursor moves (~2.8 refreshes per candidate against ~31 reads). The heap's working set is then two small arrays that stay in L1 instead of 48 scattered objects.
3. Primitive block metadata. PaginatedDimMetadata stores per-block header fields in parallel arrays instead of a BlockHeader[] of records, so the block walks in blockContaining and seekTo are pure array scans. It also drops ~80 bytes of object graph per block, which is tens of MB of live metadata on a large index.
4. Skip-list search only when the target is past the current block. Probes on a dense posting list land close to where the cursor already sits, so every non-essential probe was running a binary search over the whole skip list to discover it had not moved.

Measured

Paired arms against the same build, 1000 queries, median of three runs each:

corpus	before	after	delta
100k	21.2 ms p50 / 33.4 p90	18.0 / 28.0	-15%
500k	106.4 ms p50 / 170.0 p90	80.4 / 127.7	-24%

Unlike #5388's copy bound - whose benefit decays as the corpus grows - this one holds and slightly widens with scale, because it removes per-posting and per-comparison cost, both of which scale with the work the query actually does. On the 1M tier I would expect it at the upper end of that range.

Two things I tried and threw away

Recording these so they are not re-attempted:

• In-place aligned-run repair. The slots holding the heap minimum form a connected subtree at the root, so the aligned run can be collected by a depth-first walk with no sifting and repaired with one sift per moved slot instead of a pop plus a push. It is a strictly smaller amount of pointer work on paper and it measured slower - 19.4 vs 17.4 ms - twice, once before and once after the key mirroring. The bottom-up sift is the wrong shape for an element that stays near the minimum, which is exactly what a just-advanced cursor is in a wide merge.
• Term-at-a-time accumulation. Attractive at first sight, since 87% of the corpus is scored anyway. The counters kill it: MaxScore already keeps 870k of the 1.1M postings out of the traversal, so TAAT would touch 2.4x more posting data to save bookkeeping that is only a constant factor cheaper.

Where the remaining headroom is

The heap is still ~45% of the query, and the reason is structural rather than a coding problem: 48 of 59 terms stay essential. With near-uniform SPLADE weights the top-10 watermark never rises far enough relative to the summed term ceilings for MaxScore to drop more of them, so 88k of 100k documents become candidates. Single-threaded work is into diminishing returns from here.

The largest remaining lever is intra-query parallelism, which was scoped as #4085 and never wired up - SparseVectorScoringPool exists in the package today with a comment saying it is waiting for the dispatch in topK. Partitioning the RID range across P workers and merging their local top-K lists is correct without any recall change (each worker returns the true top-K of its range; a lower local watermark only makes each worker prune less). On a query this dominated by a single-threaded merge, that is a several-fold latency win rather than a percentage. It is a real feature with a CPU-versus-latency trade-off, so I would want a decision on it rather than assuming it.

@tae898 - this branch is independent of the block-copy one and can be measured on its own if that is easier; it needs no rebuild and changes no format. Both branches are now pushed, and issue-5467-sparse-fixed-cost contains issue-5388-block-payload-copy if you would rather measure them stacked.

[lvca]

Merged to main as 02f5d5f03.

Final state, on top of what I posted above:

• Dropped the now-dead PaginatedDimMetadata.blockHeader() (zero callers once the decode path moved to the primitive accessors) and the stale comment referencing it.
• MemtableSourceCursor overrides currentBucketId() / currentPosition() instead of inheriting the RID-derived defaults.
• Engine index suite on the rebased tree: 852 tests green (up 3 for the new CursorPrimitivePositionTest).
• Full multi-module run: engine 9,881 / server 703 / HA Raft 761 / console 403 / integration 37 / others, zero failures, zero errors. The reactor stopped in gremlin-it on ClassNotFoundException: org.apache.tinkerpop.gremlin.util.MessageSerializer during test discovery; that is an artifact of running mvn test across the reactor (inter-module dependencies resolve to target/classes rather than packaged jars, which drops a transitive TinkerPop dependency). Verified unrelated: gremlin-it run standalone against this exact engine build passes, 253 tests, BUILD SUCCESS.

@tae898 — both rounds are now on main, so a single build gets you the block-copy bound (#5388) and this. Expected combined effect on the INT8 1M tier is roughly -8 to -9% from the copy bound and -20%-ish from this one, but they compose on the same query so please treat that as a rough prior rather than a prediction to score against; the honest measurement is whatever your harness reports. The invariants remain the ones worth checking: recall identical to the digit, and the per-query Spearman and decile shape unchanged in form.

Remaining lever is intra-query parallelism (#4085) as described above — still an open design decision, not queued.

[tae898]

Fresh CPU profile on the current line, which changes the picture from the one I posted on #5388 last week. Setup: Big-ANN 1M real SPLADE, embedded INT8, settled index, steady query loop over the 1000 dev queries, async-profiler cpu for 240 s, 24,286 samples. Engine: 26.8.1.dev20 plus 8f0819d37 (the block-payload bound). Not including 02f5d5f03 or the parallel-array heap, so this is the state those two changes were aimed at.

Collapsed stacks: https://gist.github.com/tae898/63c69cb1aa29fff37cb9e7e44e5dd953

Self time, everything above 1%:

frame	self
BmwScorer.siftDown	24.4%
BmwScorer.pushHeap	11.1%
BmwScorer.scan	10.4%
DimCursor.blockMaxAt	8.6%
PaginatedSegmentDimCursor.decodeBlockIfNeeded	8.2%
DimCursor.advance	7.4%
PaginatedSegmentDimCursor.seekTo	6.8%
BmwScorer.scoreCandidate	6.2%
DimCursor.seekTo	3.1%
DimCursor.materializeMin	2.0%
jbyte_disjoint_arraycopy	1.3%
BmwScorer.tryBlockMaxSkip	1.2%
VarInt.readUnsignedVarLong	1.2%

Two things worth your time.

1. Your block-payload bound is confirmed independently. jbyte_disjoint_arraycopy was 10.6% in the dev6 profile and is 1.3% here. That is the mechanical confirmation I could not give you when I was benchmarking the wrong artifact, and it agrees with the -11.4% wall-clock we measured at this tier.

2. Top-K heap maintenance is now the single largest cost: 35.5% of self time (siftDown 24.4 + pushHeap 11.1). On #5473 I guessed 11.4% from the dev6 profile and attributed it to the wrong code; the real figure on today's line is three times that, and it is the BmwScorer heap you have just rewritten as parallel arrays. So that change is aimed squarely at the top of this profile, not at a marginal cost. If the 24 -> 18 ns/op you measured at k=64 carries, this tier should move noticeably, and I will report whatever it does.

Ranked by what is left after your two merged changes:

• Heap: 35.5%, addressed by the parallel-array collector, unmeasured by us yet.
• blockMaxAt at 8.6% self plus tryBlockMaxSkip 1.2%, while the skip almost never fires on SPLADE. This is your target 3, still unimplemented, and it is now the second-largest single line. Your own suggestion of memoising blockContaining and the per-source loop looks better than my skip-rate gating idea, which you correctly pointed out would disable the machinery exactly when the threshold starts making skips likely.
• Cursor movement: advance 7.4 + seekTo 6.8 + 3.1 = 17.3%, the per-candidate probing of non-essential terms.
• Block decode: 8.2%, now genuinely decode rather than copying.

For context on why this matters beyond the 100k tier this issue is about: we now have the full 8.84M Big-ANN tier measured, and the gap to specialists widens with scale (387 ms p50 vs Qdrant 16.4 and Milvus 40.5, so 18x at 1M becomes 24x at 8.84M). The one genuinely good number there is build time, where ArcadeDB is fastest of the four at 942 s against Milvus 1,002, Qdrant 1,741 and Elasticsearch 3,077. Happy to re-profile at 8.84M if the scaling behaviour rather than the constant is what you want to attack.

[lvca]

Round 2 is merged to main as ab0ffe6aa, aimed at the second line of @tae898's fresh profile: the block-max probe at 8.6% self time, plus the cursor-movement group.

What was wrong

Two pieces of per-candidate work that did not need to be per-candidate:

• The block-max bound was recomputed for every document the query considered, even though its value is unchanged across a whole block - 128 documents at the default setting. Each recomputation re-walked every segment the term lives in and, inside each, that segment's block index.
• A query term that lives in a single segment still paid the full multi-segment merge. That is the normal case on a settled, compacted index, and there the merge has nothing to decide.

Both are now handled: the bound is computed once per block range and reused across the documents it covers, and a single-segment term short-circuits the merge.

Measured

Paired arms against the same build, SPLADE-shaped corpus, INT8, 59-term queries, top-10, median of five alternating rounds:

corpus	before	after	delta
100k	2.95 ms p50 / 3.08 p90	2.61 / 2.73	-11.5%
500k	15.13 ms p50	13.44	-11.2%

Results are byte-identical in every arm - this changes only how the bound is obtained, never what the query visits or returns. No rebuild, no format change.

One caveat on reading those numbers: the two changes measure about -4% each in isolation and -11% together. They are not additive, so please don't try to score them separately.

Where things stand

@tae898 - main now carries all three merged rounds (#5388's copy bound, #5467 round 1, and this). Between them they were aimed at the whole top of your profile except block decode. Whatever your harness reports is the honest number; the invariants worth checking are the usual ones - recall identical to the digit, per-query Spearman and decile shape unchanged in form.

The remaining lever is still intra-query parallelism (#4085), which is a genuine CPU-versus-latency trade-off rather than a cleanup, so it stays an open design decision rather than something I'll queue silently. Single-threaded work on this traversal is into diminishing returns: with near-uniform SPLADE weights most query terms stay in the traversal no matter how good the pruning is, which is a property of the data rather than of the implementation.

---

❤️ Thanks for helping make ArcadeDB better! ArcadeDB is free and open source, sustained by its community. If it's useful to you or your company, please consider becoming a sponsor to keep development going.

[tae898]

Round 2 verified on real SPLADE. The 1M tier moves -19.3%, and unlike the copy bound the gain does not decay with corpus size.

Provenance first, since I got this wrong once. Engine jars compiled locally from our main merged with ab0ffe6aa and passed to the wheel build explicitly (JAR Source: .../lib (staged into local-jars)), and I checked the shipped jar actually contains the change before measuring: javap on DimCursor shows ensureBlockBounds(int, long) and materializeSingle(), and SourceCursor shows both blockEndAt overloads. The arm therefore carries all three merged rounds: 8f0819d37, 02f5d5f03, ab0ffe6aa.

Same host, same cpuset 0-11, 24 GB container, 8 GB heap, Big-ANN real SPLADE, INT8, settled index, N=5, median [min-max]. Baseline is the arm I reported on #5388 (dev20 + copy bound only), same 995-query set in both.

cell	before (copy bound)	after (all three rounds)	delta
1M p50	46.48 ms [45.84-46.86]	37.52 ms [36.76-37.74]	-19.3%
1M p99	196.2 ms [193.1-198.8]	162.3 ms [159.3-164.0]	-17.3%
1M QPS	16.6	20.3	+22%
100k p50	8.03 ms [7.71-8.51]	6.54 ms [6.38-6.80]	-18.6%
100k p99	24.44 ms [23.74-26.30]	19.82 ms [19.24-20.08]	-18.9%
1M recall@10	0.9935	0.9935	identical
100k recall@10	0.9950	0.9950	identical
1M build	93.1 s [92.8-94.1]	93.4 s [90.4-94.0]	unchanged

Your -20% estimate for the 1M tier from round 1 lands almost exactly, and I am reporting the two pieces together as you asked rather than trying to separate them.

The invariants you named. Recall is identical to the digit at both tiers. Build time is unchanged, so nothing moved into the write path. Per-query shape from the cliff probe at 1M:

	before	after
Spearman(ms, sum_df)	0.896	0.889
Spearman(ms, nnz)	0.903	0.898

The decile curve moves down as a whole and keeps its shape. Each decile of queries binned by summed posting length, median ms, and on the right each decile as a multiple of the first so the form is directly comparable:

decile	before	after	delta	xd1 before	xd1 after
d1	24.90	17.79	-28.6%	1.00	1.00
d2	37.33	26.53	-28.9%	1.50	1.49
d3	49.86	34.15	-31.5%	2.00	1.92
d4	55.22	38.63	-30.0%	2.22	2.17
d5	64.20	44.26	-31.1%	2.58	2.49
d6	79.45	54.29	-31.7%	3.19	3.05
d7	99.04	66.62	-32.7%	3.98	3.74
d8	128.13	89.82	-29.9%	5.15	5.05
d9	169.48	118.17	-30.3%	6.81	6.64
d10	229.88	166.19	-27.7%	9.23	9.34

So this is a uniform scaling of the existing curve, not a change in how latency responds to posting mass. Latency still tracks summed posting length just as strongly, which is the property that makes this workload hard in the first place.

One thing I will flag rather than explain away: the probe's own p50 falls 75.17 to 52.03 ms, -30.8%, against the benchmark's -19.3% on the same tier and the same build. The probe times each query in isolation while the benchmark runs a stream, so the two are not measuring the same thing, and the probe's absolute numbers have always sat above the benchmark's. What makes it worth mentioning is the contrast with the copy bound: on that change the probe barely moved (74.66 to 75.17) while the benchmark showed -11.4%, which is the opposite ordering. I would not read too much into it from two data points, but it is consistent with the copy bound helping sustained streaming (memory bandwidth) while rounds 1 and 2 cut the per-query cost directly.

Where the line stands now. Taking dev20 as the starting point, the three rounds together are:

tier	dev20	+ copy bound	+ #5467 r1 and r2	total
1M p50	52.49 ms	46.48	37.52	-28.5%
100k p50	8.94 ms	8.03	6.54	-26.9%

Two observations worth your time.

The scaling behaviour changed, which the copy bound did not do. The copy bound gave -11.4% at 1M and -10.2% at 100k, near enough the same at both tiers. Rounds 1 and 2 give -19.3% at 1M against -18.6% at 100k, so the per-candidate work you removed was being paid on a larger corpus fraction as the index grows. That is consistent with the profile: blockMaxAt at 8.6% self and cursor movement at 17.3% are per-candidate costs, and 88% of the corpus becomes a scored candidate on this weight distribution.

The remaining profile is now dominated by the heap. The July profile put top-K maintenance at 35.5% of self time (siftDown 24.4 + pushHeap 11.1), and the parallel-array collector from #5473 is in this arm too, so part of the gain above may belong to it rather than to #5467. I cannot separate them from the wall clock and did not try. If you want that split I can profile this build and post the collapsed stacks again, which would also tell us what the top line is now that block-max probing and cursor movement have both been cut.

For the paper's context: the 8.84M tier remains the hard case, where the gap to specialists widens with scale and build time is the one number in ArcadeDB's favour. Happy to re-profile at 8.84M if the scaling rather than the constant is what you want to attack next.

[lvca]

@tae898 one clarification on the comparison numbers before we act on them.

Looking at how the other engines behave by default on sparse, most of them retrieve exactly:

• Qdrant: sparse search is exact by design, explicitly unlike their dense path
• Milvus: drop_ratio_build / drop_ratio_search both default to 0, which is exhaustive
• Elasticsearch: the outlier, prune defaults to true on sparse_vector queries, so it drops query tokens unless you turn it off

Since you measured recall@10 = 1.00 for Qdrant and Milvus, I read your numbers as exact against exact, which would mean the gap to us is implementation rather than an approximate/exact mismatch. Before we pick a direction, could you confirm three things:

1. Were the engines run at their defaults, in particular Milvus drop_ratio_search and ES prune?
2. How was the ground truth for recall computed: an independent exhaustive scan, or one of the engines' own output?
3. Is the scoring the same on all sides, i.e. plain dot product over the SPLADE weights, with no IDF modifier applied on one and not the others?

Why it matters: if it really is exact against exact, then the right thing for us to attack is our own read path, and adding an approximate mode would be papering over that. If some of the engines were pruning, the comparison needs restating first. Either answer is useful, I would just rather not build the wrong thing.