Attribution counters
Speculative completion rate, fallback rate, pruned blocks, and cache composition — then re-measure selective-without-fallback.
Lance full-text search · sketch
Read the skip data before the payload.
V1/V2 store a token's whole posting list as one row, with each block's max score buried in the first bytes of its compressed payload. V3 gives every 128-doc block its own row and pulls the skip metadata out into narrow columns — so the executor can prove a block useless before paying to read it.
95% QPS at 6% memorySelective cache reaches 1376–1408 QPS with 4.09 MiB resident, against full-prewarm's 1452 QPS at 66.08 MiB.
Prune before IOBlock bound checks move from after payload decode to before payload reads.
Exact top-k, alwaysEvery skipped block is proven out by its upper bound; anything unproven falls back to the full path.
The score lives inside the thing it should judge
One row of invert.lance holds a token's entire posting list: a List<LargeBinary> where each element is one 128-doc compressed block. The 8-byte header of every block carries block_max_score and first_doc_id — exactly the two numbers WAND needs to decide whether the block is worth reading.
invert.lance · one row = one token's posting list (V2)
8-byte header: block_max_score + first_doc_id
128-doc compressed payload
Header width exaggerated for visibility — it is 8 B in a ~1 KB block.
Term-level metadata is fine.
_max_score and _length are separate columns — you can project them without touching payload.Block-level metadata is not.To see one block's score you must read and decode the whole row. Lance reads List rows whole; there is no element-level IO.
ConsequenceWAND's block skipping can only happen in the decode layer — after every byte has already crossed the network into memory.
The move: pull skip out, one block per row
Split the storage by access pattern instead of by term. The skip data leaves the payload and becomes narrow columns you can project alone; each block becomes an independently addressable row; positions align to the same row ids; a coarse skip layer aggregates block groups for long-range advance(target).
skip metadata leaves the payload
V2: six blocks welded into one row. The blue headers are the decision inputs — trapped inside the decision objects.
posting_coarse_skip · doc range + group max over every block group
V3: skip columns are narrow and projectable; terms maps token_id → block_start + num_blocks; payload and positions rows are fetched only when selected. The payload codec stays FTS-private — Lance only provides row addressing, range reads, and column projection.
Same query, two read paths
One term, twelve blocks, three of them can beat the current top-k threshold. Watch what crosses the network in each version.
V2 one row per token
network
12.4 KB
12.4 KB crossed · 12 blocks decoded · 9 discarded late
executor · after decode
wire 12.4 KB · decoded 12/12
pruned after decode
V3 one row per block
network
144 B skip metadata
3.1 KB selected payload
3.2 KB crossed · 3 blocks decoded · pruned before payload
executor · before payload reads
wire 3.2 KB · decoded 3/12
pruned before payload reads
Illustrative sizes for one mid-frequency term: 12 × 128-doc blocks ≈ 1 KB each, skip metadata 12 B per block; widths not to scale. Striped bars are bytes in flight. Outlined slots in V3 are blocks the executor knows about but never fetches.
Prune by proof, not by guess
Drag the top-k threshold. A block issues a payload read only if its block_max_score — an upper bound on any score inside it — can still beat the threshold. As the heap fills during a real query, the threshold rises and the read plan shrinks.
block_max_score per block · one term, 16 blocks
threshold τ5.6
blocks kept4 / 16
payload plan≈ 4.1 KB
bytes avoided75%
Exactness contract. Pruning is never approximate: a skipped block is one whose upper bound proves it cannot reach top-k. When the proof cannot be completed, the executor falls back to full posting-list materialization and recomputes everything — same result set, same scores.
- Resolvetoken →
terms→ block row range - Read skipproject first/last/max columns, or hit cache
- Bound-checkthreshold vs term bound vs block max
- Fetch survivorspayload ranges for kept rows only
- Lazy positionsphrase reads the same row ids on demand
Cache the valuable rows, keep an exact fallback
Full-prewarm is no longer the only cache semantic. Selective prewarm reads the skip metadata for workload terms, ranks their block rows by block_max_score, and warms only the top slice — plus a workload-scoped fallback posting-list cache so a failed proof never sends query IO back to S3.
Accent bars are warmed payload (and, when requested, positions) rows. Everything else stays cold on the object store — but its skip metadata is cached, so the executor can still prove what it isn't missing.
- V3BlockMetadataKey(token_id) — a term's block skip metadata
- V3TopBlockRowsKey(token_id) — the rows selective prewarm picked
- V3PostingBlockKey(block_row, with_position) — one payload block
resident cache, measured
V3 selective (top 10%)4.09 MiB
V2 full-prewarm55.84 MiB
V3 full-prewarm66.08 MiB
Speculative search, isolated.When every query term's selected rows are cached, the executor tries a speculative pass with its own threshold, heap, and score state. It returns only when the result is provably exact; otherwise it falls back — and never reuses partial scores.
Measured boundaries
lance-bench-ec2, one S3 dataset, 120k docs, 160 queries, limit=10. Resident cache is much larger than bytes read (decompressed postings, positions, entry overhead), so the MiB ratios do not extrapolate to GB-scale indexes.
| Mode | QPS | Query IO | Resident cache |
|---|---|---|---|
| V2 cold | 13.6 | 494 reads / 14.6 MB | 65 entries |
| V3 cold | 11.2 | 594 reads / 14.4 MB | 48 entries |
| V3 top-block cache, no fallback | 66.6 | 235 reads / 778 KB | 484 entries |
| V3 selective cache (top 10%) | 1376–1408 | 0 reads / 0 B | 4.09 MiB |
| V3 full-prewarm | 1452 | 0 reads / 0 B | 66.08 MiB |
| V2 full-prewarm | 1426 | 0 reads / 0 B | 55.84 MiB |
ProvenOn this workload, selective cache reaches ~95% of full-prewarm QPS with ~6% of its resident cache, and zero remote reads at query time.
Not provenBlock pruning's independent contribution. The no-fallback run (66.6 QPS, still 235 reads) suggests most of the QPS comes from the workload-scoped fallback cache — attribution needs the observability counters first.
Known regressionV3 cold is slower than V2 cold (11.2 vs 13.6 QPS, 594 vs 494 reads, bytes flat): cold pruning saved little payload here, while metadata reads added a hop, amplified by re-reading hot terms across queries.
Follow-up work
The layout already exposes the row-level metadata these layers need.
Cold-path metadata reuse
Keep block metadata and coarse skip resident across queries and coalesce metadata ranges, to close the cold regression.
Prewarm range coalescing
Selective prewarm issues 409 ranges vs full-prewarm's 35 for similar bytes; targeted token chunking should close that gap.
Workload scope beyond query lists
Extend selection from a fixed query list to query-log weighting or global score-aware prewarm under a memory budget.
Cache-entry aggregation
Shrink full-prewarm's 240k-entry overhead. Complementary, not a substitute: it still caches every payload row.