Struct Collection 

pub struct Collection { /* private fields */ }

Vectors under keys: the index, the vectors it reranks against, and the table that turns one into the other.

Implementations

impl Collection

pub fn new(dim: usize, metric: Metric) -> Result<Collection>

An empty collection that has allocated nothing yet.

Errors

Code::Invalid for a dimension of zero or past MAX_DIM, and Code::Unsupported for a metric this build does not measure.

pub fn dim(&self) -> usize

How many coordinates a vector here has.

pub fn metric(&self) -> Metric

What nearness means here.

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 partitions hold between them, which is more than Collection::len by however many boundary copies Tuning::spill has made.

pub fn tuning(&self) -> Tuning

The knobs the index is searched with.

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

Change them, which is what EF_RUNTIME on the wire means.

pub fn contains(&self, key: &[u8]) -> bool

Whether the collection holds a vector under key.

pub fn get(&self, key: &[u8]) -> Option<&[f32]>

The vector under key, where it lies.

pub fn keys(&self) -> impl Iterator<Item = &[u8]>

Every key in the collection, in no order worth relying on.

pub fn key_at(&self, n: usize) -> Option<&[u8]>

The nth key, counting from zero, in that same order.

For a caller that wants one member and not all of them, which is what VRANDMEMBER is and what walking the whole table to throw it away would be the wrong way to answer.

pub fn id(&self, key: &[u8]) -> Option<u64>

The id the index knows key by.

An id is the slot the vector sits in. It is stable while the key is there, it changes if the key is removed and written again, and it is handed out so that a caller keeping something else per vector can key it by a small integer rather than by a second copy of the key. The attribute a vector set holds is the first of those and a pushed down filter’s tag will be the next.

pub fn put(&mut self, key: &[u8], v: &[f32]) -> Result<bool>

Put a vector in under key, and say whether the key is new.

Replacing is the same call. The old code comes out of its partition and the new one goes into whichever partition it belongs to now, so nothing accumulates and there is no rebuild waiting at the end of it.

Errors

Code::Invalid when the vector is not Collection::dim long, when a coordinate is not a number, or when a cosine collection is handed a vector of length zero, which has no direction to store. Code::Full for a key past the length limit.

pub fn put_tagged(&mut self, key: &[u8], v: &[f32], tag: u64) -> Result<bool>

The same, with the tag a filtered search will meet in the posting scan.

A tag is 64 bits and it travels beside the code rather than beside the vector, which is the whole reason a filter here costs nothing: the scan is already reading that cache line to get at the code, so testing the tag is one instruction on a word that has arrived anyway. See Signature for how a set of field and value pairs becomes one, and Collection::search_where for the other end of it.

A tag of zero passes no filter except Any, which is what an untagged collection wants: Collection::put is this with a zero and every search over it is unfiltered.

Errors

As Collection::put.

pub fn tag(&self, key: &[u8]) -> Option<u64>

The tag key was stored with, if it is here.

pub fn retag(&mut self, key: &[u8], tag: u64) -> bool

Change the tag under key without touching the vector, and say whether there was one.

The tag summarises something outside the vector, so it can go stale while the vector is still right. Rewriting it is one store into the posting, with no requantisation and no maintenance, which is what makes it cheap enough to redo every tag in a collection when the summary changes.

pub fn remove(&mut self, key: &[u8]) -> bool

Take a vector out, saying whether it was there.

A delete here is a delete and not a tombstone: the member leaves its posting and the last member of that posting moves into the hole.

pub fn search( &self, q: &[f32], k: usize, skip: Option<&[u8]>, ) -> Result<Vec<Match>>

The k nearest keys to q, nearest first, with skip left out.

skip is what makes a more-like-this search work: the vector already stored under a key is always nearest to itself, and nobody asked what a thing is most similar to itself.

Errors

Code::Invalid when q is not Collection::dim long or holds a coordinate that is not a number.

pub fn search_where( &self, q: &[f32], k: usize, skip: Option<&[u8]>, filter: &impl Filter, ) -> Result<Vec<Match>>

The same, over only the members whose tag filter allows.

The filter runs inside the posting scan and not on the answers, which is the difference between a filtered search and a search followed by a filter. A filter matching one member in a thousand, applied to the nearest ten, returns nothing almost every time; applied in the scan it keeps reading further partitions until it has k or until it has spent Tuning::widen, so it returns the nearest ten that pass.

It can still come back with fewer than k. That is the trade every engine makes here and it is the right one, because the alternative to giving up after a bounded widen is reading the whole collection for a query that was going to find nothing anyway.

Errors

As Collection::search.

pub fn search_exact( &self, q: &[f32], k: usize, skip: Option<&[u8]>, ) -> Result<Vec<Match>>

The same answer, arrived at by measuring every vector in the collection.

This is what the index is an approximation of, so it is the thing recall is measured against, and it is what VSIM ... TRUTH asks for. It reads no codes at all: the estimator exists to avoid this walk and there is nothing it can contribute to a walk that is happening anyway.

Linear in the collection, which is the point. A client asking for it on a million vectors is asking for a million distances and should get them rather than a refusal, because the reason to ask is to find out what the index missed.

Errors

As Collection::search.

pub fn search_exact_where( &self, q: &[f32], k: usize, skip: Option<&[u8]>, filter: &impl Filter, ) -> Result<Vec<Match>>

The same walk, over only the members the filter allows.

There is no scan to push the filter into here, because there is no scan: this measures everything. It exists so that a client asking for the exact answer and asking for a filter gets the exact answer to the question it asked, rather than being told the two options do not go together.

Errors

As Collection::search.

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

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

A caller with a maintenance slice runs this until it returns less than the budget. A caller without one gets what Collection::put does on its own, which is the same work in smaller pieces.

pub fn memory_bytes(&self) -> usize

What the collection is holding: the vectors, the codes and the keys.

pub fn code_bytes(&self) -> usize

The searchable size of the collection, which is the number the 32x claim is about.

impl Collection

pub fn save<B: Blocks>( &self, blocks: &mut B, scratch: &mut Scratch, ) -> Result<Chain>

Write the collection down and say where the root went.

The root’s address and length are what a checkpoint entry records, so this returns the pair rather than putting it anywhere: which checkpoint this belongs to is the shard’s business.

Errors

Code::Full if a section is longer than a chain holds, which for the centroids means a collection with more partitions than 512 MiB of them, and whatever the store returns while it is being written to.

pub fn load<B: Blocks>( blocks: &mut B, at: Chain, stored: &impl Stored, ) -> Result<Restored>

Read a collection back out of an image, taking the vectors from stored.

Errors

Code::Corrupt for an image that does not describe a collection this build can hold: a kind or a metric it does not know, sections that disagree with the header that named them, an id in two partitions, or an id in a partition that the key table does not have.

Trait Implementations

impl Debug for Collection

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

Formats the value using the given formatter.