Proposal: Block-Row Posting Layout and Block Executor for FTS Index V3

[Xuanwo]

• Visit https://xuanwo.io/sketches/lance-fts-v3-block-row-layout/ first for a quick glance (animated explainer).
• Visit perf(fts): prune V3 posting blocks during query execution #7669 for testing and evaluting.

---

Context: V2 became the default inverted index format in #7512. This proposal defines the next index format version, V3: a block-row posting layout, a block-level query executor, and a selective prewarm/cache mode. The numbers in Measured Boundaries come from a working prototype, benchmarked on EC2 against S3.

Summary

V3 is a new format version for the FTS inverted index. On the storage side, it splits the posting list from "one row per token" into a block-row layout: each 128-doc posting block becomes its own row, with the skip metadata pulled out into narrow columns. On the query side, the executor plans at block granularity: it reads skip metadata first and skips a payload block only when the block's score upper bound proves it cannot enter the top-k; whenever completeness cannot be proven, it falls back to the full posting-list path. On the cache side, prewarm gains a selective mode that populates the cache by workload scope and block score instead of loading everything. Every new V3 path returns the same top-k set and scores as the full path.

Measured on a 120k-doc S3 dataset (160 queries, limit=10): selective cache reaches 1376–1408 QPS with 4.09 MiB resident — about 95% of full-prewarm QPS at about 6% of its resident cache.

Problem

V1/V2 store a token's entire posting list as one row of the postings file, with the row number acting as the token id:

invert.lance (V2, one row = one token's full posting list)
  _posting: List<LargeBinary>          -- each element is one 128-doc compressed
                                          block (doc id deltas + freqs); the first
                                          8 bytes of every block embed
                                          block_max_score (f32) + first_doc_id (u32)
  _max_score: Float32                  -- term-level upper bound
  _length: UInt32                      -- number of postings
  _compressed_position: LargeBinary    -- shared stream of all positions for the token
  _position_block_offset: List<UInt32> -- manually maintained positions block offsets

_max_score and _length are separate columns, so term-level metadata can be projected on its own. But the block-level decision inputs — block max score and doc id bounds — are embedded in each block's header and only become visible after the payload has been read. Querying a token therefore always reads the whole row back and materializes the full posting list; WAND's block skipping can only happen at the decode layer, after every byte has already crossed the network into memory. Cold reads on S3, high-frequency terms, small top-k, and OR/WAND queries all amplify range bytes and peak memory.

Splitting the storage alone is not enough: if the reader still fetches all block rows back and rebuilds the full posting list, the layout has only changed the file shape. So V3 defines the layout, the query execution, and the cache contract together.

Proposed Design

Block-row layout

A V3 index consists of four kinds of files:

terms
  token_id -> block_start, num_blocks, df, max_score, length

posting_blocks
  row_id = global block row
  columns: first_doc_id, last_doc_id, block_max_score, posting_payload

posting_positions
  row_id = posting_blocks.row_id
  columns: compressed_position

posting_coarse_skip
  coarse ranges over posting_blocks for cheaper long-range skipping

A term's block rows must be contiguous with monotonic block_start; block_start + num_blocks defines its row range. The three skip columns are narrow and can be read via column projection alone; posting_payload and compressed_position are fetched only for selected rows. posting_coarse_skip is always written by the builder; it aggregates doc id ranges and group max scores at a group granularity fixed by the format, and serves long-distance advance(target) and segmented metadata reads for high-frequency terms. A reader that ignores it must produce identical results — it can only change the IO plan.

Ownership boundaries: the builder cuts posting lists into fixed-size blocks, writes the block-row tables, and maintains the term → block-range prefix mapping; the reader interprets V3 metadata as block row ranges; the executor decides which blocks to read. The payload codec stays FTS-private binary — Lance provides only row-level random access, range reads, and column projection.

Block executor

Queries move from term-level materialization to block-level planning:

1. Query tokens map to token ids; terms yields each term's block row range.
2. Read (or hit in cache) the block metadata: first_doc_id, last_doc_id, block_max_score.
3. Use the current top-k threshold, the query term's upper bound, and the block max score to decide whether a block can possibly contribute to the result set.
4. Fetch posting_payload only for blocks that can contribute, generating payload ranges from the skip columns; already-cached block rows are served from the block cache.
5. When phrase/proximity needs positions, lazily read the same block rows from posting_positions.

Pruning is not approximate search: every skipped block must be proven unable to enter the top-k by its upper bound. When the proof cannot be completed, the executor falls back to full posting-list materialization.

Selective prewarm and cache

Selective prewarm reads the skip metadata for the workload scope, picks each query term's most valuable block rows by block_max_score, then warms the payload, optionally positions, and fallback posting lists for the workload terms. In the current setup the workload scope comes from a query list; percent=10 keeps the top 10% of block rows by score for each query term.

Cache keys:

• V3BlockMetadataKey(token_id) — a term's block skip metadata.
• V3TopBlockRowsKey(token_id) — the block rows selective prewarm picked for that term.
• V3PostingBlockKey(block_row, with_position) — a single posting block payload, optionally with positions.

When every query term's selected rows and metadata are cached, the executor first runs a speculative block search over those rows. That pass uses an isolated threshold, result heap, and score state, and returns only when the result is provably exact; otherwise it falls back. The fallback posting-list cache exists so that a fallback does not push query-time IO back to S3; it is also workload-scoped, not a full prewarm.

Observability

The executor and cache must expose: reads for block metadata, payload blocks, payload ranges, and position blocks; the number of pruned blocks; how often the full posting-list path triggers; speculative pass completion and fallback rates; and cache composition (entries and bytes for skip metadata, payload, positions, and fallback posting lists). Without these counters it is impossible to tell whether a win comes from block pruning, block cache hits, or the workload-scoped fallback cache.

Contract and Invariants

• posting_positions row ids must equal posting_blocks row ids; when an index has no positions, phrase/proximity returns an explicit error.
• Whether the index was built with positions decides whether phrase/proximity can execute at all; prewarm's with_position only decides whether query time needs lazy positions IO — with_position=false does not promise zero-IO phrase/proximity.
• first_doc_id, last_doc_id, and block_max_score must be sufficient for block-level upper-bound decisions without reading payload.
• The block executor is enabled only on the V3 layout; V2/V1 keep the existing posting-list path.
• Selective prewarm selects by score and workload scope, not physical row order; percent or a cache budget only sets the cutoff on the score-ranked population.
• Every new V3 path must return the same top-k set and scores as the full path; when completeness cannot be proven, fall back — never return approximate results, never reuse speculative partial scores.

Compatibility and Migration

V3 is a new index format version. The V2 reader, the existing posting-list materialization path, and the public APIs are all preserved; the compatibility goal is that any mix of V2 and V3 cache states, query types, and fallback returns the same semantic results. prewarm_index keeps meaning full prewarm; selective prewarm is a new entry point that only changes the cache population policy. The full-prewarm path stays long-term as the correctness boundary for uncovered query types, failed speculative proofs, and the rollout window.

Measured Boundaries

One S3 dataset, 120k docs, 160 queries, limit=10. Full-prewarm reads about 2.73 MB from storage; resident cache is much larger than the bytes read (decompressed postings, positions, and cache entry overhead), so the MiB ratios below do not extrapolate directly 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 posting-list cache)	66.6	235 reads / 778 KB	484 entries
V3 selective cache (top 10%, with positions)	1376–1408	0 reads / 0 B	4.09 MiB / 1030 entries
V3 full-prewarm	1452	0 reads / 0 B	66.08 MiB / 240268 entries
V2 full-prewarm	1426	0 reads / 0 B	55.84 MiB / 120660 entries

