Struct fuzzy_rocks::Table

pub struct Table<ValueT: Serialize + DeserializeOwned, const MAX_DELETES: usize, const MEANINGFUL_KEY_LEN: usize, const UNICODE_KEYS: bool> { /* fields omitted */ }

A collection containing records that may be searched by key

-MAX_DELETES is the number of deletes to store in the database for variants created by the SymSpell optimization. If MAX_DELETES is too small, the variant will not be found and therefore the distance_function will not have an opportunity to evaluate the match. However, if MAX_DELETES is too large, it will hurt performance by evaluating too many candidates.

Empirically, values near 2 seem to be good in most situations I have found. I.e. 1 and 3 might be appropriate sometimes. 4 ends up exploding in most cases I’ve seen so the SymSpell logic may not be a good fit if you need to find keys 4 edits away. 0 edits is an exact match.

-MEANINGFUL_KEY_LEN is an optimization where only a subset of the key is used for creating variants. So, if MEANINGFUL_KEY_LEN = 10 then only the first 10 characters of the key will be used to generate and search for variants.

This optimization is predicated on the idea that long key strings will not be very similar to each other. For example the key incomprehensibilities will cause variants to be generated for incomprehe, meaning that a search for incomprehension would find incomprehensibilities and evauate it with the distance_function even though it is further than MAX_DELETES.

In a dataset where many keys share a common prefix, or where keys are organized into a namespace by concatenating strings, this optimization will cause problems and you should either pass a high number to effectively disable it, or rework this code to use different logic to select the substring

-UNICODE_KEYS specifies whether the keys are UTF-8 encoded strings or not. UFT-8 awareness is required to avoid deleting partial characters thus rendering the string invalid. This comes at a performance cost, however, so passing false is more efficient if you plan to use regular ascii or any other kind of data as the table’s keys.

Implementations

impl<ValueT: 'static + Serialize + DeserializeOwned, const MAX_DELETES: usize, const MEANINGFUL_KEY_LEN: usize, const UNICODE_KEYS: bool> Table<ValueT, MAX_DELETES, MEANINGFUL_KEY_LEN, UNICODE_KEYS>

pub fn new(path: &str) -> Result<Self, String>

Creates a new Table, backed by the database at the path provided

WARNING: No sanity checks are performed to ensure the database being opened matches the parameters of the table being created. Therefore you may see bugs if you are opening a table that was created using a different set of parameters.

NOTE: rocksdb::Error is a wrapper around a string, so if an error occurs it will be the unwrapped RocksDB error.

pub fn reset(&mut self) -> Result<(), String>

Resets a Table, dropping every record in the table and restoring it to an empty state.

(Dropping in a database sense, not a Rust sense)

pub fn record_id_is_valid(&self, record_id: RecordID) -> bool

Returns true if a RecordID can be used to refer to a record in a Table, otherwise returns false. A deleted record will still have a valid RecordID.

Use this function instead of comparing a RecordID to RecordID::NULL.

pub fn delete(&mut self, record_id: RecordID) -> Result<ValueT, String>

Deletes a record from the Table.

A deleted record cannot be accessed or otherwise found, but the RecordID may be reassigned using Table::replace.

pub fn get_value(&self, record_id: RecordID) -> Result<ValueT, String>

Returns the value associated with the specified record

NOTE: rocksdb::Error is a wrapper around a string, so if an error occurs it will be the unwrapped RocksDB error.

pub fn default_distance_func(&self) -> impl Fn(&[u8], &[u8]) -> u64

Convenience function that returns the edit_distance function associated with a Table

pub fn edit_distance(key_a: &[u8], key_b: &[u8]) -> u64

An implementation of the basic Levenstein distance function, which may be passed to lookup_fuzzy, lookup_best, or used anywhere else a distance function is needed.

This implementation uses the Wagner-Fischer Algorithm, as it’s described here

