FSST: Fast Random Access String Compression

Peter Boncz Thomas Neumann Viktor Leis

CWI TUM FSU Jena
boncz@[Link] neumann@[Link] [Link]@[Link]

ABSTRACT
corpus corpus
Strings are prevalent in real-world data sets. They often
(uncompressed) symbol table (compressed)
occupy a large fraction of the data and are slow to process.
In this work, we present Fast Static Symbol Table (FSST), [Link] 0 http:// 7 063
a lightweight compression scheme for strings. On text data, [Link] 1 www. 4 07
FSST offers decompression and compression speed similar to [Link] 2 uni-jena 8 123
or better than the best speed-optimized compression meth- [Link] 3 .de 3 1854
ods, such as LZ4, yet offers significantly better compression [Link] 4 .org 4 0194
factors. Moreover, its use of a static symbol table allows ran-
... 5 a 1 ...
6 [Link] 6
dom access to individual, compressed strings, enabling lazy
7 [Link] 6
decompression and query processing on compressed data. 8 wikipedi 8
We believe these features will make FSST a valuable piece 9 vldb 4
in the standard compression toolbox. ...
255
PVLDB Reference Format:
Peter Boncz, Thomas Neumann, and Viktor Leis. FSST: Fast symbol length
Random Access String Compression. PVLDB, 13(11): 2649-2661, Figure 1: FSST provides very fast – yet effective –
2020.
DOI: [Link] string compression, by replacing symbols of length
1-8 by 1-byte codes. Finding a good symbol table
is a key challenge, addressed in Section 4. Tech-
1. INTRODUCTION niques to make FSST compression very fast, includ-
In many real-world databases, including ERP [18] and vi- ing AVX512, are described in Section 5.
sual analytics [21], a large fraction of the data is represented
as strings. This is because strings are often used as a catch-
all type for data of wide variety: In real-world databases, Most strings stored in databases are fairly small – gen-
both human-generated text (e.g., description or comment erally less than 200 bytes and often less than 30 bytes per
fields) and machine-generated identifiers (e.g., URLs, email string. General-purpose compressors such as LZ4 are not
addresses, IP addresses, UUIDs, non-integer surrogate keys) suited for compressing small, individual strings, because they
are virtually always represented as strings. require input sizes on the order of several kilobytes for good
Strings are often highly compressible, and many systems compression factors (cf. Section 6.1). Some columnar data-
rely on dictionaries to compress strings. However, because base systems therefore use these general-purpose compres-
strings often have many unique values, dictionary compres- sion methods on coarse granularity, compressing columnar
sion, which uniquely maps strings to fixed-size integers, is blocks of disk-resident data (i.e., compressing many string
not always effective or applicable. Dictionary compression values together). However, database systems generally bene-
needs fully repeating strings to reduce size, and thus does fit from random access to individual string attributes, which
not benefit when strings are similar but not equal. Also, is not possible when using block-wise general-purpose string
many systems apply dictionary compression on chunks that compression. Examples of database access that requires
are smaller than the whole relation (e.g. row groups or data random access to individual strings are: selection push-
blocks), which may limit its effectiveness further. down in data scans (e.g., with strings stored in a colum-
nar block), data access in joins and aggregations (e.g., with
strings stored in a hash table) – or in fact any operator that
This work is licensed under the Creative Commons Attribution- does not consume all values in sequential order.
NonCommercial-NoDerivatives 4.0 International License. To view a copy We present Fast Static Symbol Table (FSST) compres-
of this license, visit [Link] For sion, a lightweight encoding scheme for strings. As is illus-
any use beyond those covered by this license, obtain permission by emailing trated in Figure 1, the key idea behind FSST is to replace
info@[Link]. Copyright is held by the owner/author(s). Publication rights frequently-occurring substrings of up to 8 bytes with 1-byte
licensed to the VLDB Endowment. codes. Decompression is very fast as it merely needs to
Proceedings of the VLDB Endowment, Vol. 13, No. 11
ISSN 2150-8097. translate each 1-byte code into a longer string using an ar-
DOI: [Link] ray of 256 entries. These entries form an immutable symbol

2649
table that is shared among a block of string values, enabling 2. RELATED WORK
decompressing individual strings. Previous random-access Most research on lightweight compression for database
compression schemes [9, 14, 4, 15] are much slower than systems concentrates on integer data [25, 11, 13, 20, 17,
FSST on bulk compression and decompression, which may 8]. Similarly, work on query processing on compressed data
explain why they have not been widely adopted. generally does not focus on strings [22, 6]. We argue that
The key features of FSST are given the prevalence and performance challenges of strings in
• random access (the ability to decompress individual real-world workloads [18, 12, 21], more research is required.
strings without having to decompress a larger block), The most common approach for compressing strings is de-
duplication using dictionaries [25, 11, 13, 20]. Dictionaries
• fast decoding (≈ 1-3 cycles/byte, or 1-3 GB/s per core, map each unique string to an integer code. The column
depending on the data set), then consists of these integer codes, which can addition-
• good compression factors (≈ 2×) for textual string ally be compressed using an integer compression scheme.
data sets, and The strings themselves, which can make up the bulk of the
data even after de-duplication, are not compressed in most
• high encoding performance (≈ 4 cycles/byte, or ≈ 1 database systems. In the following, we describe some of the
GB/s per core). proposals for compressing the string data itself.
In comparison with LZ4, which is so far the best general- Binnig et al. [5] propose an order-preserving string dictio-
purpose lightweight compression method (effective and much nary with delta-prefix compression. The dictionary is repre-
faster than e.g., snappy and zstd [1, 2]), FSST is better over sented as a hybrid trie/B-tree data structure that stores the
all dimensions on typical database string columns. FSST unique strings in sorted order. This order is exploited by
provides comparable – but often, faster – decompression and the delta-prefix compression, which truncates the common
compression speed, and noticeably better compression fac- prefixes of neighboring strings. To enable reasonably fast
tors on textual data on top of its ability to compress and random access to individual strings, the full string is stored
decompress strings individually, enabling random-access – for every k (e.g., 16) strings. While delta-prefix compression
which stands in contrast with all general-purpose methods is effective for some data sets (e.g., URLs), many other com-
(including LZ4) that only support efficient block-wise de- mon string data sets (e.g., UUIDs) do not have long shared
compression. These features are useful in many applica- prefixes, which makes this scheme ineffective. Global dic-
tions, but are particularly useful in database systems. Fast tionaries have additional downsides (e.g., more expensive
compression and decompression enables all strings in the updates) that have precluded their widespread adoption.
database to be stored in compressed form without significant Another approach for compressing the string dictionary
performance loss, and being able to decompress individual was proposed by Arz and Fischer [4], who developed a vari-
strings enables fast point access (e.g., into a B-tree, a trie, ant of LZ78 [24] that allows decompressing individual strings.
a hash-table, or a sort buffer holding compressed strings). However, with this approach decompression is fairly expen-
FSST can be integrated into existing data management sive, requiring more than 1 microsecond for strings with an
systems and columnar file formats like Parquet, and should average length of 19 [4]. This corresponds to roughly 100
be used in conjunction with dictionary compression. In CPU cycles per character or tens of megabytes per second,
other words, after de-duplicating strings, FSST can be used which is too slow for many data management use cases.
to compress the unique strings within the dictionary. Given PostgreSQL does not use string dictionaries, but instead
that strings make up a large fraction of real-world data [18, implements an approach called “The Oversized-Attribute
21], this can have a substantial impact on overall space con- Storage Technique” (TOAST). Values that are larger than
sumption. The C++ source code of FSST released under 2 KB are compressed using a “fairly simple and very fast
the MIT License, the “dbtext” compression database text member of the LZ family of compression techniques” [3],
corpus we contribute, and the replication package of this and smaller values remain uncompressed. 2 KB is indeed a
paper are available here: reasonable threshold for general-purpose compression algo-
rithms, but short strings require a different approach.
[Link] Byte Pair [9, 23] is one of few compression schemes that al-
The rest of the paper is organized as follows. In Sec- low decompressing individual, short strings. It first performs
tion 2 we first describe related work on string compression, a full pass over the data, determining which byte values do
which is surprisingly sparse in comparison with the avail- not occur in the input and counting how often each pair of
able research on integer compression. Section 3 then in- bytes occur. It then replaces the most common pair of bytes
troduces the basic idea behind FSST and how decompres- with an unused byte value. This process is repeated until
sion is implemented. The key algorithmic challenge of our there are no more unused bytes. In contrast to FSST’s es-
approach is finding a good symbol table given a particu- caping scheme, Byte Pair’s reliance on unused bytes implies
lar data set, for which we provide a genetic-like bottom-up that, in general, unseen data cannot be compressed given
algorithm in Section 4. FSST decompression is fast right an existing compression table. The recursive nature of Byte
out of the box, but making compression fast is non-trivial. Pair makes decompression iterative and – therefore – slow.
Techniques for this, including using AVX512 SIMD, are de- RePair [14] (Recursive Pairing) is a random-access com-
scribed in Section 5. Section 6 evaluates FSST using a wide pression format that recursively constructs a hierarchical
variety of real-world string data showing that it offers good symbol grammar. The initial grammar consists of all single-
(de)compression speed and very good compression factors. byte symbols, and is recursively extended by replacing the
We also include an evaluation on TPC-H, where FSST is most frequent pair of consecutive symbols in the source text
integrated in the Umbra database system. Finally, we sum- by a new symbol, reevaluating the frequencies of all of the
marize the paper and present future work in Section 7. symbol pairs with respect to the extended grammar, and

