Compressing strings with FSST

We’ve released our Apache-licensed implementation of FSST, you can check it out on GitHub!

String compression, in brief

pub trait StringCodec {
  /// Decode and return the string at the given index.
  fn decode(index: usize) -> String;
}

Dictionary Encoding

pub struct DictionaryArray {
    /// The string at index `i` is replaced with the code `i`.
    /// Stored a single time at the top of the file.
    codes: Vec<String>,
    /// The encoded values. Each string is represented by
    /// an 8-byte code which is an index into the `codes`
    /// table.
    array: Vec<usize>,
}

impl StringCodec for DictionaryArray {
    fn decode(&self, index: usize) -> String {
        // Step 1: lookup the code in the `index` position
        let code = self.array[index];
        // Step 2: map the code back to a string
        self.codes[code].clone()
    }
}

• Dictionaries only operate at the level of entire strings. If you have repetition that only manifests at the substring level, dictionary encoding won’t help you.
• Dictionaries only compress well if your data is low-cardinality. As the number of unique values approaches the length of the array, dictionary compression becomes useless, and if you’re not careful it can even be larger than the raw dataset. This is especially pertinent for request logs, JSON records, UUIDs, and free text.
• You cannot use dictionary encoding to compress data that is not in the dictionary; you instead need to build a new dictionary from scratch. This comes up if you’re building a system that cares about fast append operations, and appending chunks to an existing column with a shared dictionary is desirable.

FSST has entered the chat

🎓 Peter Boncz, Thomas Neumann, and Viktor Leis. 2020. FSST: fast random access string compression.
Proc. VLDB Endow. 13, 12 (August 2020), 2649–2661.
https://doi.org/10.14778/3407790.3407851

Putting the ST in FSST

[0xFF, b'h', 0xFF, b'e', 0xFF, b'l', 0xFF, b'l', 0xFF, b'o']

struct FSSTArray {
    /// `symbols` stores the symbol table. Each symbol can be a string
    /// of 1 to 8 bytes, which we pack into a u64.
    symbols: Vec<u64>,

    /// The length of each symbol. This vector has the same length
    /// as `symbols`.
    symbol_lengths: Vec<u8>,

    /// The encoded variable-length byte array. bytes[i] is the i-th encoded
    /// string.
    ///
    /// Each encoded string will be a sequence of 8-bit unsigned
    /// integer offsets into the `symbols` table.
    bytes: Vec<Vec<u8>>
}

impl StringCodec for FSSTArray {
    fn decode(&self, index: usize) -> String {
        // Get the compressed value at the index.
        // This is a byte array of codes.
        let codes = self.bytes[index];
        let mut pos = 0;
        let mut result = Vec::new();
        while pos < codes.len() {
            let next_code = codes[pos];
            if next_code == ESCAPE {
                // Emit an escape byte
                pos += 1;
                result.push(code[pos]);
            } else {
                // Lookup the code in the symbol table
                let symbol = self.symbols[code];
                let len = self.symbol_lengths[code] as usize;
                result.extend_from_slice(&symbol.to_le_bytes()[0..len]);
            }

            pos += 1;
        }

        // Convert the UTF-8 encoded bytes into a String for the caller
        String::from_utf8(result).unwrap()
    }
}

A seat at the (symbol) table

• Maximum symbols: how big can the symbol table grow. This is directly linked to the code size. Because we’re using byte codes, this is 255 (leaving the 256th code for an escape).
• Maximum symbol length: How many bytes can each symbol hold? This was chosen to be 8 bytes so that it can always fit into a single 64-bit register.
• Number of generations: How many generations does the table selection algorithm proceed for? Because we concatenate symbols at the end of each generation, we must have at least 3 generations to have a chance to generate any 8 byte symbols. The creators of FSST did a lot of empirical testing and found 5 to provide the best balance between speed and compression quality.

• We compress our target string using our existing symbol table. When we compress, we count the symbols that were used in the encoded output. We also concatenate adjacent symbols as candidates for new symbols to add.
• For all existing and candidate symbols, we assign them a gain (count * length), and preserve the top 255 symbols by gain.
• We set the top 255 as the new symbol table to use in the next generation.

• Maximum symbols: 4
• Maximum symbol length: 3
• Number of generations: 2

• Extending support from single-strings to string arrays with many values. The naive way to do this is to call the compression/decompression kernels in a loop. A more advanced variant would compress the entire array range as a single mega-string to avoid branching.
• Training the symbol table on a whole array forces us to compress the full-size array 5 times, which is slow. Instead, we choose a small fixed-size sample of 16KB, drawn as 512B chunks sampled uniformly at random across all elements of the array. Both 16KB and 512 were chose empirically by the authors as good tradeoffs between locality (longer runs are more realistic representations of the source) and performance (getting a diverse enough sample to train a table that compresses the whole array well).
• The authors of the paper implemented an AVX-512 compression kernel, which we have not implemented in the Rust code but can lead to better performance over the scalar variant. You can learn more about their “meatgrinder” in Section 5 of the paper.

Closing thoughts