Struct Partitions 

pub struct Partitions { /* private fields */ }

A collection of vectors, quantised, partitioned, and updated in place.

Implementations

impl Partitions

pub fn new(dim: usize, bits: Bits, seed: u64, tuning: Tuning) -> Partitions

An empty collection of dim dimensional vectors.

The first vector inserted becomes the first centroid, and the index grows by splitting from there, so there is no build step and no moment where the shape of the collection has to be known in advance.

Panics

If dim is zero.

pub fn dim(&self) -> usize

How many coordinates a vector here has.

pub fn len(&self) -> usize

How many vectors are in the collection.

pub fn is_empty(&self) -> bool

Whether there are none.

pub fn partitions(&self) -> usize

How many partitions the collection has grown to.

pub fn entries(&self) -> usize

How many coded members the postings hold between them.

The same as Partitions::len until Tuning::spill puts a vector near a boundary into more than one partition, and the ratio of the two is what replication is costing in memory and in scan time.

pub fn tuning(&self) -> Tuning

The knobs.

pub fn retune(&mut self, tuning: Tuning)

Change the knobs on a collection that already has vectors in it.

Tuning::probe, Tuning::rerank and Tuning::widen are read by each search, so they take effect on the next one. That is what makes a recall against latency curve measurable on one built index rather than on one built per row, and it is what EF_RUNTIME means to a client that thinks it is talking to a graph.

Tuning::posting and Tuning::sweep are what maintenance aims at, so lowering posting does not split anything by itself. The partitions move towards the new size as Partitions::maintain gets called, which is the same way they got to the old one.

pub fn quantizer(&self) -> &Quantizer

The quantiser, whose seed and width a catalogue entry has to record.

pub fn code_bytes(&self) -> usize

How many bytes the codes take, which is the searchable size of the collection and the number the 32x claim is about.

pub fn insert(&mut self, id: u64, v: &[f32])

Put a vector in, replacing whatever was under id.

Two appends and no locks: the code goes on the end of the nearest partition’s posting, and the caller puts the full precision vector in the log. Nothing else in the index is touched, which is the difference between this and a graph.

Panics

If v is not Partitions::dim long.

pub fn insert_tagged(&mut self, id: u64, v: &[f32], tag: u64)

The same, with the tag a filter will meet in the scan.

See Filter for what a tag is and Signature for the encoding to reach for when the attributes do not fit in one exactly.

Panics

If v is not Partitions::dim long.

pub fn tag(&self, id: u64) -> Option<u64>

The tag id was inserted with, if it is still here.

pub fn retag(&mut self, id: u64, tag: u64) -> bool

Change the tag id carries, saying whether it was there.

The tag sits beside the code and nothing about the placement depends on it, so this is one write and no maintenance. That is what makes it affordable to recompute every tag in a collection when the thing the tag summarises changes, which for a document index is a field being indexed or stopping being indexed.

pub fn remove(&mut self, id: u64) -> bool

Take a vector out, saying whether it was there.

The last member of the posting moves into the hole. There is no tombstone, so there is nothing to accumulate and nothing to compact.

pub fn contains(&self, id: u64) -> bool

Whether id is in the collection.

pub fn search(&self, q: &[f32], k: usize, vectors: &impl Vectors) -> Vec<Hit>

The k nearest vectors to q, measured exactly.

The codes pick the candidates and the log settles the order, so the answer is as exact as brute force whenever the candidates contained the truth, and the recall table is about how often they do.

Panics

If q is not Partitions::dim long.

pub fn search_where( &self, q: &[f32], k: usize, filter: &impl Filter, vectors: &impl Vectors, ) -> Vec<Hit>

The k nearest vectors to q that a filter allows.

The filter runs inside the scan, on the tag that sits next to the code, so a member the filter rejects is never ranked and never takes a place that an answer should have had. Filtering afterwards instead is what makes a filtered vector search a lottery, and the more selective the filter the worse a lottery it is.

A selective filter also means the nearest few partitions may not hold k members that pass, so the scan keeps going into further partitions until it has enough or until it has spent Tuning::widen. A filter that matches almost nothing returns fewer answers rather than reading the whole collection, which is the trade every engine makes here and is worth saying out loud.

Panics

If q is not Partitions::dim long.

pub fn search_costed( &self, q: &[f32], k: usize, filter: &impl Filter, vectors: &impl Vectors, ) -> (Vec<Hit>, Work)

The same again, and what the scan behind it cost.

See Work. Worth having in front of a caller rather than behind a feature flag, because with Tuning::patience set the cost of a search is a property of the query and not of the settings, and a tuner that cannot see it is guessing.

Panics

If q is not Partitions::dim long.

pub fn candidates(&self, q: &[f32], want: usize) -> Vec<(u64, f32)>

The want best candidates by the estimator, without rerank.

This is what a filter will eventually push into, and it is what the recall of the codes alone is measured on.

Panics

If q is not Partitions::dim long.

pub fn candidates_where( &self, q: &[f32], want: usize, filter: &impl Filter, ) -> Vec<(u64, f32)>

The same, with the filter run inside the scan.

Panics

If q is not Partitions::dim long.

pub fn candidates_costed( &self, q: &[f32], want: usize, filter: &impl Filter, ) -> (Vec<(u64, f32)>, Work)

The same again, and what reading them cost.

The cost is here because Tuning::patience makes it vary from one query to the next, and a knob whose whole point is that different queries pay different amounts is not one anybody can set without being able to see what it did. It is also the honest way to compare two settings: recall against partitions actually read, rather than recall against the budget neither of them spent.

Panics

If q is not Partitions::dim long.

pub fn needs_maintenance(&self) -> bool

Whether there is a split or a merge waiting.

pub fn maintain(&mut self, vectors: &impl Vectors, budget: usize) -> usize

Do bounded maintenance, and say how many vectors it looked at.

budget is in vectors touched rather than in time, because time is not something a storage engine gets to measure cheaply and a vector is the unit all of this work is actually made of. Call it from a maintenance slice until it returns less than the budget, which means there was nothing left to do.

Trait Implementations

impl Debug for Partitions

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.