recern_vector/
collection.rs

1use std::collections::{BinaryHeap, HashMap};
2use std::fmt;
3use std::time::{Duration, Instant};
4
5use serde_json::Value;
6
7use crate::error::{Error, Result};
8use crate::filter::Filter;
9use crate::hnsw::{Candidate, Counters, Graph, HnswParams, Vectors};
10use crate::metric::{self, Metric};
11use crate::rng::SplitMix64;
12
13pub(crate) const DEFAULT_SEED: u64 = 0x5245_4345_524E_5645;
14const MAX_DIM: usize = 65_536;
15
16const SELECTIVITY_SAMPLE: usize = 512;
17
18/// Storage precision. Int8 uses a symmetric scale per vector; original floats
19/// are not retained. Exact searches are exact over the stored approximation.
20#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
21pub enum Quantization {
22    #[default]
23    F32,
24    Int8,
25}
26impl Quantization {
27    pub fn as_str(self) -> &'static str {
28        match self {
29            Self::F32 => "f32",
30            Self::Int8 => "int8",
31        }
32    }
33}
34
35#[derive(Clone, Copy, Debug, PartialEq, Eq)]
36pub struct CollectionConfig {
37    pub dim: usize,
38    pub metric: Metric,
39    pub hnsw: HnswParams,
40    pub quantization: Quantization,
41}
42
43impl CollectionConfig {
44    pub fn new(dim: usize, metric: Metric) -> Self {
45        Self {
46            dim,
47            metric,
48            hnsw: HnswParams::default(),
49            quantization: Quantization::F32,
50        }
51    }
52
53    pub fn with_hnsw(mut self, hnsw: HnswParams) -> Self {
54        self.hnsw = hnsw;
55        self
56    }
57
58    pub fn with_quantization(mut self, quantization: Quantization) -> Self {
59        self.quantization = quantization;
60        self
61    }
62
63    fn validate(&self) -> Result<()> {
64        if self.dim == 0 || self.dim > MAX_DIM {
65            return Err(Error::InvalidArgument(format!(
66                "dim must be between 1 and {MAX_DIM}"
67            )));
68        }
69        self.hnsw.validate()
70    }
71}
72
73/// A stored record. For cosine collections `vector` is the normalized vector.
74#[derive(Clone, Debug, PartialEq)]
75pub struct Record {
76    pub id: String,
77    pub vector: Vec<f32>,
78    pub metadata: Option<Value>,
79}
80
81/// A bounded page in physical insertion order. Cursors are valid only while
82/// the collection is unchanged; take a read-only snapshot for an export.
83#[derive(Clone, Debug, PartialEq)]
84pub struct RecordPage {
85    pub records: Vec<Record>,
86    pub next_offset: Option<usize>,
87}
88
89#[derive(Clone, Debug, PartialEq)]
90pub struct SearchHit {
91    pub id: String,
92    pub distance: f32,
93    pub metadata: Option<Value>,
94}
95
96#[derive(Clone, Debug, Default)]
97pub struct SearchOptions {
98    /// Candidate list size; defaults to the collection's `ef_search`.
99    pub ef: Option<usize>,
100    /// Scan every record instead of using the index.
101    pub exact: bool,
102    pub filter: Option<Filter>,
103}
104
105impl SearchOptions {
106    pub fn ef(mut self, ef: usize) -> Self {
107        self.ef = Some(ef);
108        self
109    }
110
111    pub fn exact(mut self) -> Self {
112        self.exact = true;
113        self
114    }
115
116    pub fn filter(mut self, filter: Filter) -> Self {
117        self.filter = Some(filter);
118        self
119    }
120}
121
122/// How a query was answered.
123#[derive(Clone, Copy, Debug, PartialEq, Eq)]
124pub enum Strategy {
125    /// HNSW graph search (filtered results are collected while traversing).
126    Hnsw,
127    /// Full scan, requested explicitly.
128    Exact,
129    /// Full scan chosen automatically because the filter is very selective.
130    FilteredExact,
131}
132
133impl fmt::Display for Strategy {
134    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
135        f.write_str(match self {
136            Strategy::Hnsw => "hnsw",
137            Strategy::Exact => "exact",
138            Strategy::FilteredExact => "exact (selective filter)",
139        })
140    }
141}
142
143struct SearchCandidates {
144    candidates: Vec<Candidate>,
145    strategy: Strategy,
146    ef: Option<usize>,
147    counters: Counters,
148    selectivity: Option<f64>,
149}
150
151/// Search results together with the work it took to produce them.
152#[derive(Clone, Debug)]
153pub struct SearchReport {
154    pub hits: Vec<SearchHit>,
155    pub strategy: Strategy,
156    /// Candidate list size used by an HNSW search.
157    pub ef: Option<usize>,
158    pub visited: usize,
159    pub distance_computations: usize,
160    /// Estimated share of live records matching the filter.
161    pub filter_selectivity: Option<f64>,
162    pub elapsed: Duration,
163}
164
165#[derive(Clone, Debug, PartialEq)]
166pub struct CollectionStats {
167    pub name: String,
168    pub config: CollectionConfig,
169    pub live: usize,
170    /// Deleted or replaced records still occupying space until `compact`.
171    pub deleted: usize,
172    /// Nodes on each HNSW layer, bottom first.
173    pub nodes_per_layer: Vec<usize>,
174    pub avg_degree_layer0: f64,
175    /// Live records that graph search can never reach from the entry point.
176    pub unreachable: usize,
177    pub vector_bytes: usize,
178    pub graph_bytes: usize,
179    pub metadata_bytes: usize,
180}
181
182#[derive(Clone, Debug)]
183pub struct RecallOptions {
184    /// Number of stored vectors used as queries.
185    pub sample: usize,
186    pub k: usize,
187    pub ef_values: Vec<usize>,
188    pub seed: u64,
189}
190
191impl Default for RecallOptions {
192    fn default() -> Self {
193        Self {
194            sample: 100,
195            k: 10,
196            ef_values: vec![16, 32, 64, 128, 256],
197            seed: 42,
198        }
199    }
200}
201
202#[derive(Clone, Debug)]
203pub struct RecallPoint {
204    pub ef: usize,
205    /// Share of the exact top-k found by the index, averaged over queries.
206    pub recall: f64,
207    pub p50: Duration,
208    pub p95: Duration,
209}
210
211#[derive(Clone, Debug)]
212pub struct RecallReport {
213    pub k: usize,
214    pub sample: usize,
215    pub exact_p50: Duration,
216    pub points: Vec<RecallPoint>,
217}
218
219pub struct Collection {
220    pub(crate) name: String,
221    pub(crate) config: CollectionConfig,
222    pub(crate) vectors: Vectors,
223    pub(crate) ids: Vec<String>,
224    pub(crate) metadata: Vec<Option<Value>>,
225    pub(crate) deleted: Vec<bool>,
226    pub(crate) graph: Graph,
227    index: HashMap<String, u32>,
228}
229
230impl Collection {
231    pub(crate) fn new(name: &str, config: CollectionConfig) -> Result<Self> {
232        config.validate()?;
233        Ok(Self {
234            name: name.to_owned(),
235            config,
236            vectors: Vectors::with_encoding(config.dim, config.quantization, config.metric),
237            ids: Vec::new(),
238            metadata: Vec::new(),
239            deleted: Vec::new(),
240            graph: Graph::new(config.hnsw, DEFAULT_SEED),
241            index: HashMap::new(),
242        })
243    }
244
245    /// Reassembles a collection read from disk, rebuilding the id index.
246    pub(crate) fn from_parts(
247        name: String,
248        config: CollectionConfig,
249        vectors: Vectors,
250        ids: Vec<String>,
251        metadata: Vec<Option<Value>>,
252        deleted: Vec<bool>,
253        graph: Graph,
254    ) -> Result<Self> {
255        config
256            .validate()
257            .map_err(|e| Error::Corrupt(format!("collection '{name}': {e}")))?;
258        let mut index = HashMap::with_capacity(ids.len());
259        for (node, id) in ids.iter().enumerate() {
260            if !deleted[node] && index.insert(id.clone(), node as u32).is_some() {
261                return Err(Error::Corrupt(format!(
262                    "collection '{name}': duplicate id '{id}'"
263                )));
264            }
265        }
266        Ok(Self {
267            name,
268            config,
269            vectors,
270            ids,
271            metadata,
272            deleted,
273            graph,
274            index,
275        })
276    }
277
278    pub fn name(&self) -> &str {
279        &self.name
280    }
281
282    pub fn config(&self) -> &CollectionConfig {
283        &self.config
284    }
285
286    /// Number of live records.
287    pub fn len(&self) -> usize {
288        self.index.len()
289    }
290
291    pub fn is_empty(&self) -> bool {
292        self.index.is_empty()
293    }
294
295    pub fn contains(&self, id: &str) -> bool {
296        self.index.contains_key(id)
297    }
298
299    /// Inserts a record, replacing any record with the same id.
300    pub fn upsert(&mut self, id: &str, vector: &[f32], metadata: Option<Value>) -> Result<()> {
301        let vector = self.prepare(vector)?;
302        if self.ids.len() >= u32::MAX as usize {
303            return Err(Error::InvalidArgument("collection is full".into()));
304        }
305        if let Some(&old) = self.index.get(id) {
306            self.deleted[old as usize] = true;
307        }
308        let node = self.append(id.to_owned(), &vector, metadata);
309        self.graph.insert(node, &self.vectors, self.config.metric);
310        Ok(())
311    }
312
313    /// Inserts many records, replacing records with the same ids, and links
314    /// them into the index using all available cores. The batch is atomic: if
315    /// any vector is invalid, the collection is left unchanged. Returns the
316    /// number of records written.
317    pub fn upsert_many<I, S, V>(&mut self, records: I) -> Result<usize>
318    where
319        I: IntoIterator<Item = (S, V, Option<Value>)>,
320        S: Into<String>,
321        V: AsRef<[f32]>,
322    {
323        self.upsert_many_with_threads(records, default_threads())
324    }
325
326    /// [`Collection::upsert_many`] with an explicit thread count. With one
327    /// thread the graph is identical to upserting the records one by one;
328    /// with more, link order (and so the exact graph) depends on scheduling.
329    pub fn upsert_many_with_threads<I, S, V>(&mut self, records: I, threads: usize) -> Result<usize>
330    where
331        I: IntoIterator<Item = (S, V, Option<Value>)>,
332        S: Into<String>,
333        V: AsRef<[f32]>,
334    {
335        let start = self.ids.len();
336        let mut replaced = Vec::new();
337        for (id, vector, metadata) in records {
338            let id = id.into();
339            let vector = match self.prepare(vector.as_ref()) {
340                Ok(vector) if self.ids.len() < u32::MAX as usize => vector,
341                Ok(_) => {
342                    self.rollback(start, replaced);
343                    return Err(Error::InvalidArgument("collection is full".into()));
344                }
345                Err(err) => {
346                    self.rollback(start, replaced);
347                    return Err(err);
348                }
349            };
350            if let Some(&old) = self.index.get(&id) {
351                self.deleted[old as usize] = true;
352                replaced.push((id.clone(), old));
353            }
354            self.append(id, &vector, metadata);
355        }
356        let end = self.ids.len();
357        self.graph.insert_batch(
358            start as u32..end as u32,
359            &self.vectors,
360            self.config.metric,
361            threads.max(1),
362        );
363        Ok(end - start)
364    }
365
366    /// Removes a record. Returns whether it existed.
367    ///
368    /// The node stays in the graph as a waypoint until [`Collection::compact`].
369    pub fn delete(&mut self, id: &str) -> bool {
370        match self.index.remove(id) {
371            Some(node) => {
372                self.deleted[node as usize] = true;
373                true
374            }
375            None => false,
376        }
377    }
378
379    pub fn get(&self, id: &str) -> Option<Record> {
380        let node = *self.index.get(id)?;
381        Some(Record {
382            id: id.to_owned(),
383            vector: self.vectors.get(node).to_vec(),
384            metadata: self.metadata[node as usize].clone(),
385        })
386    }
387
388    /// Reads live records without cloning the entire collection or its index.
389    /// Replaced/deleted records are skipped. At most `limit` records are owned
390    /// by the returned page, regardless of the size of the database.
391    pub fn records_page(&self, offset: usize, limit: usize) -> Result<RecordPage> {
392        if limit == 0 || limit > 10_000 || offset > self.ids.len() {
393            return Err(Error::InvalidArgument(
394                "record page requires a valid offset and a limit from 1 to 10000".into(),
395            ));
396        }
397        let mut records = Vec::with_capacity(limit.min(self.len()));
398        let mut next = offset;
399        while next < self.ids.len() && records.len() < limit {
400            let node = next;
401            next += 1;
402            if !self.deleted[node] {
403                records.push(Record {
404                    id: self.ids[node].clone(),
405                    vector: self.vectors.get(node as u32).to_vec(),
406                    metadata: self.metadata[node].clone(),
407                });
408            }
409        }
410        while next < self.ids.len() && self.deleted[next] {
411            next += 1;
412        }
413        Ok(RecordPage {
414            records,
415            next_offset: (next < self.ids.len()).then_some(next),
416        })
417    }
418
419    pub fn search(
420        &self,
421        query: &[f32],
422        k: usize,
423        options: &SearchOptions,
424    ) -> Result<Vec<SearchHit>> {
425        Ok(self.explain(query, k, options)?.hits)
426    }
427
428    /// Runs a search and reports how it was executed.
429    pub fn explain(
430        &self,
431        query: &[f32],
432        k: usize,
433        options: &SearchOptions,
434    ) -> Result<SearchReport> {
435        let start = Instant::now();
436        let found = self.search_candidates(query, k, options)?;
437        Ok(SearchReport {
438            hits: found.candidates.into_iter().map(|c| self.hit(c)).collect(),
439            strategy: found.strategy,
440            ef: found.ef,
441            visited: found.counters.visited,
442            distance_computations: found.counters.distance_computations,
443            filter_selectivity: found.selectivity,
444            elapsed: start.elapsed(),
445        })
446    }
447
448    /// Visits borrowed search results without cloning IDs or metadata. The
449    /// caller can bound response serialization before allocating large hits.
450    /// Candidate order matches `search`; no mutation may occur during the visit.
451    pub fn visit_search<'a>(
452        &'a self,
453        query: &[f32],
454        k: usize,
455        options: &SearchOptions,
456        mut visitor: impl FnMut(&'a str, f32, Option<&'a Value>) -> Result<()>,
457    ) -> Result<()> {
458        for candidate in self.search_candidates(query, k, options)?.candidates {
459            let node = candidate.id as usize;
460            let distance = if self.config.metric == Metric::Cosine {
461                candidate.dist.max(0.0)
462            } else {
463                candidate.dist
464            };
465            visitor(&self.ids[node], distance, self.metadata[node].as_ref())?;
466        }
467        Ok(())
468    }
469
470    fn search_candidates(
471        &self,
472        query: &[f32],
473        k: usize,
474        options: &SearchOptions,
475    ) -> Result<SearchCandidates> {
476        if k == 0 {
477            return Err(Error::InvalidArgument("k must be greater than zero".into()));
478        }
479        let query = self.prepare(query)?;
480        let filter = options.filter.as_ref();
481        let selectivity = filter.map(|f| self.estimate_selectivity(f));
482        let base_ef = options.ef.unwrap_or(self.config.hnsw.ef_search).max(k);
483        let adaptive_ef = selectivity.map_or(base_ef, |s| {
484            ((base_ef as f64 / s.max(1.0 / self.len().max(1) as f64)).ceil() as usize)
485                .min(self.len())
486                .max(k)
487        });
488        let exact_cost = selectivity.map(|s| {
489            self.graph.len() as f64 / self.config.dim.max(1) as f64 + self.len() as f64 * s
490        });
491        let graph_cost = adaptive_ef as f64 * self.config.hnsw.m as f64 * 0.5;
492        let strategy = if options.exact {
493            Strategy::Exact
494        } else if exact_cost.is_some_and(|cost| cost <= graph_cost) {
495            Strategy::FilteredExact
496        } else {
497            Strategy::Hnsw
498        };
499
500        let accept = |node: u32| {
501            !self.deleted[node as usize]
502                && filter.is_none_or(|f| f.matches(self.metadata[node as usize].as_ref()))
503        };
504        let mut counters = Counters::default();
505        let (found, ef) = match strategy {
506            Strategy::Hnsw => {
507                let ef = adaptive_ef;
508                let found = self.graph.search(
509                    &query,
510                    k,
511                    ef,
512                    &self.vectors,
513                    self.config.metric,
514                    &accept,
515                    &mut counters,
516                );
517                (found, Some(ef))
518            }
519            Strategy::Exact | Strategy::FilteredExact => {
520                (self.scan(&query, k, &accept, &mut counters), None)
521            }
522        };
523
524        Ok(SearchCandidates {
525            candidates: found,
526            strategy,
527            ef,
528            counters,
529            selectivity,
530        })
531    }
532
533    pub fn stats(&self) -> CollectionStats {
534        let nodes = self.graph.len();
535        let reachable = self.graph.reachable();
536        let unreachable = (0..nodes)
537            .filter(|&n| !self.deleted[n] && !reachable[n])
538            .count();
539        let layer0_links: usize = self.graph.links.iter().map(|layers| layers[0].len()).sum();
540        let graph_bytes: usize = self
541            .graph
542            .links
543            .iter()
544            .map(|layers| {
545                size_of::<Vec<Vec<u32>>>()
546                    + layers
547                        .iter()
548                        .map(|l| size_of::<Vec<u32>>() + l.len() * 4)
549                        .sum::<usize>()
550            })
551            .sum();
552        let metadata_bytes = self
553            .metadata
554            .iter()
555            .flatten()
556            .map(|m| serde_json::to_vec(m).map_or(0, |b| b.len()))
557            .sum();
558
559        CollectionStats {
560            name: self.name.clone(),
561            config: self.config,
562            live: self.len(),
563            deleted: nodes - self.len(),
564            nodes_per_layer: self.graph.nodes_per_layer(),
565            avg_degree_layer0: if nodes == 0 {
566                0.0
567            } else {
568                layer0_links as f64 / nodes as f64
569            },
570            unreachable,
571            vector_bytes: self.vectors.bytes(),
572            graph_bytes,
573            metadata_bytes,
574        }
575    }
576
577    /// Measures how many of the exact nearest neighbors the index finds.
578    ///
579    /// Stored vectors are sampled as queries; each query's own record is
580    /// excluded from both the exact and the approximate results.
581    pub fn estimate_recall(&self, options: &RecallOptions) -> Result<RecallReport> {
582        if options.k == 0 || options.sample == 0 || options.ef_values.is_empty() {
583            return Err(Error::InvalidArgument(
584                "k, sample and ef values must be non-empty and greater than zero".into(),
585            ));
586        }
587        let mut live: Vec<u32> = (0..self.graph.len() as u32)
588            .filter(|&n| !self.deleted[n as usize])
589            .collect();
590        if live.len() < 2 {
591            return Err(Error::InvalidArgument(
592                "recall needs at least two records".into(),
593            ));
594        }
595
596        let mut rng = SplitMix64::new(options.seed);
597        let sample = options.sample.min(live.len());
598        for i in 0..sample {
599            let j = i + rng.below(live.len() - i);
600            live.swap(i, j);
601        }
602        let queries = &live[..sample];
603        let k = options.k.min(live.len() - 1);
604        let metric = self.config.metric;
605
606        let mut exact_times = Vec::with_capacity(sample);
607        let truths: Vec<Vec<u32>> = queries
608            .iter()
609            .map(|&q| {
610                let accept = |n: u32| n != q && !self.deleted[n as usize];
611                let start = Instant::now();
612                let found = self.scan(&self.vectors.get(q), k, &accept, &mut Counters::default());
613                exact_times.push(start.elapsed());
614                found.into_iter().map(|c| c.id).collect()
615            })
616            .collect();
617
618        let mut points = Vec::with_capacity(options.ef_values.len());
619        for &ef in &options.ef_values {
620            let mut times = Vec::with_capacity(sample);
621            let mut found_total = 0;
622            for (&q, truth) in queries.iter().zip(&truths) {
623                let accept = |n: u32| n != q && !self.deleted[n as usize];
624                let start = Instant::now();
625                let found = self.graph.search(
626                    &self.vectors.get(q),
627                    k,
628                    ef.max(k),
629                    &self.vectors,
630                    metric,
631                    &accept,
632                    &mut Counters::default(),
633                );
634                times.push(start.elapsed());
635                found_total += found.iter().filter(|c| truth.contains(&c.id)).count();
636            }
637            points.push(RecallPoint {
638                ef,
639                recall: found_total as f64 / (k * sample) as f64,
640                p50: percentile(&mut times, 0.50),
641                p95: percentile(&mut times, 0.95),
642            });
643        }
644
645        Ok(RecallReport {
646            k,
647            sample,
648            exact_p50: percentile(&mut exact_times, 0.50),
649            points,
650        })
651    }
652
653    /// Rebuilds the collection without deleted records. Returns how many
654    /// were removed.
655    pub fn compact(&mut self) -> usize {
656        let removed = self.graph.len() - self.len();
657        if removed == 0 {
658            return 0;
659        }
660        let mut fresh = Collection::new(&self.name, self.config)
661            .expect("configuration was validated when the collection was created");
662        for node in 0..self.graph.len() {
663            if !self.deleted[node] {
664                let vector = self.vectors.get(node as u32);
665                fresh.append(self.ids[node].clone(), &vector, self.metadata[node].clone());
666            }
667        }
668        let live = fresh.ids.len() as u32;
669        fresh.graph.insert_batch(
670            0..live,
671            &fresh.vectors,
672            fresh.config.metric,
673            default_threads(),
674        );
675        *self = fresh;
676        removed
677    }
678
679    fn prepare(&self, vector: &[f32]) -> Result<Vec<f32>> {
680        if vector.len() != self.config.dim {
681            return Err(Error::DimensionMismatch {
682                expected: self.config.dim,
683                actual: vector.len(),
684            });
685        }
686        if vector.iter().any(|x| !x.is_finite()) {
687            return Err(Error::InvalidVector(
688                "contains NaN or infinite values".into(),
689            ));
690        }
691        let mut vector = vector.to_vec();
692        if self.config.metric == Metric::Cosine && !metric::normalize(&mut vector) {
693            return Err(Error::InvalidVector(
694                "zero vector has no direction for cosine".into(),
695            ));
696        }
697        Ok(vector)
698    }
699
700    /// Appends an already prepared record without linking it into the graph.
701    fn append(&mut self, id: String, vector: &[f32], metadata: Option<Value>) -> u32 {
702        let node = self.ids.len() as u32;
703        self.vectors.push(vector);
704        self.ids.push(id.clone());
705        self.metadata.push(metadata);
706        self.deleted.push(false);
707        self.index.insert(id, node);
708        node
709    }
710
711    /// Undoes the appends of a failed batch that started at node `start`.
712    fn rollback(&mut self, start: usize, replaced: Vec<(String, u32)>) {
713        for node in start..self.ids.len() {
714            let id = &self.ids[node];
715            if self.index.get(id) == Some(&(node as u32)) {
716                self.index.remove(id);
717            }
718        }
719        self.vectors.truncate(start);
720        self.ids.truncate(start);
721        self.metadata.truncate(start);
722        self.deleted.truncate(start);
723        for (id, old) in replaced.into_iter().rev() {
724            if (old as usize) < start {
725                self.deleted[old as usize] = false;
726                self.index.insert(id, old);
727            }
728        }
729    }
730
731    fn scan(
732        &self,
733        query: &[f32],
734        k: usize,
735        accept: &dyn Fn(u32) -> bool,
736        counters: &mut Counters,
737    ) -> Vec<Candidate> {
738        let mut heap = BinaryHeap::with_capacity(k.min(self.len()) + 1);
739        for node in 0..self.graph.len() as u32 {
740            if !accept(node) {
741                continue;
742            }
743            counters.visited += 1;
744            counters.distance_computations += 1;
745            let dist = self.vectors.distance(query, node, self.config.metric);
746            if heap.len() < k {
747                heap.push(Candidate { dist, id: node });
748            } else if heap.peek().is_some_and(|w: &Candidate| dist < w.dist) {
749                heap.pop();
750                heap.push(Candidate { dist, id: node });
751            }
752        }
753        let mut out = heap.into_vec();
754        out.sort();
755        out
756    }
757
758    /// Estimates the share of live records matching `filter`. Small
759    /// collections are checked fully; larger ones from a random sample, since
760    /// an evenly spaced one aliases with periodic insertion patterns.
761    fn estimate_selectivity(&self, filter: &Filter) -> f64 {
762        let nodes = self.graph.len();
763        let mut rng = SplitMix64::new(DEFAULT_SEED);
764        let sample: Box<dyn Iterator<Item = usize>> = if nodes <= SELECTIVITY_SAMPLE {
765            Box::new(0..nodes)
766        } else {
767            Box::new((0..SELECTIVITY_SAMPLE).map(move |_| rng.below(nodes)))
768        };
769        let (mut checked, mut matched) = (0usize, 0usize);
770        for node in sample.filter(|&n| !self.deleted[n]) {
771            checked += 1;
772            if filter.matches(self.metadata[node].as_ref()) {
773                matched += 1;
774            }
775        }
776        if checked == 0 {
777            1.0
778        } else {
779            matched as f64 / checked as f64
780        }
781    }
782
783    fn hit(&self, candidate: Candidate) -> SearchHit {
784        let node = candidate.id as usize;
785        // Rounding can push the cosine distance of identical vectors just
786        // below zero; report it as 0.
787        let distance = match self.config.metric {
788            Metric::Cosine => candidate.dist.max(0.0),
789            _ => candidate.dist,
790        };
791        SearchHit {
792            id: self.ids[node].clone(),
793            distance,
794            metadata: self.metadata[node].clone(),
795        }
796    }
797}
798
799fn default_threads() -> usize {
800    std::thread::available_parallelism().map_or(1, |n| n.get())
801}
802
803fn percentile(times: &mut [Duration], p: f64) -> Duration {
804    if times.is_empty() {
805        return Duration::ZERO;
806    }
807    times.sort_unstable();
808    times[((times.len() - 1) as f64 * p).round() as usize]
809}
recern_vector/collection.rs

recern_vector/
collection.rs