impl<ValueT: 'static + Serialize + DeserializeOwned, const MAX_DELETES: usize, const MEANINGFUL_KEY_LEN: usize> Table<ValueT, MAX_DELETES, MEANINGFUL_KEY_LEN, true>

pub fn insert(&mut self, key: &str, value: &ValueT) -> Result<RecordID, String>

Inserts a new key-value pair into the table and returns the RecordID of the new record

This function will always create a new record, regardless of whether an identical key exists. It is permissible to have two distinct records with identical keys.

NOTE: This function takes an &T for value rather than an owned T because it must make an internal copy regardless of passed ownership, so requiring an owned object would ofter result in a redundant copy. However this is different from most containers, and makes things feel awkward when using String types for values.

NOTE: rocksdb::Error is a wrapper around a string, so if an error occurs it will be the unwrapped RocksDB error.

pub fn replace(
    &mut self,
    record_id: RecordID,
    key: &str,
    value: &ValueT
) -> Result<(), String>

Replaces a record in the Table with the supplied key-value pair

If the supplied record_id references an existing record, the existing record contents will be deleted. If the supplied record_id references a record that has been deleted, this function will succeed, but is the record_id is invalid then this function will return an error.

If the key exactly matches the existing record’s key, this function will be more efficient as it will not need to update the stored variants.

NOTE: rocksdb::Error is a wrapper around a string, so if an error occurs it will be the unwrapped RocksDB error.

pub fn get_record(
    &self,
    record_id: RecordID
) -> Result<(String, ValueT), String>

Returns the key and value associated with the specified record

NOTE: rocksdb::Error is a wrapper around a string, so if an error occurs it will be the unwrapped RocksDB error.

pub fn lookup_exact<'a>(
    &'a self,
    key: &'a str
) -> Result<impl Iterator<Item = RecordID> + 'a, String>

Locates all records in the table with keys that precisely match the key supplied

NOTE: rocksdb::Error is a wrapper around a string, so if an error occurs it will be the unwrapped RocksDB error.

pub fn lookup_fuzzy_raw<'a>(
    &'a self,
    key: &'a str
) -> Result<impl Iterator<Item = RecordID> + 'a, String>

Locates all records in the table with a key that is within a deletion distance of MAX_DELETES of the key supplied, based on the SymSpell algorithm.

This function underlies all fuzzy lookups, and does no further filtering based on any distance function.

NOTE: rocksdb::Error is a wrapper around a string, so if an error occurs it will be the unwrapped RocksDB error.

pub fn lookup_fuzzy<'a, D: 'static + Copy + Zero + PartialOrd, F: 'a + Fn(&[u8], &[u8]) -> D>(
    &'a self,
    key: &'a str,
    distance_function: F,
    threshold: D
) -> Result<impl Iterator<Item = (RecordID, D)> + 'a, String>

Locates all records in the table for which the supplied distance_function evaluates to a result smaller than the supplied threshold when comparing the record’s key with the supplied key

NOTE: rocksdb::Error is a wrapper around a string, so if an error occurs it will be the unwrapped RocksDB error.

pub fn lookup_best<D: 'static + Copy + Zero + PartialOrd, F: Fn(&[u8], &[u8]) -> D>(
    &self,
    key: &str,
    distance_function: F
) -> Result<RecordID, String>

Locates the record in the table for which the supplied distance_function evaluates to the lowest value when comparing the record’s key with the supplied key.

If no matching record is found within the table’s MAX_DELETES, this method will return an error.

NOTE: If two or more results have the same returned distance value and that is the smallest value, the implementation does not specify which result will be returned.

NOTE: rocksdb::Error is a wrapper around a string, so if an error occurs it will be the unwrapped RocksDB error.

impl<ValueT: 'static + Serialize + DeserializeOwned, const MAX_DELETES: usize, const MEANINGFUL_KEY_LEN: usize> Table<ValueT, MAX_DELETES, MEANINGFUL_KEY_LEN, false>