2650
Algorithm 1 FSST-decoding Algorithm 2 FSST-encoding, given a symbol table.
void decode(uint8_t*& in, uint8_t*& out, void encode(uint8_t*& in,uint8_t*& out, SymbolTable& st)
uint64_t sym[255], uint8_t len[255]) { { uint16_t pos = [Link](in);
uint8_t code = *in++; if (pos <= 255) { // no (real) symbol found
if (code != 255) { *(out++) = 255;
*((uint64_t*)out) = sym[code]; *(out++) = *(in++);
out += len[code]; } else {
} else { // escape code *(out++) = (uint8_t) pos;
*out++ = *in++; in += [Link][pos].len; // symbol length in bytes
} }
} }

then repeating the process until there is no pair of adja- Relying on the fast unaligned stores that are available
cent symbols that occurs twice. Grammar construction in on modern processors, this implementation requires few in-
RePair is expensive, and the constructed grammar can be structions and is branch-free. It is also cache efficient as both
large and complex. Recent work improved RePair decoding the symbol table (2048 byte) and the length array (256 byte)
speed using AVX512, but the reported throughput is still easily fit into the level 1 CPU cache.
below 100MB/s [15], 20× slower than FSST; while encoding
remains at least two orders of magnitude slower than FSST. 3.2 Escape Code
We reserve the code 255 as an escape marker indicating
that the following byte in the input needs to be copied as is,
3. FAST STATIC SYMBOL TABLE i.e., without lookup in the symbol table. Note that having
FSST’s compression is based on the observation that, al- an escape code is not strictly necessary; it would also be
though each individual string might be short and have little possible to use only those bytes that do not occur in the in-
redundancy, the strings of a column often have common sub- put string as codes (as in the Byte Pair scheme discussed in
strings. To exploit this, FSST identifies frequently-occurring Section 2). However, escaping has three advantages. First,
substrings, which we call symbols, and replaces them with it enables compressing arbitrary (unseen) text using an ex-
short, fixed-size codes. Figure 1 illustrates this idea. For a isting symbol table. Second, it allows symbol table con-
URL corpus like the one shown in the figure, good symbols struction to be performed on a sample of the data, thereby
might be “[Link] “www.”, and “.org”. speeding up compression. Third, it frees up symbols that
For efficiency reasons, symbols have a length between 1 would otherwise be reserved for low-frequency bytes, thereby
and 8 bytes and are identified at byte (not bit) boundaries. improving the compression factor. Algorithm 1 shows the
Codes are always 1 byte long, which means there can be up implementation of decoding with escaping. While this code
to 256 symbols. However, one of the codes is reserved as an contains a branch, it is well predictable since escape charac-
escape code as described in Section 3.2. ters are rare in real-world data sets (otherwise the escaped
Given a particular data set, the compression algorithm input byte would have been included in the symbol table).
first constructs a symbol table that maps codes to symbols Therefore, in practice, this version is faster than the one
(and vice versa). One crucial aspect of FSST is that the without escaping thanks to its higher compression factor.
symbol table, which is the only state used during decom- Our open-source implementation optimizes decoding by
pression, is immutable (i.e., static). This allows individual detecting the absence of escapes (byte 255) in the next 4-byte
strings to be decompressed independently without having word using computation, and if so, decodes 4 codes without
to decompress any other strings in the same compression having to look for escapes. It handles the presence of escapes
block. General-purpose compression algorithms like LZ4, in efficiently using a programming trick called “Duff’s device”.
contrast, modify their internal state during compression and All in all, FSST decoding is among the fastest string decom-
decompression, which precludes cheap point access. pressors, approaching 2 GB/s in our evaluation.

3.1 Decompression 3.3 Compression

Given a symbol table and a compressed string, decompres- The algorithmic challenge of FSST is finding a symbol ta-
sion is fairly simple. Each code is translated via an array ble for a given data set – we describe how to do this in Sec-
lookup into its symbol and the symbols are appended to the tion 4. However, as Algorithm 2 shows, given a symbol ta-
output buffer. To make decompression efficient, we repre- ble, the actual compression is conceptually straightforward.
sent each symbol as an 8-byte (64-bit) word and store all findLongestSymbol finds the longest matching symbol at the
symbols in an array. In addition, we have a second array current input position. If no matching symbol was found,
that stores the length of each word. Using this representa- the input byte is escaped. Otherwise, the output is the code
tion, a code can be decompressed by unconditionally storing of the symbol found and the input position is incremented
the 64-bit word into the output buffer, and then advancing by the length of the symbol. Given the simplicity of the rest
the output buffer by the actual length of the symbol: of the code, it is clear that the performance of compression
is dominated by findLongestSymbol. Its implementation is
void decodeBasic(uint8_t*& in, uint8_t*& out, described in Section 4.3.
uint64_t sym[256], uint8_t len[256]) {
uint8_t code = *in++; 3.4 Useful Properties
*((uint64_t*)out) = sym[code]; // fast unaligned store
out += len[code]; Strings stay Strings. Strings compressed in FSST be-
} come sequences of codes, i.e., sequences of bytes, so they ef-

2651
fectively stay strings. This benefits the integration of FSST byte only occurs at the end of each string, there are ef-
in existing (database) systems. Namely, already existing in- fectively 254 codes left for compression. This slightly de-
frastructures to store strings can be re-used unchanged. grades compression (the 255-least valuable symbol has to
be dropped from the symbol table, and its occurrences will
Compressed Query Processing. When querying an FSST- be handled using escaped bytes), but this optional mode
compressed database, one can postpone decompressing these allows FSST to fit into many existing infrastructures.
values early in the query and do this only later. One rea-
son that may force decompression is that some function or
operator in the query actually needs to inspect the string
4. SYMBOL TABLE CONSTRUCTION
values. Strings often face equality comparisons and a nice The compression factor achieved by FSST on a data set
property of FSST is that such comparisons can be directly depends on the 255 symbols chosen for the symbol table. We
performed on the compressed value (even with the standard first discuss why constructing a good symbol table is chal-
string equality function), as long as both operands are com- lenging and then describe an effective bottom-up algorithm.
pressed with the same symbol table. Hence, in queries with
an equality-selection predicate that compare a (compressed)
4.1 The Dependency Issue
table column against a constant, one can compress this con- A naive, single-pass algorithm for constructing a symbol
stant and then process the predicate on compressed strings. table would be to first count how often each substring of
length 1 through 8 occurs in the data, and then pick the top
String Matching. It may be possible to perform more 255 symbols ordered by gain (i.e., number of occurrences *
complex often-occurring string operations (e.g., LIKE pattern symbol length). The problem with this approach is that the
matching) on compressed strings as well, by the transforma- chosen symbols may overlap, and that the computed gains
tion of automata designed for their recognition in a byte- are therefore overestimates. In a URL data set, for exam-
stream – re-mapping these onto a code-stream. This paper ple, the 8-byte symbol “[Link] might be chosen as the
will not endeavor this route yet: we leave it to future work. most promising symbol. However, the symbols “ttp://ww”
However, it may not always be beneficial to perform costly and “tp://www” would seem equally promising, even though
operations on FSST-compressed strings, because FSST de- they do not improve compression once “[Link] has been
compression is so fast; hence the compressed method should added to the symbol table. Adding all three candidates to
never become slower by more than the compression factor. the symbol table would be a waste of the limited number of
Late Decompression. If the operators that access the codes and would negatively affect the compression factor.
strings require their decompression, this can be done just Another issue is that greedily picking the longest symbol
before it is needed; all operators lower in the query plan during encoding does not necessarily maximize compression
can just store, copy and forward the compressed strings. effectiveness. For example, if “[Link] “<a href=”, and
The smaller size of the strings will make such manipula- “h” would be symbols in the symbol table, then the encode()
tion faster, but it will also decrease the size of hash-tables, method would not use the most valuable symbol “[Link]
sort-buffers (reducing cache misses) and exchange spreading to encode the string “<a href="[Link] be-
buffers (also reducing network traffic, in case of parallel and cause the symbol “"h” would have consumed the letter “h”
distributed query processing). Decoding strings on a remote already1 . To summarize, symbol overlap combined with
computer may require sending the symbol table, which, as greedy encoding create the dependency issue between sym-
we will argue next, is small. bols that makes it hard to estimate gain and therefore to
create good symbol tables. To reflect the dependency issue
Small Symbol Table. Symbol tables have a maximum between symbols in compression, we call the gain computed
size of 8*255+255 bytes, but typically take just a few hun- based on frequency in the text static gain. The actual gain
dred bytes, because the average symbol length usually is achieved by a symbol is often significantly less.
around two. Thus, it is perfectly feasible to compress each Our first attempt at symbol table construction created a
page for each string column with a separate symbol table, suffix array to identify the symbols with highest gain. With
but more coarse-grained granularities are also possible (per a suffix array-based approach, the first symbol picked will
row-group, or the whole table). Finer-grained symbol table indeed have the highest compression gain. However, the
construction leads to better compression factors, since the compression gain of subsequent symbols depends on earlier
symbol table will be more tuned to the compressed data. symbols. Correcting for the dependencies on earlier sym-
This does complicate the processing infrastructure for op- bols is very difficult and, depending on how it is done, leads
erating on compressed strings, since it needs to keep track to large over- or underestimates. For this reason this ap-
which symbol table belongs to which string. proach produced significantly worse symbol tables than the
evolutionary algorithm we will present subsequently.
Parallelism. Since there is no (de)compression state, FSST
To deal with the dependency issue, one could fall back
(de)compression is trivial to parallelize – only the symbol
to generating all possible symbol tables, testing them, and
table construction algorithm may need to be serialized. On
choosing the best one. The cost of testing one solution, is
the other hand, it may also be acceptable to have each thread
the cost of compressing the text, which is linear in its size
that bulk-loads a chunk of data construct a separate symbol
N . However, finding an optimal solution (i.e., the 255 sym-
table (that should be put into each block header), such that
bols that give the highest compression) is computationally
compression also becomes trivially parallel.
1
We experimented with an encoding function that frames
0-terminated Strings. FSST optionally can generate 0- string compression as a dynamic programming problem,
terminated strings (as used in C): code 0 then encodes the rather than applying findLongestSymbol() greedily. However,
zero-byte symbol. Because in 0-terminated strings the zero- we found that the compression factor only marginally im-
proves, while encoding performance is severely affected.

