String columns dominate many real analytical workloads, but they are awkward for database engines: values are variable length, comparisons are branchy, and repeated prefixes or substrings waste bandwidth from disk to memory to CPU cache. Compression is therefore not just a storage-saving feature. In database execution engines, the best compression schemes reduce bytes moved while preserving enough structure for predicates, scans, and projections to stay fast.
FSST, or Fast Static Symbol Table, is a string compression scheme designed for database systems. It builds a small static table of frequent byte sequences, assigns one-byte codes to those symbols, and then encodes strings by greedily replacing common substrings with compact codes. CedarDB’s implementation combines FSST with dictionary compression: dictionary keys remain cheap fixed-width values for predicates, while FSST compresses the dictionary payload to reduce storage and cold-read cost.
The transferable topic is how to integrate a byte-oriented string codec into a columnar storage engine without destroying query performance. The engine must choose when FSST is worth it, persist symbol tables and offsets, keep filters on compressed keys when possible, and account for the trade-off that decompression-heavy hot queries can slow down even when cold scans become faster.
Dictionary compression stores unique strings once and replaces each row value with a small integer key. If the dictionary is sorted lexicographically, equality and range predicates can often translate the query literal into key ranges, then compare fixed-width integers across the column. That is far cheaper than decompressing and comparing variable-length strings for every row.
FSST builds a static table of up to 255 useful byte sequences, with one byte reserved as an escape code for literals that are not represented by a symbol. Symbols can be up to eight bytes long. Compression scans the input, chooses the longest matching symbol at each offset, and emits the one-byte code; decompression expands each code through the symbol table.
A storage engine should not apply FSST just because it saves a few bytes. CedarDB’s write-up describes using a penalty threshold so FSST must be meaningfully smaller than the next best scheme before it is chosen. That acknowledges the core trade-off: FSST can reduce I/O and cache pressure, but decompression is more expensive than returning a dictionary value or reading an uncompressed short string.
A database codec is successful only if it improves the end-to-end query plan. The compressed layout must support filtering, random access, selective decompression, and predictable memory behavior. A smaller byte stream that forces full decompression before every predicate can be a net loss.
FSST samples the input column, repeatedly estimates which byte sequences produce the highest compression gain, and stores the best symbols in a compact table. The table is static after construction, so decoding is simple and fast: each code indexes a symbol and copies its bytes to the output. The escape code preserves correctness for bytes or sequences not present in the table.
def build_fsst_symbols(sample_strings):
symbols = {}
for _ in range(MAX_ROUNDS):
counts = Counter()
for value in sample_strings:
encoded = encode_with_current_symbols(value, symbols)
counts.update(single_bytes(encoded))
counts.update(adjacent_symbol_pairs(encoded))
candidates = score_by_saved_bytes(counts)
symbols = choose_top(candidates, limit=255) # one code is reserved for ESC
return symbols
def encode(value, symbols):
out = bytearray()
i = 0
while i < len(value):
match = longest_symbol_at(value, i, symbols)
if match:
out.append(symbols[match].code)
i += len(match)
else:
out.append(ESC)
out.append(value[i])
i += 1
return outApplying FSST directly to every row value saves space but makes predicates harder because compressed strings remain variable-length byte sequences. The CedarDB pattern is to build the dictionary first, store row values as integer keys, and then FSST-compress the dictionary’s string payload. Equality predicates still binary-search the dictionary once, then scan integer keys. Decompression is delayed until a query actually needs to materialize output strings.
A persistent FSST block must store enough metadata to decode individual values: the symbol table, symbol lengths, compressed bytes, and offsets into the compressed byte region. In a dictionary-plus-FSST layout, the row column stores fixed-width dictionary keys; the dictionary stores offsets and compressed strings; and the FSST symbol table travels with the compressed block or segment.
Analytical engines scan many rows and often apply filters before projecting full string values. Dictionary-plus-FSST is a strong fit when the workload benefits from compact cold reads and can keep most predicate evaluation on integer keys. URL columns, categorical labels, names, paths, and generated benchmark strings often contain repeated substrings that FSST can exploit.
When data is read from disk or object storage, reducing bytes transferred can dominate decompression cost. CedarDB reports that enabling FSST reduced ClickBench storage by about 20% overall and string storage by about 35%, while TPC-H saw over 40% total storage reduction and almost 60% string storage reduction. Those savings can directly improve cold-scan latency.
The same layout concerns apply to columnar file formats and data interchange layers. A compressed string column should carry its symbol table, offsets, validity information, and statistics in a way that allows readers to skip, filter, or lazily materialize data. The goal is interoperability without forcing every consumer to eagerly inflate every string.
Choose the codec per segment or block, not globally. Sample the segment, estimate candidate layouts, and record the winning scheme in metadata. Include a penalty threshold so a more CPU-expensive codec must earn its place through substantial byte savings.
type CompressionChoice struct {
Scheme string
EncodedBytes int
DecodeCost float64
}
func chooseStringCodec(candidates []CompressionChoice, fsstPenaltyPct int) CompressionChoice {
best := minBySize(candidates)
second := secondBestBySize(candidates)
if best.Scheme == "DICT_FSST" {
required := second.EncodedBytes * (100 - fsstPenaltyPct) / 100
if best.EncodedBytes > required {
return second
}
}
return best
}Keep predicates in the compressed domain whenever possible. For equality, find the literal in the sorted dictionary and compare row keys. For ranges, find lower and upper dictionary key bounds. For substring or LIKE predicates, expect more decompression unless the engine maintains additional indexes or specialized summaries.
Decompress only values that survive filters and are required by the projection. If a query filters on one compressed string column but returns numeric aggregates, the engine may never need to materialize most strings. This is where dictionary-plus-FSST can outperform direct row-wise compression.