You are viewing a plain text version of this content. The canonical link for it is here.
Posted to issues@lucene.apache.org by "goankur (via GitHub)" <gi...@apache.org> on 2026/09/10 00:33:37 UTC
[PR] Parallel O_DIRECT rerank reads for larger-than-RAM KNN search [lucene]
goankur opened a new pull request, #16656:
URL: https://github.com/apache/lucene/pull/16656
### Title:
Parallel `O_DIRECT` full-precision rerank reads for larger-than-RAM KNN search
### Description
Two-phase KNN — quantized (BBQ) graph search in RAM, then full-precision fp32
rerank of the shortlist — keeps recall high while shrinking the resident
footprint. But the rerank reads the `fp32` vectors serially, and once the index
exceeds RAM those reads hit disk, where serializing a query's few-hundred-vector
shortlist dominates p99.
This PR:
- **`ParallelVectorReadable`** (core, `store`): an optional `IndexInput`
capability to fetch a batch of fixed-size float vectors at scattered offsets,
possibly in parallel.
- **`RescoreTopNQuery` / `FullPrecisionFloatVectorSimilarityValuesSource`**: the
full-precision rescorer reads the shortlist via that capability, off the main
field's own raw fp32 through a new `Lucene99FlatVectorsReader` accessor (no
duplicate rerank field).
- **`Lucene99FlatVectorsWriter`**: 4 KB page-aligns FLOAT32 vector data so each
read is a single block (padding is transparent to readers).
- **`SelectiveDirectIODirectory`** (misc): opens only `.vec` with `O_DIRECT` and
implements the capability; it fetches the shortlist through a **caller-owned
read `Executor`**, sized independently of the searcher's executor. The core
read path is Directory-agnostic; mmap inputs fall back to serial reads.
### Benchmarks
25M Cohere-v3 (1024-dim), 102 GB index, process capped to 10 GB (~10× smaller
than the fp32 working set) so rerank reads hit disk. Local NVMe, fio 136k
random-4KB IOPS / 1.12 GB/s. Single-stream, oversample 5, fanout 100.
| Metric | mmap baseline | O_DIRECT rerank (this PR) |
|---|---|---|
| p99 latency | 176 ms | 23.5 ms |
| recall | 0.963 | 0.963 |
| read IOPS | 35.4k | 50.9k |
| avg read size | ~28 KB (readahead-amplified) | 4 KB |
Under concurrent load the design meets p99 ≤ 50 ms at ~240–245 QPS on this box
(one-off validation numbers, not committed).
### Notes for reviewers
- Per-query rerank read concurrency is a **storage concern**: it follows the
caller-owned read `Executor` on `SelectiveDirectIODirectory`, decoupled from
the searcher's executor so a larger-than-RAM deployment can keep enough reads
in flight to saturate the device without widening CPU-side search parallelism.
- The capability interface is float-vector-specific (mirrors
`IndexInput.readFloats`) rather than a general byte-oriented batch read — a
deliberate choice to avoid a decode copy on the rerank hot path. Happy to
generalize if preferred.
- New test `TestSelectiveDirectIODirectory` covers parallel + serial reads,
shuffled offsets, and the empty shortlist.
--
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: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [PR] Parallel O_DIRECT rerank reads for larger-than-RAM KNN search [lucene]
Posted by "jimczi (via GitHub)" <gi...@apache.org>.
jimczi commented on PR #16656:
URL: https://github.com/apache/lucene/pull/16656#issuecomment-5790260964
> I already built parts of it [in my private branch](https://github.com/apache/lucene/compare/main...goankur:lucene:prefetch-rerank-clean) so please take a look and advise the changes that would be suitable for the new PR.
Yep that s exactly this. Currently the api is modelled after the HNSW use case that prefetches N neighbours at a time. Since they are random they just call prefetch N times on different part of the file. A more natural API for prefetch would be `int prefetch(int ord, int size)` to prefetch contiguous vectors (size=1 for a single one) and then the multiple ords one just call the contiguous prefetch N times.
--
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: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [PR] Parallel O_DIRECT rerank reads for larger-than-RAM KNN search [lucene]
Posted by "goankur (via GitHub)" <gi...@apache.org>.
goankur closed pull request #16656: Parallel O_DIRECT rerank reads for larger-than-RAM KNN search
URL: https://github.com/apache/lucene/pull/16656
--
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: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [PR] Parallel O_DIRECT rerank reads for larger-than-RAM KNN search [lucene]
Posted by "goankur (via GitHub)" <gi...@apache.org>.
goankur commented on PR #16656:
URL: https://github.com/apache/lucene/pull/16656#issuecomment-5806091673
> @jimczi
>
> A more natural API for prefetch would be `int prefetch(int ord, int size)` to prefetch contiguous
> vectors (size=1 for a single one) and then the multiple ords one just call the contiguous prefetch
> N times.
Done, and opened as #16705. `prefetch(int ord, int count)` is the primitive; the array form
coalesces ordinals that are consecutive in the array and calls it once per run. Two notes on the shape:
- I named the second parameter `count` rather than `size`, since `size` collides with `size()` meaning "number of vectors in the field."
- I read the `int` return as "the number of vectors a prefetch was actually issued for, 0 if none," mirroring `IndexInput#prefetch`'s boolean. Let me know if you meant something else.
The dedup codecs in sandbox needed their own override: they map field ords to group ords, so a contiguous run of field ords is not contiguous on disk. Without it they would inherit the no-op default, the same silent break as the quantized wrapper.
Closing this one. The `VectorBatch`/`ParallelVectorReadable` SPI is not justified — prefetch on the existing API wins in both the single-stream and concurrent regimes, as measured in #16705. Executor-parallel prefetch issuance will follow as a separate PR on top of it.
--
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: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [PR] Parallel O_DIRECT rerank reads for larger-than-RAM KNN search [lucene]
Posted by "goankur (via GitHub)" <gi...@apache.org>.
goankur commented on PR #16656:
URL: https://github.com/apache/lucene/pull/16656#issuecomment-5786111862
Thanks jimczi - You were right, and the baseline was the problem. Measured: across a full 10,000-query run the JVM issues **23 `madvise` calls in total**, versus **~228 per query** once prefetch is wired through. Everything below is re-measured on that basis.
**Changes (branch off `main`, no new SPI):**
Code is on a branch rather than a PR to keep the queue clean: https://github.com/apache/lucene/compare/main...goankur:lucene:prefetch-rerank-clean. It excludes the measurement-only switches; the 10.49 ms row in table below additionally requires the #16145 backoff fix.
- `KnnVectorValues#prefetch(int ord)`; array form loops over it. I kept its `<=1` skip (a lone ord is read immediately) — `TestOffHeapVectorValues` pins that, and the ring calls the single-ord form directly.
- Forward `prefetch` in `ScalarQuantizedVectorValues`, `ScalarQuantizedFloat16VectorValues`, `NormalizedFloatVectorValues`. This was the silent break.
- `DoubleValues#prefetch(int doc)` (default no-op), implemented by `FullPrecisionFloatVectorSimilarityValuesSource` over a separate `copy()` view so prefetching runs ahead without disturbing the scoring iterator.
- `RescoreTopNQuery`: ring of doc IDs across leaves, prefetch ahead of scoring — heap stays flat, no `count × dim` materialization. Deferral is disabled when `valuesSource.needsScores()`, since `DoubleValuesSource.fromScorer` reads the scorer's current score.
- **Prefetch issuance moved onto `indexSearcher.getTaskExecutor()`.** The second phase was entirely single-threaded while `AbstractKnnVectorQuery` already fans the first phase over that executor. This was the largest single win.
- Test: `TestRescoreTopNQueryPrefetch` counts `IndexInput#prefetch` per extension through slices/clones and asserts `.vec` is prefetched ~once per candidate. It fails with `.vec=0` if any forwarding override is dropped.
**Method:** 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`/page-fault/syscall counts via bpftrace, device via `iostat -x` (`aqu-sz`, `rareq-sz`). MGLRU is off (`lru_gen/enabled` = `0x0000`).
**Single-stream p99:**
| read path | p99 | aqu-sz | avg read |
|---|---|---|---|
| stock mmap (QD 1) | 252.0 ms | — | 27.8 KB |
| mmap + batched prefetch + backoff enabled (default) | 221.0 ms | — | 19.7 KB |
| mmap + batched prefetch + backoff disabled | 17.09 ms | 2.91 | 4.22 KB |
| **mmap + batched + parallel prefetch** (backoff disabled) | **10.49 ms** | 10.47 | 4.22 KB |
| O_DIRECT + 32-thread pool (this PR) | 13.13 ms | 6.65 | 4.33 KB |
**Concurrent, 100 QPS Poisson, 32 handler threads / 32-deep queue, 0 shed** (prefetch rows with backoff disabled):
| read path | p50 | p99 |
|---|---|---|
| mmap + batched + parallel prefetch | 7.72 | **31.83 ms** |
| mmap + batched prefetch, single-threaded issuance | 11.87 | 34.53 ms |
| O_DIRECT + 32-thread pool | 13.52 | 45.72 ms |
**Your specific points:**
- **Read amplification:** `--enable-native-access` was on, so `MADV_RANDOM` was active. The 27.6 KB reproduces (27.8 KB) but it's an artifact of nothing prefetching — with prefetch active, reads are **4.22 KB**. Per-inode attribution also shows stock pulls **91 GB `.vex` vs 88 GB `.vec`** over 10k queries (20.7 MB/query), i.e. half that traffic is graph and O_DIRECT-on-`.vec` never addressed it.
- **Eviction:** O_DIRECT does avoid the fills (~0 vs 0.38 MB/query of `.vex` re-reads), but the latency cost is small: raising the cgroup 10→16 GB cut major faults **92×** (35 → 0.38/query) and p99 only **12%**. So the page cache behaves as you said.
- **#16145 backoff:** live and expensive — **221 → 17.09 ms** (13×). Worth noting it's invisible in a pure-cold microbench (#16279 shows 3.389 vs 3.394 ops/ms with it disabled) because every miss resets the counter; it only bites when the pattern mixes hits and misses, which is the real rerank pattern.
- **#16279:** ran it, 4 KB reads, 100 GB file, cold. `ffiPread` T01 **0.573** vs your 0.58; `mmapRandom` 0.314; `ffiPreadDirectIO` 0.643 / 2.587 / 8.219 (T01/T04/T16); `mmapRandomBatchedPrefetch` **3.394 / 9.636 / 9.852**. `MADV_RANDOM` makes no measurable difference once prefetch is on.
- **`prefetch(int ord)` PR:** I already built parts of it [in my private branch]( https://github.com/apache/lucene/compare/main...goankur:lucene:prefetch-rerank-clean) so please take a look and advise the changes that would be suitable for the new PR.
**Tried and discarded:** burst size (prefetch 64/128/512 candidates before scoring) is flat, 16.55/16.91/16.77 ms — in-flight depth is not issue-rate limited. Coalescing is inapplicable here (~16 candidates per segment, ~206 MB apart) and reducing `madvise` count is actively harmful: prefetching every 2nd candidate halved calls and made p99 **7.7× worse** (17.1 → 131.4 ms, faults 35 → 389/query). Each 12.2 µs `madvise` buys away an ~88 µs fault.
**Where this leaves the PR:** the `VectorBatch`/`ParallelVectorReadable` SPI isn't justified — prefetch on the existing API wins in both regimes. I'd like to withdraw it and instead split out (1) your `prefetch(int ord)` + wrapper forwarding, (2) executor-parallel issuance in `RescoreTopNQuery`, (3) the 4 KB `Lucene99FlatVectorsWriter` alignment, which is orthogonal and helps every path.
--
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: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [PR] Parallel O_DIRECT rerank reads for larger-than-RAM KNN search [lucene]
Posted by "jimczi (via GitHub)" <gi...@apache.org>.
jimczi commented on PR #16656:
URL: https://github.com/apache/lucene/pull/16656#issuecomment-5748849380
Thanks for this.
The conclusion that the time is lost waiting rather than computing looks right.
I also think the structure is right: queue the candidates, submit them together, then score them.
My point is that Lucene already has a hook for this: `IndexInput#prefetch(offset, length)`, “start this read, I’ll consume it later.” So the three phases don’t need a new SPI.
`RescoreTopNQuery` never calls it today. That means the “stock mmap” result is really “mmap at queue depth 1.” It’s slow because nothing tells the kernel about the next candidate, not because it’s mmap.
I’d also revisit the two reasons for routing `.vec` around the page cache. Lucene already applies `MADV_RANDOM` to that file through `DataAccessHint.RANDOM` in `Lucene99FlatVectorsReader`, and it addresses both:
- **Read amplification.** `VM_RAND_READ` disables readahead in the mmap fault path. Both `do_sync_mmap_readahead` and `do_async_mmap_readahead` return early, so a fault reads only the pages it needs. That makes the 27.6 KB read per 4 KB vector surprising. I’d double-check that `--enable-native-access` was enabled for that run. Without it, `madvise` never runs and `MemorySegmentIndexInput#prefetch` always returns false.
- **Eviction of the graph and codes.** The mmap fault path doesn’t mark folios as accessed. A page faulted once under a random mapping goes onto the inactive list and gets reclaimed first. The graph and quantized codes are touched on every query, so they stay active. As long as the rerank working set is manageable, the page cache already acts like the bounded rerank buffer you’re building by hand. It would also be worth testing with MGLRU enabled and disabled. MGLRU marks mapped folios active on fault, and it’s disabled by default on 6.1, so your current runs use classic LRU.
This is why mmap + `MADV_RANDOM` + batched `WILLNEED` is hard to beat here. There’s already a lot of relevant work:
- **#16044** started from the same observation: mmap page-fault storms in cgroup-limited containers with indices larger than RAM. It proposed a native `pread` Directory and grew into a broad study across three platforms, four cache regimes, 1–16 threads, mmap `NORMAL`, `MADV_RANDOM`, batched `WILLNEED`, FFI `pread`, `FileChannel`, and `pread` + `O_DIRECT`.
Batched prefetch won every memory-pressured case. The biggest margin was exactly where you are: one thread, cold, and file ≫ RAM.
| 16 KB random reads, cold, file > RAM, NVMe (ops/ms) | T01 | T08 | T16 |
|---|---|---|---|
| `pread` | 0.58 | 4.02 | 4.65 |
| mmap, no prefetch (`MADV_RANDOM`) | 0.15 | 1.10 | 1.94 |
| **mmap + batched prefetch** | **4.19** | 5.62 | 5.98 |
That T01 result is around 67k IOPS / 1.25 GB/s from one thread, which is what `fio` gets from that device at iodepth 16. It’s a different box from your g6, so it’s only indicative, but it’s the same order as your 67.3k without a ring or native dependency.
- **#16279** is the JMH harness behind it — basically `fio` in Java over Lucene’s store primitives. It’s the easiest way to compare prefetch with your O_DIRECT results on the same hardware without touching the search path.
- **#16145** and **#14156** cover the weak spot in mmap prefetch. The power-of-two backoff in `MemorySegmentIndexInput#prefetch` suppresses `madvise` when the index barely fits in RAM, exactly when it matters most. That’s a live tuning issue in one method.
Here’s how we do it in Elasticsearch using APIs Lucene already has. The ring sits outside the leaf loop, so a candidate in segment N+1 can be prefetched while segment N is still being scored. The window isn’t tied to one input, so there’s no per-file ceiling:
```java
PrefetchRing ring = new PrefetchRing(WINDOW); // WINDOW = 100 for us; doc ids, never vectors
for (LeafReaderContext leaf : reader.leaves()) {
FloatVectorValues values = leaf.reader().getFloatVectorValues(field);
Scorer inner = weight.scorer(leaf);
if (values == null || inner == null) continue;
VectorScorer rescorer = values.rescorer(queryVector); // full precision
KnnVectorValues.DocIndexIterator vectorIter = values.iterator();
DocIdSetIterator conj =
ConjunctionUtils.intersectIterators(List.of(vectorIter, inner.iterator()));
for (int doc = conj.nextDoc(); doc != NO_MORE_DOCS; doc = conj.nextDoc()) {
values.prefetch(vectorIter.index()); // fire and forget
if (ring.isFull()) {
// oldest entry was prefetched WINDOW candidates ago; scores via VectorScorer.Bulk
ring.advance(scoreOldest(ring, buffer, results));
}
ring.append(doc, leaf.docBase, rescorer);
}
}
while (ring.size() > 0) ring.advance(scoreOldest(ring, buffer, results));
```
Heap stays flat because the ring holds `WINDOW` doc IDs instead of count × dim floats across a barrier. Outstanding submissions from one thread provide the depth. There’s no read pool and no context-switch cost.
The current limitation is that `values.prefetch(ord)` doesn’t work. `KnnVectorValues#prefetch` only accepts an array and returns early below two ords. Also, `Lucene104ScalarQuantizedVectorsReader.ScalarQuantizedVectorValues` (what `getFloatVectorValues()` returns for a quantized field) forwards `vectorValue` and `rescorer`, but not prefetching. So it silently does nothing on the BBQ rerank path.
We hit the same issue in Elasticsearch and fixed it in our wrapper. The upstream change is small: add `prefetch(int ord)`, make the array version loop over it, and forward it from the wrapper like the other methods. I’m happy to open that PR so you have something to build on.
This doesn’t rule out O_DIRECT. It should also be able to rescore efficiently, but it doesn’t need the new SPI either. The input can submit asynchronously during `prefetch` and reap during `readFloats`. Inputs from the same directory can share a ring. Submissions can also accumulate until the first dependent read forces a flush, which is what `VectorBatch#execute` expresses.
The query loop stays the same and the store chooses the mechanism.
Would you be up for measuring the prefetch path before adding the API, on the same box and at the same operating point? I still expect mmap to be better, but if O_DIRECT clearly wins, that’s a real result. The next step would be your Directory behind `prefetch`, not a new interface.
--
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: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org