DiskANN

Positioning and trade-offs

How it compares with this repository's other indexes

Build and search architecture

Build

Unfiltered search

1. Load the PQ codebook, adaptively packed row IDs, PQ codes, and the block-compressed adjacency locator index into resident memory.
2. Use the PQ distance table, four-code neighbor batches, and a reusable contiguous heap frontier to traverse the Vamana graph with search-list size L.
3. Read only adjacency windows needed by the selected beam.
4. Read raw-vector windows for at most min(L, max(4 × top_k, 64)) candidates.
5. Compute squared-L2 distances from the persisted F32/F16 records and return the best top_k.

Every sorted adjacency list independently uses canonical delta-varint encoding only when it is smaller than fixed-width IDs; otherwise it falls back to raw little-endian u32. Locator positions use one u64 base per 16 nodes plus a u16 relative offset and u16 degree/encoding value per node, for 4 × N + 8 × ceil(N / 16) bytes. Raw fallback guarantees that compression cannot increase adjacency payload bytes or logical page count.

SSD and object-store deployment

All tiers use exactly the same file. Quality-gated filtered graph traversal uses the separately validated beam width 4 for every tier; the table's wider beams apply to ordinary unfiltered graph search. The Reader selects exactly once while opening: below 50 µs selects Memory, below 750 µs selects LocalStorage, below 3 ms selects RemoteStorage, and 3 ms or more selects ObjectStore. SeekReadCapabilities::estimated_random_read_latency_nanos bypasses measurement when an adapter already knows representative latency; zero reuses the mandatory header read's elapsed time and adds no probe I/O. Window and range-count capabilities can refine the selected plan; physical alignment remains encapsulated by the storage adapter. A remote callback receives all ranges for a round together and should issue them concurrently.

Usage

index.type=diskann
dimension=128
metric=l2
deployment-profile=local_storage
diskann.build-preset=balanced

use paimon_vindex_core::index::{
    VectorIndexReader, VectorIndexReaderOptions, VectorSearchParams,
};

let options = VectorIndexReaderOptions::new(4 * 1024 * 1024 * 1024);
// `input` comes from the storage/cache layer and implements SeekRead.
let mut reader = VectorIndexReader::open_with_options(input, options)?;
reader.optimize_for_search()?;
let plan = reader.read_plan(); // Current effective DiskANN I/O/cache diagnostics.
reader.warmup_queries(&representative_queries, representative_query_count, 100)?;
reader.calibrate_search_width(&representative_queries, representative_query_count, 10)?;
let params = VectorSearchParams::automatic(10);
let (ids, squared_l2) = reader.search(&query, params)?;

The core API depends only on SeekRead; the application storage adapter owns local-cache, object-store, and transport details. Its pread implementation should issue all ranges in a search round concurrently and may report immutable-source capabilities so DiskANN does not overfill a callback or choose the wrong coalescing size. Its I/O executor must remain runnable when CPU query workers are saturated: recursively scheduling range reads onto that same fully occupied worker pool can starve the reads while every query waits on single-flight cache entries. The benchmark therefore uses an independent range-I/O pool for DiskANN. The generic Read + Seek adapter is a sequential compatibility path, not the recommended production integration.

The parent Reader and retained search-session clones share one immutable raw-vector LRU. Query-local caches hold borrowed Arc windows, so concurrent reranks for the same range are single-flighted instead of reading duplicate bytes. Cache hits and oldest eviction update linked recency metadata in constant time, and capacity is charged by retained Vec::capacity(). Misses in one search are read together; a query whose working set is larger than its local-reference allowance bypasses local retention, while batch rerank processes bounded chunks. DiskAnnSearchStats resets per top-level search and exposes raw-vector hits, storage misses, and evictions across both cache layers.

F16 compact-vector rerank on AArch64 loads unaligned half-precision lanes, rejects non-finite values, converts them to F32, and accumulates L2 in the same NEON loop. This removes the temporary decode buffer and the second SIMD pass while preserving the scalar fallback and sentinel behavior on other targets.

Cold adjacency windows outside the automatically sized hot prefix use a separate bounded LRU shared by the Reader and its batch workers. Concurrent misses for the same window are single-flighted: one worker performs the positional read while the others wait and then borrow the immutable payload. Successful reads move their existing Vec allocation into shared ownership without copying the payload. Capacity is charged by actual retained allocation capacity and clipped to both the adjacency section and the remaining total memory budget. Budgets of at least 1 MiB use 16 independently locked capacity shards. Every graph worker also bounds query-local cold-window references to 8 MiB and releases least-recently-used windows between beam rounds.

DiskANN retains cloned storage handles as reusable search sessions. Small batches (up to four queries per worker) run graph traversal and persisted-vector rerank concurrently end to end, avoiding a serial parent-rerank bottleneck; the interleaved layout always uses this path because the graph read already contains the vector. Larger compact-layout batches keep the object-store-friendly path: workers return node IDs, the parent unions raw-vector windows, and rerank streams chunks of at most 64 MiB and 1024 ranges. Unsupported sources fall back to complete serial queries. Single and batch rerank retain only the best top_k results per query in bounded heaps. Rust storage adapters, C/Python range callbacks, and JNI inputs opt into reusable sessions through try_clone_reader. Every clone must expose the same immutable byte sequence and be safe for concurrent calls.

reader = VectorIndexReader(
    input_with_concurrent_pread_many,
    memory_budget_bytes=4 * 1024 * 1024 * 1024,
)
reader.optimize_for_search()
plan = reader.read_plan()
reader.warmup_queries(representative_queries, l_search=100)
reader.calibrate_search_width(representative_queries, top_k=10)
ids, distances = reader.search(
    query, SearchParams.automatic(top_k=10)
)