2652
Uncompressed bol table by compressing, one can also count the pairs of sub-
t u m c w i t u m v l d b len = 13 sequent codes that manifest themselves to the compressor.
The pair of two symbols is a candidate for becoming a new,
empty symbol table
longer symbol. Thereby, we refine the symbol table by con-
catenating frequently-occurring pairs of short symbols into
Iteration 1 new, longer, higher-gain symbols. To exploit these ideas,
$ t $ u $ m $ c $ w $ $ d $ b the symbol table construction algorithm performs multiple
len = 26 iterations in which it refines the symbol table. In each iter-
Symbol table symbol um tu wi cw mc ation, we add new promising symbols that then replace less
len 2 2 2 2 2
count 2 2 1 1 1 worthwhile symbols from the previous iteration.
gain 4 4 2 2 2 (len * cnt) Our iterative algorithm starts with an empty symbol ta-
ble. Each iteration consists of two steps: (1) we iterate over
the corpus, encoding it on the fly using the current symbol
Iteration 2
table. This phase calculates the overall quality of the sym-
tu mc wi tu $ m $ v $ l $ d $ b len = 14 bol table (the compression factor), but also counts how often
Symbol table symbol tum tu wit mcw vl each symbol occurs in the compressed representation, as well
len 3 2 3 3 2 as each pair of successive symbols. (2) we use these counts
count 2 2 1 1 1 to construct a new symbol table by selecting the symbols
gain 6 4 3 3 2 with the highest apparent gains.
We always consider all symbols from the previous gener-
Iteration 3 ation, plus all new symbols generated by concatenating all
tum $ c wit $ u $ m vl $ d $ b len = 13
occurring pairs of symbols. The new generation of symbols
in the next iteration simply consists of the top-255 symbols
Symbol table symbol mvl cwi vld tum wit considering their apparent gain in the previous iteration.
len 3 3 3 3 3 Here, we mean with considering: computing the apparent
count 1 1 1 1 1 gain (frequency*length) of a symbol, using the observed fre-
gain 3 3 3 3 3
quency the symbol being chosen during actual compression.
In addition to pairs of symbols, we also (re-)consider all
Iteration 4 symbols that consist of a single byte, as well as consider ex-
tum cwi tum vld $ b len = 6 tending each existing symbol with the next occurring byte
– even if that single byte is not currently a symbol2 .
Symbol table symbol tum cwi vld b Figure 2 illustrates the algorithm by showing 4 iterations
len 3 3 3 1 on the example corpus “tumcwitumvldb”. To keep the ex-
count 2 1 1 1
gain 6 3 3 1 ample manageable, we limit the maximum symbol length
to 3 (rather than 8) and that the maximum symbol table
size to 5 (rather than 255). After each iteration, we show
Compressed the compressed string at the top, but instead of codes, for
tum cwi tum vld b len = 5 readability, we show the corresponding symbols. “$” stands
Figure 2: Four iterations of symbol table construc- for the escape byte. In the first iteration the length of the
tion algorithm on the corpus “tumcwitumvldb” with compressed string temporarily doubles because the symbol
a maximum symbol length of 3 and a maximum sym- table is initially empty and every symbol must be escaped.
bol table size of 5. “$” stands for the escape byte. At the bottom of the figure, we show the symbol table, i.e.,
the top-5 symbols based on static gain. After the iteration
expensive. The number of possible symbols is bounded by 1, the top-5 symbols by static gain are “um”, “tu”, “wi”, “cw”,
N ∗ 8 (i.e. a substring of length between 1 and 8, starting and “mc”. The former two of these top symbols (“um”, “tu”)
at any position) but
that gives a bound on the number of have a gain of 4 since they occur twice, while the latter three
8N
symbol tables of 255 . Being more practical, when creating symbols (“wi”, “cw”, and “mc”) occur just once and therefore
a symbol table from a sample of a few tens of KB real-world have a gain of 2. Note that the symbols “mv”, “vl”, “ld”, “db”,
text, one could narrow the problem down to choosing 255 “m”, “t”, “u” also have a gain of 2 and could have been picked
from, for example, the top-3000 symbols in terms of static as well. In other words, when picking the top symbols, the
gain. The search space algorithm resolved ties arbitrarily.

for symbol tables then still remains
an unreasonable 3000
255
, a number with 378 digits.
2
The reason to always consider single byte(-extension)s is
4.2 Algorithm Overview that it makes the algorithm more robust: creating a longer
symbol from two shorter ones may cause the shorter symbol
In the following, we present a bottom-up algorithm that to disappear because the longer takes away some of its gain
has linear time complexity and overcomes the dependency and thereby it may end up outside the top-255. In a next
issue using multiple iterations and on-the-fly compression. generation, this longer symbol may also lose the competition
The key idea behind our bottom-up algorithm is that the for survival; so that eventually a valuable symbol could dis-
true worth of a collection of symbols is only learned while appear due to greedy combining. In essence, without recon-
compressing the corpus with the symbols interacting. In sidering single byte(-extension)s, symbols would only grow
longer, and going back to shorter symbols if that is better
other words, by counting the actually occurring codes in the would never be possible. Continuously injecting single-byte
compressed representation, we sidestep the dependency is- symbol(-extension)s allows to “re-grow” valuable longer sym-
sue. Another building block is that, when evaluating a sym- bols that were lost due to such “too greedy” choices.

2653
 In iterations 2, 3, and 4, the quality of the symbol table Algorithm 3 Simplified Python-style pseudo code for
