Struct SymbolTable 

pub struct SymbolTable { /* private fields */ }

A trained symbol table, and everything needed to compress and decompress against it.

Implementations

impl SymbolTable

pub fn footprint(&self) -> usize

How many bytes of memory this table is holding.

Mostly the hash table, which is sixty five thousand slots however few symbols are in it. That is the number a vector in FSST form reports, and it is why the form is a decision about a page rather than about a chunk: one table over a hundred chunks is nothing per chunk and one table per chunk is a megabyte.

pub fn empty() -> Self

A table with no symbols, which escapes everything and doubles its input. The starting point of training, and what a column of nothing but unique bytes ends up with.

pub fn train(samples: &[&[u8]]) -> Self

Trains a table on a sample.

The caller picks the sample. Section 6.3 says a systematic sample across the chunk rather than the first N rows, because column data is frequently clustered, and that decision belongs to whoever knows what the chunk is rather than to this function.

pub fn len(&self) -> usize

How many symbols are in the table.

pub fn is_empty(&self) -> bool

Whether the table has no symbols, in which case every byte of every string escapes.

pub fn serialized_len(&self) -> usize

How many bytes serialize writes. At most 2049 for a full table, and that is the number section 6.4 is weighing when it says a shared symbol table is cheaper than a shared dictionary.

pub fn serialize(&self, out: &mut Vec<u8>)

Writes the table itself, which has to travel with the data it compressed.

pub fn deserialize(bytes: &[u8]) -> Result<(Self, usize)>

Reads back what serialize wrote, and says how many bytes it consumed.

Errors

If the bytes are truncated or describe a symbol of zero or more than eight bytes.

pub fn compress(&self, input: &[u8], out: &mut Vec<u8>)

Compresses one string, appending to out.

Strings are compressed one at a time against a shared table rather than as one stream, because that is what keeps random access, which is the first of the two reasons this encoding was chosen at all.

pub fn decompress(&self, input: &[u8], out: &mut Vec<u8>) -> Result<()>

Decompresses one string, appending to out.

A symbol goes out as all eight of the bytes its u64 holds, and then the cursor steps back over the ones that were not part of it. Eight is a length the compiler knows, so that is one store. The length a symbol really has is only known at run time, so copying exactly that many bytes is a call into memcpy for one to eight of them, and building a Vec to copy them out of, which is what this used to do, is a heap allocation and a free on top.

That mattered more than anything else in the engine. SELECT COUNT(*) FROM hits WHERE URL LIKE '%google%' over ClickBench spends almost all of its time here, because the search itself runs once per distinct URL and finding those means decompressing the column, and the allocation, the free and the copy together were 41% of the query.

Errors

If the input ends on an escape byte, or holds a code the table does not have.

Trait Implementations

impl Debug for SymbolTable

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

Formats the value using the given formatter.

impl Eq for SymbolTable

impl PartialEq for SymbolTable

Two tables are equal when they hold the same symbols in the same order.

The three lookup tables are built from the symbols when a table is built and hold nothing the symbols do not, so comparing them would be comparing the same information a second time over sixty five thousand entries. A vector in FSST form carries a table, and a vector is compared for equality all over the tests, so this is on a path that gets walked.

fn eq(&self, other: &Self) -> bool

Equality operator ==.

fn ne(&self, other: &Rhs) -> bool

Inequality operator !=.