This is an automated email from the ASF dual-hosted git repository.
JingsongLi pushed a commit to branch main
in repository https://gitbox.apache.org/repos/asf/paimon-vector-index.git
The following commit(s) were added to refs/heads/main by this push:
new 27af94d perf: improve IVF-SQ training, encoding, and reader reuse
(#91)
27af94d is described below
commit 27af94dbd120da97a457d2b196b47e23912dbaa5
Author: Jingsong Lee <[email protected]>
AuthorDate: Sun Sep 6 20:45:47 2026 +0800
perf: improve IVF-SQ training, encoding, and reader reuse (#91)
---
core/src/index.rs | 4 +-
core/src/ivfsq.rs | 119 +++++++-----
core/src/ivfsq_io.rs | 504 ++++++++++++++++++++++++++++++++++++++++++++------
core/src/sq.rs | 407 ++++++++++++++++++++++++++++++++++++----
core/src/topk.rs | 4 +
docs/api.html | 13 +-
docs/development.html | 17 +-
docs/index.html | 71 ++++---
docs/ivf-flat.html | 2 +-
docs/ivf-rq.html | 4 +-
docs/ivf-sq.html | 40 ++--
docs/releases.html | 2 +
12 files changed, 987 insertions(+), 200 deletions(-)
diff --git a/core/src/index.rs b/core/src/index.rs
index 198eaed..773984f 100644
--- a/core/src/index.rs
+++ b/core/src/index.rs
@@ -1464,8 +1464,8 @@ impl<R: SeekRead> VectorIndexReader<R> {
IVFFLAT_MAGIC =>
Ok(Self::IvfFlat(IVFFlatIndexReader::open_with_header(
reader, header,
)?)),
- IVF_SQ_MAGIC => Ok(Self::IvfSq(IVFSQIndexReader::open_with_header(
- reader, header,
+ IVF_SQ_MAGIC =>
Ok(Self::IvfSq(IVFSQIndexReader::open_with_header_and_options(
+ reader, header, options,
)?)),
MAGIC => Ok(Self::IvfPq(IVFPQIndexReader::open_with_header(
reader, header,
diff --git a/core/src/ivfsq.rs b/core/src/ivfsq.rs
index c39a62e..af69ed9 100644
--- a/core/src/ivfsq.rs
+++ b/core/src/ivfsq.rs
@@ -15,10 +15,10 @@
// specific language governing permissions and limitations
// under the License.
-//! IVF with per-list, per-dimension 8-bit residual scalar quantization.
+//! IVF with per-dimension 8-bit residual scalar quantization.
use crate::coarse::CoarseAssignment;
-use crate::distance::{fvec_madd, preprocess_vectors, MetricType};
+use crate::distance::{preprocess_vectors, MetricType};
use crate::ivfpq::RowIdFilter;
use crate::kmeans::{self, KMeansConfig};
use crate::sq::ScalarQuantizer;
@@ -86,9 +86,14 @@ impl IVFSQIndex {
self.quantizer_centroids =
kmeans::kmeans_train(&KMeansConfig::default(), &processed, n,
self.d, self.nlist);
self.coarse_assignment.reset();
- let (list_ids, residuals) = self.assign_residuals(&processed, n);
- self.sq.train(&residuals, n);
- self.train_list_sqs(&list_ids, &residuals);
+ let list_ids = self.coarse_assignment.assign(
+ &processed,
+ n,
+ &self.quantizer_centroids,
+ self.nlist,
+ self.d,
+ );
+ self.train_list_sqs(&processed, &list_ids);
}
pub fn add(&mut self, data: &[f32], ids: &[i64], n: usize) {
@@ -247,44 +252,39 @@ impl IVFSQIndex {
}
}
- fn assign_residuals(&mut self, processed: &[f32], n: usize) ->
(Vec<usize>, Vec<f32>) {
- let list_ids = self.coarse_assignment.assign(
- processed,
- n,
- &self.quantizer_centroids,
- self.nlist,
- self.d,
- );
- let mut residuals = vec![0.0f32; n * self.d];
- for i in 0..n {
- let vector = &processed[i * self.d..(i + 1) * self.d];
- self.write_residual(
- vector,
- list_ids[i],
- &mut residuals[i * self.d..(i + 1) * self.d],
- );
+ fn train_list_sqs(&mut self, data: &[f32], list_ids: &[usize]) {
+ if list_ids.is_empty() {
+ self.sq = ScalarQuantizer::new(self.d);
+ self.list_sqs = vec![self.sq.clone(); self.nlist];
+ return;
}
- (list_ids, residuals)
- }
-
- fn train_list_sqs(&mut self, list_ids: &[usize], residuals: &[f32]) {
- let mut list_residuals = vec![Vec::new(); self.nlist];
- for (i, &list_id) in list_ids.iter().enumerate() {
- let residual = &residuals[i * self.d..(i + 1) * self.d];
- list_residuals[list_id].extend_from_slice(residual);
+ let mut list_rows = vec![Vec::new(); self.nlist];
+ for (row, &list_id) in list_ids.iter().enumerate() {
+ list_rows[list_id].push(row);
}
- self.list_sqs = vec![self.sq.clone(); self.nlist];
- for (list_id, values) in list_residuals.iter().enumerate() {
- if !values.is_empty() {
- let mut sq = ScalarQuantizer::new(self.d);
- sq.train(values, values.len() / self.d);
- self.list_sqs[list_id] = sq;
+ let trained = list_rows
+ .par_iter()
+ .enumerate()
+ .map(|(list_id, rows)| {
+ (!rows.is_empty()).then(|| {
+ ScalarQuantizer::train_residual_rows(data, rows,
self.list_centroid(list_id))
+ })
+ })
+ .collect::<Vec<_>>();
+ let mut mins = vec![f32::INFINITY; self.d];
+ let mut maxs = vec![f32::NEG_INFINITY; self.d];
+ for sq in trained.iter().flatten() {
+ for dim in 0..self.d {
+ mins[dim] = mins[dim].min(sq.mins[dim]);
+ maxs[dim] = maxs[dim].max(sq.maxs[dim]);
}
}
- }
-
- fn write_residual(&self, vector: &[f32], list_id: usize, out: &mut [f32]) {
- fvec_madd(vector, self.list_centroid(list_id), -1.0, out);
+ self.sq = ScalarQuantizer::with_dimension_bounds(self.d, mins, maxs);
+ // A training sample may contain only a handful of rows in a partition.
+ // Its extrema severely clip unseen residuals (including constant
sample
+ // dimensions). Pool the observed residual bounds across partitions;
+ // retain per-list metadata so existing v1 files keep their own bounds.
+ self.list_sqs = vec![self.sq.clone(); self.nlist];
}
pub(crate) fn list_centroid(&self, list_id: usize) -> &[f32] {
@@ -312,23 +312,46 @@ fn append_encoded_rows(
output_codes: &mut Vec<u8>,
) {
output_ids.reserve(rows.len());
- output_codes.reserve(rows.len().saturating_mul(d));
- let mut residual = vec![0.0f32; d];
- let mut code = vec![0u8; d];
- for &row in rows {
- let vector = &data[row * d..(row + 1) * d];
- fvec_madd(vector, centroid, -1.0, &mut residual);
- sq.encode(&residual, &mut code);
- output_ids.push(input_ids[row]);
- output_codes.extend_from_slice(&code);
+ if rows.is_empty() {
+ return;
}
+ let start = output_codes.len();
+ output_codes.resize(start + rows.len() * d, 0);
+ sq.encode_residual_rows(data, rows, centroid, &mut output_codes[start..]);
+ output_ids.extend(rows.iter().map(|&row| input_ids[row]));
}
#[cfg(test)]
mod tests {
use super::*;
+ use crate::distance::fvec_madd;
use std::collections::HashSet;
+ #[test]
+ fn sparse_partition_bounds_do_not_collapse_unseen_residuals() {
+ let mut index = IVFSQIndex::new(2, 3, MetricType::L2);
+ index.set_quantizer_centroids(vec![0.0, 0.0, 10.0, 10.0, 20.0, 20.0]);
+ index.train_list_sqs(&[-2.0, -2.0, 10.0, 10.0, 12.0, 12.0], &[0, 1,
1]);
+ // Partition zero saw only one residual and partition two was empty.
+ // Neither should freeze future vectors at a sample's constant value.
+ index.add(&[0.0, 0.0, 20.0, 20.0], &[42, 43], 2);
+ let mut distances = [0.0; 2];
+ let mut labels = [0; 2];
+ index.search(
+ &[0.0, 0.0, 20.0, 20.0],
+ 2,
+ 1,
+ 3,
+ &mut distances,
+ &mut labels,
+ );
+ assert_eq!(labels, [42, 43]);
+ assert!(
+ distances.iter().all(|&distance| distance < 0.001),
+ "{distances:?}"
+ );
+ }
+
#[test]
fn ivfsq_full_scan_recalls_added_vector() {
let d = 4;
diff --git a/core/src/ivfsq_io.rs b/core/src/ivfsq_io.rs
index 6fb7c5b..5daf168 100644
--- a/core/src/ivfsq_io.rs
+++ b/core/src/ivfsq_io.rs
@@ -30,11 +30,14 @@ use crate::io::{ReadRequest, SeekRead, SeekWrite};
use crate::ivfpq::RowIdFilter;
use crate::ivfsq::IVFSQIndex;
use crate::kmeans;
+use crate::read_options::VectorIndexReaderOptions;
use crate::sq::ScalarQuantizer;
use crate::topk::TopKHeap;
use rayon::prelude::*;
+use std::collections::VecDeque;
use std::io;
use std::mem::size_of;
+use std::sync::Arc;
pub const IVF_SQ_MAGIC: u32 = 0x49565351; // "IVSQ"
pub const IVF_SQ_VERSION: u32 = 1;
@@ -58,6 +61,7 @@ pub fn write_ivfsq_index(index: &IVFSQIndex, out: &mut dyn
SeekWrite) -> io::Res
})
})?;
let sorted_lists = (0..index.nlist)
+ .into_par_iter()
.map(|list_id| build_sorted_sq_list_metadata(index, list_id))
.collect::<io::Result<Vec<_>>>()?;
@@ -121,20 +125,42 @@ pub fn write_ivfsq_index(index: &IVFSQIndex, out: &mut
dyn SeekWrite) -> io::Res
write_i32_le(out, list_counts[list_id])?;
write_i32_le(out, list_id_bytes_lens[list_id])?;
}
- for (list_id, list) in sorted_lists.iter().enumerate() {
- if list.order.is_empty() {
- continue;
+ // Bound transposition scratch independently of the total index size. An
+ // oversized individual list still uses at most one list's code buffer.
+ const TRANSPOSE_BATCH_BYTES: usize = 16 * 1024 * 1024;
+ let mut start = 0;
+ while start < index.nlist {
+ let mut end = start;
+ let mut bytes = 0;
+ while end < index.nlist {
+ let next = index.codes[end].len();
+ if end > start && next >
TRANSPOSE_BATCH_BYTES.saturating_sub(bytes) {
+ break;
+ }
+ bytes += next;
+ end += 1;
}
- let codes = block_sorted_sq_codes(
- &index.codes[list_id],
- &list.order,
- index.d,
- IVF_SQ_SCAN_BLOCK_SIZE,
- );
- out.write_all(&codes)?;
- write_i64_le(out, list.base_id)?;
- write_i32_le(out, usize_to_i32(list.id_bytes.len(), "delta ID
section")?)?;
- out.write_all(&list.id_bytes)?;
+ let blocked = (start..end)
+ .into_par_iter()
+ .map(|list_id| {
+ block_sorted_sq_codes(
+ &index.codes[list_id],
+ &sorted_lists[list_id].order,
+ index.d,
+ IVF_SQ_SCAN_BLOCK_SIZE,
+ )
+ })
+ .collect::<Vec<_>>();
+ for (list, codes) in sorted_lists[start..end].iter().zip(blocked) {
+ if list.order.is_empty() {
+ continue;
+ }
+ out.write_all(&codes)?;
+ write_i64_le(out, list.base_id)?;
+ write_i32_le(out, usize_to_i32(list.id_bytes.len(), "delta ID
section")?)?;
+ out.write_all(&list.id_bytes)?;
+ }
+ start = end;
}
Ok(())
}
@@ -152,18 +178,26 @@ pub struct IVFSQIndexReader<R: SeekRead> {
pub list_counts: Vec<i32>,
pub list_id_bytes_lens: Vec<i32>,
loaded: bool,
+ list_cache: Option<SqListCache>,
}
impl<R: SeekRead> IVFSQIndexReader<R> {
- pub fn open(mut reader: R) -> io::Result<Self> {
+ pub fn open(reader: R) -> io::Result<Self> {
+ Self::open_with_options(reader, VectorIndexReaderOptions::new(0))
+ }
+
+ /// Open with a bounded cache of decoded partitions. `open` retains the
+ /// uncached positional-I/O behavior for callers that manage their own
cache.
+ pub fn open_with_options(mut reader: R, options: VectorIndexReaderOptions)
-> io::Result<Self> {
let mut header = [0u8; IVF_SQ_HEADER_SIZE];
reader.pread(&mut [ReadRequest::new(0, &mut header)])?;
- Self::open_with_header(reader, header)
+ Self::open_with_header_and_options(reader, header, options)
}
- pub(crate) fn open_with_header(
+ pub(crate) fn open_with_header_and_options(
mut reader: R,
header: [u8; IVF_SQ_HEADER_SIZE],
+ options: VectorIndexReaderOptions,
) -> io::Result<Self> {
let read_u32 =
|offset: usize| u32::from_le_bytes(header[offset..offset +
4].try_into().unwrap());
@@ -339,6 +373,19 @@ impl<R: SeekRead> IVFSQIndexReader<R> {
));
}
+ let resident = size_of::<Self>()
+ + quantizer_centroids.capacity() * size_of::<f32>()
+ + list_offsets.capacity() * size_of::<i64>()
+ + list_counts.capacity() * size_of::<i32>()
+ + list_id_bytes_lens.capacity() * size_of::<i32>()
+ + list_sqs.capacity() * size_of::<ScalarQuantizer>()
+ + std::iter::once(&sq)
+ .chain(&list_sqs)
+ .map(|sq| (sq.mins.capacity() + sq.maxs.capacity()) *
size_of::<f32>())
+ .sum::<usize>();
+ let list_cache =
+ SqListCache::new(nlist,
options.memory_budget_bytes.saturating_sub(resident));
+
Ok(Self {
reader,
d,
@@ -352,6 +399,7 @@ impl<R: SeekRead> IVFSQIndexReader<R> {
list_counts,
list_id_bytes_lens,
loaded: true,
+ list_cache,
})
}
@@ -429,6 +477,56 @@ impl<R: SeekRead> IVFSQIndexReader<R> {
.collect()
}
+ fn read_scan_lists(&mut self, list_ids: &[usize]) ->
io::Result<Vec<Arc<SqListData>>> {
+ if self.list_cache.is_none() {
+ return self
+ .read_inverted_lists(list_ids)
+ .map(|lists| lists.into_iter().map(Arc::new).collect());
+ }
+ let mut results = vec![None; list_ids.len()];
+ let mut misses = Vec::new();
+ for (position, &list_id) in list_ids.iter().enumerate() {
+ if list_id >= self.nlist {
+ return Err(io::Error::new(
+ io::ErrorKind::InvalidInput,
+ "IVF-SQ list ID out of range",
+ ));
+ }
+ let cache = self.list_cache.as_mut().unwrap();
+ if let Some(entry) = &cache.entries[list_id] {
+ if entry.offset == self.list_offsets[list_id]
+ && entry.count == self.list_counts[list_id]
+ && entry.id_bytes_len == self.list_id_bytes_lens[list_id]
+ && entry.d == self.d
+ {
+ results[position] = Some(Arc::clone(&entry.list));
+ continue;
+ }
+ // Public reader metadata may have been edited by a low-level
+ // caller. Never serve a payload for a different range or
shape.
+ cache.remove(list_id);
+ cache.order.retain(|&id| id != list_id);
+ }
+ misses.push((position, list_id));
+ }
+ if !misses.is_empty() {
+ let missing_ids = misses.iter().map(|&(_, id)|
id).collect::<Vec<_>>();
+ let loaded = self.read_inverted_lists(&missing_ids)?;
+ for ((position, list_id), list) in misses.into_iter().zip(loaded) {
+ let list = Arc::new(list);
+ self.list_cache.as_mut().unwrap().insert(CachedSqList {
+ offset: self.list_offsets[list_id],
+ count: self.list_counts[list_id],
+ id_bytes_len: self.list_id_bytes_lens[list_id],
+ d: self.d,
+ list: Arc::clone(&list),
+ });
+ results[position] = Some(list);
+ }
+ }
+ Ok(results.into_iter().map(Option::unwrap).collect())
+ }
+
fn batch_read_end(&self, list_ids: &[usize]) -> io::Result<usize> {
let payload_lengths = list_ids
.iter()
@@ -563,16 +661,28 @@ impl<R: SeekRead> IVFSQIndexReader<R> {
}
let count =
self.batch_read_end(&probe_indices[batch_start..])?.max(1);
let batch_end = (batch_start + count).min(probe_indices.len());
- let lists =
self.read_inverted_lists(&probe_indices[batch_start..batch_end])?;
+ let lists =
self.read_scan_lists(&probe_indices[batch_start..batch_end])?;
let centroids = &self.quantizer_centroids;
let list_sqs = &self.list_sqs;
let global_sq = &self.sq;
let candidate_count = lists.iter().map(|list|
list.ids.len()).sum::<usize>();
if candidate_count >= PARALLEL_SQ_SCAN_MIN_CANDIDATES {
- let per_list_results = lists
+ let first = &lists[0];
+ scan_sq_list(
+ &query,
+ first,
+ ¢roids[first.list_id * d..(first.list_id + 1) * d],
+ list_sqs.get(first.list_id).unwrap_or(global_sq),
+ metric,
+ filter,
+ &mut SqScanScratch::default(),
+ &mut heap,
+ );
+ let cutoff = heap.distance_limit();
+ let per_list_results = lists[1..]
.par_iter()
.map_init(SqScanScratch::default, |scratch, list| {
- let mut local_heap = TopKHeap::new(k);
+ let mut local_heap = TopKHeap::with_max_distance(k,
cutoff);
let list_id = list.list_id;
scan_sq_list(
&query,
@@ -666,6 +776,9 @@ pub(crate) fn search_batch_ivfsq_reader_filter_range<R:
SeekRead>(
));
}
validate_batch_seed(seed_ids, seed_distances, nq, k)?;
+ if nq == 1 && probe_start == 0 && seed_ids.is_empty() {
+ return reader.search_with_filter(queries, k, probe_end, filter);
+ }
let processed = preprocess_vectors(queries, nq, reader.d, reader.metric);
let (all_probe_indices, _) = kmeans::find_topk_batch(
&processed,
@@ -731,41 +844,36 @@ pub(crate) fn search_batch_ivfsq_reader_filter_range<R:
SeekRead>(
}
let count =
reader.batch_read_end(&unique_lists[batch_start..])?.max(1);
let batch_end = (batch_start + count).min(unique_lists.len());
- let loaded_lists =
reader.read_inverted_lists(&unique_lists[batch_start..batch_end])?;
+ let loaded_lists =
reader.read_scan_lists(&unique_lists[batch_start..batch_end])?;
let centroids = &reader.quantizer_centroids;
let list_sqs = &reader.list_sqs;
let global_sq = &reader.sq;
- let per_list_results = loaded_lists
- .par_iter()
- .map_init(SqScanScratch::default, |scratch, list| {
- let list_id = list.list_id;
- list_to_queries[list_id]
- .iter()
- .map(|&query_index| {
- let query = &processed[query_index * d..(query_index +
1) * d];
- let mut heap = TopKHeap::new(k);
+ let mut list_positions = vec![None; reader.nlist];
+ for (position, list) in loaded_lists.iter().enumerate() {
+ list_positions[list.list_id] = Some(position);
+ }
+ // Keep a query's heap across partitions. Besides avoiding nprobe
+ // allocations and merges, this carries the current cutoff into later
scans.
+ heaps.par_iter_mut().enumerate().for_each_init(
+ SqScanScratch::default,
+ |scratch, (query_index, heap)| {
+ let query = &processed[query_index * d..(query_index + 1) * d];
+ for &list_id in
all_probe_indices[query_index].iter().skip(probe_start) {
+ if let Some(position) = list_positions[list_id] {
scan_sq_list(
query,
- list,
+ &loaded_lists[position],
¢roids[list_id * d..(list_id + 1) * d],
list_sqs.get(list_id).unwrap_or(global_sq),
metric,
filter,
scratch,
- &mut heap,
+ heap,
);
- (query_index, heap.into_sorted())
- })
- .collect::<Vec<_>>()
- })
- .collect::<Vec<_>>();
- for list_results in per_list_results {
- for (query_index, results) in list_results {
- for (distance, row_id) in results {
- heaps[query_index].push(distance, row_id);
+ }
}
- }
- }
+ },
+ );
batch_start = batch_end;
}
@@ -868,6 +976,75 @@ pub struct SqListData {
pub codes: Vec<u8>,
}
+struct CachedSqList {
+ offset: i64,
+ count: i32,
+ id_bytes_len: i32,
+ d: usize,
+ list: Arc<SqListData>,
+}
+
+impl CachedSqList {
+ fn retained_bytes(&self) -> usize {
+ size_of::<SqListData>()
+ + 2 * size_of::<usize>()
+ + self.list.ids.capacity() * size_of::<i64>()
+ + self.list.codes.capacity()
+ }
+}
+
+/// FIFO eviction keeps cache bookkeeping O(1) without per-hit allocations.
+/// Both the slot table and queue are reserved and charged to the budget up
front.
+struct SqListCache {
+ entries: Vec<Option<CachedSqList>>,
+ order: VecDeque<usize>,
+ capacity_bytes: usize,
+ retained_bytes: usize,
+}
+
+impl SqListCache {
+ fn new(nlist: usize, budget: usize) -> Option<Self> {
+ let fixed = nlist.checked_mul(size_of::<Option<CachedSqList>>() +
size_of::<usize>())?;
+ if budget <= fixed {
+ return None;
+ }
+ let entries = (0..nlist).map(|_| None).collect::<Vec<_>>();
+ let order = VecDeque::<usize>::with_capacity(nlist);
+ let fixed = entries.capacity() * size_of::<Option<CachedSqList>>()
+ + order.capacity() * size_of::<usize>();
+ if budget <= fixed {
+ return None;
+ }
+ Some(Self {
+ entries,
+ order,
+ capacity_bytes: budget.saturating_sub(fixed),
+ retained_bytes: 0,
+ })
+ }
+
+ fn remove(&mut self, list_id: usize) {
+ if let Some(entry) = self.entries[list_id].take() {
+ self.retained_bytes -= entry.retained_bytes();
+ }
+ }
+
+ fn insert(&mut self, entry: CachedSqList) {
+ let bytes = entry.retained_bytes();
+ let list_id = entry.list.list_id;
+ if bytes > self.capacity_bytes || self.entries[list_id].is_some() {
+ return;
+ }
+ while bytes > self.capacity_bytes - self.retained_bytes {
+ let oldest = self.order.pop_front().expect("nonempty cache over
budget");
+ self.remove(oldest);
+ }
+ self.retained_bytes += bytes;
+ self.order.push_back(list_id);
+ self.entries[list_id] = Some(entry);
+ }
+}
+
#[derive(Clone, Copy)]
struct BatchedListRead {
input_index: usize,
@@ -929,6 +1106,7 @@ fn scan_sq_rows(
centroid,
metric,
IVF_SQ_SCAN_BLOCK_SIZE,
+ heap.distance_limit(),
&mut scratch.parameters,
&mut scratch.distances,
);
@@ -1083,13 +1261,16 @@ fn block_sorted_sq_codes(
block_size: usize,
) -> Vec<u8> {
debug_assert_eq!(row_major.len(), order.len() * d);
- let mut blocked = Vec::with_capacity(row_major.len());
+ let mut blocked = vec![0; row_major.len()];
for block_start in (0..order.len()).step_by(block_size) {
let block_len = (order.len() - block_start).min(block_size);
- for dimension in 0..d {
- for lane in 0..block_len {
- let source_row = order[block_start + lane];
- blocked.push(row_major[source_row * d + dimension]);
+ let block = &mut blocked[block_start * d..(block_start + block_len) *
d];
+ for (dimension, column) in
block.chunks_exact_mut(block_len).enumerate() {
+ for (dst, &source_row) in column
+ .iter_mut()
+ .zip(&order[block_start..block_start + block_len])
+ {
+ *dst = row_major[source_row * d + dimension];
}
}
}
@@ -1123,6 +1304,121 @@ mod tests {
use std::sync::atomic::{AtomicU64, AtomicUsize, Ordering};
use std::sync::Arc;
+ #[test]
+ fn ivfsq_partition_cache_reuses_payloads_and_keeps_filters_query_local() {
+ let (index, data, _) = build_index(37, 8, 4_097);
+ let bytes = serialized_index(&index);
+ let calls = Arc::new(AtomicUsize::new(0));
+ let source = CountingReader {
+ inner: Cursor::new(bytes.clone()),
+ calls: Arc::clone(&calls),
+ };
+ let mut cached = IVFSQIndexReader::open_with_options(
+ source,
+ VectorIndexReaderOptions::new(4 * 1024 * 1024),
+ )
+ .unwrap();
+ let mut uncached = IVFSQIndexReader::open(Cursor::new(bytes)).unwrap();
+ let query = &data[127 * 37..128 * 37];
+ let expected = uncached.search(query, 10, 8).unwrap();
+ assert_eq!(cached.search(query, 10, 8).unwrap(), expected);
+ calls.store(0, Ordering::Relaxed);
+ let first = cached.read_scan_lists(&[0, 1]).unwrap();
+ let again = cached.read_scan_lists(&[1, 0]).unwrap();
+ assert!(Arc::ptr_eq(&first[0], &again[1]));
+ assert!(Arc::ptr_eq(&first[1], &again[0]));
+ let filter = std::collections::HashSet::from([expected.0[3]]);
+ assert_eq!(
+ cached
+ .search_with_filter(query, 10, 8, Some(&filter))
+ .unwrap(),
+ uncached
+ .search_with_filter(query, 10, 8, Some(&filter))
+ .unwrap()
+ );
+ assert_eq!(cached.search(query, 10, 8).unwrap(), expected);
+ assert_eq!(
+ calls.load(Ordering::Relaxed),
+ 0,
+ "warm scans must not reenter positional I/O"
+ );
+ }
+
+ #[test]
+ fn
ivfsq_partition_cache_is_bounded_and_evicts_without_retaining_duplicate_keys() {
+ fn entry(list_id: usize, bytes: usize) -> CachedSqList {
+ CachedSqList {
+ offset: list_id as i64,
+ count: 1,
+ id_bytes_len: 1,
+ d: bytes,
+ list: Arc::new(SqListData {
+ list_id,
+ ids: vec![list_id as i64],
+ codes: vec![0; bytes],
+ }),
+ }
+ }
+ let fixed = 4 * (size_of::<Option<CachedSqList>>() +
size_of::<usize>());
+ let size = entry(0, 64).retained_bytes();
+ let mut cache = SqListCache::new(4, fixed + size * 2).unwrap();
+ cache.insert(entry(0, 64));
+ cache.insert(entry(1, 64));
+ cache.insert(entry(1, 64));
+ assert_eq!(cache.order.iter().copied().collect::<Vec<_>>(), [0, 1]);
+ cache.insert(entry(2, 64));
+ assert!(cache.entries[0].is_none());
+ assert!(cache.entries[1].is_some());
+ assert!(cache.entries[2].is_some());
+ assert_eq!(cache.retained_bytes, size * 2);
+ cache.insert(entry(3, size * 3));
+ assert!(
+ cache.entries[3].is_none(),
+ "an oversized partition must bypass the cache"
+ );
+ assert_eq!(cache.retained_bytes, size * 2);
+ assert!(SqListCache::new(4, 0).is_none());
+ assert!(SqListCache::new(4, fixed).is_none());
+ }
+
+ #[test]
+ fn
ivfsq_cache_misses_retry_after_io_failure_and_zero_budget_stays_uncached() {
+ let (index, _, _) = build_index(5, 2, 65);
+ let bytes = serialized_index(&index);
+ let mut cached = IVFSQIndexReader::open_with_options(
+ Cursor::new(bytes.clone()),
+ VectorIndexReaderOptions::new(1024 * 1024),
+ )
+ .unwrap();
+ cached.read_scan_lists(&[0]).unwrap();
+ let offset = cached.list_offsets[1];
+ cached.list_offsets[1] = bytes.len() as i64 + 1;
+ assert!(cached.read_scan_lists(&[1]).is_err());
+ assert!(cached.list_cache.as_ref().unwrap().entries[1].is_none());
+ cached.list_offsets[1] = offset;
+ let expected = cached.read_scan_lists(&[1]).unwrap();
+ // Even a warmed entry must not hide an edited offset.
+ cached.list_offsets[1] = bytes.len() as i64 + 1;
+ assert!(cached.read_scan_lists(&[1]).is_err());
+ cached.list_offsets[1] = offset;
+ assert_eq!(
+ cached.read_scan_lists(&[1]).unwrap()[0].ids,
+ expected[0].ids
+ );
+ let calls = Arc::new(AtomicUsize::new(0));
+ let source = CountingReader {
+ inner: Cursor::new(bytes),
+ calls: Arc::clone(&calls),
+ };
+ let mut uncached =
+ IVFSQIndexReader::open_with_options(source,
VectorIndexReaderOptions::new(0)).unwrap();
+ assert!(uncached.list_cache.is_none());
+ calls.store(0, Ordering::Relaxed);
+ uncached.read_scan_lists(&[0, 1]).unwrap();
+ uncached.read_scan_lists(&[0, 1]).unwrap();
+ assert_eq!(calls.load(Ordering::Relaxed), 2);
+ }
+
fn build_index(d: usize, nlist: usize, n: usize) -> (IVFSQIndex, Vec<f32>,
Vec<i64>) {
let data = (0..n)
.flat_map(|i| {
@@ -1189,6 +1485,48 @@ mod tests {
assert_eq!(batch.1, [first.1, second.1].concat());
}
+ #[test]
+ fn ivfsq_single_query_batch_and_seeded_probe_ranges_match_full_search() {
+ let d = 37;
+ let nlist = 8;
+ let (index, data, _) = build_index(d, nlist, 8_193);
+ let bytes = serialized_index(&index);
+ let mut reader = IVFSQIndexReader::open(Cursor::new(bytes)).unwrap();
+ let query = &data[127 * d..128 * d];
+ let expected = reader.search(query, 10, nlist).unwrap();
+ let one = search_batch_ivfsq_reader(&mut reader, query, 1, 10,
nlist).unwrap();
+ assert_eq!(one, expected);
+ let first =
+ search_batch_ivfsq_reader_filter_range(&mut reader, query, 1, 10,
0, 3, &[], &[], None)
+ .unwrap();
+ let refined = search_batch_ivfsq_reader_filter_range(
+ &mut reader,
+ query,
+ 1,
+ 10,
+ 3,
+ nlist,
+ &first.0,
+ &first.1,
+ None,
+ )
+ .unwrap();
+ // Repeated vectors can tie; verify distances and the returned IDs'
scores.
+ assert_eq!(refined.1, expected.1);
+ for (&id, &distance) in refined.0.iter().zip(&refined.1) {
+ let (ids, distances) = reader
+ .search_with_filter(
+ query,
+ 1,
+ nlist,
+ Some(&std::collections::HashSet::from([id])),
+ )
+ .unwrap();
+ assert_eq!(ids, [id]);
+ assert_eq!(distances, [distance]);
+ }
+ }
+
#[test]
fn ivfsq_large_batch_scans_queries_in_parallel_without_duplicate_reads() {
let d = 16;
@@ -1292,20 +1630,64 @@ mod tests {
}
#[test]
- fn ivfsq_open_coalesces_resident_metadata() {
- let (index, _, _) = build_index(8, 32, 512);
- let calls = Arc::new(AtomicUsize::new(0));
- let source = CountingReader {
- inner: Cursor::new(serialized_index(&index)),
- calls: Arc::clone(&calls),
- };
- let mut reader = IVFSQIndexReader::open(source).unwrap();
- reader.optimize_for_search().unwrap();
- assert_eq!(
- calls.load(Ordering::SeqCst),
- 2,
- "direct IVF-SQ open should use one header read and one
resident-metadata read"
- );
+ fn ivfsq_reader_entry_points_preserve_cache_policy_and_header_reads() {
+ use crate::index::VectorIndexReader;
+
+ let (index, data, _) = build_index(8, 8, 512);
+ let bytes = serialized_index(&index);
+ let query = &data[..8];
+ let expected = IVFSQIndexReader::open(Cursor::new(bytes.clone()))
+ .unwrap()
+ .search(query, 5, 8)
+ .unwrap();
+ for (unified, budget, cached) in [
+ (false, None, false),
+ (false, Some(0), false),
+ (false, Some(1), false),
+ (false, Some(1024 * 1024), true),
+ (true, None, true),
+ (true, Some(0), false),
+ (true, Some(1), false),
+ (true, Some(1024 * 1024), true),
+ ] {
+ let calls = Arc::new(AtomicUsize::new(0));
+ let source = CountingReader {
+ inner: Cursor::new(bytes.clone()),
+ calls: Arc::clone(&calls),
+ };
+ let options = budget.map(VectorIndexReaderOptions::new);
+ let mut reader = if unified {
+ let reader = match options {
+ Some(options) =>
VectorIndexReader::open_with_options(source, options),
+ None => VectorIndexReader::open(source),
+ }
+ .unwrap();
+ let VectorIndexReader::IvfSq(reader) = reader else {
+ panic!("SQ file must dispatch to the SQ reader");
+ };
+ reader
+ } else {
+ match options {
+ Some(options) =>
IVFSQIndexReader::open_with_options(source, options),
+ None => IVFSQIndexReader::open(source),
+ }
+ .unwrap()
+ };
+ reader.optimize_for_search().unwrap();
+ assert_eq!(
+ calls.swap(0, Ordering::Relaxed),
+ 2,
+ "open should read the header and resident metadata exactly
once"
+ );
+ assert_eq!(reader.search(query, 5, 8).unwrap(), expected);
+ assert_eq!(calls.swap(0, Ordering::Relaxed), 1);
+ assert_eq!(reader.search(query, 5, 8).unwrap(), expected);
+ assert_eq!(
+ calls.load(Ordering::Relaxed),
+ usize::from(!cached),
+ "cache policy for unified={unified}, budget={budget:?}"
+ );
+ }
}
#[test]
diff --git a/core/src/sq.rs b/core/src/sq.rs
index 0785055..ffe58be 100644
--- a/core/src/sq.rs
+++ b/core/src/sq.rs
@@ -101,6 +101,54 @@ impl ScalarQuantizer {
self.encode_batch(vector, 1, code);
}
+ /// Gather and quantize a partition without materializing its residual
matrix.
+ pub(crate) fn encode_residual_rows(
+ &self,
+ data: &[f32],
+ rows: &[usize],
+ offset: &[f32],
+ codes: &mut [u8],
+ ) {
+ assert_eq!(codes.len(), rows.len() * self.d);
+ assert_eq!(offset.len(), self.d);
+ assert_eq!(self.mins.len(), self.d);
+ assert_eq!(self.maxs.len(), self.d);
+ let scales = self
+ .mins
+ .iter()
+ .zip(&self.maxs)
+ .map(
+ |(&min, &max)| {
+ if min < max {
+ 255.0 / (max - min)
+ } else {
+ 0.0
+ }
+ },
+ )
+ .collect::<Vec<_>>();
+ for (&row, code) in rows.iter().zip(codes.chunks_exact_mut(self.d)) {
+ let vector = &data[row * self.d..(row + 1) * self.d];
+ encode_residual(vector, offset, &self.mins, &self.maxs, &scales,
code);
+ }
+ }
+
+ pub(crate) fn train_residual_rows(data: &[f32], rows: &[usize], offset:
&[f32]) -> Self {
+ let d = offset.len();
+ let mut mins = vec![f32::INFINITY; d];
+ let mut maxs = vec![f32::NEG_INFINITY; d];
+ // Subtraction is monotone: subtracting the centroid from the extrema
+ // gives exactly the extrema of the rounded residuals, with O(d)
scratch.
+ for &row in rows {
+ update_bounds_batch(&data[row * d..(row + 1) * d], 1, d, &mut
mins, &mut maxs);
+ }
+ for dim in 0..d {
+ mins[dim] -= offset[dim];
+ maxs[dim] -= offset[dim];
+ }
+ Self::with_dimension_bounds(d, mins, maxs)
+ }
+
pub fn decode_batch(&self, codes: &[u8], n: usize, vectors: &mut [f32]) {
let len = n * self.d;
assert!(codes.len() >= len);
@@ -209,6 +257,7 @@ impl ScalarQuantizer {
offset: &[f32],
metric: MetricType,
block_size: usize,
+ cutoff: f32,
parameters: &mut Vec<f32>,
distances: &mut Vec<f32>,
) {
@@ -226,7 +275,9 @@ impl ScalarQuantizer {
primary[dimension] = query[dimension] - offset[dimension] -
self.mins[dimension];
scales[dimension] = (self.maxs[dimension] -
self.mins[dimension]) * (1.0 / 255.0);
}
- blocked_sq_l2(primary, scales, codes, count, self.d, block_size,
distances);
+ blocked_sq_l2(
+ primary, scales, codes, count, self.d, block_size, cutoff,
distances,
+ );
return;
}
@@ -426,21 +477,24 @@ fn blocked_sq_l2(
count: usize,
d: usize,
block_size: usize,
+ cutoff: f32,
distances: &mut [f32],
) {
#[cfg(target_arch = "x86_64")]
if block_size == 32 && is_x86_feature_detected!("avx2") {
unsafe {
- return blocked_sq_l2_avx2(biases, scales, codes, count, d,
distances);
+ return blocked_sq_l2_avx2(biases, scales, codes, count, d, cutoff,
distances);
}
}
#[cfg(target_arch = "aarch64")]
if block_size == 32 {
unsafe {
- return blocked_sq_l2_neon(biases, scales, codes, count, d,
distances);
+ return blocked_sq_l2_neon(biases, scales, codes, count, d, cutoff,
distances);
}
}
- blocked_sq_l2_scalar(biases, scales, codes, count, d, block_size,
distances);
+ blocked_sq_l2_scalar(
+ biases, scales, codes, count, d, block_size, cutoff, distances,
+ );
}
fn blocked_sq_l2_scalar(
@@ -450,6 +504,7 @@ fn blocked_sq_l2_scalar(
count: usize,
d: usize,
block_size: usize,
+ cutoff: f32,
distances: &mut [f32],
) {
let mut code_offset = 0usize;
@@ -457,14 +512,20 @@ fn blocked_sq_l2_scalar(
let block_len = (count - block_start).min(block_size);
let block_distances = &mut distances[block_start..block_start +
block_len];
block_distances.fill(0.0);
- for dimension in 0..d {
- let column = &codes
- [code_offset + dimension * block_len..code_offset + (dimension
+ 1) * block_len];
- let bias = biases[dimension];
- let scale = scales[dimension];
- for lane in 0..block_len {
- let difference = bias - column[lane] as f32 * scale;
- block_distances[lane] += difference * difference;
+ let checkpoint = (d / 2).max(32).min(d);
+ for (start, end) in [(0, checkpoint), (checkpoint, d)] {
+ if start > 0 && block_distances.iter().all(|&distance| distance >=
cutoff) {
+ break;
+ }
+ for dimension in start..end {
+ let column = &codes[code_offset + dimension * block_len
+ ..code_offset + (dimension + 1) * block_len];
+ let bias = biases[dimension];
+ let scale = scales[dimension];
+ for lane in 0..block_len {
+ let difference = bias - column[lane] as f32 * scale;
+ block_distances[lane] += difference * difference;
+ }
}
}
code_offset += block_len * d;
@@ -479,6 +540,7 @@ unsafe fn blocked_sq_l2_neon(
codes: &[u8],
count: usize,
d: usize,
+ cutoff: f32,
distances: &mut [f32],
) {
use std::arch::aarch64::*;
@@ -487,23 +549,29 @@ unsafe fn blocked_sq_l2_neon(
for block_start in (0..full_count).step_by(32) {
let code_base = block_start * d;
let mut accumulators = [vdupq_n_f32(0.0); 8];
- for dimension in 0..d {
- let column = codes.as_ptr().add(code_base + dimension * 32);
- let bias = vdupq_n_f32(biases[dimension]);
- let scale = vdupq_n_f32(scales[dimension]);
- for chunk in 0..4 {
- let code_u16 = vmovl_u8(vld1_u8(column.add(chunk * 8)));
- let code_low =
vcvtq_f32_u32(vmovl_u16(vget_low_u16(code_u16)));
- let code_high =
vcvtq_f32_u32(vmovl_u16(vget_high_u16(code_u16)));
- let difference_low = vfmsq_f32(bias, code_low, scale);
- let difference_high = vfmsq_f32(bias, code_high, scale);
- accumulators[chunk * 2] =
- vfmaq_f32(accumulators[chunk * 2], difference_low,
difference_low);
- accumulators[chunk * 2 + 1] = vfmaq_f32(
- accumulators[chunk * 2 + 1],
- difference_high,
- difference_high,
- );
+ let checkpoint = (d / 2).max(32).min(d);
+ for (start, end) in [(0, checkpoint), (checkpoint, d)] {
+ if start > 0 && accumulators.iter().all(|&acc| vminvq_f32(acc) >=
cutoff) {
+ break;
+ }
+ for dimension in start..end {
+ let column = codes.as_ptr().add(code_base + dimension * 32);
+ let bias = vdupq_n_f32(biases[dimension]);
+ let scale = vdupq_n_f32(scales[dimension]);
+ for chunk in 0..4 {
+ let code_u16 = vmovl_u8(vld1_u8(column.add(chunk * 8)));
+ let code_low =
vcvtq_f32_u32(vmovl_u16(vget_low_u16(code_u16)));
+ let code_high =
vcvtq_f32_u32(vmovl_u16(vget_high_u16(code_u16)));
+ let difference_low = vfmsq_f32(bias, code_low, scale);
+ let difference_high = vfmsq_f32(bias, code_high, scale);
+ accumulators[chunk * 2] =
+ vfmaq_f32(accumulators[chunk * 2], difference_low,
difference_low);
+ accumulators[chunk * 2 + 1] = vfmaq_f32(
+ accumulators[chunk * 2 + 1],
+ difference_high,
+ difference_high,
+ );
+ }
}
}
for (chunk, accumulator) in accumulators.into_iter().enumerate() {
@@ -521,6 +589,7 @@ unsafe fn blocked_sq_l2_neon(
count - full_count,
d,
32,
+ cutoff,
&mut distances[full_count..],
);
}
@@ -534,6 +603,7 @@ unsafe fn blocked_sq_l2_avx2(
codes: &[u8],
count: usize,
d: usize,
+ cutoff: f32,
distances: &mut [f32],
) {
use std::arch::x86_64::*;
@@ -542,15 +612,27 @@ unsafe fn blocked_sq_l2_avx2(
for block_start in (0..full_count).step_by(32) {
let code_base = block_start * d;
let mut accumulators = [_mm256_setzero_ps(); 4];
- for dimension in 0..d {
- let column = codes.as_ptr().add(code_base + dimension * 32);
- let bias = _mm256_set1_ps(biases[dimension]);
- let scale = _mm256_set1_ps(scales[dimension]);
- for (chunk, accumulator) in accumulators.iter_mut().enumerate() {
- let bytes = _mm_loadl_epi64(column.add(chunk * 8).cast());
- let code = _mm256_cvtepi32_ps(_mm256_cvtepu8_epi32(bytes));
- let difference = _mm256_sub_ps(bias, _mm256_mul_ps(code,
scale));
- *accumulator = _mm256_add_ps(*accumulator,
_mm256_mul_ps(difference, difference));
+ let checkpoint = (d / 2).max(32).min(d);
+ for (start, end) in [(0, checkpoint), (checkpoint, d)] {
+ if start > 0
+ && accumulators.iter().all(|&acc| {
+ _mm256_movemask_ps(_mm256_cmp_ps::<_CMP_GE_OQ>(acc,
_mm256_set1_ps(cutoff)))
+ == 255
+ })
+ {
+ break;
+ }
+ for dimension in start..end {
+ let column = codes.as_ptr().add(code_base + dimension * 32);
+ let bias = _mm256_set1_ps(biases[dimension]);
+ let scale = _mm256_set1_ps(scales[dimension]);
+ for (chunk, accumulator) in
accumulators.iter_mut().enumerate() {
+ let bytes = _mm_loadl_epi64(column.add(chunk * 8).cast());
+ let code = _mm256_cvtepi32_ps(_mm256_cvtepu8_epi32(bytes));
+ let difference = _mm256_sub_ps(bias, _mm256_mul_ps(code,
scale));
+ *accumulator =
+ _mm256_add_ps(*accumulator, _mm256_mul_ps(difference,
difference));
+ }
}
}
for (chunk, accumulator) in accumulators.into_iter().enumerate() {
@@ -568,6 +650,7 @@ unsafe fn blocked_sq_l2_avx2(
count - full_count,
d,
32,
+ cutoff,
&mut distances[full_count..],
);
}
@@ -870,6 +953,131 @@ unsafe fn update_bounds_batch_neon(
}
}
+fn encode_residual(
+ vector: &[f32],
+ offset: &[f32],
+ mins: &[f32],
+ maxs: &[f32],
+ scales: &[f32],
+ codes: &mut [u8],
+) {
+ #[cfg(target_arch = "aarch64")]
+ let start = unsafe { encode_residual_neon(vector, offset, mins, scales,
codes) };
+ #[cfg(target_arch = "x86_64")]
+ let start = if is_x86_feature_detected!("avx2") {
+ unsafe { encode_residual_avx2(vector, offset, mins, scales, codes) }
+ } else {
+ 0
+ };
+ #[cfg(not(any(target_arch = "aarch64", target_arch = "x86_64")))]
+ let start = {
+ let _ = scales;
+ 0
+ };
+ for dim in start..codes.len() {
+ codes[dim] = encode_value(vector[dim] - offset[dim], mins[dim],
maxs[dim]);
+ }
+}
+
+#[cfg(target_arch = "aarch64")]
+#[target_feature(enable = "neon")]
+unsafe fn encode_residual_neon(
+ vector: &[f32],
+ offset: &[f32],
+ mins: &[f32],
+ scales: &[f32],
+ codes: &mut [u8],
+) -> usize {
+ use std::arch::aarch64::*;
+ let mut dim = 0;
+ while dim + 16 <= codes.len() {
+ let mut packed = [vdupq_n_u32(0); 4];
+ for (chunk, out) in packed.iter_mut().enumerate() {
+ let i = dim + chunk * 4;
+ let residual = vsubq_f32(
+ vld1q_f32(vector.as_ptr().add(i)),
+ vld1q_f32(offset.as_ptr().add(i)),
+ );
+ let value = vmulq_f32(
+ vsubq_f32(residual, vld1q_f32(mins.as_ptr().add(i))),
+ vld1q_f32(scales.as_ptr().add(i)),
+ );
+ *out = vcvtaq_u32_f32(vminq_f32(
+ vdupq_n_f32(255.0),
+ vmaxq_f32(vdupq_n_f32(0.0), value),
+ ));
+ }
+ let low = vcombine_u16(vmovn_u32(packed[0]), vmovn_u32(packed[1]));
+ let high = vcombine_u16(vmovn_u32(packed[2]), vmovn_u32(packed[3]));
+ vst1q_u8(
+ codes.as_mut_ptr().add(dim),
+ vcombine_u8(vmovn_u16(low), vmovn_u16(high)),
+ );
+ dim += 16;
+ }
+ // Keep the same four-dimension SIMD boundary as encode_batch.
+ while dim + 4 <= codes.len() {
+ let residual = vsubq_f32(
+ vld1q_f32(vector.as_ptr().add(dim)),
+ vld1q_f32(offset.as_ptr().add(dim)),
+ );
+ let value = vmulq_f32(
+ vsubq_f32(residual, vld1q_f32(mins.as_ptr().add(dim))),
+ vld1q_f32(scales.as_ptr().add(dim)),
+ );
+ let rounded = vcvtaq_u32_f32(vminq_f32(
+ vdupq_n_f32(255.0),
+ vmaxq_f32(vdupq_n_f32(0.0), value),
+ ));
+ let bytes = vmovn_u16(vcombine_u16(vmovn_u32(rounded), vdup_n_u16(0)));
+ codes[dim..dim + 4]
+
.copy_from_slice(&vget_lane_u32::<0>(vreinterpret_u32_u8(bytes)).to_le_bytes());
+ dim += 4;
+ }
+ dim
+}
+
+#[cfg(target_arch = "x86_64")]
+#[target_feature(enable = "avx2")]
+unsafe fn encode_residual_avx2(
+ vector: &[f32],
+ offset: &[f32],
+ mins: &[f32],
+ scales: &[f32],
+ codes: &mut [u8],
+) -> usize {
+ use std::arch::x86_64::*;
+ let mut dim = 0;
+ while dim + 8 <= codes.len() {
+ let residual = _mm256_sub_ps(
+ _mm256_loadu_ps(vector.as_ptr().add(dim)),
+ _mm256_loadu_ps(offset.as_ptr().add(dim)),
+ );
+ let value = _mm256_mul_ps(
+ _mm256_sub_ps(residual, _mm256_loadu_ps(mins.as_ptr().add(dim))),
+ _mm256_loadu_ps(scales.as_ptr().add(dim)),
+ );
+ let value = _mm256_min_ps(
+ _mm256_set1_ps(255.0),
+ _mm256_max_ps(_mm256_setzero_ps(), value),
+ );
+ let floor = _mm256_floor_ps(value);
+ let up = _mm256_cmp_ps::<_CMP_GE_OQ>(_mm256_sub_ps(value, floor),
_mm256_set1_ps(0.5));
+ let rounded =
+ _mm256_cvttps_epi32(_mm256_add_ps(floor, _mm256_and_ps(up,
_mm256_set1_ps(1.0))));
+ let words = _mm_packus_epi32(
+ _mm256_castsi256_si128(rounded),
+ _mm256_extracti128_si256::<1>(rounded),
+ );
+ _mm_storel_epi64(
+ codes.as_mut_ptr().add(dim).cast(),
+ _mm_packus_epi16(words, words),
+ );
+ dim += 8;
+ }
+ dim
+}
+
fn encode_batch_simd(
data: &[f32],
n: usize,
@@ -1286,6 +1494,129 @@ impl DistanceContext {
mod tests {
use super::*;
+ #[test]
+ fn residual_encoder_matches_separate_subtraction_and_encoding() {
+ for d in [1, 3, 4, 7, 8, 15, 16, 17, 31, 32, 37, 128] {
+ let mins = (0..d)
+ .map(|j| if j % 5 == 0 { 7.0 } else { -2.0 })
+ .collect::<Vec<_>>();
+ let maxs = (0..d)
+ .map(|j| if j % 5 == 0 { 7.0 } else { 253.0 })
+ .collect::<Vec<_>>();
+ let sq = ScalarQuantizer::with_dimension_bounds(d, mins, maxs);
+ let offset = (0..d).map(|j| j as f32 * 0.25 -
4.0).collect::<Vec<_>>();
+ // Includes clipping, exact half-way rounding, and constant
dimensions.
+ let levels = [-10.0, -2.0, -1.5, 0.5, 127.5, 252.5, 253.0, 260.0];
+ let data = (0..levels.len() * d)
+ .map(|i| levels[(i / d + i % d) % levels.len()] + offset[i %
d])
+ .collect::<Vec<_>>();
+ let rows = [7, 0, 3, 2, 3, 6, 1, 5, 4];
+ let mut actual = vec![99; rows.len() * d];
+ sq.encode_residual_rows(&data, &rows, &offset, &mut actual);
+ let mut expected = vec![0; actual.len()];
+ for (&row, code) in rows.iter().zip(expected.chunks_exact_mut(d)) {
+ let residual = (0..d)
+ .map(|j| data[row * d + j] - offset[j])
+ .collect::<Vec<_>>();
+ sq.encode(&residual, code);
+ }
+ assert_eq!(actual, expected, "dimension {d}");
+ }
+ }
+
+ #[test]
+ fn residual_extrema_match_materialized_residuals() {
+ let d = 37;
+ let data = (0..19 * d)
+ .map(|i| ((i * 17 % 131) as f32 - 65.0) * 0.031)
+ .collect::<Vec<_>>();
+ let offset = (0..d).map(|j| j as f32 * 0.17 - 1.0).collect::<Vec<_>>();
+ let rows = [18, 1, 3, 7, 0, 1];
+ let actual = ScalarQuantizer::train_residual_rows(&data, &rows,
&offset);
+ let residuals = rows
+ .iter()
+ .flat_map(|&row| {
+ (0..d)
+ .map(|j| data[row * d + j] - offset[j])
+ .collect::<Vec<_>>()
+ })
+ .collect::<Vec<_>>();
+ let mut expected = ScalarQuantizer::new(d);
+ expected.train(&residuals, rows.len());
+ assert_eq!(actual.mins, expected.mins);
+ assert_eq!(actual.maxs, expected.maxs);
+ }
+
+ #[test]
+ fn blocked_l2_cutoff_preserves_every_competitive_distance() {
+ for d in [1, 31, 32, 33, 64, 65, 128] {
+ for count in [1, 31, 32, 33, 63, 64, 65, 97] {
+ for block_size in [7, 32] {
+ let sq = ScalarQuantizer::with_bounds(d, 0.0, 255.0);
+ let query = vec![0.0; d];
+ let mut codes = Vec::new();
+ for start in (0..count).step_by(block_size) {
+ let len = (count - start).min(block_size);
+ for dim in 0..d {
+ for lane in 0..len {
+ // One entire far block, and a lane whose
distance
+ // grows only in the last dimension, guard
both sides.
+ codes.push(if start < 32 {
+ 20
+ } else if lane == 0 {
+ if dim + 1 == d {
+ 10
+ } else {
+ 0
+ }
+ } else {
+ 1
+ });
+ }
+ }
+ }
+ let mut parameters = Vec::new();
+ let mut exact = Vec::new();
+ sq.distances_to_blocked_codes_with_offset(
+ &query,
+ &codes,
+ count,
+ &query,
+ MetricType::L2,
+ block_size,
+ f32::INFINITY,
+ &mut parameters,
+ &mut exact,
+ );
+ for cutoff in [0.0, 50.0, 100.0, 1000.0, f32::INFINITY] {
+ let mut actual = Vec::new();
+ sq.distances_to_blocked_codes_with_offset(
+ &query,
+ &codes,
+ count,
+ &query,
+ MetricType::L2,
+ block_size,
+ cutoff,
+ &mut parameters,
+ &mut actual,
+ );
+ for (&full, &pruned) in exact.iter().zip(&actual) {
+ if full < cutoff {
+ assert_eq!(pruned, full);
+ } else {
+ assert!(
+ pruned >= cutoff,
+ "unsafe cutoff d={d}, count={count},
block={block_size}"
+ );
+ }
+ }
+ }
+ }
+ }
+ }
+ }
+
#[test]
fn test_scalar_quantizer_round_trips_bounds() {
let data = vec![-1.0, 0.0, 1.0, 3.0];
diff --git a/core/src/topk.rs b/core/src/topk.rs
index ae7bfc6..c600af1 100644
--- a/core/src/topk.rs
+++ b/core/src/topk.rs
@@ -86,6 +86,10 @@ impl TopKHeap {
self.is_full().then(|| self.data[0].0)
}
+ pub(crate) fn distance_limit(&self) -> f32 {
+ self.worst_distance().unwrap_or(self.max_distance)
+ }
+
pub(crate) fn into_sorted(mut self) -> Vec<(f32, i64)> {
self.data.sort_by(|a, b| a.0.total_cmp(&b.0));
self.data
diff --git a/docs/api.html b/docs/api.html
index 0be8fbb..b1e004d 100644
--- a/docs/api.html
+++ b/docs/api.html
@@ -68,27 +68,28 @@
</section>
<section class="article-section" id="reader-options">
- <h2>Reader options for DiskANN</h2>
- <p>Reader options are accepted by every binding and affect DiskANN
only. Other index families continue to use their existing positional-I/O
behavior.</p>
+ <h2>Reader options for DiskANN and IVF-SQ</h2>
+ <p>Reader options are accepted by every binding. The memory budget
controls DiskANN resident state and caches, and IVF-SQ's decoded-partition
cache. The latency hint and read-plan inspection described below are
DiskANN-specific.</p>
<div class="table-wrap"><table><thead><tr><th>Concept</th><th>Rust /
Python</th><th>C / C++ / Java</th><th>Default</th></tr></thead><tbody>
<tr><td>Random-read latency hint</td><td>Input capability
<code>estimated_random_read_latency_nanos</code></td><td>C/C++ field / Java
<code>estimatedRandomReadLatencyNanos()</code></td><td>0: reuse the mandatory
header read's elapsed time; positive values bypass measurement</td></tr>
- <tr><td>Total Reader
memory</td><td><code>memory_budget_bytes</code></td><td><code>memory_budget_bytes</code>
/ constructor argument</td><td>4 GiB; automatically partitioned among required
resident state, a profile-sized adjacency prefix, a bounded cold-adjacency LRU,
and a bounded raw-vector LRU</td></tr>
+ <tr><td>Total Reader
memory</td><td><code>memory_budget_bytes</code></td><td><code>memory_budget_bytes</code>
/ constructor argument</td><td>4 GiB; DiskANN divides it among resident state
and adjacency/raw-vector caches. IVF-SQ reserves resident metadata first and
uses the remainder for a bounded decoded-partition FIFO cache; zero disables
that cache.</td></tr>
</tbody></table></div>
+ <p>For IVF-SQ, the unified Rust reader's <code>open</code> and
binding constructors use the default budget; <code>open_with_options</code>
allows an override. Direct <code>IVFSQIndexReader::open</code> is uncached,
while its <code>open_with_options</code> enables caching. A zero or
insufficient budget disables retention, but required metadata still loads. The
limit accounts for resident metadata and retained cache allocations, not
transient query buffers or storage-adapter allo [...]
<p>The Reader has no public storage-tier switch. DiskANN selects an
internal tier once during <code>open</code> from the latency hint or mandatory
header-read timing; its latency, window, and beam policy then remain stable.
<code>read_plan</code> / <code>readPlan</code> exposes that policy together
with the current effective preload and shared-cache capacities. Those
capacities are zero before resident initialization and may shrink when lazy
row-ID lookup state consumes the sam [...]
<p>A storage adapter may additionally advertise
<code>preferred_window_bytes</code> and a maximum range count named
<code>max_ranges_per_pread</code> in Rust or <code>max_ranges_per_read</code>
in C/C++/Python. Zero means unspecified. DiskANN rounds the requested window to
complete 4 KiB logical pages, bounds it to 1 MiB, limits each
<code>pread</code> batch to the advertised range count, and keeps physical
alignment concerns inside the storage adapter. Build-time <code>deploym [...]
</section>
<section class="article-section" id="warmup">
<h2>Search warm-up</h2>
- <p>After opening a Reader and before repeated searches, initialize
resident state and, for DiskANN, optionally replay a small representative query
set. Warm-up builds process-local caches without changing the file or search
results.</p>
- <div
class="table-wrap"><table><thead><tr><th>Language</th><th>Resident
initialization</th><th>Representative-query warm-up</th><th>DiskANN width
calibration</th></tr></thead><tbody>
+ <p>After opening a Reader and before repeated searches, initialize
resident state and optionally replay a small representative query set. DiskANN
exposes a query warm-up method; IVF-SQ populates its partition cache through
ordinary <code>search</code> or batch-search calls. Warm-up builds
process-local caches without changing the file or search results.</p>
+ <div
class="table-wrap"><table><thead><tr><th>Language</th><th>Resident
initialization</th><th>DiskANN query warm-up</th><th>DiskANN width
calibration</th></tr></thead><tbody>
<tr><td>Rust</td><td><code>optimize_for_search</code></td><td><code>warmup_queries</code></td><td><code>calibrate_search_width</code></td></tr>
<tr><td>C</td><td><code>paimon_vindex_reader_optimize_for_search</code></td><td><code>paimon_vindex_reader_warmup_queries</code></td><td><code>paimon_vindex_reader_calibrate_search_width</code></td></tr>
<tr><td>C++</td><td><code>optimize_for_search</code></td><td><code>warmup_queries</code></td><td><code>calibrate_search_width</code></td></tr>
<tr><td>Java</td><td><code>optimizeForSearch</code></td><td><code>warmupQueries</code></td><td><code>calibrateSearchWidth</code></td></tr>
<tr><td>Python</td><td><code>optimize_for_search</code></td><td><code>warmup_queries</code></td><td><code>calibrate_search_width</code></td></tr>
</tbody></table></div>
- <p><code>optimize_for_search</code> is optional for correctness: the
first search performs the same initialization lazily. It builds IVF-PQ
residual-L2 tables or DiskANN resident PQ/row-ID state and its automatically
budgeted hot adjacency prefix. DiskANN <code>warmup_queries</code> then
executes top-1 graph traversal and persisted-vector rerank for each supplied
query, priming immutable adjacency and raw-vector LRUs. Other index families
treat representative warm-up as residen [...]
+ <p><code>optimize_for_search</code> is optional for correctness: the
first search performs the same initialization lazily. It builds IVF-PQ
residual-L2 tables or DiskANN resident PQ/row-ID state and its automatically
budgeted hot adjacency prefix. DiskANN <code>warmup_queries</code> then
executes top-1 graph traversal and persisted-vector rerank for each supplied
query, priming immutable adjacency and raw-vector LRUs. Other index families
treat this method as resident initializ [...]
</section>
<section class="article-section" id="rust">
diff --git a/docs/development.html b/docs/development.html
index 6993a82..fc3e5f7 100644
--- a/docs/development.html
+++ b/docs/development.html
@@ -26,7 +26,7 @@
<section class="hero detail-hero"><p class="eyebrow">Build · test ·
measure</p><h1>Development and benchmarks</h1><p class="hero-lead">Run the
standard Rust checks, exercise the C/C++, Java, and Python integrations, and
measure ANN and filtered-query behavior with reproducible workloads.</p><div
class="badge-row"><span class="badge strong">Cargo workspace</span><span
class="badge">CMake smoke tests</span><span class="badge">Maven /
pytest</span><span class="badge">Criterion benchmark [...]
<div class="doc-layout">
- <aside class="toc" aria-label="On this page"><strong>On this
page</strong><a href="#workspace">Repository layout</a><a href="#rust">Rust
checks</a><a href="#ann">ANN benchmark</a><a href="#diskann-bench">DiskANN
benchmark</a><a href="#c">C FFI</a><a href="#cpp">C++</a><a
href="#java">Java/JNI</a><a href="#python">Python</a><a href="#format">Format
compatibility</a></aside>
+ <aside class="toc" aria-label="On this page"><strong>On this
page</strong><a href="#workspace">Repository layout</a><a href="#rust">Rust
checks</a><a href="#ann">ANN benchmark</a><a href="#ivfsq-bench">IVF-SQ
benchmark</a><a href="#diskann-bench">DiskANN benchmark</a><a href="#c">C
FFI</a><a href="#cpp">C++</a><a href="#java">Java/JNI</a><a
href="#python">Python</a><a href="#format">Format compatibility</a></aside>
<article class="article">
<section class="article-section" id="workspace">
<h2>Repository layout</h2>
@@ -103,7 +103,20 @@ cargo bench -p paimon-vindex-core --bench
ann_bench</code></pre></div>
<div class="callout"><strong>Physical versus intrinsic
dimension</strong><code>ANN_NOISE_DIMENSIONS=64</code> spreads independent
per-vector noise evenly over 64 of the 1024 stored dimensions; the other
dimensions retain cluster-center signal. This creates a repeatable
storage/compute scale workload without pretending that 1024 independent
uniform-noise dimensions resemble production embeddings. With all 1024
dimensions independently noisy, same-cluster distances concentrate so [...]
<div
class="table-wrap"><table><thead><tr><th>Variable</th><th>Meaning</th></tr></thead><tbody><tr><td><code>ANN_DATASET_NAME</code></td><td>Comma-free
label written to every CSV row</td></tr><tr><td><code>ANN_BASE_FVECS /
ANN_QUERY_FVECS / ANN_GROUND_TRUTH_IVECS</code></td><td>Optional public-data
files; set all three together. Their vector count, query count, dimension, and
ground-truth width are inspected before the full payload is
loaded.</td></tr><tr><td><code>ANN_N / ANN_ [...]
<div class="callout warning"><strong>Large-run memory
boundary</strong>The current public writer API accepts an in-memory vector
slice and each index writer retains its encoded or raw build state. A raw 10
GiB DiskANN run therefore needs roughly the 10 GiB source allocation plus
DiskANN's separately budgeted build state. On a 48 GiB machine, use a 32 GiB
DiskANN budget and run one index per process. This benchmark validates large
immutable builds; it is not a streaming-ingest b [...]
- <p>The benchmark executes three serving cases by default.
<code>local_ssd_warm_cache</code> uses the real index file with no artificial
delay. <code>remote_cache_2ms</code> adds a fixed 2 ms delay per
<code>pread</code> call while reading all ranges in that call concurrently.
<code>object_store_20ms</code> uses the <code>ObjectStore</code> read plan:
open/optimization and sequential-query latency are the measured CPU/I/O time
plus 20 ms for every observed dependent read round, [...]
+ <p>The benchmark executes three serving cases by default.
<code>local_ssd_warm_cache</code> uses the real index file with no artificial
delay. <code>remote_cache_2ms</code> adds a fixed 2 ms delay per
<code>pread</code> call while reading all ranges in that call concurrently.
<code>object_store_20ms</code> uses the <code>ObjectStore</code> read plan:
open/optimization and sequential-query latency are the measured CPU/I/O time
plus 20 ms for every observed dependent read round, [...]
+ </section>
+
+ <section class="article-section" id="ivfsq-bench">
+ <h2>Reproduce the IVF-SQ benchmark</h2>
+ <p>The <a href="ivf-sq.html#benchmarks">September 2026 results</a>
compare the preceding implementation at <code>8dcabf2</code> with the optimized
IVF-SQ implementation on SIFT1M, GIST1M, and normalized GloVe-100. Convert the
public data as described above, retaining the first 1,000 held-out queries and
using <code>--normalize-l2</code> for GloVe. Run from the repository root, one
benchmark at a time, with no concurrent compilation.</p>
+ <div class="code-block"><span class="code-label">Shell · after
exporting the three public ANN file paths</span><pre><code>cargo bench -p
paimon-vindex-core --bench ann_bench --no-run
+RAYON_NUM_THREADS=8 ANN_INDEXES=IVF_SQ ANN_TRAIN_N=65536 \
+ANN_NLIST=1024 ANN_NPROBE=64 ANN_K=10 \
+ANN_STORAGE_CASES=local_ssd_warm_cache \
+ANN_OUTPUT_DIR=/path/on/target/ssd \
+cargo bench -p paimon-vindex-core --bench ann_bench</code></pre></div>
+ <p>Set <code>ANN_BASE_FVECS</code>, <code>ANN_QUERY_FVECS</code>,
and <code>ANN_GROUND_TRUTH_IVECS</code> to the converted files. Repeat each
corpus three times in separate processes and report the median of each metric.
Use the same data and settings for baseline and current builds. The recorded
runs used Rust 1.95 release builds on Apple M4 Pro (12 CPU cores, 48 GiB RAM).
Set <code>ANN_KEEP_INDEXES=1</code> to retain each generated
<code>ANN_OUTPUT_DIR/<pid>/ivf_sq.inde [...]
+ <div class="callout"><strong>Measurement boundaries</strong>Build
time includes training, encoding, and serialization. Native
<code>ann_bench</code> uses a 4 GiB reader budget: sequential queries can reuse
partitions loaded earlier in the sweep; batch timing uses a separate fresh
reader and includes payload reads and cache insertion. The baseline reader does
not cache SQ partitions. The local results use a warm filesystem cache and do
not measure cold storage or object-store be [...]
</section>
<section class="article-section" id="diskann-bench">
diff --git a/docs/index.html b/docs/index.html
index 685e09b..c405008 100644
--- a/docs/index.html
+++ b/docs/index.html
@@ -9,7 +9,7 @@
<head>
<meta charset="utf-8">
<meta name="viewport" content="width=device-width, initial-scale=1">
- <meta name="description" content="Compare the six Apache Paimon Vector Index
families by accuracy, latency, storage, build cost, and on-disk layout.">
+ <meta name="description" content="Compare the five Apache Paimon Vector
Index families by accuracy, latency, storage, build cost, and on-disk layout.">
<title>Index Selection Guide · Paimon Vector Index</title>
<link rel="stylesheet" href="styles.css">
<script src="docs.js" defer></script>
@@ -57,7 +57,7 @@
</div>
<aside class="hero-note">
<strong>The short answer</strong>
- Measure IVF-FLAT first. For compact indexes, choose IVF-SQ for
batch throughput, IVF-RQ for higher recall, or IVF-PQ for the smallest files.
Choose DiskANN for an immutable collection when high recall and small local-SSD
reads justify a much slower build; validate its recall independently for the
production metric.
+ Measure IVF-FLAT first. For compact indexes, start with IVF-SQ
when one byte per dimension fits; compare IVF-RQ for smaller configurable codes
or IVF-PQ for the smallest files. Validate each against the recall target.
Choose DiskANN for an immutable collection when high recall and small local-SSD
reads justify a much slower build; validate its recall independently for the
production metric.
</aside>
</div>
</section>
@@ -108,8 +108,8 @@
<thead><tr><th>Index</th><th>Representation</th><th>Candidate
search</th><th>Main payload per vector</th><th>Accuracy profile</th><th>Build
cost</th><th>Primary controls</th><th>Best fit</th></tr></thead>
<tbody>
<tr data-index-row data-fit="compact latency"><td><a
href="ivf-pq.html">IVF-PQ</a></td><td>8-bit PQ codes; optional
OPQ</td><td>Distance-table lookup over compact codes</td><td>About
<code>m</code> bytes</td><td>PQ reconstruction error; OPQ may improve uneven
subspaces</td><td>Medium to high</td><td>Automatic
<code>nlist</code>/<code>nprobe</code>/<code>pq.m</code>; target-based OPQ;
explicit overrides</td><td>Minimum file and selected-list bytes among IVF when
the measured [...]
- <tr data-index-row data-fit="compact latency simple"><td><a
href="ivf-sq.html">IVF-SQ</a></td><td>8-bit scalar residual codes with per-list
bounds</td><td>SIMD code scan in probed lists</td><td>About <code>d</code>
bytes</td><td>Per-coordinate scalar quantization
loss</td><td>Low</td><td>Automatic <code>nlist</code>/<code>nprobe</code>;
explicit overrides</td><td>Highest measured compact batch throughput when
0.80–0.86 recall meets the target</td></tr>
- <tr data-index-row data-fit="compact recall"><td><a
href="ivf-rq.html">IVF-RQ</a></td><td>Multi-bit rotated residual levels +
coarse/full factors</td><td>Bounded sign-plane scan, then full bit-plane
refinement</td><td>Default about <code>padded_d/2+20</code>
bytes</td><td>Measured 0.82–0.91 Recall@10 across GloVe-100, SIFT1M, and GIST1M
at four bits</td><td>Low to medium</td><td>Automatic
<code>nlist</code>/<code>nprobe</code>; budget-based bits; explicit
overrides</td><td> [...]
+ <tr data-index-row data-fit="compact latency simple"><td><a
href="ivf-sq.html">IVF-SQ</a></td><td>8-bit scalar residual codes with pooled
training bounds</td><td>SIMD code scan in probed lists</td><td>About
<code>d</code> bytes</td><td>Per-coordinate scalar quantization
loss</td><td>Low</td><td>Automatic <code>nlist</code>/<code>nprobe</code>;
explicit overrides</td><td>Compact SIMD scans with pooled training bounds and a
bounded partition cache</td></tr>
+ <tr data-index-row data-fit="compact recall"><td><a
href="ivf-rq.html">IVF-RQ</a></td><td>Multi-bit rotated residual levels +
coarse/full factors</td><td>Bounded sign-plane scan, then full bit-plane
refinement</td><td>Default about <code>padded_d/2+20</code>
bytes</td><td>Measured 0.82–0.91 Recall@10 across GloVe-100, SIFT1M, and GIST1M
at four bits</td><td>Low to medium</td><td>Automatic
<code>nlist</code>/<code>nprobe</code>; budget-based bits; explicit
overrides</td><td> [...]
<tr data-index-row data-fit="recall latency"><td><a
href="diskann.html">DiskANN</a></td><td>Global Vamana + resident PQ + persisted
rerank vectors</td><td>PQ-guided graph traversal and F32/F16
rerank</td><td><code>E·d + pq.m + 4(R+1)</code> bytes, approximately;
<code>E=4</code> or <code>2</code></td><td>Approximate candidate discovery;
F32-exact or F16-quantized distances for reranked candidates</td><td>Very
high</td><td>Build preset + deployment/capacity objectives; calib [...]
<tr data-index-row data-fit="recall simple"><td><a
href="ivf-flat.html">IVF-FLAT</a></td><td>Raw <code>f32</code>
vectors</td><td>Exact distance scan in probed lists</td><td>About
<code>4d</code> bytes</td><td>No quantization loss; recall mainly depends on
<code>nprobe</code></td><td>Low</td><td>Automatic
<code>nlist</code>/<code>nprobe</code>; explicit overrides</td><td>Recall
ceiling, frequent rebuilds, IP/cosine, or production sets whose scan bytes are
affordable</td></tr>
</tbody>
@@ -119,10 +119,14 @@
<section class="section" id="public-corpus-check">
<div class="section-heading">
- <h2>Measured comparison: public SIFT1M, GIST1M, and GloVe-100
corpora</h2>
- <p>This repository's unified benchmark builds all five indexes over
standard public vectors, searches the same independent public queries, and
scores every result against published exact neighbors. The results below are
the homepage's sole performance evidence.</p>
+ <h2>Public-corpus benchmark results</h2>
+ <p><strong>IVF-SQ was refreshed on 6 September 2026 across all three
corpora.</strong> Its build and local-search cells below use three-run native
<code>ann_bench</code> medians with eight Rayon workers. The other four index
rows retain their July 2026 measurements with 12 workers; these tables record
the latest available results for each index, not a new simultaneous five-index
ranking.</p>
+ <p>All rows use the same public corpus shapes, 1,000 independent
queries, <code>nlist=1024</code>, <code>nprobe=64</code>, and Top-10. Native
batch timing includes the first payload reads and cache insertion on a fresh
reader. The remote-model results remain archived separately below.</p>
</div>
+ <details id="benchmark-setup">
+ <summary><strong>Historical five-index setup and reproduction
parameters · July 2026</strong></summary>
+ <p>The following records the original 12-worker comparison. For the
refreshed eight-worker IVF-SQ configuration, use the <a
href="development.html#ivfsq-bench">current reproduction guide</a>.</p>
<h3>Benchmark setup</h3>
<div class="callout warning"><strong>This is not the
zero-configuration benchmark</strong>Running <code>cargo bench -p
paimon-vindex-core --bench ann_bench</code> without public file paths uses a
20k-vector, 64-dimensional generated smoke workload. Reproducing the results
below requires the public files, recorded IVF and DiskANN search settings, a
fixed worker count, and an output directory on the storage device being
measured. File shape, training count, and multi-index process [...]
<p>The real-data run uses the public <a
href="https://github.com/erikbern/ann-benchmarks";>ANN-Benchmarks</a> SIFT1M,
GIST1M, and GloVe-100 files, the first 1,000 independent test queries, and
their published Top-100 exact neighbors. Recall@10 compares only the first ten
published neighbors. SIFT and GIST contain one million base vectors with 128
and 960 dimensions. GloVe contains 1,183,514 vectors with 100 dimensions and
angular ground truth; its base and query vectors are L2-nor [...]
@@ -140,14 +144,30 @@
<div class="callout"><strong>Equal relative PQ budget</strong>The
default <code>pq.code-ratio=0.0625</code> automatically resolves SIFT to
<code>pq.m=32</code>, GIST to <code>pq.m=240</code>, and GloVe to
<code>pq.m=25</code>. Every code occupies 6.25% as many bytes as its raw
<code>f32</code> vector and leaves four dimensions per PQ sub-vector. The
concrete value is persisted in index metadata; use explicit <code>pq.m</code>
only as an expert override.</div>
<p>The cross-index run was recorded on 25 July 2026 using an Apple M4
Pro with 12 logical CPUs and 48 GiB RAM, a release build with Rust 1.95, real
APFS files with warm operating-system pages, and the automatic 4 GiB DiskANN
Reader budget. The IVF-RQ staged A/B and rebased IVF-PQ warm-local refresh were
recorded on 30 July on the same host and toolchain. The reproduction command
pins Rayon to 12 workers instead of relying on automatic host parallelism. The
modeled serving profile [...]
- <h4>Build, file, and peak process memory</h4>
+ </details>
+
+ <h3 id="build-results">Build, file, and peak process memory</h3>
<div class="table-wrap"><table><thead><tr><th>Index</th><th>SIFT
build</th><th>SIFT file / RSS</th><th>GIST build</th><th>GIST file /
RSS</th><th>GloVe build</th><th>GloVe file / RSS</th></tr></thead><tbody>
<tr><td>IVF-PQ</td><td>8.74 s</td><td>0.032 / 0.88 GiB</td><td>55.4
s</td><td>0.230 / 5.00 GiB</td><td>7.92 s</td><td>0.030 / 0.85 GiB</td></tr>
- <tr><td>IVF-SQ</td><td>3.93 s</td><td>0.122 / 0.79 GiB</td><td>22.7
s</td><td>0.907 / 5.09 GiB</td><td>3.86 s</td><td>0.113 / 0.71 GiB</td></tr>
+ <tr><td><strong>IVF-SQ · 6 Sep</strong></td><td>0.886
s</td><td>0.122 / 0.77 GiB</td><td>5.850 s</td><td>0.907 / 4.87
GiB</td><td>0.797 s</td><td>0.113 / 0.72 GiB</td></tr>
<tr><td>IVF-RQ</td><td>3.92 s</td><td>0.080 / 0.71 GiB</td><td>23.5
s</td><td>0.471 / 4.65 GiB</td><td>4.03 s</td><td>0.095 / 0.68 GiB</td></tr>
<tr><td>DiskANN</td><td>74.0 s</td><td>0.361 / 1.51 GiB</td><td>11
min 26 s</td><td>2.089 / 7.94 GiB</td><td>2 min 33 s</td><td>0.396 / 1.45
GiB</td></tr>
<tr><td>IVF-FLAT</td><td>4.05 s</td><td>0.479 / 1.83
GiB</td><td>24.9 s</td><td>3.582 / 12.74 GiB</td><td>4.10 s</td><td>0.443 /
1.60 GiB</td></tr>
</tbody></table></div>
+ <h3 id="local-results">Native local-storage results</h3>
+ <div class="table-wrap"><table><thead><tr><th>Index /
search</th><th>SIFT Recall / P95 / batch QPS / read</th><th>GIST Recall / P95 /
batch QPS / read</th><th>GloVe Recall / P95 / batch QPS /
read</th></tr></thead><tbody>
+ <tr><td>IVF-PQ</td><td>0.7142 / 0.72 ms / 7,899 / 2.18
MiB</td><td>0.7410 / 2.47 ms / 950 / 17.84 MiB</td><td>0.5819 / 0.64 ms / 8,048
/ 1.84 MiB</td></tr>
+ <tr><td><strong>IVF-SQ · 6 Sep</strong></td><td>0.9811 / 0.298 ms /
8,987 / 0.115 MiB</td><td>0.9400 / 1.828 ms / 998 / 0.850 MiB</td><td>0.8760 /
0.282 ms / 10,009 / 0.108 MiB</td></tr>
+ <tr><td>IVF-RQ</td><td>0.9148 / 1.20 ms / 3,074 / 5.54
MiB</td><td>0.9039 / 4.41 ms / 444 / 37.02 MiB</td><td>0.8203 / 1.23 ms / 2,917
/ 5.89 MiB</td></tr>
+ <tr><td>DiskANN</td><td>0.9915 / 1.50 ms / 9,009 / 0.66
MiB</td><td>0.9336 / 1.83 ms / 4,651 / 0.83 MiB</td><td>0.8355 / 1.90 ms /
6,289 / 0.96 MiB</td></tr>
+ <tr><td>IVF-FLAT</td><td>0.9937 / 1.88 ms / 8,510 / 33.19
MiB</td><td>0.9549 / 11.38 ms / 875 / 283.40 MiB</td><td>0.8832 / 1.40 ms /
9,502 / 27.57 MiB</td></tr>
+ </tbody></table></div>
+ <p>The refreshed SQ reader reuses decoded partitions within its memory
budget. The read column is average payload I/O per sequential query, including
cache misses while that sweep warms the reader; it is not the full
selected-list size or a cold-cache promise. SQ batch QPS includes the first
batch's payload reads on a separate reader. The recorded July rows predate this
SQ cache and training change.</p>
+ <p>For IVF-SQ, train / encode-add / serialize medians in SIFT / GIST /
GloVe order are 252 / 538 / 93 ms; 1696 / 3613 / 563 ms; 187 / 517 / 90 ms.
Stage medians are computed independently and need not sum to the median total.
See the <a href="ivf-sq.html#benchmarks">same-configuration baseline
comparison</a> for the optimization's measured effect.</p>
+
+ <details id="historical-implementation-notes">
+ <summary><strong>Historical implementation notes and earlier SQ
scores · July 2026</strong></summary>
+ <p>These notes preserve earlier snapshots. Their performance and
implementation descriptions have been superseded where the refreshed tables
above provide results.</p>
<div class="callout"><strong>IVF-SQ build and scan refresh</strong>The
add path now borrows L2/IP input, assigns rows once, and encodes lists in
parallel with one residual scratch vector per active list task instead of
materializing an additional <code>N × d</code> residual matrix. In the
immediately preceding same-machine run, SIFT/GIST/GloVe peak RSS was 1.81 /
12.92 / 1.60 GiB; it is now 0.79 / 5.09 / 0.71 GiB. A Top-K threshold fast path
skips hash work for candidates that ca [...]
<div class="callout"><strong>30 July IVF-PQ batch-table reuse
refresh</strong>The rebased Reader retains the v1 zero-copy/transposed-code,
ordered-list, one-byte row-ID, and first-column accumulation fast paths. For
large 8-bit residual-L2 batches, the default <code>Auto</code> mode now factors
each distance table into reusable per-list and per-query components when the
reuse heuristic and 64 MiB working-memory guard both pass; small or unsuitable
batches keep the direct path, an [...]
<div class="callout"><strong>Latest IVF-FLAT storage and scan
review</strong>The v1 writer retains only sort permutations and encoded IDs,
materializes one sorted raw-vector list at a time, and reproduced all three
prior public files byte-for-byte. The Reader now receives list bytes directly
into an <code>f32</code>-aligned allocation; an internal prefix of at most
three bytes keeps the raw-vector suffix aligned despite variable-length row
IDs, so search no longer allocates and d [...]
@@ -169,16 +189,11 @@
<div class="callout"><strong>Final open-source cross-check and format
decision</strong><a
href="https://github.com/facebookresearch/faiss/wiki/Fast-accumulation-of-PQ-and-AQ-codes-%28FastScan%29";>Faiss
FastScan</a> still trades down to 4-bit lookup tables and a 32-row layout, so
it is not a transparent replacement for the published 8-bit IVF-PQ v1. Faiss
Panorama's additional level-oriented energy data was not needed to keep the
existing IVF-FLAT v1 progressive cutoff. Lance's pa [...]
<p>DiskANN spends almost all build time constructing one global graph:
about 18× IVF-FLAT on SIFT, 28× on GIST, and 37× on GloVe. The balanced F16
default makes its files about 42% smaller than IVF-FLAT on GIST and 11% smaller
on GloVe, but they remain much larger than the compact IVF encodings because
persisted rerank vectors, resident codes, and graph edges are all material.
Peak RSS remains below the raw IVF writers because the DiskANN writer does not
retain a second full raw- [...]
- <h4>Warm local-storage result</h4>
- <div class="table-wrap"><table><thead><tr><th>Index /
search</th><th>SIFT Recall / P95 / batch QPS / read</th><th>GIST Recall / P95 /
batch QPS / read</th><th>GloVe Recall / P95 / batch QPS /
read</th></tr></thead><tbody>
- <tr><td>IVF-PQ</td><td>0.7142 / 0.72 ms / 7,899 / 2.18
MiB</td><td>0.7410 / 2.47 ms / 950 / 17.84 MiB</td><td>0.5819 / 0.64 ms / 8,048
/ 1.84 MiB</td></tr>
- <tr><td>IVF-SQ</td><td>0.8627 / 0.79 ms / 11,082 / 8.38
MiB</td><td>0.8577 / 3.56 ms / 1,502 / 70.95 MiB</td><td>0.8036 / 0.71 ms /
12,962 / 6.99 MiB</td></tr>
- <tr><td>IVF-RQ</td><td>0.9148 / 1.20 ms / 3,074 / 5.54
MiB</td><td>0.9039 / 4.41 ms / 444 / 37.02 MiB</td><td>0.8203 / 1.23 ms / 2,917
/ 5.89 MiB</td></tr>
- <tr><td>DiskANN</td><td>0.9915 / 1.50 ms / 9,009 / 0.66
MiB</td><td>0.9336 / 1.83 ms / 4,651 / 0.83 MiB</td><td>0.8355 / 1.90 ms /
6,289 / 0.96 MiB</td></tr>
- <tr><td>IVF-FLAT</td><td>0.9937 / 1.88 ms / 8,510 / 33.19
MiB</td><td>0.9549 / 11.38 ms / 875 / 283.40 MiB</td><td>0.8832 / 1.40 ms /
9,502 / 27.57 MiB</td></tr>
- </tbody></table></div>
- <p>IVF-SQ is the compact-throughput choice: it leads the compact
indexes on all three local batch runs. IVF-RQ uses smaller files and raises
recall from 0.8627 / 0.8577 / 0.8036 to 0.9148 / 0.9039 / 0.8203, but batch
throughput falls by about 3.4–4.4×. IVF-PQ is smaller and faster than RQ, but
its 0.5819–0.7410 recall makes it a capacity-first choice rather than a default
accuracy compromise. DiskANN is compelling on SIFT and especially GIST: it
reads below 1 MiB per query on bot [...]
+ </details>
+ <details id="historical-remote-results">
+ <summary><strong>Historical remote and object-store models · July
2026</strong></summary>
+ <p>All rows in this archive, including IVF-SQ, retain the original
implementation and 12-worker configuration. The current pooled-bound and cached
IVF-SQ has not been remeasured under these latency models.</p>
<h4>Remote cache with 2 ms per I/O round</h4>
<div class="table-wrap"><table><thead><tr><th>Index /
search</th><th>SIFT Recall / P95 / batch QPS / rounds</th><th>GIST Recall / P95
/ batch QPS / rounds</th><th>GloVe Recall / P95 / batch QPS /
rounds</th></tr></thead><tbody>
<tr><td>IVF-PQ</td><td>0.7142 / 6.16 ms / 7,282 / 1.0</td><td>0.7410
/ 7.12 ms / 1,162 / 1.0</td><td>0.5819 / 5.94 ms / 8,243 / 1.0</td></tr>
@@ -200,6 +215,7 @@
<p>At 20 ms per round, IVF-RQ is the strongest measured compact
one-round option: it reaches 0.90-class recall on SIFT/GIST and 0.8203 on
GloVe. IVF-SQ is faster when its lower recall is enough, and IVF-PQ is smaller
when stronger quantization loss is acceptable. IVF-FLAT now looks competitive
on one-round SIFT/GloVe in this fixed-latency model, but that result assumes
28–33 MiB transfers have no bandwidth cost; GIST's 283 MiB and five rounds
expose the boundary. DiskANN averages [...]
<div class="callout warning"><strong>The automatic read plan affects
approximate search</strong>The latency-derived local tier uses graph beam 4
while remote and object-store tiers use beam 16, so the same
<code>l_search</code> can return different approximate candidates; this is
visible for both GIST and GloVe at <code>l_search=100</code>. The tiers use 16
KiB, 32 KiB, and 64 KiB coalescing windows respectively. Storage latency itself
does not change ground truth. Compare indexe [...]
<div class="callout warning"><strong>Remote-model boundary</strong>The
vectors and exact neighbors are public corpus data, but the 2 ms and 20 ms
profiles are controlled I/O models rather than measurements from a production
cache or object store. They add fixed latency without modeling bandwidth, cache
misses, TLS, retries, throttling, request limits, or tail-latency
variance.</div>
+ </details>
</section>
<section class="section" id="decision">
@@ -207,24 +223,25 @@
<h2>Choose by constraint</h2>
<p>There is no best index independent of data distribution. Narrow
the field to one or two candidates, then evaluate Recall@K, P95/P99 latency,
file size, build time, and object-store bytes on real queries.</p>
</div>
- <div class="callout"><strong>Practical default order</strong>First
reject indexes that cannot meet the measured recall target. Build IVF-FLAT to
establish the corpus-specific IVF ceiling. If a compact representation is
required, choose IVF-SQ for throughput, IVF-RQ for recall, or IVF-PQ for
minimum bytes. Evaluate DiskANN separately for immutable data served from local
SSD; do not select it only because the collection is large or assume L2 results
transfer to another metric.</div>
+ <div class="callout"><strong>Practical default order</strong>First
reject indexes that cannot meet the measured recall target. Build IVF-FLAT to
establish the corpus-specific IVF ceiling. If a compact representation is
required, start with IVF-SQ when its one-byte-per-dimension codes fit; compare
IVF-RQ at the required bit budget and IVF-PQ for minimum bytes. Evaluate
DiskANN separately for immutable data served from local SSD; do not select it
only because the collection is larg [...]
<h3>Measured recommendation matrix</h3>
- <div class="table-wrap"><table><thead><tr><th>Production
constraint</th><th>Start with</th><th>Evidence from this run</th><th>Move away
when</th></tr></thead><tbody>
+ <p>Except for the refreshed SQ results, numerical evidence below comes
from the July five-index matrix. The latest SQ results cover SIFT, GIST, and
GloVe; other algorithms have not been rerun in this refresh.</p>
+ <div class="table-wrap"><table><thead><tr><th>Production
constraint</th><th>Start with</th><th>Recorded evidence</th><th>Move away
when</th></tr></thead><tbody>
<tr><td>Establish a recall ceiling or debug ranking
quality</td><td><a href="ivf-flat.html">IVF-FLAT</a></td><td>Highest measured
recall on all three corpora: 0.9937 / 0.9549 / 0.8832, with roughly four-second
SIFT/GloVe builds.</td><td>The 28–283 MiB selected-list reads or raw-vector
file size exceed the serving budget.</td></tr>
- <tr><td>Highest compact batch throughput</td><td><a
href="ivf-sq.html">IVF-SQ</a></td><td>11,082 / 1,502 / 12,962 local batch QPS
at 0.8627 / 0.8577 / 0.8036 recall; files are about one quarter of
IVF-FLAT.</td><td>The recall gate is above SQ, or one byte per dimension is
still too large.</td></tr>
- <tr><td>Strongest recall in a compact IVF file</td><td><a
href="ivf-rq.html">IVF-RQ</a></td><td>0.9148 / 0.9039 / 0.8203 recall in files
smaller than IVF-SQ, with one sequential read round per query in all three
modeled profiles.</td><td>Batch throughput is the primary SLO; the four-bit
scanner is 3–4.5× slower than SQ in the local run.</td></tr>
+ <tr><td>Compact scans and repeated-query throughput</td><td><a
href="ivf-sq.html">IVF-SQ</a></td><td>The <a href="#local-results">refreshed
three-corpus SQ row</a> records pooled-bound recall, native P95, batch QPS, and
average payload I/O. Files are about one quarter of IVF-FLAT.</td><td>The
recall gate is above SQ, or one byte per dimension is still too large.</td></tr>
+ <tr><td>Configurable codes smaller than IVF-SQ</td><td><a
href="ivf-rq.html">IVF-RQ</a></td><td>The historical four-bit run reached
0.9148 / 0.9039 / 0.8203 recall in files smaller than IVF-SQ, with one
sequential read round per query in all three modeled profiles.</td><td>The
chosen width misses the recall or throughput target. Compare the current SQ
implementation before accepting the extra scan cost.</td></tr>
<tr><td>Minimum index file and compact-IVF scan bytes</td><td><a
href="ivf-pq.html">IVF-PQ</a></td><td>The smallest files—0.032 / 0.230 / 0.030
GiB—and the smallest IVF selected-list reads at 1.84–17.84 MiB, with strong
batch throughput.</td><td>0.5819–0.7410 recall is below the gate; increase the
PQ budget or choose SQ/RQ instead.</td></tr>
<tr><td>High-recall immutable data on local SSD</td><td><a
href="diskann.html">DiskANN</a>, checked against IVF-FLAT for the same
metric</td><td>The recorded L2-equivalent run reached 0.9915 / 0.9336 / 0.8355
recall with 0.66 / 0.83 / 0.96 MiB reads; SIFT/GIST P95 is 1.50 / 1.83
ms.</td><td>Metric-specific recall misses the gate, rebuilds are frequent, the
file is not locally cached, preview maturity is unacceptable, or the corpus
behaves like GloVe at <code>l_search=100</code> [...]
- <tr><td>Frequent rebuilds or rapidly changing snapshots</td><td><a
href="ivf-flat.html">IVF-FLAT</a>, <a href="ivf-sq.html">IVF-SQ</a>, or <a
href="ivf-rq.html">IVF-RQ</a></td><td>These build in about 4 seconds on
SIFT/GloVe and 23–25 seconds on GIST; IVF-PQ is about 2× slower and DiskANN is
18–37× slower than IVF-FLAT.</td><td>The serving phase dominates lifetime cost
enough to justify PQ training or graph construction.</td></tr>
- <tr><td>Direct 2/20 ms remote or object-store reads</td><td>Compact
IVF selected by recall: PQ → SQ → RQ</td><td>PQ and RQ use one sequential
multi-range round here; SQ does so on SIFT/GloVe and averages 1.9 rounds on
GIST. Choose successively more recall at greater bytes or CPU
cost.</td><td>Bandwidth, request limits, or real tail latency invalidate the
fixed-latency model; prefer a complete local SSD cache and rerun the
benchmark.</td></tr>
+ <tr><td>Frequent rebuilds or rapidly changing snapshots</td><td><a
href="ivf-flat.html">IVF-FLAT</a>, <a href="ivf-sq.html">IVF-SQ</a>, or <a
href="ivf-rq.html">IVF-RQ</a></td><td>The historical five-index run favored
these IVF variants for rebuild cost. Refreshed SQ builds take 0.886 s / 5.850 s
/ 0.797 s on SIFT / GIST / GloVe.</td><td>The serving phase dominates lifetime
cost enough to justify PQ training or graph construction.</td></tr>
+ <tr><td>Direct 2/20 ms remote or object-store reads</td><td>Compact
IVF selected by measured recall, payload bytes, and cache budget</td><td>In the
historical uncached run, PQ and RQ used one sequential multi-range round; SQ
did so on SIFT/GloVe and averaged 1.9 rounds on GIST. Current SQ cache hits
avoid payload reads; measure miss behavior on the real
adapter.</td><td>Bandwidth, request limits, or real tail latency invalidate the
fixed-latency model; prefer a complete local S [...]
<tr><td>Inner product or cosine</td><td>IVF-FLAT as the recall
control; DiskANN as an additional candidate for immutable local-SSD
serving</td><td>All five implementations support L2, IP, and cosine. DiskANN
normalizes cosine internally and uses metric-aware graph construction and exact
reranking, but the displayed public-corpus matrix was recorded through the
L2-equivalent benchmark path.</td><td>The selected configuration misses its
metric-specific recall gate—retune <code>np [...]
</tbody></table></div>
- <div class="callout warning"><strong>A displayed winner can still be
the wrong choice</strong>These recommendations apply to the recorded
<code>nlist=1024</code>, <code>nprobe=64</code>, PQ ratio, RQ bits, and
<code>l_search=100</code>. For example, the current GloVe run does not reach
0.90 recall with any index, and current GIST reaches 0.95 only with IVF-FLAT.
If a required recall threshold is not present in the table, tune and rebuild
rather than choosing the closest result.</div>
+ <div class="callout warning"><strong>A displayed winner can still be
the wrong choice</strong>These recommendations apply to the recorded
<code>nlist=1024</code>, <code>nprobe=64</code>, PQ ratio, RQ bits, and
<code>l_search=100</code>. For example, the historical GloVe run does not reach
0.90 recall with any index, and historical GIST reaches 0.95 only with
IVF-FLAT. The new SQ GloVe result also remains below 0.90. If a required recall
threshold is not present in the table, tune [...]
<div class="card-grid">
<article class="card"><h3>I need a trustworthy baseline</h3><p>Start
with IVF-FLAT. It exposes the IVF partition ceiling without quantization loss
and rebuilds quickly.</p><a class="card-link" href="ivf-flat.html">Explore
IVF-FLAT →</a></article>
- <article class="card"><h3>I need compact high recall</h3><p>Choose
IVF-RQ when its 0.82–0.91 measured recall matters more than batch throughput;
compare every result with the IVF-FLAT ceiling.</p><a class="card-link"
href="ivf-rq.html">Explore IVF-RQ →</a></article>
+ <article class="card"><h3>I need configurable compact
codes</h3><p>Try IVF-RQ when SQ is too large and tune the bit width against
recall and throughput. Compare every result with the IVF-FLAT ceiling and the
current SQ baseline.</p><a class="card-link" href="ivf-rq.html">Explore IVF-RQ
→</a></article>
<article class="card"><h3>I need the smallest index</h3><p>Choose
IVF-PQ when its corpus-specific recall passes the gate. It is the
capacity-first option, not the automatic middle ground.</p><a class="card-link"
href="ivf-pq.html">Explore IVF-PQ →</a></article>
- <article class="card"><h3>I need compact batch speed</h3><p>Choose
IVF-SQ when one byte per dimension fits and its measured 0.80–0.86 recall is
enough; it is the fastest compact scanner here.</p><a class="card-link"
href="ivf-sq.html">Explore IVF-SQ →</a></article>
+ <article class="card"><h3>I need compact batch speed</h3><p>Choose
IVF-SQ when one byte per dimension fits. Pooled training bounds and bounded
partition caching improve the measured three-corpus recall and repeated-query
performance; validate the target corpus and cache budget.</p><a
class="card-link" href="ivf-sq.html">Explore IVF-SQ →</a></article>
<article class="card"><h3>Raw vectors exceed RAM but fit local
SSD</h3><p>Evaluate DiskANN for immutable L2, IP, or cosine data when high
recall and sub-MiB query reads justify a much slower build; retain IVF-FLAT as
the metric-specific accuracy control.</p><a class="card-link"
href="diskann.html">Explore DiskANN →</a></article>
<article class="card"><h3>Data lives in S3, OSS, or
HDFS</h3><p>Prefer durable publication plus a complete local SSD cache. For
direct remote reads, start with a compact IVF index when one-round scans meet
recall; use DiskANN only after measuring its corpus-dependent coalesced graph
rounds.</p><a class="card-link" href="diskann.html#deployment">Compare
deployment modes →</a></article>
</div>
@@ -250,7 +267,7 @@
<tr><td><code>deployment-profile</code></td><td>Build</td><td>DiskANN</td><td>Selects
interleaved layout for eligible memory/local serving and compact layout for
remote/object serving</td><td>Explicit layout/encoding/build-distance overrides
always win</td></tr>
<tr><td><code>estimated_random_read_latency_nanos</code></td><td>Reader input
capability</td><td>DiskANN</td><td>Selects the internal read window, graph
beam, and automatic cache partition without probe I/O</td><td>0 measures the
mandatory header read; positive values are useful for known remote/cache
latency</td></tr>
<tr><td><code>l_search</code></td><td>Query</td><td>DiskANN</td><td>Larger
DiskANN candidate list, usually higher recall and latency</td><td>Auto uses
calibrated 100/200/400 when available, otherwise <code>max(100,
2k)</code></td></tr>
-
<tr><td><code>memory_budget_bytes</code></td><td>Reader</td><td>DiskANN</td><td>Controls
required resident state plus automatically partitioned adjacency/raw-vector
caches</td><td>4 GiB; cache sub-budgets are internal</td></tr>
+
<tr><td><code>memory_budget_bytes</code></td><td>Reader</td><td>DiskANN,
IVF-SQ</td><td>Reserves resident state, then bounds DiskANN
adjacency/raw-vector caches or the IVF-SQ partition cache</td><td>4 GiB; cache
sub-budgets are internal</td></tr>
</tbody></table></div>
</section>
diff --git a/docs/ivf-flat.html b/docs/ivf-flat.html
index aad9289..5dc76b1 100644
--- a/docs/ivf-flat.html
+++ b/docs/ivf-flat.html
@@ -92,7 +92,7 @@ let params = VectorSearchParams::new(10,
16);</code></pre></div>
<section class="article-section" id="tuning">
<h2>Tuning order</h2>
- <ol><li><strong>Fix the metric.</strong> Build exact ground truth
with the production metric and include zero-vector edge cases for
cosine.</li><li><strong>Start automatic.</strong> Supply the final corpus
count, inspect the resolved <code>nlist</code>, and use automatic query
width.</li><li><strong>Calibrate only if needed.</strong> Sweep explicit
<code>nprobe</code> around the automatic value and record Recall@K, P95/P99,
selected lists, and bytes read.</li><li><strong>Measur [...]
+ <ol><li><strong>Fix the metric.</strong> Build exact ground truth
with the production metric and include zero-vector edge cases for
cosine.</li><li><strong>Start automatic.</strong> Supply the final corpus
count, inspect the resolved <code>nlist</code>, and use automatic query
width.</li><li><strong>Calibrate only if needed.</strong> Sweep explicit
<code>nprobe</code> around the automatic value and record Recall@K, P95/P99,
selected lists, and bytes read.</li><li><strong>Measur [...]
</section>
<section class="article-section" id="limits">
diff --git a/docs/ivf-rq.html b/docs/ivf-rq.html
index 76424f8..add8457 100644
--- a/docs/ivf-rq.html
+++ b/docs/ivf-rq.html
@@ -18,7 +18,7 @@
<section class="article-section" id="position">
<h2>Positioning and trade-offs</h2>
<div class="metric-strip"><div class="metric"><span
class="label">Default code</span><span class="value"><code>padded_d / 2</code>
bytes</span></div><div class="metric"><span class="label">Per-vector
factors</span><span class="value">5 × <code>f32</code></span></div><div
class="metric"><span class="label">Learned model</span><span class="value">IVF
centroids only</span></div><div class="metric"><span
class="label">Dimension</span><span class="value">Any positive value</span></d
[...]
- <div class="split"><div class="pro-con"><h3>Good fit</h3><ul><li>You
need higher recall than IVF-SQ at a smaller serialized size.</li><li>Training
time and model complexity should stay close to IVF-FLAT.</li><li>The source
supports one concurrent multi-range read for selected
lists.</li><li>Approximate in-list ranking is acceptable and measured against
real ground truth.</li></ul></div><div class="pro-con"><h3>Poor
fit</h3><ul><li>Raw-vector or exact reranking accuracy is manda [...]
+ <div class="split"><div class="pro-con"><h3>Good fit</h3><ul><li>You
need smaller codes than IVF-SQ while meeting the measured recall
target.</li><li>Training time and model complexity should stay close to
IVF-FLAT.</li><li>The source supports one concurrent multi-range read for
selected lists.</li><li>Approximate in-list ranking is acceptable and measured
against real ground truth.</li></ul></div><div class="pro-con"><h3>Poor
fit</h3><ul><li>Raw-vector or exact reranking accur [...]
<div class="callout"><strong>Why it remains IVF-RQ</strong>The
public index family name is unchanged. The pre-release 1-bit/query-bit
experiment was replaced completely: bit width is now a property of persisted
data, not a per-query switch.</div>
</section>
@@ -94,7 +94,7 @@ let params = VectorSearchParams::new(10,
64);</code></pre></div>
<section class="article-section" id="tuning">
<h2>Tuning order</h2>
- <ol><li>Run IVF-FLAT with the target <code>nlist/nprobe</code> to
establish the partition recall ceiling.</li><li>Start IVF-RQ at the default
four bits.</li><li>If recall is low for both indexes, increase
<code>nprobe</code>. If only IVF-RQ is low, try five bits before increasing I/O
through more lists.</li><li>Compare IVF-SQ when simpler/faster scans matter;
compare IVF-PQ when minimum size matters.</li><li>Validate the final choice on
a public or production corpus, including [...]
+ <ol><li>Run IVF-FLAT with the target <code>nlist/nprobe</code> to
establish the partition recall ceiling.</li><li>Start IVF-RQ at the default
four bits.</li><li>If recall is low for both indexes, increase
<code>nprobe</code>. If only IVF-RQ is low, try five bits before increasing I/O
through more lists.</li><li>Compare the <a
href="ivf-sq.html#benchmarks">current IVF-SQ recall and scan results</a> when
one byte per dimension fits; compare IVF-PQ when minimum size matters.</li><
[...]
</section>
<section class="article-section" id="limits">
diff --git a/docs/ivf-sq.html b/docs/ivf-sq.html
index 3cf58e0..34a52c9 100644
--- a/docs/ivf-sq.html
+++ b/docs/ivf-sq.html
@@ -8,12 +8,13 @@
<html lang="en">
<head><meta charset="utf-8"><meta name="viewport" content="width=device-width,
initial-scale=1"><meta name="description" content="IVF-SQ residual scalar
quantization, tuning, I/O behavior, and stable v1 storage
layout."><title>IVF-SQ · Paimon Vector Index</title><link rel="stylesheet"
href="styles.css"><script src="docs.js" defer></script></head>
<body>
+ <a class="skip-link" href="#main">Skip to content</a>
<header class="site-header"><div class="header-inner"><a class="brand"
href="index.html" aria-label="Paimon Vector Index documentation home"><span
class="brand-mark">VI</span><span>Paimon Vector Index</span></a><nav
class="site-nav" data-site-nav aria-label="Documentation"><a
href="index.html">Overview</a><a href="api.html">API</a><a
href="development.html">Development</a><a href="ivf-flat.html">IVF-FLAT</a><a
href="ivf-pq.html">IVF-PQ</a><a href="ivf-rq.html">IVF-RQ</a><a href="ivf-sq
[...]
- <main>
- <section class="hero detail-hero"><p class="eyebrow">Per-list residual
scalar quantization</p><h1>IVF-SQ</h1><p class="hero-lead">Store one unsigned
byte per residual dimension and scan the selected IVF lists directly. IVF-SQ
targets the gap between raw IVF-FLAT and aggressively compressed IVF-PQ/RQ
without paying for a graph in every list.</p><div class="badge-row"><span
class="badge strong">1 byte / dimension</span><span class="badge">Per-list
bounds</span><span class="badge">SIMD [...]
- <div class="article-layout">
+ <main id="main"><div class="page-shell">
+ <section class="hero detail-hero"><p class="eyebrow">Residual scalar
quantization</p><h1>IVF-SQ</h1><p class="hero-lead">Store one unsigned byte per
residual dimension and scan the selected IVF lists directly. IVF-SQ targets the
gap between raw IVF-FLAT and aggressively compressed IVF-PQ/RQ without paying
for a graph in every list.</p><div class="badge-row"><span class="badge
strong">1 byte / dimension</span><span class="badge">Pooled training
bounds</span><span class="badge">SIMD sc [...]
+ <div class="doc-layout">
<aside class="toc"><strong>On this page</strong><a
href="#position">Position</a><a href="#algorithm">Algorithm</a><a
href="#usage">Usage</a><a href="#parameters">Parameters</a><a
href="#storage">Storage</a><a href="#comparison">Open-source comparison</a><a
href="#io">I/O and batching</a><a href="#benchmarks">Public
benchmarks</a></aside>
- <article>
+ <article class="article">
<section class="article-section" id="position">
<h2>Position</h2>
<p>IVF-SQ preserves the IVF partitioning model and replaces every
residual <code>f32</code> component with an 8-bit scalar code. It usually
occupies about one quarter of IVF-FLAT's vector payload. Unlike IVF-PQ, each
dimension is quantized independently, so there is no subquantizer-count
parameter or codebook lookup table.</p>
@@ -21,7 +22,7 @@
</section>
<section class="article-section" id="algorithm">
<h2>Build and search</h2>
- <ol><li>Train the IVF coarse centroids and assign training vectors
to lists.</li><li>Subtract each list centroid and learn per-dimension
minimum/maximum residual bounds for that list.</li><li>Encode every residual
coordinate to an unsigned byte. Empty training lists use the global residual
bounds.</li><li>At query time, select <code>nprobe</code> lists, load their
sorted row IDs and codes in one multi-range read, scan the codes with SIMD L2
or inner-product kernels, and merge t [...]
+ <ol><li>Train the IVF coarse centroids and assign training vectors
to lists.</li><li>Compute per-dimension residual extrema using partition-local
reductions, then pool them across the training sample. This avoids clipping
unseen vectors to the narrow or constant bounds of sparsely sampled
partitions.</li><li>Encode every residual coordinate to an unsigned byte. New
indexes use pooled residual bounds for every list; existing v1 files retain
their recorded per-list bounds.</li><l [...]
<p>Cosine input is normalized through the shared metric
preprocessing path. Filters are checked while scanning, so excluded rows do not
enter the top-K heap.</p>
</section>
<section class="article-section" id="usage">
@@ -48,29 +49,42 @@ let params = VectorSearchParams::new(10,
16);</code></pre></div>
<h2>Stable v1 storage</h2>
<div class="storage-map" aria-label="IVF-SQ file layout"><div
class="storage-block primary"><strong>64 B header</strong>IVSQ v1</div><div
class="storage-block"><strong>Global bounds</strong><code>2 × d ×
f32</code></div><div class="storage-block"><strong>Per-list
bounds</strong><code>2 × nlist × d × f32</code></div><div
class="storage-block"><strong>IVF centers</strong><code>nlist × d ×
f32</code></div><div class="storage-block"><strong>Offset
table</strong><code>nlist × 16 B</ [...]
<p>Every non-empty list is sorted by signed row ID before writing.
Codes come first and are transposed within up-to-32-row blocks, with dimension
before row lane, so SIMD evaluates multiple candidates together and the reader
scans directly from the list payload allocation. The trailing IDs use the
shared delta-varint encoding and remain aligned with code lanes. The normative
byte layout and golden fixture are in the <a
href="../core/STORAGE_FORMAT.md#ivf-sq-v1">storage-format s [...]
+ <div class="callout"><strong>Upgrading existing indexes</strong>The
header, flags, code layout, and row-ID encoding remain IVSQ v1. Existing files
gain the reader optimizations without rebuilding and keep their recorded
quantization bounds. Retrain and rebuild to obtain pooled bounds and their
measured recall improvement. New files store the pooled bounds in the existing
per-list metadata fields.</div>
</section>
<section class="article-section" id="comparison">
<h2>Open-source comparison</h2>
- <p><a
href="https://github.com/facebookresearch/faiss/blob/main/faiss/IndexScalarQuantizer.cpp";>Faiss
IVF-SQ</a> provides residual SQ4/SQ6/SQ8/F16 encodings, parallel add, and
query-parallel scanning over generic inverted lists. <a
href="https://github.com/zilliztech/knowhere/blob/main/thirdparty/faiss/faiss/cppcontrib/knowhere/IndexIVFScalarQuantizerCC.cpp";>Milvus
Knowhere</a> builds on the same scanner model and adds concurrent
inverted-list mutation. This implementation deli [...]
- <p>The comparison did produce two build changes: non-cosine inputs
are borrowed instead of copied, and assigned lists are encoded in parallel with
one reusable residual vector per worker. It did not justify changing the
persisted layout. SQ4/SQ6 would overlap IVF-PQ/RQ, quantile clipping would
introduce another corpus-sensitive accuracy parameter, and compressing the
relatively small resident bounds would save little beside the <code>N ×
d</code> code payload. The existing code [...]
+ <p><a
href="https://github.com/facebookresearch/faiss/blob/main/faiss/IndexScalarQuantizer.cpp";>Faiss
IVF-SQ</a> provides residual SQ4/SQ6/SQ8/F16 encodings, parallel add, and
query-parallel scanning over generic inverted lists. <a
href="https://github.com/zilliztech/knowhere/blob/main/thirdparty/faiss/faiss/cppcontrib/knowhere/IndexIVFScalarQuantizerCC.cpp";>Milvus
Knowhere</a> builds on the same scanner model and adds concurrent
inverted-list mutation. This implementation deli [...]
+ <p>Non-cosine inputs are borrowed, residual extrema are reduced in
parallel without a training residual matrix, and assigned rows are encoded
directly with precomputed scales and packed NEON/AVX2 conversion. The persisted
layout is unchanged. SQ4/SQ6 would overlap IVF-PQ/RQ, quantile clipping would
introduce another corpus-sensitive accuracy parameter, and compressing the
relatively small resident bounds would save little beside the <code>N ×
d</code> code payload. The existing [...]
</section>
<section class="article-section" id="io">
<h2>I/O and batching</h2>
- <p>Open reads the fixed header and contiguous resident metadata in
two positional operations; the outer type dispatcher adds one small magic read.
A query submits selected list ranges through the abstract positional-read
interface in capability- and 64 MiB-bounded multi-range batches. SIFT1M and
GloVe-100 use one payload round per query at <code>nprobe=64</code>;
960-dimensional GIST1M averages 1.9. Batch search first deduplicates the lists
selected across queries, loads each u [...]
- <p>The add path retains the caller's L2/IP slice without copying it,
partitions assigned row positions by list, and encodes those lists in parallel.
Each active list task reuses one <code>d</code>-component residual buffer and
one code buffer; the add path never materializes an <code>N × d</code> residual
matrix. The writer retains only each list's row-order permutation and encoded
IDs. It generates one list's blocked codes directly from the in-memory
row-major codes, writes th [...]
- <p>During scanning, a candidate whose distance cannot improve a full
Top-K heap is rejected before row-ID hashing. Batch remains query-parallel
after a measured list-major experiment regressed SIFT/GIST throughput; list
payloads are still deduplicated and read once.</p>
- <p>IVF-SQ still reads complete selected lists. At high
<code>nprobe</code>, scan bytes grow linearly; DiskANN is the better fit when
the workload requires small page-granular reads from a large local-SSD
index.</p>
+ <p>Open reads the fixed header and contiguous resident metadata in
two positional operations; the unified type dispatcher reuses that header. On a
cache miss, a query submits selected list ranges through the abstract
positional-read interface in capability- and 64 MiB-bounded multi-range
batches. The historical uncached measurements below use one payload round per
query for SIFT1M and GloVe-100 at <code>nprobe=64</code>; GIST1M averages 1.9.
Batch search first deduplicates the [...]
+ <p>The add path retains the caller's L2/IP slice without copying it,
partitions assigned row positions by list, and encodes those lists in parallel.
Each active list task precomputes one <code>d</code>-component scale vector and
fuses residual subtraction with quantization directly into the destination
codes; the add path never materializes an <code>N × d</code> residual matrix.
The writer retains only each list's row-order permutation and encoded IDs. It
transposes lists in pa [...]
+ <p>During scanning, a candidate whose distance cannot improve a full
Top-K heap is rejected before row-ID hashing. Batch scanning keeps one heap per
query across loaded lists, avoiding per-list heaps and result merging. L2 scans
may reject a complete 32-row block when its nonnegative partial distances
cannot improve the current heap; returned candidates retain their complete
distances. Single-query batches use the ordinary partition-parallel search
path.</p>
+ <p><code>VectorIndexReader::open</code>,
<code>open_with_options</code>, and the language bindings use the reader memory
budget (4 GiB by default) for a FIFO cache of decoded partitions. Resident
metadata, cache slots, queue storage, and retained payload capacities are
charged before insertion. Hits share immutable payloads without copying or
positional I/O; filters and scores remain query-local. Oversized streamed lists
bypass the cache. Zero budget disables caching, while req [...]
+ <p>Populate the cache by replaying representative queries through
<code>search</code> or <code>search_batch</code>. For IVF-SQ,
<code>optimize_for_search</code> and <code>warmup_queries</code> only ensure
resident metadata is loaded; they do not prefetch partitions.</p>
+ <p>On cache misses, IVF-SQ still reads complete selected lists. At
high <code>nprobe</code>, scan bytes grow linearly; DiskANN is the better fit
when the workload requires small page-granular reads from a large local-SSD
index.</p>
</section>
<section class="article-section" id="benchmarks">
<h2>Public benchmarks</h2>
- <p>On the documented Apple M4 Pro run with one million-scale public
vectors, <code>nlist=1024</code>, <code>nprobe=64</code>, <code>k=10</code>,
and 12 Rayon workers:</p>
+ <h3>September 2026: optimization results</h3>
+ <p>Three-run native <code>ann_bench</code> medians on Apple M4 Pro
(12 CPU cores, 48 GiB RAM), with Rust 1.95 release builds, eight workers,
<code>nlist=1024</code>, <code>nprobe=64</code>, <code>k=10</code>, 65,536
training rows, and 1,000 held-out public queries. Baseline commit
<code>8dcabf2</code> and the current implementation use the same input files
and settings; GloVe is L2-normalized.</p>
+ <p>Values show baseline → current. Build time includes training,
encoding, and serialization. Sequential queries can reuse earlier partitions
with the current 4 GiB reader budget; batch timing uses a separate fresh reader
and includes payload reads and cache insertion. The baseline reader does not
cache SQ partitions.</p>
+ <div class="table-wrap"><table><thead><tr><th>Corpus</th><th>Index
build (ms)</th><th>Query P95 (µs)</th><th>Batch
QPS</th><th>Recall@10</th></tr></thead><tbody>
+ <tr><td>SIFT1M</td><td>934 → 886</td><td>840 → 298</td><td>6,417 →
8,987</td><td>0.8626 → 0.9811</td></tr>
+ <tr><td>GIST1M</td><td>6,404 → 5,850</td><td>4,386 →
1,828</td><td>899 → 998</td><td>0.8576 → 0.9400</td></tr>
+ <tr><td>GloVe-100</td><td>849 → 797</td><td>739 → 282</td><td>6,988
→ 10,009</td><td>0.8036 → 0.8760</td></tr>
+ </tbody></table></div>
+ <p>File sizes are unchanged. These warm local-filesystem
measurements do not establish performance on cold storage, object stores, or
other architectures and distributions. Pooled bounds can lose resolution on
extreme-outlier data. See the <a
href="development.html#ivfsq-bench">reproduction guide</a> and the <a
href="index.html#build-results">current build and local-search tables</a>.</p>
+ <h3 id="historical-benchmarks">Historical uncached
implementation</h3>
+ <p>The following measurements predate pooled bounds and partition
caching. They use <code>nlist=1024</code>, <code>nprobe=64</code>,
<code>k=10</code>, and 12 Rayon workers on Apple M4 Pro. Keep them separate
from the current eight-worker comparison above, which now includes a GIST
rerun.</p>
<div
class="table-wrap"><table><thead><tr><th>Dataset</th><th>Recall@10</th><th>Build
/ peak RSS</th><th>Warm P95 / batch
QPS</th><th>Read/query</th></tr></thead><tbody><tr><td>SIFT1M</td><td>0.8627</td><td>3.93
s / 0.79 GiB</td><td>0.79 ms / 11,082</td><td>8.38
MiB</td></tr><tr><td>GIST1M</td><td>0.8577</td><td>22.7 s / 5.09
GiB</td><td>3.56 ms / 1,502</td><td>70.95
MiB</td></tr><tr><td>GloVe-100</td><td>0.8036</td><td>3.86 s / 0.71
GiB</td><td>0.71 ms / 12,962</td><td>6.99 Mi [...]
<p>Compared with the immediately preceding implementation on the
same files, peak RSS dropped by 56–61%, local P95 improved by 3–8%, and batch
throughput improved by about 8–61%, depending on dimension and cache behavior.
File bytes and read bytes are unchanged.</p>
<nav class="pager" aria-label="Index navigation"><a
href="ivf-rq.html"><small>Previous</small>← IVF-RQ</a><a
href="diskann.html"><small>Next</small>DiskANN →</a></nav>
</section>
</article>
</div>
- </main>
+ </div></main>
<footer class="site-footer"><div class="footer-inner"><span>Apache Paimon
Vector Index</span><span>IVF-SQ · v1</span></div></footer>
</body>
</html>
diff --git a/docs/releases.html b/docs/releases.html
index a45d83e..75598c0 100644
--- a/docs/releases.html
+++ b/docs/releases.html
@@ -49,6 +49,8 @@
<section class="article-section" id="upcoming">
<h2>Upcoming: 0.5.0</h2>
<p>The repository is currently developing the 0.5.0 line. Until an
ASF vote passes and the signed source archive appears under Apache downloads,
code and packages from this line are development artifacts rather than an
Apache release.</p>
+ <p>IVF-SQ now pools residual training bounds, fuses residual
encoding, transposes output in bounded parallel batches, and reuses query heaps
with conservative L2 block pruning. Unified readers and language bindings also
cache decoded partitions within the existing reader memory budget. The <a
href="ivf-sq.html#benchmarks">SIFT1M/GIST1M/GloVe benchmarks</a> record build,
native query, and recall results with reproducible commands.</p>
+ <p>IVSQ v1 files remain compatible. Existing indexes receive reader
optimizations without a rebuild; retrain and rebuild to use the new
quantization bounds. Set the reader memory budget to zero to disable the SQ
cache; direct Rust <code>IVFSQIndexReader::open</code> remains uncached. See <a
href="api.html#reader-options">reader options</a> and <a
href="ivf-sq.html#storage">upgrade details</a>.</p>
<div class="callout warning"><strong>Rust IVF API
migration</strong>Version 0.5.0 makes <code>quantizer_centroids</code> private
on <code>IVFFlatIndex</code>, <code>IVFPQIndex</code>, <code>IVFSQIndex</code>,
and <code>IVFRQIndex</code>. Replace direct reads with
<code>quantizer_centroids()</code> and direct assignments with
<code>set_quantizer_centroids(...)</code>. The setter validates the centroid
shape, rejects replacement after vectors are added, and refreshes cached deriv
[...]
</section>