steadily increases. After iteration 4, the corpus, which ini- bottom-up symbol table construction.
tially had a length of 13, is compressed to length of 5. The class SymbolTable:
figure also shows that our algorithm makes mistakes, but def __init__(st): # constructor
that these are repaired in one of the next iterations. For [Link] = 0
example, in iteration 2, symbol “tu” looks quite attractive [Link][257] = [0]*256
[Link][512] = [’’]*512
with a static gain of 4, but because “tum” is also in the sym- # the first 256 symbols are escaped bytes
bol table, “tu” turns out to be worthless and is discarded in for code in range(0,255)
iteration 3. [Link][code] = chr(code)
4.3 Bottom-Up Symbol Table Construction def insert(st, s):
Algorithm 3 shows pseudo-code in Python style for the [Link][256+[Link]++] = s
bottom-up algorithm. The open-source C++ FSST im-
def findLongestSymbol(st, text):
plementation is of course much faster. Nevertheless, class, var letter = ord(text[0])
method, and variable names in this pseudo-code follow our # try all symbols that start with this letter
real implementation. The main methods are: for code in range([Link][letter],[Link][letter+1])
if ([Link]([Link][code]))
• buildSymbolTable(). This is the top-level entry point return code # symbol, code >= 256
of the algorithm. Given a text, it builds a symbol table return letter # non-symbol byte (will be escaped)
in 5 iterations; starting with an empty symbolTable().
In it, the [Link][] array always starts with 256 # compress the sample and count the frequencies
pseudo-symbols, representing single bytes. These are def compressCount(st, count1, count2, text):
used to represent and administer the frequency of var pos = 0
var prev, code = [Link](text[pos:])
escaped bytes (i.e., the situation where compression while ((pos += [Link][code].len()) < [Link]())
would use 2 bytes to represent a byte of text due to prev = code
an extra escape byte 255 getting generated). The next code = [Link](text[pos:])
[Link], up to 255, entries in the [Link][] ar- # count the frequencies
ray contain the real symbols (initially [Link]=0). count1[code]++ # count single symbol[code]
count2[prev][code]++ # count concat(prev,code)
• compressCount(). This method compresses a text us- # we also count frequencies for the next byte only
ing the current symbol table st. In the first itera- if (code >= 256)
tion with the empty symbol table, it will only use nextByte = ord(text[pos])
count1[nextByte]++
escaped bytes and the result will be twice the input count2[prev][nextByte]++
size. Rather than producing compressed output text,
this method just records the frequency of the codes or def makeTable(st, count1, count2): # pick top symbols
bytes it encounters; as well as the frequencies of the var res = SymbolTable()
subsequent codes or bytes, in two arrays (count1[] and var cands = []
count2[][], where the latter is 2-dimensional). for code1 in range(0,256+[Link])
# single symbols (+all bytes 0..255) are candidates
• makeTable(). Using the frequencies in count2[][] gain = [Link][code1].len() * count1[code1]
and count1[], it generates all possible candi- [Link](cands, (gain, [Link][code1]))
for code2 in range(0,256+[Link])
date symbols and calculates their gain. It # concatenated symbols are also candidates
considers all single-bytes as new symbols s = ([Link][code1]+ [Link][code2])[:8]
([Link][0..255]), all symbols of the previous gain = [Link]() * count2[code1][code2]
generation ([Link][256..256+[Link]]), but [Link](cands, (gain, s))
also all combinations of these (concatenations, up to # fill with the most worthwhile candidates
length 8). Using a priority queue, the 255 symbols while ([Link] < 255)
[Link]([Link](cands))
with highest apparent gain (which is length*count) return [Link]()
are inserted in the new symbol table.
• findLongestSymbol(). This method finds the longest def makeIndex(st): # make index for findLongestSymbol
# sort the real symbols and init the letter index
matching (pseudo-)symbol in a text. We store the var tmp = sort([Link][256,256+[Link]])
(real) symbols (those from code 256 on) in lexicograph- for i in range(0,[Link]).reverse()
ical order, but when one string prefixes the other, the var letter = ord(tmp[i][0])
longest is first. This means that when testing for prefix [Link][letter] = 256+i
match all real symbols from first to last, the first hit [Link][256+i] = tmp[i]
will be the longest. This method restricts the search [Link][256] = 256+[Link] # sentinel
return st
to the range of symbols that start with the first byte
text[0]. For this purpose, there is an [Link][byte] def buildSymbolTable(st, text): # top-level entry point
array that keeps the position of the first (real) symbol var res = SymbolTable()
that starts with a certain byte. for generation in [1,2,3,4,5]
var count1[512] = [0]*512
• makeIndex(). This helper method is called to final- var count2[512][512] = [count1]*512
ize a new symbol table. It sorts the symbols lex- [Link](res, count1, count2, text)
icographically as described above and initializes the res = [Link](res, count1, count2)
[Link][]. return res

2654
4.4 Number of Iterations and Sampling Algorithm 4 Lossy Perfect Hashing: no loops & branches
Our bottom-up approach means that we start with small struct Symbol {
union val { char buf[8]; uint64_t num}; // allows2compare str as int
symbols (size 1-2 after the first iteration), which grow over uint16_t code; // bits [0..8]=code [12..15]=len. Unused: code=511
time (size 2-4 after the second and up to size 8 after the third uint16_t ignoredBits; // unused bits in num, i.e. 64-len*8
iteration). Thus, at least three iterations are necessary to get }
to the maximum symbol length 8. Having larger symbols is struct SymbolTable {
of course crucial for good compression factors. We observed uint8_t nSymbols; // # of normal symbols (not counting escapes)
that 5 iterations are generally enough to converge to a good Symbol symbols[512]; // all symbols: 0-255 escapes, then n Symbols
compression factor. Besides the number of iterations, sym- // uint16_t stores code&length: resp. bits [0..8] and bits [12..15]
bol table construction speed obviously also depends on the uint16_t shortCodes[256][256];//codes (511=unused) of 1-2byte symbs
size of training corpus. Luckily, we can train our algorithm
Symbol hashTab[hashTabSize]; // keyed on the first three bytes
using a sample rather than using the full corpus: Intuitively, static uint64_t hashTabSize = 4096; // fits L1
using a sample works well because it is highly unlikely that uint64_t hash(uint64_t x) { return (x*2971215073)^(x>>15); }
symbols that occur frequently in the full corpus are uncom- }
mon in the sample. Experimentally, we indeed found that
void encodeScalar(uint8_t*& cur, uint8_t*& out, SymbolTable& st){
a fairly modest sample size results in compression factors uint64_t word = *(uint64_t*)cur;
close to those of using the full corpus. Therefore, the com-
pression utility we ship in our code uses a 16KB sample for // speculatively write 1st byte (required for escapes, else harmless)
out[1] = (uint8_t) word;
compressing each 4MB chunk of string data. To save time in
the first iterations, we further reduce the sample adaptively: // lookup in lossy perfect hash table
growing it from 6% to 100% of the full sample linearly over uint64_t idx = hash(word & 0xFFFFFF) & ([Link]-1);
Symbol s = [Link][idx]; // fetch symbol from hash table
the 5 iterations. Finally, to improve cache efficiency, we split uint64_t num = word & (0xFFFFFFFFFFFFFFFF >> [Link]);
the 256K count2[][] counters into 4 minor bits (frequently
accessed) and 12 (infrequently accessed) high bits. uint16_t code = ([Link]==num & [Link]!=511) ? // hastable hit?
[Link] : [Link][word&0xFFFF]; // conditional move
out[0] = (uint8_t) code; // write out code. Note: (uint8_t) 511=255
5. OPTIMIZING COMPRESSION SPEED
// advance the pointers with predication (i.e. without branches)
The performance-critical method for compression in Al- out += 2-((code>>8)&1); // increase with 1 or 2 (escape = 9th bit)
gorithm 3 is findLongestSymbol(). Our eventual goal is very cur += (code>>12); // symbol length is in bits [12..15] of code
high compression performance using SIMD. An important }
restriction in SIMD is that loops and branches are not sup-
ported. However, findLongestSymbol() loops over all symbols
that start with a particular byte, and compares the strings The additional shortCodes[A][B] array has 65536 entries (A
(startswith()) and branches away on the first hit. and B are bytes) used to check whether there is a 2-byte
We therefore eliminate the use of loops and branches from symbol AB that matches the next two bytes. If the array
the scalar code in Section 5.1 and describe its AVX512 ver- contains 511, its slot is free (escape); otherwise it contains
sion in Section 5.2. First, however, we describe the data the code of a normal symbol. After inserting the 2-byte
structures needed for this. codes in the array, we put in all free slots shortCodes[A][*]
the code of 1-byte symbols A. Thus, we can use the array to
Lossy Perfect Hashing. Rather than storing the sym- check whether either a 2- or 1-byte symbol matches.
bols in a sorted array (indexed by sIndex[]), we switched The optimized findLongestSymbol() first checks a string pre-
over to a perfect hash table hashTab[], plus a lookup array fix match with the symbol in the perfect hash table found by
shortCodes[][] (described later). using the next 3 bytes ABC as lookup key, and fetches code X
In a perfect hash table, there are no collisions and the of that symbol. If there is a hit, a symbol of length 3 or more
hash computation immediately points to a bucket where the matches the text. It also fetches Y = shortCodes[A][B] as the
key should be, if present. Perfect hash tables normally need potential next code, using short 1-2 byte symbols only. The
at least two hash functions and an additional offset array, choice between these two can be made using a conditional
which is used to eliminate hash collisions. To make encod- move (hit?X:Y), which is also supported in SIMD. This way,
ing fast, we do not have time for computing two hash func- no loop or branch is needed.
tions, and a memory access to an offset array; we just use
a single multiplicative hash on the [Link]. That is 5.1 Predicated Scalar Compression.
why we switch to a lossy approach: if two symbols are in In Algorithm 4 we show a scalar FSST-compression kernel
a hash-collision with each other, we only keep the symbol that advances one symbol in a text, and effectively inlines
with highest apparent gain. Rather than ending up with less findLongestSymbol(). The data layout is quite optimized:
than 255 symbols (due to throwing out collisions), we keep codes (0-511) are represented as 16-bit integers, but we also
inserting symbols into the symbol table until it reaches 255 store the length of the symbol in its 4 highest bits (bits
symbols. In other words, the penalty of throwing colliding 12-15). We leverage the fact that FSST symbols fit into a
symbols out, is alleviated by the bottom-up symbol gen- 8-byte word to avoid string comparisons. This can be seen
eration mechanism that will find alternative, non-colliding in the union C++ definition of Symbol in the first lines of Al-
symbols to fill the table. gorithm 4. We even pre-materialize the amount of unused
The hash key are the first three bytes of a symbol. Sym- bits in symbols shorter than 8 (i.e., 64-8*len) as ignoredBits
bols with the same 3-byte prefix are therefore always colli- to speed up the hash lookup by two fewer operations.
sions, in addition to hash collisions when two different 3-byte The current position in the text is cur, and the compressed
keys hash onto the same bucket. string is appended at out; both these in-out parameters are

