Skip to main content

mnemo_engine/
index.rs

1//! IVF + PQ approximate-nearest-neighbour index (Phase 2 of the build plan).
2//!
3//! Exact search is `O(n)`. This module makes retrieval sub-linear:
4//!
5//! 1. **IVF** (inverted file): vectors are grouped into roughly `√n`
6//!    partitions by k-means. A query scans only the `n_probe` partitions
7//!    whose centroids are nearest to it.
8//! 2. **PQ** (product quantization): each vector is cut into `m` contiguous
9//!    subspaces; every subspace is quantized to one of up to 256 learned
10//!    codewords, so a whole vector collapses to `m` bytes. Candidate
11//!    distances are summed from precomputed per-subspace lookup tables — the
12//!    scan never touches a full float vector.
13//! 3. **Rerank**: the `n_rerank` closest candidates by PQ distance are
14//!    returned to the store, which loads their exact vectors for final,
15//!    precise ranking.
16//!
17//! All distances *inside* the index are squared-L2. The index only has to
18//! produce a good candidate *set*; the store reranks with the caller's actual
19//! metric (cosine / dot / L2). For embedding vectors — which tend to have
20//! similar norms — L2-nearest and cosine-nearest largely agree, and a
21//! generous `n_rerank` absorbs the rest.
22
23use rand::rngs::StdRng;
24use rand::seq::SliceRandom;
25use rand::{Rng, SeedableRng};
26use serde::{Deserialize, Serialize};
27
28use crate::error::{MnemoError, Result};
29
30/// Slot marker for an empty [`U128Map`] slot (values are partition or row
31/// numbers, so `u32::MAX` is never a real value).
32const VACANT: u32 = u32::MAX;
33
34/// Home slot of a ULID (or any `u128` id) in a table of `cap` slots.
35/// ULIDs carry 80 random low bits, so folding the halves and a
36/// multiplicative mix is enough; the high bits of `hash * cap` then pick
37/// the slot, so `cap` needn't be a power of two (a power-of-two table at
38/// <= 3/4 load can sit at 3/8, doubling its size for nothing).
39pub(crate) fn slot_home(k: u128, cap: usize) -> usize {
40    let x = (k as u64) ^ ((k >> 64) as u64).rotate_left(29);
41    let h = x.wrapping_mul(0x9E37_79B9_7F4A_7C15);
42    ((h as u128 * cap as u128) >> 64) as usize
43}
44
45/// The slot after `i`, wrapping at `cap`.
46pub(crate) fn next_slot(i: usize, cap: usize) -> usize {
47    if i + 1 == cap {
48        0
49    } else {
50        i + 1
51    }
52}
53
54/// Forward distance from slot `from` to slot `to`, wrapping at `cap`.
55fn cyclic_dist(from: usize, to: usize, cap: usize) -> usize {
56    if to >= from {
57        to - from
58    } else {
59        to + cap - from
60    }
61}
62
63/// Slot count that holds `n` entries at <= 3/4 load.
64pub(crate) fn table_capacity_for(n: usize) -> usize {
65    (n * 4 / 3 + 1).max(16)
66}
67
68/// PERF-1 step 4: a compact `u128 → u32` map (linear probing,
69/// backward-shift deletion) for the ANN's id → partition assignment. It
70/// takes 20 bytes a slot at <= 3/4 load, about 27 bytes an entry, against
71/// about 43 for `HashMap<u128, usize>` (whose 32-byte, 16-aligned slots
72/// dominate).
73#[derive(Clone, Debug, Default)]
74pub(crate) struct U128Map {
75    keys: Vec<u128>,
76    vals: Vec<u32>,
77    len: usize,
78}
79
80impl U128Map {
81    pub(crate) fn with_capacity(n: usize) -> Self {
82        let mut m = Self::default();
83        m.resize(table_capacity_for(n));
84        m
85    }
86
87    fn resize(&mut self, cap: usize) {
88        let keys = std::mem::replace(&mut self.keys, vec![0; cap]);
89        let vals = std::mem::replace(&mut self.vals, vec![VACANT; cap]);
90        self.len = 0;
91        for (k, v) in keys.into_iter().zip(vals) {
92            if v != VACANT {
93                self.insert(k, v);
94            }
95        }
96    }
97
98    fn find(&self, k: u128) -> Option<usize> {
99        if self.vals.is_empty() {
100            return None;
101        }
102        let cap = self.vals.len();
103        let mut i = slot_home(k, cap);
104        loop {
105            if self.vals[i] == VACANT {
106                return None;
107            }
108            if self.keys[i] == k {
109                return Some(i);
110            }
111            i = next_slot(i, cap);
112        }
113    }
114
115    #[cfg(test)]
116    pub(crate) fn get(&self, k: u128) -> Option<u32> {
117        self.find(k).map(|i| self.vals[i])
118    }
119
120    pub(crate) fn contains_key(&self, k: u128) -> bool {
121        self.find(k).is_some()
122    }
123
124    pub(crate) fn insert(&mut self, k: u128, v: u32) {
125        debug_assert_ne!(v, VACANT);
126        if (self.len + 1) * 4 > self.vals.len() * 3 {
127            let cap = (self.vals.len() * 2).max(table_capacity_for(self.len + 1));
128            self.resize(cap);
129        }
130        let cap = self.vals.len();
131        let mut i = slot_home(k, cap);
132        loop {
133            if self.vals[i] == VACANT {
134                self.keys[i] = k;
135                self.vals[i] = v;
136                self.len += 1;
137                return;
138            }
139            if self.keys[i] == k {
140                self.vals[i] = v;
141                return;
142            }
143            i = next_slot(i, cap);
144        }
145    }
146
147    pub(crate) fn remove(&mut self, k: u128) -> Option<u32> {
148        let i = self.find(k)?;
149        let out = self.vals[i];
150        let cap = self.vals.len();
151        // Backward-shift: pull later entries of the probe run into the
152        // hole when the hole lies on their path from home.
153        let mut hole = i;
154        let mut j = i;
155        loop {
156            j = next_slot(j, cap);
157            if self.vals[j] == VACANT {
158                break;
159            }
160            let home = slot_home(self.keys[j], cap);
161            let from_home = cyclic_dist(home, j, cap);
162            let from_hole = cyclic_dist(hole, j, cap);
163            if from_home >= from_hole {
164                self.keys[hole] = self.keys[j];
165                self.vals[hole] = self.vals[j];
166                hole = j;
167            }
168        }
169        self.vals[hole] = VACANT;
170        self.len -= 1;
171        Some(out)
172    }
173
174    #[cfg(test)]
175    pub(crate) fn len(&self) -> usize {
176        self.len
177    }
178
179    /// Heap bytes held by the two slot arrays.
180    #[cfg(feature = "dev-hooks")]
181    pub(crate) fn heap_bytes(&self) -> usize {
182        self.keys.capacity() * std::mem::size_of::<u128>()
183            + self.vals.capacity() * std::mem::size_of::<u32>()
184    }
185}
186
187/// Estimated heap bytes of a `HashMap<K, V>` with the given capacity:
188/// one `(K, V)` slot plus one control byte per bucket, with buckets
189/// rounded up from capacity at the 7/8 load factor. An estimate for the
190/// P-0 device budget, not an exact allocator figure.
191#[cfg(feature = "dev-hooks")]
192pub(crate) fn hash_map_bytes<K, V>(capacity: usize) -> usize {
193    if capacity == 0 {
194        return 0;
195    }
196    let buckets = (capacity * 8 / 7).next_power_of_two();
197    buckets * (std::mem::size_of::<(K, V)>() + 1)
198}
199
200/// Default RNG seed — fixed so index builds are reproducible.
201const DEFAULT_SEED: u64 = 0x4d_4e_45_4d_4f_49_44_58; // "MNEMOIDX"
202/// Training-set cap: k-means trains on at most this many sampled vectors.
203const TRAIN_CAP: usize = 50_000;
204/// Codewords per PQ subspace.
205const PQ_CODEWORDS: usize = 256;
206
207/// Tuning knobs for building and querying an [`IvfPqIndex`].
208#[derive(Clone, Copy, Debug)]
209pub struct IndexConfig {
210    /// Number of IVF partitions. `0` means auto (`ceil(√n)`).
211    pub n_partitions: usize,
212    /// Number of PQ subspaces. `0` means auto (`dims / 4`). Previously
213    /// `dims / 8` before PR ANN-1 — see [`IndexConfig::default`] for
214    /// why the bump.
215    pub pq_subspaces: usize,
216    /// Partitions scanned per query (the IVF accuracy/speed dial).
217    /// `0` means auto (`ceil(partitions / 2)`). Previously a fixed `8`
218    /// before PR ANN-1.
219    pub n_probe: usize,
220    /// Candidates handed back for exact reranking (the PQ accuracy dial).
221    /// `0` means auto (`500`). Previously a fixed `64` before PR ANN-1.
222    pub n_rerank: usize,
223    /// Lloyd-iteration count for every k-means run.
224    pub kmeans_iters: usize,
225    /// RNG seed for reproducible builds.
226    pub seed: u64,
227}
228
229/// Auto-pick `n_probe` from the IVF partition count.
230///
231/// Formula: `max(ceil(partitions / 2), min(partitions, 100))`.
232///
233/// Full probe up to 100 partitions (so ~10K / √10K ≈ 100 corpora
234/// clear the 0.95 recall@10 target — ANN-1.1 measured 0.964 at
235/// n_probe=100 + n_rerank=100 vs 0.914 at n_probe=50), half probe
236/// above. At the three measured tiers:
237///
238/// - 10K   ≈ 100 partitions  → 100 (full)
239/// - 100K  ≈ 317 partitions  → 159 (half, from ceil(317/2))
240/// - 1M    ≈ 1000 partitions → 500 (half)
241///
242/// Query latency scales linearly with `n_probe` (and therefore with
243/// `n_partitions * fraction_probed`); see `ann_defaults_v0_6_0` in
244/// `test/scripts/perf_v0.5.0.json` for the measured per-tier numbers.
245pub(crate) fn effective_auto_n_probe(partitions: usize) -> usize {
246    let half = partitions.div_ceil(2);
247    let full_up_to_100 = partitions.min(100);
248    half.max(full_up_to_100).max(1)
249}
250
251/// Auto-pick `n_rerank` from the live vector count.
252///
253/// Formula: `(n_vectors / 200).clamp(100, 1000)`. Hits the planner's
254/// ANN-1.1 targets exactly:
255///
256/// - 10K vectors  → 50 → clamped to 100 (plenty for ~0.98 recall@10)
257/// - 100K vectors → 500 (matches the ann_recall_grid_v2 knee)
258/// - 1M vectors   → 5000 → clamped to 1000 (keeps latency bounded;
259///   recall at 1M is "measure in Phase 11.1" per the planner)
260///
261/// Pre-ANN-1.1 the default was a fixed 500 at every size, which cost
262/// ~5 ms of record-decode time on 10K files for no recall gain over
263/// 100 — rerank is bounded by exact decrypt-and-score cost (~10 µs
264/// per candidate on hardware AES).
265pub(crate) fn effective_auto_n_rerank(n_vectors: usize) -> usize {
266    (n_vectors / 200).clamp(100, 1000)
267}
268
269impl Default for IndexConfig {
270    fn default() -> Self {
271        // All four of n_partitions / pq_subspaces / n_probe / n_rerank
272        // default to 0, which [`IvfPqIndex::build`] interprets as "pick
273        // a sensible value from the corpus and partition count":
274        //
275        // - n_partitions → `ceil(sqrt(n))`
276        // - pq_subspaces → `dims/4` (384-dim → 96 subspaces).
277        //   Previously `dims/8` (48); PR ANN-1 bumped it after the
278        //   ann_recall_grid_v2 harness showed that 48 subspaces capped
279        //   100K recall@10 at ~0.92 even with the full-scan rerank,
280        //   while 96 subspaces lifts the knee to 0.98 at ~10 ms/query
281        //   on an M1. Costs 2x the PQ codes per vector (48 → 96 bytes,
282        //   negligible against the 1.5 KB raw vector) and ~15 % more
283        //   build time.
284        // - n_probe → `ceil(partitions / 2)` (ANN-1) — scales with
285        //   partition count. Previously fixed at 8, which at 317
286        //   partitions scanned 2.5 % of the index per query. The
287        //   planner's "express relative to index size" clause.
288        // - n_rerank → `(n_vectors / 200).clamp(100, 1000)` (ANN-1.1).
289        //   10K files land on 100 rerank (plenty for ~0.98 recall@10
290        //   on this corpus); 100K lands on 500 (the measured
291        //   ann_recall_grid_v2 knee); 1M caps at 1000. ANN-1 shipped a
292        //   fixed 500 at every size, which cost ~5 ms of record-decode
293        //   time on small files for no recall gain. Still fixed per
294        //   build if explicit; computed per query from the live vector
295        //   count when auto.
296        //
297        // Explicit non-zero values still override, so callers who want
298        // the old tiny defaults can set them (useful for very small
299        // corpora where sqrt(n) partitions is overkill).
300        Self {
301            n_partitions: 0,
302            pq_subspaces: 0,
303            n_probe: 0,
304            n_rerank: 0,
305            kmeans_iters: 25,
306            seed: DEFAULT_SEED,
307        }
308    }
309}
310
311/// A read-only snapshot of an index's shape, surfaced via `Mnemo::stats`.
312///
313/// `Serialize`/`Deserialize` derived so the MCP `stats` tool (and any
314/// other JSON-shaped consumer) can emit / round-trip it without a
315/// per-field object build. Plain-old-data type — no invariants to
316/// preserve across (de)serialization.
317#[derive(Clone, Copy, Debug, Serialize, Deserialize)]
318pub struct IndexInfo {
319    /// Vectors currently held in the index.
320    pub vectors: usize,
321    /// IVF partition count.
322    pub partitions: usize,
323    /// PQ subspace count.
324    pub subspaces: usize,
325    /// Default partitions probed per query.
326    pub n_probe: usize,
327    /// Default candidates reranked per query.
328    pub n_rerank: usize,
329}
330
331/// Squared Euclidean distance between two equal-length vectors.
332fn squared_l2(a: &[f32], b: &[f32]) -> f32 {
333    let mut s = 0.0f32;
334    for i in 0..a.len() {
335        let d = a[i] - b[i];
336        s += d * d;
337    }
338    s
339}
340
341/// Index of the nearest centroid (flat layout, `stride` floats each).
342fn nearest(centroids: &[f32], stride: usize, v: &[f32]) -> usize {
343    let mut best = 0usize;
344    let mut best_d = f32::INFINITY;
345    let count = centroids.len() / stride;
346    for i in 0..count {
347        let d = squared_l2(&centroids[i * stride..(i + 1) * stride], v);
348        if d < best_d {
349            best_d = d;
350            best = i;
351        }
352    }
353    best
354}
355
356/// k-means (k-means++ seeding, Lloyd iterations). Returns a flat
357/// `k * dim` centroid buffer; `k` may shrink to `points.len()`.
358fn kmeans(points: &[&[f32]], k: usize, iters: usize, rng: &mut StdRng) -> Vec<f32> {
359    let n = points.len();
360    let dim = points[0].len();
361    let k = k.clamp(1, n);
362
363    // --- k-means++ seeding ---
364    let mut centroids: Vec<f32> = Vec::with_capacity(k * dim);
365    let first = rng.gen_range(0..n);
366    centroids.extend_from_slice(points[first]);
367    let mut d2: Vec<f32> = points
368        .iter()
369        .map(|p| squared_l2(p, &centroids[0..dim]))
370        .collect();
371
372    while centroids.len() / dim < k {
373        let sum: f32 = d2.iter().sum();
374        let pick = if sum <= 0.0 {
375            rng.gen_range(0..n)
376        } else {
377            let mut t = rng.gen::<f32>() * sum;
378            let mut chosen = n - 1;
379            for (i, &w) in d2.iter().enumerate() {
380                t -= w;
381                if t <= 0.0 {
382                    chosen = i;
383                    break;
384                }
385            }
386            chosen
387        };
388        let base = centroids.len();
389        centroids.extend_from_slice(points[pick]);
390        let new = &centroids[base..base + dim];
391        for (i, p) in points.iter().enumerate() {
392            let nd = squared_l2(p, new);
393            if nd < d2[i] {
394                d2[i] = nd;
395            }
396        }
397    }
398
399    // --- Lloyd iterations ---
400    let kk = centroids.len() / dim;
401    for _ in 0..iters {
402        let mut sums = vec![0.0f32; kk * dim];
403        let mut counts = vec![0usize; kk];
404        for p in points {
405            let a = nearest(&centroids, dim, p);
406            counts[a] += 1;
407            for d in 0..dim {
408                sums[a * dim + d] += p[d];
409            }
410        }
411        for c in 0..kk {
412            if counts[c] == 0 {
413                // Reseed an empty cluster onto a random point.
414                let r = rng.gen_range(0..n);
415                centroids[c * dim..(c + 1) * dim].copy_from_slice(points[r]);
416            } else {
417                let inv = 1.0 / counts[c] as f32;
418                for d in 0..dim {
419                    centroids[c * dim + d] = sums[c * dim + d] * inv;
420                }
421            }
422        }
423    }
424    centroids
425}
426
427/// Product-quantization codebook: one learned set of codewords per subspace.
428#[derive(Serialize, Deserialize, Clone, Debug)]
429struct PqCodebook {
430    /// Subspace boundaries; subspace `s` spans `[sub_offsets[s], sub_offsets[s+1])`.
431    sub_offsets: Vec<usize>,
432    /// Per subspace: a flat `ks[s] * subdim` codeword buffer.
433    centroids: Vec<Vec<f32>>,
434    /// Codeword count per subspace (`≤ 256`, so a code fits in a `u8`).
435    ks: Vec<usize>,
436}
437
438impl PqCodebook {
439    fn m(&self) -> usize {
440        self.sub_offsets.len() - 1
441    }
442
443    /// Train one codebook per subspace on the sampled training vectors.
444    fn train(
445        sub_offsets: &[usize],
446        train: &[&[f32]],
447        iters: usize,
448        rng: &mut StdRng,
449    ) -> PqCodebook {
450        let m = sub_offsets.len() - 1;
451        let mut centroids = Vec::with_capacity(m);
452        let mut ks = Vec::with_capacity(m);
453        for s in 0..m {
454            let (lo, hi) = (sub_offsets[s], sub_offsets[s + 1]);
455            let subs: Vec<Vec<f32>> = train.iter().map(|v| v[lo..hi].to_vec()).collect();
456            let refs: Vec<&[f32]> = subs.iter().map(|x| x.as_slice()).collect();
457            let k = PQ_CODEWORDS.min(refs.len()).max(1);
458            let cs = kmeans(&refs, k, iters, rng);
459            ks.push(cs.len() / (hi - lo));
460            centroids.push(cs);
461        }
462        PqCodebook {
463            sub_offsets: sub_offsets.to_vec(),
464            centroids,
465            ks,
466        }
467    }
468
469    /// Encode a full vector into `m` codeword indices.
470    fn encode(&self, v: &[f32]) -> Vec<u8> {
471        let m = self.m();
472        let mut code = vec![0u8; m];
473        for (s, slot) in code.iter_mut().enumerate().take(m) {
474            let (lo, hi) = (self.sub_offsets[s], self.sub_offsets[s + 1]);
475            *slot = nearest(&self.centroids[s], hi - lo, &v[lo..hi]) as u8;
476        }
477        code
478    }
479
480    /// Precompute, for a query, the distance from each query subspace to every
481    /// codeword. Asymmetric distance = sum of one lookup per subspace.
482    ///
483    /// PERF-1 step 5: one flat buffer with a fixed [`PQ_CODEWORDS`]-entry row
484    /// per subspace (rows of subspaces with fewer codewords are padded and
485    /// never read), so the scan indexes a row with a `u8` code and no bounds
486    /// check, instead of chasing one heap `Vec` per subspace.
487    fn distance_table(&self, q: &[f32]) -> Vec<f32> {
488        let m = self.m();
489        let mut table = vec![0.0f32; m * PQ_CODEWORDS];
490        for (s, row) in table.chunks_exact_mut(PQ_CODEWORDS).enumerate() {
491            let (lo, hi) = (self.sub_offsets[s], self.sub_offsets[s + 1]);
492            let sd = hi - lo;
493            let qs = &q[lo..hi];
494            let cs = &self.centroids[s];
495            for (c, slot) in row.iter_mut().enumerate().take(self.ks[s]) {
496                *slot = squared_l2(qs, &cs[c * sd..(c + 1) * sd]);
497            }
498        }
499        table
500    }
501}
502
503/// Asymmetric (PQ) distance of one code against a query's flat distance
504/// table: one lookup per subspace, summed.
505///
506/// PERF-1 step 5: four named accumulators over 4-subspace blocks instead of
507/// one running sum. A single sum is a chain of `m` dependent float adds (96
508/// at 384 dims), which made this loop latency-bound and about half of a
509/// warm recall at 100K. (An accumulator *array* indexed by `s & 3` was
510/// tried first and ran 2.3x slower than the single chain: it stays in
511/// memory.) Micro-benchmark, 50K codes of 96: 4.0 ms → 1.45 ms. The order
512/// of the additions changes, so the sum can differ in the last bits; it
513/// only ranks the rerank shortlist, and `ann_recall_grid_v2` recall@10 is
514/// unchanged in every cell.
515fn adc_distance(code: &[u8], table: &[f32]) -> f32 {
516    const K: usize = PQ_CODEWORDS;
517    let (mut a0, mut a1, mut a2, mut a3) = (0.0f32, 0.0f32, 0.0f32, 0.0f32);
518    let mut codes = code.chunks_exact(4);
519    let mut rows = table.chunks_exact(4 * K);
520    for (c, r) in (&mut codes).zip(&mut rows) {
521        a0 += r[c[0] as usize];
522        a1 += r[K + c[1] as usize];
523        a2 += r[2 * K + c[2] as usize];
524        a3 += r[3 * K + c[3] as usize];
525    }
526    let done = code.len() / 4 * 4;
527    for (&c, r) in codes
528        .remainder()
529        .iter()
530        .zip(table[done * K..].chunks_exact(K))
531    {
532        a0 += r[c as usize];
533    }
534    (a0 + a1) + (a2 + a3)
535}
536
537/// One IVF partition: parallel arrays of memory IDs and their PQ codes.
538#[derive(Serialize, Deserialize, Clone, Debug, Default)]
539struct Posting {
540    ids: Vec<u128>,
541    /// Flat `ids.len() * m` byte buffer of PQ codes.
542    codes: Vec<u8>,
543}
544
545/// FMT-9c.3: one recorded change to an index: a vector added to a
546/// partition with its PQ code, or an id removed.
547#[derive(Serialize, Deserialize, Clone, Debug, PartialEq)]
548pub(crate) enum IndexOp {
549    Add(u128, u32, Vec<u8>),
550    Remove(u128),
551}
552
553/// An IVF + PQ approximate-nearest-neighbour index over the database's vectors.
554#[derive(Serialize, Deserialize, Clone, Debug)]
555pub struct IvfPqIndex {
556    dims: usize,
557    n_partitions: usize,
558    n_probe: usize,
559    n_rerank: usize,
560    /// Flat `n_partitions * dims` IVF centroid buffer.
561    centroids: Vec<f32>,
562    pq: PqCodebook,
563    partitions: Vec<Posting>,
564    /// `id -> partition`. Reconstructed from `partitions` after load, never
565    /// serialized.
566    #[serde(skip)]
567    assignment: U128Map,
568    /// PERF-2 (v0.19.0): whether `assignment` has been built. A loaded index
569    /// builds it only when a write path needs it ([`Self::ensure_assignment`]),
570    /// so a read-only first recall doesn't pay for it. Never serialized.
571    #[serde(skip)]
572    assignment_ready: bool,
573    /// FMT-9c.3: when `Some`, every change is also recorded here, so a v9
574    /// commit can persist just the changes (a delta run) instead of the
575    /// whole index. Never serialized.
576    #[serde(skip)]
577    log: Option<Vec<IndexOp>>,
578    // Serialized shape is frozen at v0.5.2's: dims, n_partitions,
579    // n_probe, n_rerank, centroids, pq, partitions. Do NOT append new
580    // fields here under the same `format::VERSION` — rmp-serde 1.3.0's
581    // positional decoder rejects extra array elements with
582    // `Error::LengthMismatch`, so appending here would break every
583    // v0.5.x reader that opens a file written by this build. See the
584    // 2026-11-01 R-001.10 standing rule: any shape change on a
585    // persisted struct now requires a version bump + migration, or
586    // goes into `Memory.metadata` under reserved `_mnemo.*` keys.
587    //
588    // The "pre-ANN-1 default sentinel" check that gives v0.5.x-built
589    // indexes the ANN-1 recall fix on upgrade is in
590    // [`Self::effective_defaults`] — a stored (n_probe, n_rerank) of
591    // exactly (8, 64) is treated as "auto" at query time, so the
592    // concrete values stay stored (old readers see something sensible)
593    // but new readers recompute from the live corpus shape.
594}
595
596impl IvfPqIndex {
597    /// Build an index over `items` (`(id, vector)` pairs).
598    pub fn build(dims: usize, items: &[(u128, &[f32])], cfg: IndexConfig) -> Result<IvfPqIndex> {
599        if items.is_empty() {
600            return Err(MnemoError::Invalid(
601                "cannot build an index over an empty database".into(),
602            ));
603        }
604        let n = items.len();
605        let mut rng = StdRng::seed_from_u64(cfg.seed);
606
607        // Training sample (all vectors when small enough).
608        let mut order: Vec<usize> = (0..n).collect();
609        let train_n = TRAIN_CAP.min(n);
610        order.partial_shuffle(&mut rng, train_n);
611        let train: Vec<&[f32]> = order[..train_n].iter().map(|&i| items[i].1).collect();
612
613        // IVF centroids.
614        let n_partitions = if cfg.n_partitions > 0 {
615            cfg.n_partitions
616        } else {
617            (n as f64).sqrt().ceil() as usize
618        }
619        .clamp(1, n);
620        let centroids = kmeans(&train, n_partitions, cfg.kmeans_iters, &mut rng);
621        let n_partitions = centroids.len() / dims;
622
623        // PQ subspaces — split `dims` into `m` near-equal contiguous spans.
624        // The auto-default is `dims/4` (PR ANN-1), where the grid shows
625        // 100K recall@10 clearing 0.98 at the knee. Earlier auto was
626        // `dims/8`; see IndexConfig::default for the trade-off.
627        let m = if cfg.pq_subspaces > 0 {
628            cfg.pq_subspaces
629        } else {
630            (dims / 4).max(1)
631        }
632        .clamp(1, dims);
633        let mut sub_offsets = Vec::with_capacity(m + 1);
634        for s in 0..=m {
635            sub_offsets.push(s * dims / m);
636        }
637        let pq = PqCodebook::train(&sub_offsets, &train, cfg.kmeans_iters, &mut rng);
638
639        // Query-time dials. Zero in cfg means "auto" — resolve to a
640        // concrete value using the formulas, then store that. Old
641        // readers (v0.5.x) see a sensible stored number; new readers
642        // (v0.6.0+) with the live corpus can recompute via
643        // `effective_defaults` on every query. The "stored == (8,64)"
644        // sentinel in `effective_defaults` is what lets v0.5.x-built
645        // files pick up the fix on upgrade without a rebuild.
646        let n_probe = if cfg.n_probe > 0 {
647            cfg.n_probe
648        } else {
649            effective_auto_n_probe(n_partitions)
650        };
651        let n_rerank = if cfg.n_rerank > 0 {
652            cfg.n_rerank
653        } else {
654            effective_auto_n_rerank(items.len())
655        };
656
657        let mut index = IvfPqIndex {
658            dims,
659            n_partitions,
660            n_probe: n_probe.max(1),
661            n_rerank: n_rerank.max(1),
662            centroids,
663            pq,
664            partitions: vec![Posting::default(); n_partitions],
665            assignment: U128Map::with_capacity(n),
666            assignment_ready: true,
667            log: None,
668        };
669        for &(id, v) in items {
670            index.add(id, v);
671        }
672        Ok(index)
673    }
674
675    /// Default `n_probe` / `n_rerank` to apply when the caller passes
676    /// `None` on a [`crate::RecallRequest`] — i.e. the user hasn't
677    /// explicitly overridden the dials for this query.
678    ///
679    /// Returns the auto-computed `(n_probe, n_rerank)` from the live
680    /// partition count + vector count when the stored pair is exactly
681    /// **`(8, 64)`** — the pre-ANN-1 fixed defaults every v0.5.x build
682    /// stamped in automatically. That's how an upgraded v0.5.x index
683    /// picks up the ANN-1 recall fix without a rebuild.
684    ///
685    /// Otherwise returns the stored `(self.n_probe, self.n_rerank)`
686    /// verbatim — the user picked these at build time and still means
687    /// them.
688    ///
689    /// New v0.6.0+ builds store the resolved auto values directly, so
690    /// a fresh build never hits the sentinel path. The sentinel is
691    /// pre-ANN-1-only.
692    ///
693    /// Note: a user who explicitly built with `IndexConfig { n_probe: 8,
694    /// n_rerank: 64, .. }` on v0.6.0+ will see their values treated as
695    /// "legacy auto" instead of pinned. That's acceptable — the ANN-1
696    /// auto formulas at very small N (10K / 100 partitions / 20K vectors)
697    /// also pick n_probe near 8 and n_rerank clamped to 100, so the
698    /// override is self-cancelling in the one regime where it matters.
699    /// Pin to any other non-legacy value to opt out explicitly.
700    pub(crate) fn effective_defaults(&self) -> (usize, usize) {
701        if self.n_probe == 8 && self.n_rerank == 64 {
702            (
703                effective_auto_n_probe(self.n_partitions),
704                effective_auto_n_rerank(self.len()),
705            )
706        } else {
707            (self.n_probe, self.n_rerank)
708        }
709    }
710
711    /// Embedding dimensionality the index was built for.
712    pub fn dims(&self) -> usize {
713        self.dims
714    }
715
716    /// Total vectors currently indexed.
717    pub fn len(&self) -> usize {
718        self.partitions.iter().map(|p| p.ids.len()).sum()
719    }
720
721    /// Whether `id` is indexed.
722    pub(crate) fn contains(&mut self, id: u128) -> bool {
723        self.ensure_assignment();
724        self.assignment.contains_key(id)
725    }
726
727    /// Every indexed id (PERF-1 reconcile).
728    pub(crate) fn ids(&self) -> impl Iterator<Item = u128> + '_ {
729        self.partitions.iter().flat_map(|p| p.ids.iter().copied())
730    }
731
732    /// Heap bytes held by the index, by part (P-0 device budget). Counts
733    /// buffer capacities; the hash map is estimated from its capacity.
734    /// Returns `(coarse_centroids, pq_codebook, posting_ids, posting_codes,
735    /// assignment_map)`.
736    #[cfg(feature = "dev-hooks")]
737    pub(crate) fn heap_bytes(&self) -> (usize, usize, usize, usize, usize) {
738        let f32s = std::mem::size_of::<f32>();
739        let centroids = self.centroids.capacity() * f32s;
740        let codebook = self
741            .pq
742            .centroids
743            .iter()
744            .map(|c| c.capacity() * f32s)
745            .sum::<usize>()
746            + self.pq.sub_offsets.capacity() * std::mem::size_of::<usize>()
747            + self.pq.ks.capacity() * std::mem::size_of::<usize>();
748        let ids = self
749            .partitions
750            .iter()
751            .map(|p| p.ids.capacity() * std::mem::size_of::<u128>())
752            .sum();
753        let codes = self.partitions.iter().map(|p| p.codes.capacity()).sum();
754        let assignment = self.assignment.heap_bytes();
755        (centroids, codebook, ids, codes, assignment)
756    }
757
758    /// Shape snapshot for statistics.
759    ///
760    /// `n_probe` / `n_rerank` here are the **effective** values that
761    /// queries actually use (after the ANN-1.1 "stored (8,64) == auto"
762    /// shim via [`Self::effective_defaults`]), not the raw stored
763    /// numbers. That's what `mnemo info`, `db.stats()` and the MCP
764    /// `stats` tool report, so an upgraded v0.5.x file shows the
765    /// larger auto values it actually searches with — not the 8/64
766    /// baked into the serialized index.
767    pub fn info(&self) -> IndexInfo {
768        let (eff_probe, eff_rerank) = self.effective_defaults();
769        IndexInfo {
770            vectors: self.len(),
771            partitions: self.n_partitions,
772            subspaces: self.pq.m(),
773            n_probe: eff_probe,
774            n_rerank: eff_rerank,
775        }
776    }
777
778    /// Rebuild the `id -> partition` map from the posting lists. Called once
779    /// after the index is deserialized (the map itself is not stored).
780    pub fn rebuild_assignment(&mut self) {
781        let n = self.partitions.iter().map(|p| p.ids.len()).sum();
782        self.assignment = U128Map::with_capacity(n);
783        for (pi, p) in self.partitions.iter().enumerate() {
784            for &id in &p.ids {
785                self.assignment.insert(id, pi as u32);
786            }
787        }
788        self.assignment_ready = true;
789    }
790
791    /// PERF-2 (v0.19.0): build the `id -> partition` map if it isn't yet:
792    /// before any change, and before `contains`.
793    pub(crate) fn ensure_assignment(&mut self) {
794        if !self.assignment_ready {
795            self.rebuild_assignment();
796        }
797    }
798
799    fn nearest_centroid(&self, v: &[f32]) -> usize {
800        nearest(&self.centroids, self.dims, v)
801    }
802
803    /// Insert or overwrite a vector. The PQ codebook and IVF centroids are
804    /// fixed at build time; only posting lists grow. This keeps the index
805    /// complete across inserts without a full rebuild — cluster drift is the
806    /// price, repaid by `Mnemo::rebuild_index` / `compact`.
807    pub fn add(&mut self, id: u128, vector: &[f32]) {
808        self.remove(id);
809        let part = self.nearest_centroid(vector);
810        let code = self.pq.encode(vector);
811        if let Some(log) = &mut self.log {
812            log.push(IndexOp::Add(id, part as u32, code.clone()));
813        }
814        let p = &mut self.partitions[part];
815        p.ids.push(id);
816        p.codes.extend_from_slice(&code);
817        self.assignment.insert(id, part as u32);
818    }
819
820    /// Remove a vector if present (no-op otherwise).
821    pub fn remove(&mut self, id: u128) {
822        self.ensure_assignment();
823        if self.assignment.contains_key(id) {
824            if let Some(log) = &mut self.log {
825                log.push(IndexOp::Remove(id));
826            }
827        }
828        if let Some(part) = self.assignment.remove(id) {
829            let m = self.pq.m();
830            let p = &mut self.partitions[part as usize];
831            if let Some(pos) = p.ids.iter().position(|&x| x == id) {
832                p.ids.remove(pos);
833                p.codes.drain(pos * m..(pos + 1) * m);
834            }
835        }
836    }
837
838    /// FMT-9c.3: start recording changes (see [`IndexOp`]).
839    pub(crate) fn enable_log(&mut self) {
840        if self.log.is_none() {
841            self.log = Some(Vec::new());
842        }
843    }
844
845    /// FMT-9c.3: the changes recorded since the last call.
846    pub(crate) fn take_log(&mut self) -> Vec<IndexOp> {
847        self.log.as_mut().map(std::mem::take).unwrap_or_default()
848    }
849
850    /// FMT-9c.3: replay recorded changes (a delta run) onto a loaded
851    /// index. Not recorded again. A change that doesn't fit this index
852    /// (a partition or code length out of range) is an error.
853    pub(crate) fn apply_ops(&mut self, ops: Vec<IndexOp>) -> Result<()> {
854        if !ops.is_empty() {
855            self.ensure_assignment();
856        }
857        let log = self.log.take();
858        let m = self.pq.m();
859        let mut res = Ok(());
860        for op in ops {
861            match op {
862                IndexOp::Add(id, part, code) => {
863                    if part as usize >= self.n_partitions || code.len() != m {
864                        res = Err(MnemoError::Invalid(
865                            "index delta does not fit the index".into(),
866                        ));
867                        break;
868                    }
869                    self.remove(id);
870                    let p = &mut self.partitions[part as usize];
871                    p.ids.push(id);
872                    p.codes.extend_from_slice(&code);
873                    self.assignment.insert(id, part);
874                }
875                IndexOp::Remove(id) => self.remove(id),
876            }
877        }
878        self.log = log;
879        res
880    }
881
882    /// Run the tiered query: IVF probe → PQ scan → top-`n_rerank` candidates.
883    /// Returns candidate IDs (nearest first by PQ distance) for the store to
884    /// rerank exactly.
885    ///
886    /// `n_probe` / `n_rerank` of `None` fall through to
887    /// [`Self::effective_defaults`] — which recomputes from the live
888    /// partition / vector count when the index is auto-flagged (ANN-1.1
889    /// in v0.6.0+) or carries the legacy pre-ANN-1 defaults (8, 64).
890    /// Any explicit value is honored verbatim.
891    pub fn query(&self, q: &[f32], n_probe: Option<usize>, n_rerank: Option<usize>) -> Vec<u128> {
892        let (auto_probe, auto_rerank) = self.effective_defaults();
893        let n_probe = n_probe.unwrap_or(auto_probe).clamp(1, self.n_partitions);
894        let n_rerank = n_rerank.unwrap_or(auto_rerank).max(1);
895
896        // Stage 1 — pick the nearest partitions.
897        let mut parts: Vec<(usize, f32)> = (0..self.n_partitions)
898            .map(|i| {
899                let c = &self.centroids[i * self.dims..(i + 1) * self.dims];
900                (i, squared_l2(q, c))
901            })
902            .collect();
903        parts.sort_by(|a, b| a.1.total_cmp(&b.1));
904        parts.truncate(n_probe);
905
906        // Stage 2 — scan PQ codes in the selected partitions.
907        let table = self.pq.distance_table(q);
908        let m = self.pq.m();
909        let total: usize = parts
910            .iter()
911            .map(|&(pi, _)| self.partitions[pi].ids.len())
912            .sum();
913        let mut cands: Vec<(u128, f32)> = Vec::with_capacity(total);
914        for (pi, _) in parts {
915            let p = &self.partitions[pi];
916            for (&id, code) in p.ids.iter().zip(p.codes.chunks_exact(m)) {
917                cands.push((id, adc_distance(code, &table)));
918            }
919        }
920
921        // Stage 3 — keep the closest `n_rerank` candidates for exact
922        // reranking. R-001.8 part 3 (ANN-1.1): partition-select first,
923        // then sort only the kept slice. Full sort of all N candidates
924        // is O(N log N); at ANN-1.1's 1M + partitions/2 defaults the
925        // candidate pool is ~500K per query, where the full sort cost
926        // dominates. `select_nth_unstable_by` is O(N) average, then
927        // the final sort is O(k log k) with k = n_rerank.
928        if n_rerank < cands.len() {
929            cands.select_nth_unstable_by(n_rerank - 1, |a, b| a.1.total_cmp(&b.1));
930            cands.truncate(n_rerank);
931        }
932        cands.sort_by(|a, b| a.1.total_cmp(&b.1));
933        cands.into_iter().map(|(id, _)| id).collect()
934    }
935}
936
937#[cfg(test)]
938mod ann_1_1_tests {
939    //! PR ANN-1.1 tests for the index-defaults upgrade path.
940    //!
941    //! The amended spec (planner 2026-11-01 URGENT AMEND, R-001.3 +
942    //! R-001.10): no new fields on `IvfPqIndex` — rmp-serde 1.3.0's
943    //! positional decoder rejects extra array elements, so any append
944    //! would break v0.5.x readers. The whole upgrade path runs on the
945    //! "stored (8, 64) == auto" sentinel in
946    //! [`IvfPqIndex::effective_defaults`].
947
948    use super::*;
949    use rand::rngs::StdRng;
950    use rand::SeedableRng;
951
952    /// Shadow of the pre-ANN-1 [`IvfPqIndex`] layout — identical to
953    /// the current one (same field order, same types). Serializing
954    /// one of these produces the exact byte stream a v0.5.x build
955    /// would write. Keeping it as a separate struct makes the
956    /// field-count guard below mechanical rather than ad-hoc.
957    #[derive(serde::Serialize, serde::Deserialize)]
958    struct V052IvfPqIndex {
959        dims: usize,
960        n_partitions: usize,
961        n_probe: usize,
962        n_rerank: usize,
963        centroids: Vec<f32>,
964        pq: PqCodebook,
965        partitions: Vec<Posting>,
966    }
967
968    fn tiny_pq(dims: usize) -> PqCodebook {
969        let sub_offsets = vec![0, dims];
970        let mut rng = StdRng::seed_from_u64(0);
971        let train: Vec<Vec<f32>> = (0..4).map(|i| vec![i as f32; dims]).collect();
972        let refs: Vec<&[f32]> = train.iter().map(|v| v.as_slice()).collect();
973        PqCodebook::train(&sub_offsets, &refs, 2, &mut rng)
974    }
975
976    #[test]
977    fn v0_5_2_index_blob_decodes_unchanged() {
978        // A byte stream in the exact v0.5.2 layout must still decode
979        // as the current `IvfPqIndex`. If we ever appended a field,
980        // rmp-serde would reject this as `LengthMismatch`.
981        let dims = 4;
982        let legacy = V052IvfPqIndex {
983            dims,
984            n_partitions: 2,
985            n_probe: 8,
986            n_rerank: 64,
987            centroids: vec![1.0, 0.0, 0.0, 0.0, 0.0, 1.0, 0.0, 0.0],
988            pq: tiny_pq(dims),
989            partitions: vec![Posting::default(); 2],
990        };
991        let bytes = rmp_serde::to_vec(&legacy).expect("serialize v0.5.2 layout");
992        let decoded: IvfPqIndex =
993            rmp_serde::from_slice(&bytes).expect("v0.5.2 bytes must decode under current schema");
994        assert_eq!(decoded.dims, 4);
995        assert_eq!(decoded.n_partitions, 2);
996        assert_eq!(decoded.n_probe, 8);
997        assert_eq!(decoded.n_rerank, 64);
998    }
999
1000    #[test]
1001    fn current_build_serializes_with_v0_5_2_field_count() {
1002        // Forward-compat guard. If someone appends a field to
1003        // `IvfPqIndex`, the serialized form will carry an extra array
1004        // element and v0.5.x readers will reject it with
1005        // `LengthMismatch`. This test fails loudly first, so the
1006        // breakage is caught by `cargo test`, not by an upset user
1007        // whose two machines run different mnemo versions.
1008        let dims = 4;
1009        let items: Vec<(u128, Vec<f32>)> = (0..32)
1010            .map(|i| (i as u128, vec![i as f32, i as f32 + 1.0, 0.0, 0.0]))
1011            .collect();
1012        let refs: Vec<(u128, &[f32])> = items.iter().map(|(id, v)| (*id, v.as_slice())).collect();
1013        let idx = IvfPqIndex::build(dims, &refs, IndexConfig::default()).unwrap();
1014        let bytes = rmp_serde::to_vec(&idx).expect("serialize current layout");
1015        // Decode via the frozen v0.5.2 shadow struct. If the current
1016        // layout has an extra appended field, this fails with
1017        // `LengthMismatch`.
1018        let as_v052: V052IvfPqIndex = rmp_serde::from_slice(&bytes)
1019            .expect("current index must decode under the v0.5.2 shape");
1020        assert_eq!(as_v052.dims, dims);
1021    }
1022
1023    #[test]
1024    fn legacy_8_64_triggers_auto_formulas_at_query_time() {
1025        // The sentinel path: stored (8, 64) on a legacy index
1026        // substitutes the auto formulas at query time — ANN-1 fix
1027        // without a rebuild.
1028        let dims = 4;
1029        let legacy = V052IvfPqIndex {
1030            dims,
1031            n_partitions: 10,
1032            n_probe: 8,
1033            n_rerank: 64,
1034            centroids: vec![0.0; 10 * dims],
1035            pq: tiny_pq(dims),
1036            partitions: (0..10)
1037                .map(|_| Posting {
1038                    ids: vec![0u128, 1u128],
1039                    codes: vec![0u8; 2],
1040                })
1041                .collect(),
1042        };
1043        let bytes = rmp_serde::to_vec(&legacy).unwrap();
1044        let decoded: IvfPqIndex = rmp_serde::from_slice(&bytes).unwrap();
1045
1046        let (auto_probe, auto_rerank) = decoded.effective_defaults();
1047        // Small corpora get full probe (ANN-1.1 formula: full up to
1048        // 100 partitions). 10 partitions → probe all 10.
1049        assert_eq!(
1050            auto_probe, 10,
1051            "auto n_probe at <=100 partitions is full probe"
1052        );
1053        assert_eq!(auto_rerank, 100, "auto n_rerank at tiny N clamps up to 100");
1054    }
1055
1056    #[test]
1057    fn new_build_stores_resolved_auto_values() {
1058        // On v0.6.0+, build() with IndexConfig::default() resolves
1059        // 0 → concrete auto values and stores THOSE in the index.
1060        // Old readers (v0.5.x) see a usable number rather than a 0
1061        // sentinel; new readers compute the same values at query
1062        // time via effective_defaults.
1063        let dims = 4;
1064        let items: Vec<(u128, Vec<f32>)> = (0..64)
1065            .map(|i| {
1066                let f = i as f32;
1067                (i as u128, vec![f, f + 1.0, f + 2.0, f + 3.0])
1068            })
1069            .collect();
1070        let refs: Vec<(u128, &[f32])> = items.iter().map(|(id, v)| (*id, v.as_slice())).collect();
1071        let idx = IvfPqIndex::build(dims, &refs, IndexConfig::default()).unwrap();
1072        assert!(
1073            idx.n_probe > 0 && idx.n_rerank > 0,
1074            "resolved values must be concrete (never 0)"
1075        );
1076        // The IndexConfig::default() formula for a 64-vector corpus
1077        // with ceil(sqrt(64)) = 8 partitions picks n_probe=4,
1078        // n_rerank=clamp(64/200, 100, 1000) = 100.
1079        let expected_rerank = (64 / 200usize).clamp(100, 1000);
1080        assert_eq!(idx.n_rerank, expected_rerank);
1081    }
1082
1083    #[test]
1084    fn explicit_build_values_persist_verbatim() {
1085        // Non-sentinel explicit values stay stored and are used at
1086        // query time. (A user who passes exactly 8/64 explicitly is
1087        // treated as legacy auto — acknowledged in the planner's
1088        // amended spec; harmless because at the tiny N where 8/64
1089        // could sensibly be chosen, the auto formulas pick similar
1090        // values.)
1091        let dims = 4;
1092        let items: Vec<(u128, Vec<f32>)> =
1093            (0..64).map(|i| (i as u128, vec![i as f32; dims])).collect();
1094        let refs: Vec<(u128, &[f32])> = items.iter().map(|(id, v)| (*id, v.as_slice())).collect();
1095        let cfg = IndexConfig {
1096            n_probe: 3,
1097            n_rerank: 17,
1098            ..Default::default()
1099        };
1100        let idx = IvfPqIndex::build(dims, &refs, cfg).unwrap();
1101        assert_eq!(idx.n_probe, 3);
1102        assert_eq!(idx.n_rerank, 17);
1103        let (p, r) = idx.effective_defaults();
1104        assert_eq!(p, 3);
1105        assert_eq!(r, 17);
1106    }
1107}
1108
1109#[cfg(test)]
1110mod u128_map_tests {
1111    use super::U128Map;
1112    use std::collections::HashMap;
1113
1114    /// Random inserts, overwrites and removes agree with `HashMap`,
1115    /// including keys that collide on their home slot.
1116    #[test]
1117    fn matches_hashmap_under_random_ops() {
1118        let mut ours = U128Map::default();
1119        let mut reference: HashMap<u128, u32> = HashMap::new();
1120        let mut x: u64 = 0x9E37_79B9;
1121        let mut next = || {
1122            x ^= x << 13;
1123            x ^= x >> 7;
1124            x ^= x << 17;
1125            x
1126        };
1127        for step in 0..60_000u32 {
1128            // A small key space forces overwrites, removes and long runs.
1129            let k = (next() % 5_000) as u128 | ((next() % 3) as u128) << 100;
1130            match next() % 4 {
1131                0 | 1 => {
1132                    ours.insert(k, step);
1133                    reference.insert(k, step);
1134                }
1135                2 => assert_eq!(ours.remove(k), reference.remove(&k)),
1136                _ => assert_eq!(ours.get(k), reference.get(&k).copied()),
1137            }
1138            assert_eq!(ours.len(), reference.len());
1139        }
1140        for (k, v) in &reference {
1141            assert_eq!(ours.get(*k), Some(*v));
1142        }
1143    }
1144}
1145
1146/// PERF-2 (v0.19.0): the most dimensions a layout-2 index run may declare,
1147/// so a damaged length can't ask for a huge allocation.
1148const L2_MAX_DIMS: usize = 65_536;
1149
1150/// Read exactly `n` bytes, after checking they fit in what's left of the
1151/// run (`used` of `len`), so a damaged count can't force a huge allocation.
1152fn l2_take<R: std::io::Read>(r: &mut R, used: &mut u64, len: u64, n: usize) -> Result<Vec<u8>> {
1153    let end = (*used)
1154        .checked_add(n as u64)
1155        .filter(|&e| e <= len)
1156        .ok_or_else(|| {
1157            MnemoError::Serialize("index layout 2: a section runs past the run".into())
1158        })?;
1159    let mut b = vec![0u8; n];
1160    r.read_exact(&mut b)
1161        .map_err(|e| MnemoError::Serialize(format!("index layout 2: {e}")))?;
1162    *used = end;
1163    Ok(b)
1164}
1165
1166fn l2_u32s<R: std::io::Read>(r: &mut R, used: &mut u64, len: u64, n: usize) -> Result<Vec<usize>> {
1167    let b = l2_take(r, used, len, n.checked_mul(4).ok_or_else(l2_overflow)?)?;
1168    Ok(b.chunks_exact(4)
1169        .map(|c| u32::from_le_bytes(c.try_into().expect("4 bytes")) as usize)
1170        .collect())
1171}
1172
1173fn l2_f32s<R: std::io::Read>(r: &mut R, used: &mut u64, len: u64, n: usize) -> Result<Vec<f32>> {
1174    let b = l2_take(r, used, len, n.checked_mul(4).ok_or_else(l2_overflow)?)?;
1175    Ok(b.chunks_exact(4)
1176        .map(|c| f32::from_le_bytes(c.try_into().expect("4 bytes")))
1177        .collect())
1178}
1179
1180fn l2_overflow() -> MnemoError {
1181    MnemoError::Serialize("index layout 2: a length overflows".into())
1182}
1183
1184impl IvfPqIndex {
1185    /// PERF-2 (v0.19.0): the index as a layout-2 run body (the caller writes
1186    /// the layout byte first). Little-endian throughout:
1187    ///
1188    /// - `u32` × 5: dims, partitions, `n_probe`, `n_rerank`, PQ subspaces `m`;
1189    /// - `u32` × (m + 1): the subspace offsets; `u32` × m: codewords per subspace;
1190    /// - `f32` × (partitions × dims): the IVF centroids;
1191    /// - `f32`: each subspace's codewords, in order;
1192    /// - `u32` × partitions: each partition's entry count;
1193    /// - `u128` × entries: the ids, partition after partition;
1194    /// - `u8` × (entries × m): the PQ codes, in the same order.
1195    ///
1196    /// Flat arrays, so loading is a copy per section instead of a msgpack
1197    /// decode per element (layout 1).
1198    pub(crate) fn write_layout2(&self, out: &mut Vec<u8>) {
1199        let m = self.pq.m();
1200        let total = self.len();
1201        out.reserve(
1202            20 + (2 * m + 1) * 4
1203                + self.centroids.len() * 4
1204                + self.pq.centroids.iter().map(|c| c.len() * 4).sum::<usize>()
1205                + self.n_partitions * 4
1206                + total * (16 + m),
1207        );
1208        let u32le = |out: &mut Vec<u8>, v: usize| out.extend_from_slice(&(v as u32).to_le_bytes());
1209        for v in [self.dims, self.n_partitions, self.n_probe, self.n_rerank, m] {
1210            u32le(out, v);
1211        }
1212        for &o in &self.pq.sub_offsets {
1213            u32le(out, o);
1214        }
1215        for &k in &self.pq.ks {
1216            u32le(out, k);
1217        }
1218        for &c in &self.centroids {
1219            out.extend_from_slice(&c.to_le_bytes());
1220        }
1221        for cb in &self.pq.centroids {
1222            for &c in cb {
1223                out.extend_from_slice(&c.to_le_bytes());
1224            }
1225        }
1226        for p in &self.partitions {
1227            u32le(out, p.ids.len());
1228        }
1229        for p in &self.partitions {
1230            for &id in &p.ids {
1231                out.extend_from_slice(&id.to_le_bytes());
1232            }
1233        }
1234        for p in &self.partitions {
1235            out.extend_from_slice(&p.codes);
1236        }
1237    }
1238
1239    /// PERF-2 (v0.19.0): read a layout-2 run body of `len` bytes (after the
1240    /// layout byte) from `r`. Every section's length is checked against
1241    /// what's left before it's allocated, and the body must end exactly at
1242    /// `len`. The `id -> partition` map isn't built here (see
1243    /// [`Self::ensure_assignment`]).
1244    pub(crate) fn read_layout2<R: std::io::Read>(r: &mut R, len: u64) -> Result<IvfPqIndex> {
1245        let bad = |what: &str| MnemoError::Serialize(format!("index layout 2: {what}"));
1246        let mut used = 0u64;
1247        let head = l2_u32s(r, &mut used, len, 5)?;
1248        let (dims, n_partitions, n_probe, n_rerank, m) =
1249            (head[0], head[1], head[2], head[3], head[4]);
1250        if dims == 0 || dims > L2_MAX_DIMS || n_partitions == 0 || m == 0 || m > dims {
1251            return Err(bad("a bad shape"));
1252        }
1253        let sub_offsets = l2_u32s(r, &mut used, len, m + 1)?;
1254        if sub_offsets[0] != 0
1255            || sub_offsets[m] != dims
1256            || sub_offsets.windows(2).any(|w| w[1] <= w[0])
1257        {
1258            return Err(bad("bad subspace offsets"));
1259        }
1260        let ks = l2_u32s(r, &mut used, len, m)?;
1261        if ks.iter().any(|&k| k == 0 || k > PQ_CODEWORDS) {
1262            return Err(bad("a bad codeword count"));
1263        }
1264        let centroids = l2_f32s(
1265            r,
1266            &mut used,
1267            len,
1268            n_partitions.checked_mul(dims).ok_or_else(l2_overflow)?,
1269        )?;
1270        let mut pq_centroids = Vec::with_capacity(m);
1271        for s in 0..m {
1272            let subdim = sub_offsets[s + 1] - sub_offsets[s];
1273            pq_centroids.push(l2_f32s(r, &mut used, len, ks[s] * subdim)?);
1274        }
1275        let counts = l2_u32s(r, &mut used, len, n_partitions)?;
1276        let total = counts
1277            .iter()
1278            .try_fold(0usize, |a, &c| a.checked_add(c))
1279            .ok_or_else(l2_overflow)?;
1280        let rest = total.checked_mul(16 + m).ok_or_else(l2_overflow)? as u64;
1281        if used.checked_add(rest) != Some(len) {
1282            return Err(bad("the postings don't match the run's length"));
1283        }
1284        // Each partition's ids, then each one's codes, read straight into
1285        // their own arrays, so nothing large is held twice.
1286        let mut partitions: Vec<Posting> = Vec::with_capacity(n_partitions);
1287        for &c in &counts {
1288            let ids = l2_take(r, &mut used, len, c * 16)?
1289                .chunks_exact(16)
1290                .map(|b| u128::from_le_bytes(b.try_into().expect("16 bytes")))
1291                .collect();
1292            partitions.push(Posting {
1293                ids,
1294                codes: Vec::new(),
1295            });
1296        }
1297        for (p, &c) in partitions.iter_mut().zip(&counts) {
1298            p.codes = l2_take(r, &mut used, len, c * m)?;
1299        }
1300        Ok(IvfPqIndex {
1301            dims,
1302            n_partitions,
1303            n_probe,
1304            n_rerank,
1305            centroids,
1306            pq: PqCodebook {
1307                sub_offsets,
1308                centroids: pq_centroids,
1309                ks,
1310            },
1311            partitions,
1312            assignment: U128Map::default(),
1313            assignment_ready: false,
1314            log: None,
1315        })
1316    }
1317}
1318
1319#[cfg(test)]
1320mod adc_tests {
1321    use super::{adc_distance, PQ_CODEWORDS};
1322
1323    /// The unrolled sum agrees with the plain one for every subspace count,
1324    /// including those that aren't a multiple of four.
1325    #[test]
1326    fn unrolled_adc_matches_the_plain_sum() {
1327        let mut x: u32 = 0xA5A5_1234;
1328        let mut next = || {
1329            x ^= x << 13;
1330            x ^= x >> 17;
1331            x ^= x << 5;
1332            x
1333        };
1334        for m in 1..=13usize {
1335            let table: Vec<f32> = (0..m * PQ_CODEWORDS)
1336                .map(|_| (next() % 10_000) as f32 / 100.0)
1337                .collect();
1338            for _ in 0..50 {
1339                let code: Vec<u8> = (0..m).map(|_| next() as u8).collect();
1340                let plain: f32 = code
1341                    .iter()
1342                    .enumerate()
1343                    .map(|(s, &c)| table[s * PQ_CODEWORDS + c as usize])
1344                    .sum();
1345                let fast = adc_distance(&code, &table);
1346                assert!(
1347                    (plain - fast).abs() <= 1e-3 * plain.abs().max(1.0),
1348                    "m={m}: {plain} vs {fast}"
1349                );
1350            }
1351        }
1352    }
1353}
1354
1355#[cfg(test)]
1356mod layout2_tests {
1357    use super::{IndexConfig, IvfPqIndex};
1358
1359    fn index(n: usize, dims: usize) -> IvfPqIndex {
1360        let mut x: u32 = 0x1234_5678;
1361        let mut next = || {
1362            x ^= x << 13;
1363            x ^= x >> 17;
1364            x ^= x << 5;
1365            (x % 2_000) as f32 / 1_000.0 - 1.0
1366        };
1367        let vs: Vec<(u128, Vec<f32>)> = (0..n)
1368            .map(|i| (i as u128 * 7 + 1, (0..dims).map(|_| next()).collect()))
1369            .collect();
1370        let items: Vec<(u128, &[f32])> = vs.iter().map(|(i, v)| (*i, v.as_slice())).collect();
1371        IvfPqIndex::build(dims, &items, IndexConfig::default()).unwrap()
1372    }
1373
1374    fn encode(idx: &IvfPqIndex) -> Vec<u8> {
1375        let mut b = Vec::new();
1376        idx.write_layout2(&mut b);
1377        b
1378    }
1379
1380    /// PERF-2: layout 2 round-trips the index exactly (the same search
1381    /// results), without building the `id -> partition` map, which the
1382    /// first change then builds.
1383    #[test]
1384    fn layout_2_round_trips() {
1385        let idx = index(600, 16);
1386        let b = encode(&idx);
1387        let mut back = IvfPqIndex::read_layout2(&mut b.as_slice(), b.len() as u64).unwrap();
1388        assert!(!back.assignment_ready);
1389        let shape = |i: &IvfPqIndex| {
1390            let x = i.info();
1391            (x.vectors, x.partitions, x.subspaces, x.n_probe, x.n_rerank)
1392        };
1393        assert_eq!(shape(&back), shape(&idx));
1394        assert_eq!(back.len(), 600);
1395        for q in [vec![0.5f32; 16], vec![-0.25f32; 16]] {
1396            assert_eq!(back.query(&q, None, None), idx.query(&q, None, None));
1397        }
1398        assert!(back.contains(8));
1399        assert!(back.assignment_ready);
1400        back.remove(8);
1401        assert!(!back.contains(8));
1402        assert_eq!(encode(&back).len(), b.len() - 16 - back.pq.m());
1403    }
1404
1405    /// A damaged run is an error, never a panic or a huge allocation: cut
1406    /// short anywhere, trailing bytes, a count past the run, a bad shape.
1407    #[test]
1408    fn a_damaged_layout_2_run_is_an_error() {
1409        let b = encode(&index(300, 8));
1410        let len = b.len() as u64;
1411        for cut in [0, 3, 20, 40, b.len() / 2, b.len() - 1] {
1412            assert!(
1413                IvfPqIndex::read_layout2(&mut &b[..cut], cut as u64).is_err(),
1414                "cut at {cut}"
1415            );
1416            // The declared length still says the whole run.
1417            assert!(
1418                IvfPqIndex::read_layout2(&mut &b[..cut], len).is_err(),
1419                "short read at {cut}"
1420            );
1421        }
1422        let mut long = b.clone();
1423        long.push(0);
1424        assert!(IvfPqIndex::read_layout2(&mut long.as_slice(), long.len() as u64).is_err());
1425        // The first partition's count set huge.
1426        let m = u32::from_le_bytes(b[16..20].try_into().unwrap()) as usize;
1427        let parts = u32::from_le_bytes(b[4..8].try_into().unwrap()) as usize;
1428        let dims = u32::from_le_bytes(b[0..4].try_into().unwrap()) as usize;
1429        let ks: Vec<usize> = (0..m)
1430            .map(|s| {
1431                let at = 20 + (m + 1) * 4 + s * 4;
1432                u32::from_le_bytes(b[at..at + 4].try_into().unwrap()) as usize
1433            })
1434            .collect();
1435        let sub = dims / m;
1436        let counts_at =
1437            20 + (2 * m + 1) * 4 + parts * dims * 4 + ks.iter().map(|k| k * sub * 4).sum::<usize>();
1438        let mut huge = b.clone();
1439        huge[counts_at..counts_at + 4].copy_from_slice(&u32::MAX.to_le_bytes());
1440        assert!(IvfPqIndex::read_layout2(&mut huge.as_slice(), len).is_err());
1441        // Bad shapes: zero dims, more subspaces than dims, a zero codeword count.
1442        for (at, v) in [(0usize, 0u32), (16, 9), (20 + (m + 1) * 4, 0)] {
1443            let mut x = b.clone();
1444            x[at..at + 4].copy_from_slice(&v.to_le_bytes());
1445            assert!(
1446                IvfPqIndex::read_layout2(&mut x.as_slice(), len).is_err(),
1447                "at {at}"
1448            );
1449        }
1450    }
1451}