Parallel O_DIRECT rerank reads for larger-than-RAM KNN search - #16656

Title:

(Implemented with AI, with Human in the loop)

Parallel O_DIRECT full-precision rerank reads for larger-than-RAM KNN search

Description (Reviewed and Edited by Human)

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 one at a time, and once the index exceeds RAM those reads hit disk, where serializing a
query's few-hundred-vector shortlist dominates p99.

This PR:

• FlatVectorsReader.readRawVectors(field, ords, count, out) (core, codecs/hnsw): an
  overridable batch read, defaulting to false ("no batch support"). Lucene99FlatVectorsReader
  implements it and Lucene104ScalarQuantizedVectorsReader delegates to its raw reader.
• ParallelVectorReadable (core, store): an optional IndexInput capability to fetch many
  fixed-size float vectors at scattered positions as one batch, possibly in parallel. Positions are
  relative to the input (like RandomAccessInput), and the vectors are written back to back into one
  flat float[] so the hot path allocates one buffer per query rather than one array per candidate.
• RescoreTopNQuery / FullPrecisionFloatVectorSimilarityValuesSource: the full-precision
  rescorer maps its shortlist to ordinals and calls readRawVectors, reranking against the main
  field's own raw fp32 (no duplicate rerank field, halving the index). When the reader cannot batch,
  it returns null and the existing per-document path handles it.
• Lucene99FlatVectorsWriter: 4 KB page-aligns FLOAT32 vector data so each vector is a single
  block instead of straddling two. The offset is self-describing, so existing indexes still read
  correctly — they just pay the extra block.
• SelectiveDirectIODirectory (misc): opens .vec with O_DIRECT (via the JDK's
  ExtendedOpenOption.DIRECT — pure JDK, no JNI) and implements the capability, fetching the
  shortlist through a caller-owned read Executor sized independently of the searcher's
  executor. Everything else — HNSW graph, quantized codes, metadata — keeps using the mmap delegate
  and stays page-cached.

Benchmark setup

• Box: AWS g6.4xlarge — 16 vCPU AMD EPYC 7R13 (Zen 3), 60 GB RAM, local NVMe instance store
  measured with fio at 136k random-4KB read IOPS / 1.1 GB/s.
• Data: 25M Cohere-v3 Wikipedia embeddings, 1024-dim fp32; 1-bit BBQ + fp32 rerank; HNSW
  maxConn 64 / beamWidth 250; 102 GB index.
• Larger-than-RAM: searcher pinned to a 10 GB cgroup v2 hard limit (swap off, 4 GB heap), so
  graph and quantized codes stay resident while every rerank read hits the SSD — ~10× the cap.
• Queries: 10,000; recall checked against exact top-100 ground truth (GPU brute force) on every
  configuration; page cache dropped before each run.

Results

Single-stream, oversample 5 / fanout 100.

The baseline moves ~67 MB per query where only 2 MB is needed (~34× amplification): the kernel's
128 KB read-ahead fetches neighbors around every 4 KB vector, and MADV_RANDOM does not stop
block-device read-ahead. O_DIRECT removes that; alignment then removes the second block per vector.

Under concurrent load (open-loop, Poisson arrivals, bounded 32-thread pool + 32-deep queue with
load shedding, latency from intended arrival, 120 s per rate), the highest rate holding
p99 ≤ 50 ms with ≤ 0.1% shed is ~90 QPS at oversample 5 / fanout 100 and ~130 QPS at the
recall-tuned oversample 3.5 / fanout 25 (recall 0.937).

Notes for reviewers

• Where the batch API lives. readRawVectors sits on FlatVectorsReader so ordinal→position
  arithmetic stays inside the codec that owns the layout.
• Read concurrency is a storage concern. It follows the caller-owned Executor on
  SelectiveDirectIODirectory, decoupled from the searcher's executor, so that enough reads can be kept in flight to saturate the device without increasing search parallelism.
• useDirectIO adds .vec to whatever DirectIODirectory already routes through direct I/O
  rather than replacing it, so the inherited merge behavior is preserved.
• The capability is float-vector-specific (mirroring IndexInput.readFloats) rather than a general
  byte-oriented batch read, deliberately, to avoid a decode copy on the rerank hot path. Happy to
  generalize if preferred.
• Inputs without the capability (e.g. mmap) are read per document exactly as before; this is opt-in
  by directory choice and changes no default.
• TestSelectiveDirectIODirectory covers parallel and serial batch reads, shuffled positions and the
  empty shortlist.