2655
 is invoked. Each segment is an encoding job. The while-
(1) memcpy, split in 511B segments (2) sort long-to-short into job queue loop in Algorithm 5 encloses the AVX512 encoding kernel:
& put terminator job queue (max 512 entries) each iteration it finds in each of the strings (=lanes) the
0 src end dst
strings to compress:
0 next symbol, advancing 1-8 bytes in the input, and 1 byte
finished 1 src end dst
1
jobs in the output (or 2, in case of an escape). This loop finishes
2 src end dst
2
5 src end dst
when there are no longer enough active jobs to fill the lanes
3
active
4 src end dst (here:8, times 3 due to unrolling). We call this a “meat-
4 jobs
5
7 grinder”, as we push data through a compression cylinder
hash (AVX512 kernel) with 24 strings in parallel.
3 src end dst
6 table
7
6 src end dst A job-description is a 64-bits integer consisting of two
todo
9 src end dst shortCodes input string offsets (cur and end). Their widths are 18 bits,
8 jobs
8 src end dst array
9 so their maximum value is 256K, which is the size of the
uncompressed string (3) expand_load gather in
segment buffer:256KB input active jobs hash table,
segment buffer (512x512). The output offset out is 19-bits,
compressed string compress_store shortCodes since in worst case FSST produces output that is twice the
segment buffer: 512KB output finished jobs input. Because some jobs will stay longer in the processing
compressed 0
strings:
kernel than others, they will not finish in the input order and
(5) 1
(4) scatter it is necessary to track the job number nr: a 9-bit number
memcpy 2 the found
& 3 codes;
(we have max. 512 jobs). Note that 18+18+19+9=64.
concat 4 appending The reason to squeeze all this control information into a
segments them to the single lane is AVX512 register pressure. By carefully us-
5
6 compressed ing as few registers as possible, it is possible to unroll this
(when all segments
jobs have 7 AVX512 fsst string ¨meatgrinder¨ kernel 3× without suffering performance degradation due to
finished) 8 - 200cpu cycles per AVX512 sequence register spilling. Unrolling AVX512 gather and scatter in-
9 - 8lanes*3xunroll=24strings in parallel structions is necessary, because they have a very long latency
- sequence finds 1 code in each string
(upwards of 25 cycles) yet multiple executions can be over-
Figure 3: AVX-512 FSST compression: a "meat- lapped (three). Note that even used in overlapped AVX512
grinder" that encodes 24 strings in parallel mode, gather instructions just load (from the CPU cache)
around 1 word per cycle amortized; whereas modern Intel
moved forward. While we eventually write one byte to out[0] processors can load two words per cycle with scalar loads.
(which due to the cast-to-byte will be the escape symbol 255 The strength of AVX512 is not memory access, but parallel
if the code=511, i.e. no symbol found), earlier we speculatively computation, which we leverage in this compression kernel.
wrote the current byte to out[1]. This speculative write We do not just fire off the SIMD kernel once to process 8
handles the case that FSST needs to escape a byte, but is strings in its 8 lanes (or 24 strings in 24 lanes, 3× unrolled),
harmless in case a real code is found. because some strings will be much shorter than others and
All in all, Algorithm 4 demonstrates a FSST compres- some will compress much more than others. This would
sion kernel without loop or branch. It can compress strings mean that many lanes would be empty towards the end of
at 10cycles per byte, which is 400MB/s on our platform, encoding work. Therefore we buffer 512 jobs and refill the
putting it among the fastest string compressors already. lanes in each iteration, when needed. Retiring jobs (lanes
An issue that we glossed over so far is dealing with end-of- in the job control register) uses the compress_store instruc-
string correctly. This kernel can jump over end-of-string, as tion, and refilling the expand_load instruction, as depicted
it blindly loads the next 8 input bytes into word. Scalar code in step (3) of Figure 3. In step (2) of Figure 3 we first
could deal with this by testing whether cur<end-7, and use radix-sorted the job queue array on reverse string length –
a slower variant to encode the last 1-7 bytes. However, in quickly, in a single pass – so the longest strings start being
SIMD we must avoid all branches. FSST deals with this by processed first, helping load balancing. Jobs may finish in a
introducing a terminator byte. This is a byte that cannot non-sequential ordering anyway, so starting encoding work
be part of a symbol longer than 1. Thus, if a terminator in non-sequential job order due to sorting does not compli-
byte is put at the end of the to-be-encoded string, match- cate the algorithm (any further).
ing cannot jump over it. We use the byte with the lowest The AVX512 encoding kernel on our benchmark runs each
frequency in the input corpus as terminator – except when iteration in about 200 cycles, and given that 24 strings are
in 0-terminated mode, because then byte 0 is the termina- processed in parallel, and each step we advance roughly 2
tor. The terminator character is appended to each 511-byte bytes in each, this translates to about 4.1 cycles per byte,
segment in the enclosing scalar code that calls the AVX512 which on our i9-7900X equates 920MB/s. As such, FSST
kernel (step 1 in Figure 3). is the fastest known string compressor available.
This AVX512 encoding kernel led to slight adaptations of
5.2 Compression in AVX512 the FSST format. Not only the SIMD, but also the scalar
code uses the 511 byte input segmenting. We use the scalar
The FSST API compresses a batch of strings, preferably
variant on architectures that do not support AVX512, but
100 or more. It is also efficient with fewer strings, even just
also to encode short strings (shorter than 10 bytes). Us-
one, if the total string volume is significant – a few tens of
ing input string segmenting in scalar code is necessary to
KB or more. The strings are copied into a temporary buffer
preserve the property that two strings encoded with the
of 512 segments, chopping up long strings if needed, and
same symbol table are binary identical. Further, the scalar
appending the terminator. This is shown in step (1) of Fig-
method also uses the terminator byte as a fast way to avoid
ure 3. When 512 segments have been gathered or there is
going over end-of-string. The terminator byte is meta-data
no more data, the AVX512 encoding kernel in Algorithm 5

