goankur opened a new pull request, #16705:
URL: https://github.com/apache/lucene/pull/16705
# Prefetch full-precision vectors when rescoring
Fixes the case where a BBQ/scalar-quantized rerank shortlist turns into one
dependent blocking read
per candidate, and makes `KnnVectorValues#prefetch` able to express a
contiguous run.
Follow-up to the discussion in #16656, which this replaces. Thanks @jimczi
for the review that
redirected it onto the existing `IndexInput#prefetch` hook.
### The problem
`RescoreTopNQuery` scored one candidate at a time and never called
`IndexInput#prefetch`, so a
shortlist of M candidates became M dependent blocking reads. Measured over a
10,000-query run, the
JVM issued **23 `madvise` calls in total** — the rerank phase ran at queue
depth 1.
A caller that did prefetch could not reach the store either. The
`FloatVectorValues` returned by
`getFloatVectorValues()` for a quantized field
(`Lucene104ScalarQuantizedVectorsReader.ScalarQuantizedVectorValues`)
forwards `vectorValue()` and `rescorer()` but not `prefetch()`, so it
silently inherited the no-op
default. Same for `ScalarQuantizedFloat16VectorValues` and
`NormalizedFloatVectorValues`. Nothing
failed; prefetching just did nothing on the rerank path.
### Changes
- **`KnnVectorValues#prefetch(int ord, int count)`** is now the primitive.
Vectors are laid out
contiguously by ordinal, so a run of them is a single read rather than one
per ordinal. It returns
the number of vectors a prefetch was actually issued for, generalizing the
boolean returned by
`IndexInput#prefetch` ("true if prefetch actually prefetched something").
`count` is clamped to
the vectors remaining after `ord`.
- **`prefetch(int[] ords, int numOrds)`** now coalesces ordinals that are
consecutive in the array
into one call — the common shape on the HNSW neighbour path — and keeps
skipping a lone ord that is
about to be read anyway (`TestOffHeapVectorValues` pins this).
- **Forward `prefetch` from the wrappers**: `ScalarQuantizedVectorValues`,
`ScalarQuantizedFloat16VectorValues`, `NormalizedFloatVectorValues`. This
was the silent break.
- **`DoubleValues#prefetch(int doc)`** (default no-op), implemented by
`FullPrecisionFloatVectorSimilarityValuesSource` over a separate `copy()`
view, so running ahead
does not disturb the iterator that `advanceExact()`/`doubleValue()` rely
on.
- **`RescoreTopNQuery`** starts the loads for a whole segment's candidates
before scoring any of
them. Only doc ids are buffered, never `count × dim` floats. Deferral is
disabled when
`valuesSource.needsScores()`, since `DoubleValuesSource.fromScorer` reads
the scorer's current
score.
- **Sandbox dedup codecs** override `prefetch(int ord, int count)` via a
shared
`DedupUtil.prefetchRemapped`: they map field ords to group ords, so
consecutive field ords are not
necessarily contiguous on disk. Without the override they would inherit
the no-op default, which is
the same silent break as above.
- **Test**: `TestRescoreTopNQueryPrefetch` counts `IndexInput#prefetch` per
file extension through
slices and clones, and asserts `.vec` is prefetched about once per
rescored candidate. It fails
with `.vec=0` if any forwarding override is dropped.
### Measurements
g6.4xlarge, kernel 6.1, local NVMe. 25M Cohere-v3 1024-d, 1-bit BBQ + fp32
rerank,
`overSample 5 / fanout 100`, `nquery=10000`, `topK=100`. Each run in a 10 GB
systemd scope against
~101 GB of vectors, page cache dropped first. Recall **0.967 in every row**.
`madvise` and page-fault
counts via bpftrace, device via `iostat -x`. MGLRU off.
Single-stream p99:
| read path | p99 | aqu-sz | avg read |
|---|---|---|---|
| before this PR (mmap, nothing prefetches) | 252.0 ms | — | 27.8 KB |
| this PR, `MemorySegmentIndexInput#prefetch` backoff as-is | 221.0 ms | — |
19.7 KB |
| this PR, with the #16145 backoff fix | **17.09 ms** | 2.91 | 4.22 KB |
Two things worth separating out:
- The 27.8 KB average read is **not** read amplification from mmap.
`MADV_RANDOM` is applied and
active (`--enable-native-access` on), and with prefetching the reads are
4.22 KB. The inflated
figure is an artifact of nothing prefetching.
- **The power-of-two backoff in `MemorySegmentIndexInput#prefetch` (#16145)
gates most of the win
here: 221 → 17.09 ms, 13x.** It is invisible in a pure-cold microbench
(#16279 measures 3.389 vs
3.394 ops/ms with it disabled) because every miss resets the counter. It
only bites when the access
pattern mixes hits and misses, which is what rerank does. That fix is
worth landing on its own.
Reducing the number of `madvise` calls is actively harmful on this path:
prefetching every 2nd
candidate halves the calls and makes p99 **7.7x worse** (17.1 → 131.4 ms,
faults 35 → 389 per
query). Each 12.2 µs `madvise` buys away an ~88 µs fault. Burst size is flat
(64/128/512 candidates
before scoring: 16.55/16.91/16.77 ms), so in-flight depth is not issue-rate
limited here.
### Two questions for reviewers
1. **Return value of `prefetch(int ord, int count)`.** I read it as "the
number of vectors a prefetch
was actually issued for, 0 if none," to mirror `IndexInput#prefetch`'s
boolean. If it should
instead mean "how far the caller may advance" or something else, it is a
one-line change in the
two off-heap classes plus the javadoc.
2. **`DoubleValues#prefetch(int doc)`.** This widens a very general API to
serve the rerank path.
The alternative is for `RescoreTopNQuery` to special-case a vector-values
source and drive
`values.prefetch(ord)` / `values.rescorer()` directly in the leaf loop,
with no new method on
`DoubleValues`. Happy to switch if that is preferred.
### Not in this PR
Issuing the prefetches on `IndexSearcher#getTaskExecutor()` rather than all
on the calling thread is
a further ~1.6x on p99 (17.09 → 10.49 ms single-stream) and is orthogonal —
it helps every read path,
not just this one. It will follow as a separate PR on top of this one.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