pub fn insert(&mut self, key: &[u8], value: &ValueT) -> Result<RecordID, String>

Inserts a new key-value pair into the table and returns the RecordID of the new record

This function will always create a new record, regardless of whether an identical key exists. It is permissible to have two distinct records with identical keys.

NOTE: This function takes an &T for value rather than an owned T because it must make an internal copy regardless of passed ownership, so requiring an owned object would ofter result in a redundant copy. However this is different from most containers, and makes things feel awkward when using String types for values.

NOTE: rocksdb::Error is a wrapper around a string, so if an error occurs it will be the unwrapped RocksDB error.

pub fn replace(
    &mut self,
    record_id: RecordID,
    key: &[u8],
    value: &ValueT
) -> Result<(), String>

Replaces a record in the Table with the supplied key-value pair

If the supplied record_id references an existing record, the existing record contents will be deleted. If the supplied record_id references a record that has been deleted, this function will succeed, but is the record_id is invalid then this function will return an error.

If the key exactly matches the existing record’s key, this function will be more efficient as it will not need to update the stored variants.

NOTE: rocksdb::Error is a wrapper around a string, so if an error occurs it will be the unwrapped RocksDB error.

pub fn get_record(
    &self,
    record_id: RecordID
) -> Result<(Box<[u8]>, ValueT), String>

Returns the key and value associated with the specified record

NOTE: rocksdb::Error is a wrapper around a string, so if an error occurs it will be the unwrapped RocksDB error.

pub fn lookup_exact<'a>(
    &'a self,
    key: &'a [u8]
) -> Result<impl Iterator<Item = RecordID> + 'a, String>

Locates all records in the table with keys that precisely match the key supplied

NOTE: rocksdb::Error is a wrapper around a string, so if an error occurs it will be the unwrapped RocksDB error.

pub fn lookup_fuzzy_raw<'a>(
    &'a self,
    key: &'a [u8]
) -> Result<impl Iterator<Item = RecordID> + 'a, String>

Locates all records in the table with a key that is within a deletion distance of MAX_DELETES of the key supplied, based on the SymSpell algorithm.

This function underlies all fuzzy lookups, and does no further filtering based on any distance function.

NOTE: rocksdb::Error is a wrapper around a string, so if an error occurs it will be the unwrapped RocksDB error.

pub fn lookup_fuzzy<'a, D: 'static + Copy + Zero + PartialOrd, F: 'a + Fn(&[u8], &[u8]) -> D>(
    &'a self,
    key: &'a [u8],
    distance_function: F,
    threshold: D
) -> Result<impl Iterator<Item = (RecordID, D)> + 'a, String>

Locates all records in the table for which the supplied distance_function evaluates to a result smaller than the supplied threshold when comparing the record’s key with the supplied key

NOTE: rocksdb::Error is a wrapper around a string, so if an error occurs it will be the unwrapped RocksDB error.

pub fn lookup_best<D: 'static + Copy + Zero + PartialOrd, F: Fn(&[u8], &[u8]) -> D>(
    &self,
    key: &[u8],
    distance_function: F
) -> Result<RecordID, String>

Locates the record in the table for which the supplied distance_function evaluates to the lowest value when comparing the record’s key with the supplied key.

If no matching record is found within the table’s MAX_DELETES, this method will return an error.

NOTE: If two or more results have the same returned distance value and that is the smallest value, the implementation does not specify which result will be returned.

NOTE: rocksdb::Error is a wrapper around a string, so if an error occurs it will be the unwrapped RocksDB error.

Trait Implementations

impl<ValueT: Serialize + DeserializeOwned, const MAX_DELETES: usize, const MEANINGFUL_KEY_LEN: usize, const UNICODE_KEYS: bool> Drop for Table<ValueT, MAX_DELETES, MEANINGFUL_KEY_LEN, UNICODE_KEYS>

fn drop(&mut self)

Executes the destructor for this type.