2656
Algorithm 5 AVX512 FSST-encoding kernel (not unrolled) that is added to the symbol table, such that when we serial-
int encodeAVX512( ize and deserialize a symbol table (for persistent storage or
SymbolTable &st, int njobs, distributed processing), this information is preserved.
uint64* injobs, *outjobs, // arrays with max 512 jobs
char *input, *output) // tempstring buffers (resp 256KB,512KB)
A final question could be whether SIMD could also be use-
{ ful for decompression. We think it is not, given the already
char *hashTab=(char*)[Link], *shortCodes=(char*)[Link]; very high decompression speed of decode() and its character-
uint64* lastjob = injobs+njobs; // points to end of injobs
__mm512_i write, job;//job bit-format: [out:19][nr:9][end:18][cur:18]
istics of having very little computational effort and consist-
__mm512_i cur, end, len, word, code, esc, idx, hash, mask, num; ing only of memory instructions (see Algorithm 1).
__mmask8 hit, loadmask=255;
int done=0, delta=8;
6. EVALUATION
while(injobs+delta < lastjob) { // while all lanes busy FSST has been designed for compressing textual string
// fetch 8 jobs. in this kernel we will find 1 code for each
job = _mm512_mask_expandloadu_epi64(job, loadmask, injobs); columns. To evaluate it, we curated a text corpus (dubbed
injobs += delta; “dbtext”) consisting of 23 string columns covering a wide
variety of real-world string data. The columns, which we
// current position in each string
cur = __mm512_srli_epi64(job, 19+9+18); // cur field at bit 46
believe to be typical for database text attributes, are shown
in Table 1 and can be categorized to into
// get 8 bytes from the input strings
word = _mm512_i64gather_epi64(cur,input,1); • machine-readable identifiers (hex, yago, email, wiki,
uuid, urls2, urls),
// code = shortCodes[X][Y]
// constants x8_YY: hexidecimal value YY in all 8 (64-bits) lanes • human-readable names (firstname, lastname, city, cre-
idx = _mm512_and_epi64(word, x8_FFFF);
code = _mm512_i64gather_epi64(idx, shortCodes, 2);
dentials, street, movies),

// speculatively put first byte into second position of write reg

• text (faust, hamlet, chinese, japanese, wikipedia),
write = _mm512_slli_epi64(_mm512_and_epi64(word,x8_FF),8);
• domain-specific codes (genome, location), and
// idx = first three bytes of string, hash fetch into icl
idx = _mm512_and_epi64(word, x8_FFFFFF); • TPC-H data (c_name, l_comment, ps_comment).
hash = _mm512_mullo_epi64(idx,x8_PRIME);//YY=2971215073
idx = _mm512_xor_epi64(hash, mm512_srli_epi64(idx, 15)); The average string length per column ranges from 7 (first-
idx = _mm512_and_epi64(idx, x8_MASK); // MASK=4095 name) to 130 (wikipedia). Most of the data comes from
idx = _mm512_slli_epi64(idx,4); // multiply idx*16 (bucket width) real-world sources such as Wikipedia, Tableau Public [10],
icl = _mm512_i64gather_epi32(idx,hashTab,1);//probe hash table
// icl (i,c,l) = uint32 ignoredBits:16,code:12,len:4 or IMDb [16]. For reproducibility, the data sets have been
published together with the MIT-licensed C++ source code.
// fetch the symbol (text) part of the hash table record and compare Note that some of these columns (e.g., hex, uuid, genome,
num = _mm512_i64gather_epi64(idx,hashTab+8,1);//next 8bytes
hit = _mm512_cmplt_epi64_mask(icl, x8_FF0000); // used?
location) would be better represented using specialized data
mask = _mm512_and_epi64(icl,x8_FF); // get ignoredBits types. However, industrial experience taught us that users
mask = _mm512_srlv_epi64(x8_FFFFFFFFFFFFFFFF, mask); virtually always use the string data type in these cases [21].
word = _mm512_and_epi64(word,mask); //clean word with mask
hit &= _mm512_cmpeq_epi64_mask(num, word); // hit?
All experiments were performed on a workstation with
icl = _mm512_srli_epi64(icl, 16); // extract code+len from icl 32GB RAM and a single 10-core (20-hyperthread) 3.3GHz
i9-7900X CPU, which has two AVX512 execution units per
// conditional move: select between shortCodes and hashTab (hit) core. This server is running Linux (Fedora Core) 4.18.16.
code = _mm512_mask_mov_epi64(code, hit, icl);
We used LZ4 version 1.8.1, and compiled all code with g++
// put code byte into write register, and scatter write to output (8.3.1) and flags -O3 -march=native. We use single-threaded
write=_mm512_or_epi64(write,_mm512_and_epi64(code,x8_FF)); execution, but note that both compression and decompres-
idx=_mm512_and_epi64(job,x8_7FFFF);//get 19-bit output offset
_mm512_i64scatter_epi64(output, idx, write, 1); sion can trivially be parallelized by splitting the data into
independent blocks (row-groups).
// job bookkeeping: advance cur and out
code = _mm512_and_epi64(code, x8_FFFF); 6.1 File Mode
len = _mm512_srli_epi64(code,12);//get symbol length from code
job = _mm512_add_epi64(job, _mm512_slli_epi64(len, 46)); Let us first compare FSST with LZ4, which is currently
esc = _mm512_srli_epi64(code, 8); // shift away 8 bits the best general-purpose lightweight compression implemen-
esc = _mm512_and_epi64(esc, x8_1)); // keep only 9th bit tation. In this experiment we treat each string column as a
job = _mm512_add_epi64(job, _mm512_sub_epi64(x8_2, esc));
cur = _mm512_srli_epi64(job, 19+9+8); // cur field at bit 46 file, concatenating all strings until each file has 8MB of data.
end = _mm512_srli_epi64(job, 19+9); // end field at bit 28 Note that this file-based mode is the best case for LZ4, since
end = _mm512_and_epi64(end, x8_3FFFF); // keep 18 bits it has large blocks to compress and we not exploit FSST’s
// write out ready jobs random access capability. We measure the compression fac-
loadmask = _mm512_cmpeq_epi64_mask(cur, end); tor, bulk compression speed, and bulk decompression speed.
_mm512_mask_compressstoreu_epi64(outjobs+done,loadmask,job); As Table 1 shows, the compression factors for FSST range
done += (delta = _mm_popcnt_u32((int) loadmask));
} from 1.63× (wiki) to 3.84× (c_name), with an average of
// flush active and unprocessed jobs 2.28×.3 In any case, as a rule of thumb, FSST halves the size
__mmask8 activemask = 255 & ~loadmask; of database text; whereas LZ4 achieves a 1.70× compression.
_mm512_mask_compressstoreu_epi64(outjobs, activemask, job);
3
int i=done+8-delta; In file mode the corpus is slightly different (each file is a
while (injobs < lastjob) outjobs[i++] = *injobs++; single string with newlines) than when each line of the file
return done; // outjobs[done..njobs-1]: 2b finished with scalar encoding is compressed as a separate string (shorter strings, no new-
}
lines). FSST compression gets a bit reduced, from 2.28× to
2.19× then. Line mode is used in the rest of the evaluation.