The C, C++, Java/JNI, and Python APIs expose the same latency hint, total Reader memory budget, and concrete read-plan diagnostics. See the shared API guide for lifecycle and callback ownership.

Build parameters

Starting values

• Start with diskann.build-preset=balanced, the automatic pq.code-ratio=0.0625, and the intended deployment-profile. The balanced preset resolves to 8-bit PQ, R=64, Lbuild=100, alpha 1.2, F16, and PQ-guided construction unless an explicit option changes the representation.
• For 8-bit PQ, the default resolves to m=32 at 128 dimensions and m=240 at 960 dimensions. Other shapes use the nearest count and balanced chunks whose widths differ by at most one. Inspect metadata for the resolved value and use explicit pq.m only after a representative recall measurement.
• Test pq.bits=4 only as a separate build. Accept it when the smaller resident footprint and faster lookup tables preserve the required Recall@K across the full l_search sweep.
• Use the F16 default for the storage/I/O baseline, but compare diskann.raw-vector-encoding=f32 when exact final distances or an unusual numeric range matters. F16 can change top-k ordering even when graph candidates are identical and rejects values outside the finite binary16 range.
• If online l_search must become very large to reach the target, test Lbuild=150/200 before increasing R.
• Increase R only after recording file size, build peak RSS, graph-page bytes, and recall. Rebuilds are required for every build-parameter change.

Query parameters

Reader and warm-up parameters

Read-plan selection is part of open, not optimize_for_search. Call optimize_for_search before accepting traffic when predictable first-query latency matters: it loads resident data, preloads the automatically sized adjacency prefix, and validates every covered 4 KiB logical page in parallel before publishing that prefix. Follow it with warmup_queries to populate query-dependent caches and calibrate_search_width to select an automatic width. None is required for correctness; the first non-empty query initializes resident data lazily.

Filtered search behavior

Every Roaring64 filter is first translated into a bitmap of matching internal nodes. Filters with at most N / 16 values lazily load the persisted (row_id, node_id) order and resolve duplicate row IDs with binary-search ranges. Dense filters use a sequential decoder over resident raw or FOR-bitpacked row IDs. If the optional lookup would exceed the Reader memory budget, sparse queries transparently use the sequential path. A filtered batch performs this translation once and shares the bitmap with every candidate worker.

The safe baseline scans matching resident PQ codes and keeps T=min(M, max(4 × top_k, 64)) candidates. A filtered batch evaluates this path in node-major tiles of up to four queries: each matching PQ code is loaded once per tile while each query keeps an independent bounded heap. The tile shrinks automatically when necessary so active PQ distance tables occupy at most 2 MiB. The resident scan does not clone or read the storage source. The graph path traverses the ordinary unfiltered graph, post-filters its candidates, and falls back to that complete matching-node PQ scan before any raw-vector read when fewer than T matches survive. It never filters graph edges, so the filter cannot disconnect traversal.

Negative stored row IDs and bitmap values above i64::MAX never match. Duplicate row IDs return every matching internal node before bounded PQ candidate selection.

Recommended tuning order

1. Fix acceptance criteria. Use production queries and filters; record Recall@K, P50/P95/P99, QPS, index bytes, peak RSS, build duration, read rounds, and bytes read.
2. Choose storage layout and characterize read latency. Benchmark interleaved on the cached local path, exercise the latency-hint or measured remote path for bandwidth-balanced network reads, and test compact when minimizing object-store request rounds matters most. Include file-size and byte-amplification results.
3. Calibrate, then verify search width. Run calibrate_search_width on representative queries, validate the chosen 100/200/400 width against exact ground truth, and use an explicit l_search only when the workload target requires it.
4. Tune PQ. Sweep pq.code-ratio around 0.0625 and record the resolved pq.m, then compare a separate 4-bit build. Both the ratio and bit width change resident memory and traversal accuracy.
5. Improve graph quality. Compare product_quantized against the full_precision control, then raise Lbuild and consider R. Do not change several build knobs in one experiment.
6. Size Reader memory. Sweep the single total memory budget after graph parameters stabilize. The Reader repartitions it automatically; use search statistics and read rounds to identify whether a larger working set has material benefit.
7. Run production-scale validation. Include cold/warm cache, concurrent queries, selective and broad filters, corrupt/truncated input, and restart/rollover behavior.

Capacity model

These formulas omit headers, alignment, allocator overhead, and per-query caches. Use measured RSS and serialized bytes as the final authority.

Current implementation boundaries

• v1 supports squared L2, negative-dot-product inner product, and 1 - cosine, with dimensions up to 1024 and 4/8-bit PQ.
• The index is static. FreshDiskANN-style insert, delete, consolidation, and graph repair are not implemented.
• Serialization builds the complete graph in memory. Raw vectors are stored as explicit F32 or F16 scalar records; there is no PQ-only result mode.
• Recall is sensitive to both PQ capacity and graph/search budgets. On the public SIFT1M and GIST1M runs, the default ratio resolved to m=32 and m=240. DiskANN Recall@10 was 0.995 and 0.973 at l_search=200, while GIST rose to 0.991 at l_search=500; use the public-corpus procedure rather than synthetic vectors when validating a new ratio.
• Remote graph traversal has dependent I/O rounds. It improved high-recall single-query latency over raw IVF scans at 2 ms RTT in the measured workload, but compact IVF-PQ won batch throughput when its lower recall was acceptable.
• Direct remote reads rely on the caller's range-read callback for actual concurrency.
• The file has strict structural validation but no embedded checksum; integrity belongs to the outer Paimon file/manifest layer.
• Generated correctness and I/O acceptance workloads pass, but production readiness still requires SIFT1M or representative full-scale recall, soak, concurrency, and failure testing.