• Proven: on this workload, selective cache reaches ~95% of full-prewarm QPS with ~6% of its resident cache and zero remote reads at query time.
• Not yet proven: block pruning's independent contribution. The gap between the no-fallback run (66.6 QPS, still 235 reads at query time) and 1376–1408 suggests most of the QPS may come from the workload-scoped fallback posting-list cache.
• Known regression: V3 cold vs V2 cold is 11.2 vs 13.6 QPS with 594 vs 494 reads and roughly flat bytes — cold pruning saved little payload here, while the extra block-metadata reads added a hop, amplified by re-reading hot terms across queries.

Prewarm IO shape: top-10% with positions issues ~409 ranges / 3.06 MB, while full-prewarm issues ~35 ranges / 2.73 MB — the selective mode saves resident memory but does not yet save prewarm bytes/ranges.

Future Work

• Attribution: once the observability counters land, measure selective-without-fallback QPS and the metadata/payload composition of cold reads, to quantify block pruning's independent contribution.
• Cold path: keep block metadata and coarse skip resident (or cheaply reusable) across queries and coalesce metadata reads, to close the cold regression against V2.
• Selective prewarm IO: range coalescing and targeted token chunking, to push 409 ranges toward the full-prewarm ballpark.
• Workload scope: extend from a fixed query list to query-log weighting or global score-aware prewarm.
• Full-prewarm cache-entry aggregation: shrink the 240k-entry overhead; complementary rather than a substitute — it still caches every payload row.

[wjones127]

This looks very good, and has quite promising benchmarks. I have a few key questions about how this will interact with the index cache.

each 128-doc posting block becomes its own row

question: how big is each block on disk in terms of bytes? Does it turn reading a few blocks into many small IOs?

question: what's the unique of caching in the index cache? Recall that we found V2 had an issue where some entries were too small, so we grouped them into chunks. If the unit is one block, the size of the block is important. It sounds like this comment is getting at this issue: "Full-prewarm cache-entry aggregation: shrink the 240k-entry overhead".