2657
Table 1: Evaluation data sets (“dbtext” corpus) and performance of FSST versus LZ4 in terms of compression
factor, compression speed, and decompression speed. Each data set is treated as a 8MB file.
avg compr. factor compr. [MB/s] decompr. [MB/s]
name len example string LZ4 FSST LZ4 FSST LZ4 FSST
hex 8 DD5AF484 1.14 2.11 1,097 944 1,891 1,546
yago 19 Ralph_A._Brown 1.25 1.63 572 768 1,394 1,078
email 22 xnj_14@[Link] 1.55 2.12 627 944 2,388 1,547
wiki 23 Benzil 1.31 1.65 556 763 1,493 1,196
uuid 37 84e22ac0-2da5-11e8-9d15- . . . 1.55 2.44 632 1,113 2,782 2,654
urls2 55 [Link] . . . 1.75 2.05 602 932 2,170 2,135
urls 63 [Link] . . . 2.77 2.16 711 986 2,264 2,296
firstname 7 RUSSEL 1.25 2.04 637 878 895 865
lastname 10 BALONIER 1.28 1.97 616 874 1,007 1,022
city 10 ROELAND PARK 1.37 2.14 540 879 1,098 1,120
credentials 11 PHD, HSPP 1.48 2.33 439 984 1,055 1,159
street 13 PURITAN AVENUE 1.60 2.38 501 1,001 1,275 1,287
movies 21 Return to ’Giant’ 1.23 1.66 541 787 1,443 1,143
faust 24 Erleuchte mein bedürftig Herz. 1.48 1.86 422 818 1,380 1,524
hamlet 30 <LINE>That to Laertes . . . 2.13 2.42 515 1,058 1,772 2,168
chinese 87 道⼈决心消除⾁会 . . . 1.40 1.70 540 591 2,503 2,163
japanese 90 せん。しかし、. . . 1.84 1.99 461 899 2,540 2,577
wikipedia 130 Weniger häufig fressen sie . . . 1.45 1.82 517 852 2,628 2,366
genome 10 atagtgaag 1.59 3.32 566 1,307 1,126 2,838
location 40 (40.84242764486843, -73 . . . 1.58 2.52 433 1,141 2,271 2,647
c_name 19 Customer#000010485 3.08 3.84 1,131 1,421 2,960 3,519
l_comment 27 nal braids nag carefully expres 2.22 3.01 605 1,164 1,664 1,893
ps_comment 124 c foxes. fluffily ironic . . . 2.79 3.38 741 1,359 2,715 3,920
average 1.70 2.28 608 977 1,857 1,942

8e+07
compr. factor compr. speed [GB/s] decomp. speed [GB/s]
result tuples / s

2.0 6e+07 FSST

1.5 4e+07
1.0
2e+07 LZ4
0.5
0.0 0e+00
1% 3% 10% 30% 100%
ST

ST

ST
k

k
ct

ct

ct
e

e
oc

oc

oc
lin

lin

lin
di

di

di

selectivity
FS

FS

FS
bl

bl

bl
4

4
LZ

LZ

LZ

LZ

LZ

LZ
4

4
LZ

LZ

LZ

Figure 4: With LZ4 short strings do not compress Figure 5: Selective queries are fast in FSST due to
well, even with a pre-generated dictionary. random access to individual values.

Table 1 shows the relative performance of LZ4 and FSST LZ4 compression suffers from blocks <27KB, and that at
on the three metrics for each data set individually and on least a few kilobytes are needed to achieve reasonable com-
average. For almost all data sets, FSST outperforms LZ4 in pression. String sizes of <100 bytes, common in databases,
terms of the compression factor and compression speed. On result in larger data sizes.
average, besides resulting in a 34% better compression fac-
tor4 , FSST also achieves 60% higher compression speed. For 6.2 Random Access
decompression speed, FSST is faster on some data sets and
In database scenarios we typically do not store large files
LZ4 is on others – with the average being almost identical.
but instead we have string attributes or dictionaries with a
So far, we treated each data set as one 8MB file, which
large number of relatively short strings. Compressing these
works well with block-based approaches like LZ4. To under-
strings individually with LZ4 gives a very poor compres-
stand whether LZ4 would also work on smaller block sizes,
sion factor, as shown in Figure 4. Plain LZ4 (LZ4 line)
we split the urls data set into blocks of different sizes and
cannot handle the short strings reasonably – the compres-
compressed each one individually:
sion factor is below 1, meaning that the data size actually
blocksize (bytes) 64K 16K 4K 1K 256 64 16 slightly increases. LZ4 also optionally supports using an
compr. factor 2.73 2.45 2.03 1.59 1.14 0.78 0.46 additional dictionary, which needs to shipped with the com-
4
If one fully sorts the lines in the files of the dbtext corpus pressed data. Using zstd to pre-generate a suitable dictio-
lexicographically, LZ4 compression improves to 2.07×; still nary for the corpus (LZ4 dict) improves the compression
not catching FSST, which is mostly indifferent to the very factor a bit, but hurts the compression speed very severely.
localized text similarities such sorting creates. The only meaningful way to use LZ4 for string attributes is

2658
Table 2: Detailed FSST encoding performance as Table 3: Evolution of FSST compression techniques
cycles-per-input-byte for various encoding kernels. – top to bottom. Properties in terms of compression
“simd3 ” is fastest, i.e., AVX512 using 3-way enrolling factor (CF), symbol table construction (SC) cost in
of the kernel in Algorithm 4. It is 2.5x faster than cycles-per-byte, when constructing a new symbol ta-
scalar encoding. ble for each 8MB of text, and string encoding (SE)
cost cycles-per-byte.
simd1 simd2 simd3 simd4 scalar
variant 1: suffix-array based construction (slowest)
7.82 5.22 4.57 4.76 4.65 hex
symbol table org: sorted CF: 1.97
9.49 6.20 4.83 5.36 11.78 yago
string encoding: dynamic programming SC: 74.8cyc/b
7.29 4.55 3.88 4.25 11.48 email
symbol matching: strncmp SE: 160.0cyc/b
9.39 5.95 4.96 5.37 12.06 wiki
6.44 4.10 3.47 3.60 8.64 uuid variant 2: suffix-array based construction (slow)
7.71 4.83 4.17 4.35 10.29 urls2 symbol table org: sorted CF: 1.97
6.42 4.14 3.53 3.87 8.51 urls string encoding: dynamic programming SC: 73.8cyc/b
8.13 5.18 4.41 4.67 11.07 firstname symbol matching: str-as-long SE: 81.7cyc/b
8.18 5.14 4.45 4.67 10.52 lastname variant 3: suffix-array based construction (less slow)
8.31 5.31 4.88 4.71 10.64 city symbol table org: sorted CF: 1.95
7.72 5.00 4.63 4.79 13.22 credentials string encoding: greedy SC: 74.0cyc/b
7.44 5.03 4.47 4.59 11.45 street symbol matching: str-as-long SE: 37.4cyc/b
9.23 5.93 4.87 5.14 11.48 movies variant 4: FSST - initial idea
8.60 5.54 4.86 5.19 12.67 faust symbol table org: sorted CF: 2.33
7.09 4.52 4.09 4.12 11.08 hamlet string encoding: greedy SC: 2.1cyc/b
9.03 5.78 4.80 5.17 13.79 chinese symbol matching: str-as-long SE: 20.0cyc/b
9.10 5.13 4.67 4.89 14.30 japanese
variant 5: FSST - lossy-perfect-hash
8.19 5.27 4.33 4.72 12.43 wikipedia
symbol table org: lossy perfect hash CF: 2.28
5.16 3.54 2.87 3.02 8.84 genome
string encoding: greedy (predicated) SC: 1.73cyc/b
5.56 3.64 3.05 3.26 5.78 location
symbol matching: str-as-long SE: 10.3cyc/b
3.93 2.61 2.21 2.47 5.41 c_name
5.64 3.76 3.16 3.34 9.78 l_comment variant 6: FSST - optimized construction
4.72 3.09 2.58 2.85 8.89 ps_comment symbol table org: lossy perfect hash CF: 2.19
7.42 4.76 4.08 4.31 10.38 average string encoding: greedy (predicated) SC: 0.83cyc/b
symbol matching: str-as-long SE: 10.3cyc/b
variant 7: FSST - AVX512 kernel 3-way unrolled (simd3 )
to compress blocks of 1,000 values together (LZ block), which symbol table org: lossy perfect hash CF: 2.19
helps compression but prevents random access. FSST of- string encoding: greedy (predicated) SC: 0.83cyc/b
fers much better compression factors and compression speed symbol matching: AVX512 SE: 4.1cyc/b
than all LZ4 variants, and decompresses just as fast as the
fastest LZ4 variant. Note that the block mode of LZ4 is
not ideal for database applications. When selecting only a This means that attribute names are not repetitively stored,
subset of the values, one still has to decompress the whole saving space, and only their values are stored in an appropri-
block for LZ4, while FSST offers random access. The effect ately typed internal column. In case of strings, such internal
of this is shown in Figure 5. When retrieving a subset of columns could then be compressed with FSST.
values from a compressed relation, the output rate of FSST
is unaffected by the selectivity, while LZ4 block has to de- 6.4 Encoding Kernels
compress all values, including values that are not needed Comparing variant 6 and 7 in Table 3, we see that AVX512
for the result. This makes FSST much more attractive for improves encoding performance by 2.5×. Table 2 investi-
database use cases. gates the performance of different encoding kernel imple-
mentations. The simd columns show the encoding per-
6.3 Non-textual data formance of the SIMD kernel with different loop unrolling
Outside our database context, the compression commu- counts. Best performance is achieved with 3-way unrolling
nity often evaluates compression methods on the Silesia cor- (i.e., “simd3 ”), beating scalar encoding by a factor 2.5.
pus, which consists of 11 files, of which 4 are textual (dick-
ens, reymont, mr, webster), one is XML and 6 are binary. 6.5 Evolution of FSST
FSST achieves 10% better compression sizes on the text files, The FSST compression algorithm went through several
but is 25% worse on the binaries, on average. iterations before arriving at the current design. This evo-
While we think binary files are not relevant for FSST, lution is retraced in Table 3, which shows the compression
its compression ratio on large XML and JSON files, which factor (CF), symbol table construction cost (CS), and string
are relevant, is 2-2.5x worse than LZ4. However, we think encoding speed (SE) for 7 variants. As mentioned earlier,
database systems should store these composite values not as our first design was based on a suffix array and achieved a re-
simple strings, but in a specialized type that allows query spectable compression factor of 1.97×, but required 74.3 cy-
processing. For instance, Snowflake recognizes the struc- cles/byte for symbol table construction and 160 cycles/byte
ture in JSON columns, and internally stores each often- for encoding. Our current AVX512 version (variant 7 in the
occurring JSON attribute in a separate internal column [7]. figure) is 90× faster for table construction and 40× faster

2659
Table 4: Query execution times in ms for TPC-H SF10 with compressed string columns, using 20 threads.
Q1 Q2 Q3 Q4 Q5 Q6 Q7 Q8 Q9 Q10 Q11 Q12 Q13 Q14 Q15 Q16 Q17 Q18 Q19 Q20 Q21 Q22 geo. mean
uncompressed 118 14 71 44 54 25 93 40 186 75 15 54 228 33 27 65 26 165 99 38 120 49 57
LZ4 131 23 72 48 53 25 80 42 190 105 15 55 250 34 27 64 26 166 91 40 118 50 59
FSST 104 15 69 42 53 25 85 39 186 71 15 52 235 29 27 52 25 162 69 39 115 28 53

for encoding than the first version – while providing a higher as text would result in short strings only, which would effec-
compression factor. The final variant is also much faster tively disable compression. To replicate the spirit of their ex-
than the initial FSST version (variant 4), thanks to lossy periment, we prepended the string ”keyvalue-padded” before
perfect hashing and AVX512 – though we had to sacrifice every key value, which makes the key columns sufficiently
about 6% of the space gains relative to variant 4. Table 3 large to see compression effects.
also shows that symbol table construction is only a fraction When running the query SELECT COUNT(*) FROM orders,
of encoding time, despite requiring multiple iterations. Op- lineitem WHERE o_orderkey = l_orderkey
timizing contruction entailed reducing iterations from 10 to we now get query execution times of 484ms uncompressed,
5, building on a sample (that grows every iteration), and 560ms when using LZ4, and 554ms when using FSST. The
shrinking the memory footprint of the counters. overhead is not caused by the decompression (which is nec-
essary because the two join predicate columns use different
dictionaries) but by the effects on the rest of the system: in
6.6 System Integration and Query Processing the uncompressed case, the strings are known to be stable,
To measure some end-to-end effects of FSST on query and the system just stores them as they are. When build-
processing, we did a prototype integration in our Umbra ing a hash table for decompressed strings, the system has
system [19]. There are different ways how one could inte- to make a copy, as the decompressed value will go away. A
grate FSST into a database system. Our implementation profiler run shows that the overhead is largely caused by
compresses each string individually, and then decompresses memcpy into the hash table, whereas the FSST decompres-
it as late as possible. Equality predicates against a constant sion itself takes just 9% of the time.
can be evaluated directly upon the compressed form and To summarize, the overhead of adding FSST compres-
decompression is needed just for non-equality comparisons, sion on TPC-H is small. Even in the worst-case experiment
sorting, and result printing. We also created an LZ4 inte- with padded strings as key columns the overhead is 14%.
gration in Umbra, where we organize tuples in blocks of size For more realistic scenarios, where just string columns are
216 and then compress all string values of a given column compressed the overhead is at most 3%, and queries like
in that block. There, random access is no longer possible, Q19 in fact become faster by 30% by adding compression.
and strings have to be decompressed on block before ac- TPC-H has few selective predicates, thus FSST cannot show
cess. Block decompression is triggered only when needed, off its random access capabilities here, but even in this bulk-
i.e., only if there are qualifying tuples after checking the processing scenario it outperforms LZ4.
non-string predicates.
Table 4 shows TPC-H results on SF10, using 20 threads. 7. SUMMARY AND FUTURE WORK
As expected, compression had little effect, as TPC-H is usu- Fast Static Symbol Table (FSST) is a lightweight, ran-
ally dominated by joins on integer columns. There are some dom access compression scheme for strings that exploits
notable exceptions though. Q13 is dominated by a like frequently-occurring substrings in a column. We presented
predicate on o_comment, and thus directly shows the over- fast algorithms for decompression and compression. For tex-
head of decompression. Both FSST and LZ4 are very fast tual data, FSST on average achieves compression factors of
here, with a slow-down of only 3% resp. 9%. Q19 makes over 2×, compresses at 4 cycles per byte with AVX512, and
heavy use of well-compressible string columns, and perfor- decompresses at 2 cycles per byte (resp. 1 GB/s and 2 GB/s
mance in fact improves. That is especially true for FSST, as on our platform). FSST thereby outperforms even the heav-
it not only saves scan memory bandwidth, but also allows ily optimized LZ4 compression library on these three met-
to push down string filter predicates. rics. However, in contrast to LZ4, FSST also supports effi-
In terms of space, the size of the string pool is 4.1GB un- cient random access to individual strings, without having to
compressed, 1.5GB with LZ4, and only 0.69GB with FSST. decompress a block of data. This makes FSST particularly
The compression factor of FSST is inflated by the fact that useful for database systems, which can exploit random ac-
Umbra inlines short strings of 12 bytes or less, and thereby cess, for example, during index lookups. Beyond database
often avoids allocation in the string pool. Many TPC-H systems, we also envision applications in information re-
strings happen to fall below that threshold after compres- trieval, network/cloud storage, text analysis and more.
sion. Space consumption differences are likely less strong In the future, we will investigate which operations besides
under other circumstances. equality can be performed directly on compressed strings
In a different TPC-H experiment, Müller et al. [18] re- without having to decompress them first. For example,
placed all TPC-H (integer) key columns by strings. Repli- we believe it is possible to develop a Knuth–Morris–Pratt-
cating this artificial experiment would not have the desired like substring search algorithm directly operating on FSST-
effect in Umbra. To allow for random access, our string val- compressed strings. It would further be interesting to ex-
ues are split into a fixed-size header and a variable part that plore a hardware implementation of FSST decompression.
is referenced by the header. For short strings our system The small size of symbol table, the fact that it is static, and
directly inlines the string into the header, and only stores finally the simplicity of the decompression algorithm, make
a pointer value for longer strings. Storing the integer keys such an undertaking highly feasible.

2660
8. REFERENCES [18] I. Müller, C. Ratsch, and F. Färber. Adaptive string
dictionary compression in in-memory column-store
[1] [Link] (shortened URI). Full URI: database systems. In EDBT, pages 283–294, 2014.
[Link] [19] T. Neumann and M. J. Freitag. Umbra: A disk-based
//[Link]/blog/2016/04/13/ system with in-memory performance. In CIDR, 2020.
evaluating-database-compression-methods-update/. [20] V. Raman, G. K. Attaluri, R. Barber, N. Chainani,
[2] [Link] (shortened URI). Full URI: D. Kalmuk, V. KulandaiSamy, J. Leenstra,
[Link] S. Lightstone, S. Liu, G. M. Lohman, T. Malkemus,
/[Link]/inikep/lzbench. R. Müller, I. Pandis, B. Schiefer, D. Sharpe, R. Sidle,
[3] [Link] (shortened URI). Full URI: A. J. Storm, and L. Zhang. DB2 with BLU
[Link] acceleration: So much more than just a column store.
//[Link]/docs/11/[Link]. PVLDB, 6(11):1080–1091, 2013.
[4] J. Arz and J. Fischer. Lempel-Ziv-78 compressed [21] A. Vogelsgesang, M. Haubenschild, J. Finis,
string dictionaries. Algorithmica, 80(7):2012–2047, A. Kemper, V. Leis, T. Muehlbauer, T. Neumann,
2018. and M. Then. Get real: How benchmarks fail to
[5] C. Binnig, S. Hildenbrand, and F. Färber. represent the real world. In DBTEST, 2018.
Dictionary-based order-preserving string compression [22] T. Westmann, D. Kossmann, S. Helmer, and
for main memory column stores. In SIGMOD, pages G. Moerkotte. The implementation and performance
283–296, 2009. of compressed databases. SIGMOD Record,
[6] Z. Chen, J. Gehrke, and F. Korn. Query optimization 29(3):55–67, 2000.
in compressed database systems. In SIGMOD, pages [23] I. H. Witten, A. Moffat, and T. C. Bell. Managing
271–282, 2001. Gigabytes (2nd Ed.): Compressing and Indexing
[7] B. Dageville, T. Cruanes, M. Zukowski, V. Antonov, Documents and Images. Morgan Kaufmann Publishers
A. Avanes, J. Bock, J. Claybaugh, D. Engovatov, Inc., San Francisco, CA, USA, 1999.
M. Hentschel, J. Huang, A. W. Lee, A. Motivala, [24] J. Ziv and A. Lempel. Compression of individual
A. Q. Munir, S. Pelley, P. Povinec, G. Rahn, sequences via variable-rate coding. IEEE Trans.
S. Triantafyllis, and P. Unterbrunner. The snowflake Information Theory, 24(5):530–536, 1978.
elastic data warehouse. In SIGMOD, 2016. [25] M. Zukowski, S. Héman, N. Nes, and P. A. Boncz.
[8] P. Damme, D. Habich, J. Hildebrandt, and Super-scalar RAM-CPU cache compression. In ICDE,
W. Lehner. Lightweight data compression algorithms: 2006.
An experimental survey. In EDBT, pages 72–83, 2017.
[9] P. Gage. A new algorithm for data compression. C
Users J., 12(2):23–38, Feb. 1994.
[10] B. Ghita, D. G. Tomé, and P. A. Boncz. White-box
compression: Learning and exploiting compact table
representations. In CIDR, 2020.
[11] A. L. Holloway, V. Raman, G. Swart, and D. J.
DeWitt. How to barter bits for chronons: compression
and bandwidth trade offs for database scans. In
SIGMOD, pages 389–400, 2007.
[12] S. Jain, D. Moritz, D. Halperin, B. Howe, and
E. Lazowska. SQLShare: Results from a multi-year
SQL-as-a-service experiment. In SIGMOD, pages
281–293, 2016.
[13] H. Lang, T. Mühlbauer, F. Funke, P. A. Boncz,
T. Neumann, and A. Kemper. Data Blocks: Hybrid
OLTP and OLAP on compressed storage using both
vectorization and compilation. In SIGMOD, pages
311–326, 2016.
[14] N. J. Larsson and A. Moffat. Offline dictionary-based
compression. In Data Compression Conference, pages
296–305, 1999.
[15] R. Lasch, I. Oukid, R. Dementiev, N. May,
S. Demirsoy, and K.-U. Sattler. Fast & strong: The
case of compressed string dictionaries on modern
CPUs. In Damon, 2019.
[16] V. Leis, A. Gubichev, A. Mirchev, P. A. Boncz,
A. Kemper, and T. Neumann. How good are query
optimizers, really? PVLDB, 9(3):204–215, 2015.
[17] D. Lemire and L. Boytsov. Decoding billions of
integers per second through vectorization. Softw.,
Pract. Exper., 45(1):1–29, 2015.

2661