[VOTE] Inverted index format V3: 256-doc posting blocks with patched-FOR frequencies

[BubbleCal]

This proposes the inverted-index format changes carried by PR #7466: an opt-in
256-doc posting block size, and a patched-FOR frequency encoding for those
blocks. It requests a PMC vote on the format change.

Motivation

The FTS posting block size is currently fixed at 128 docs. Larger blocks halve
per-block overhead (headers, skip entries, arrow offsets) and give the
block-max WAND/MAXSCORE query paths wider skip granularity. But plain FOR
frequency encoding gets worse as blocks grow: the whole block is packed at the
bit width of its largest value, so one large term frequency widens all 256
values. On a 200M-doc benchmark corpus (avg tf ~= 4), frequencies cost 4.7
bits/posting under plain FOR; one outlier per block was the dominant cause.

Format specification

A full 256-doc posting block is laid out as:

[first_doc  u32]                 first doc id, also the delta base
[doc_nbits  u8 ]                 FOR bit width for doc-id deltas
[doc payload]                    256 doc-id deltas, bit-packed (BitPacker8x)
[freq_width u8 ]                 patched-FOR body bit width
[exceptions u8 ]                 number of patched exceptions (<= 31)
[freq body]                      256 freqs masked to freq_width, bit-packed
[exception table]                per exception: (index u8, high bits varint)

Unlike 128-doc blocks, V3 blocks carry no per-block max-score prefix: V3
indexes always store impact skip data (#7602), which supplies a tighter
per-block score bound, so the stored f32 would be dead weight (~4B x one
entry per 256 postings across the index).

V3 also adopts Lucene's norm semantics for scoring: BM25 doc lengths are
quantized to a SmallFloat-style byte code (4 mantissa bits, exact below 8,
<= 6.25% relative error) at query time. This quarters the doc-length
working set the scoring path pulls through the cache and matches what
Lucene has always done; scores on V3 differ from exact-length BM25 by the
quantization error. 128-block indexes keep exact-length scoring unchanged.

Frequency encoding is Lucene PForUtil-style patched FOR: the body width is
chosen to minimize total bytes; values wider than the body width store their
high bits in the exception table and are patched after SIMD unpack. Doc ids
remain delta + FOR, unchanged from the 128-doc layout. The final partial
block keeps the existing varint-delta tail encoding.

Measured on the 200M-doc corpus (99.7B postings): frequencies drop from 4.7
to ~2.5 bits/posting, about 27G. For whole-index numbers, a like-for-like
comparison must exclude positions: the earlier 536G index carried ~380G of
position data (orthogonal to this proposal), so the positions-free footprint
under the current 128-doc format is ~156G (postings + fixed-width impact
metadata). The rebuilt positions-free 256-doc index — this PR's patched-FOR
frequencies plus the stacked #7602 impact encoding — is 130G. A Lucene 10.4
index over the same corpus with equivalent options (freqs + norms, no
positions) is 132G.

Compatibility

• The inverted list format version is stored in the index metadata and
  readers dispatch on it: V1 = 128-doc blocks + fixed32 tails,
  V2 = 128-doc blocks + varint tails (current default), V3 = 256-doc blocks.
• 256-doc blocks and format V3 are introduced by this same PR, so V3 is
  defined from day one as "256-doc blocks with patched-FOR frequencies".
  There are no pre-existing V3 indexes to break.
• 128-doc-block indexes (V1/V2) are bit-for-bit unaffected: the patched-FOR
  arm is only reachable for 256-doc blocks, and the writer never selects it
  for V1/V2.
• The default block size remains 128 (V2). 256/V3 is opt-in via index
  creation parameters.
• Old readers encountering a V3 index fail closed with an explicit
  "unsupported format version" error rather than misreading data. New
  readers read V1/V2 through the unchanged legacy code paths.

Rollout and follow-ups

The stacked PR #7602 (impact skip data) adds a varint impact-entry encoding
that is likewise keyed off the 256-doc/V3 format and follows the same
compatibility rule (128 keeps fixed-width entries). Query-side work built on
these formats (#7603, #7604) does not change the on-disk format.

Requesting a PMC vote on the V3 format change described above.

[jackye1995]

+1

[Xuanwo]

Seems nice, here is my +1 binding