Order-Preserving Key Compression for
In-Memory Search Trees

As shown in Figure 1, a string axis lays out all possible source strings on a single axis in lexicographical order. We can represent a dictionary encoding scheme using this model and highlight three important properties: (1) completeness, (2) unique decodability, and (3) order-preserving.

Let $\Sigma$ denote the source string alphabet. $\Sigma^{*}$ is the set of all possible finite-length strings over $\Sigma$. Similarly, let $X$ denote the code alphabet and $X^{*}$ be the code space. Typically, $\Sigma$ is the set of all characters, and $X=\{0,1\}$. A dictionary $D:S\rightarrow C,S\in\Sigma^{*},C\in X^{*}$ maps a subset of the source strings $S$ to the set of codes $C$.

On the string axis, a dictionary entry $s_{i}\rightarrow c_{i}$ is mapped to an interval $I_{i}$, where $s_{i}$ is a prefix of all strings within $I_{i}$. The choice of $I_{i}$ is not unique. For example, as shown in Figure 2, both $\left[\mbox{{abcd}},\mbox{{abcf}}\right)$ and $\left[\mbox{{abcgh}},\mbox{{abcpq}}\right)$ are valid mappings for dictionary entry abc$\rightarrow$0110. In fact, any sub-interval of $\left[\mbox{{abc}},\mbox{{abd}}\right)$ is a valid mapping in this example. If a source string $src$ falls into the interval $I_{i}$, then a dictionary lookup on $src$ returns the corresponding entry $s_{i}\rightarrow c_{i}$.

We can model the dictionary encoding method as a recursive process. Given a source string $src$, one can lookup $src$ in the dictionary and obtain an entry $(s\rightarrow c)\in D,s\in S,c\in C$, such that $s$ is a prefix of $src$, i.e., $src=s\boldsymbol{\cdot}src_{suffix}$, where “$\boldsymbol{\cdot}$” is the concatenation operation. We then replace $s$ with $c$ in $src$ and repeat the process²²2One can use a different dictionary at every step. For performance reasons, we consider a single dictionary throughout the process in this paper. using $src_{suffix}$.

To guarantee that encoding always makes progress, we must ensure that every dictionary lookup is successful. This means that for any $src$, there must exist a dictionary entry $s\rightarrow c$ such that $len(s)\!>\!0$ and $s$ is a prefix of $src$. In other words, we must consume some prefix from the source string at every lookup. We call this property dictionary completeness. Existing dictionary compression schemes for DBMSs are usually not complete because they only assign codes to the string values already seen by the DBMS. These schemes cannot encode arbitrary strings unless they grow the dictionary, but growing to accommodate new entries may require the DBMS to re-encode the entire corpus (Binnig et al., 2009). In the string axis model, a dictionary is complete if and only if the union of all the intervals (i.e., $\bigcup I_{i}$) covers the entire string axis.

A dictionary encoding $Enc:\Sigma^{*}\rightarrow X^{*}$ is uniquely decodable if $Enc$ is an injection (i.e., there is a one-to-one mapping from every element of $\Sigma^{*}$ to an element in $X^{*}$). To guarantee unique decodability, we must ensure that (1) there is only one way to encode a source string and (2) every encoded result is unique. Under our string axis model, these requirements are equivalent to (1) all intervals $I_{i}$’s are disjoint and (2) the set of codes $C$ used in the dictionary are uniquely decodable (we only consider prefix codes in this paper).

With these requirements, we can use the string axis model to construct a dictionary that is both complete and uniquely decodable. As shown in Figure 1, for a given dictionary size of $n$ entries, we first divide the string axis into $n$ consecutive intervals $I_{0},I_{1},\dots,I_{n-1}$, where the max-length common prefix $s_{i}$ of all strings in $I_{i}$ is not empty (i.e., $len(s_{i})\!>\!0$) for each interval. We use $b_{0},b_{1},\dots,b_{n-1},b_{n}$ to denote interval boundaries. That is, $I_{i}=[b_{i},b_{i+1})$ for $i=0,1,\dots,n-1$. We then assign a set of uniquely decodable codes $c_{0},c_{1},\dots,c_{n-1}$ to the intervals. Our dictionary is thus $s_{i}\rightarrow c_{i},i=0,1,\dots,n\!-\!1$. A dictionary lookup maps the source string to a single interval $I_{i}$, where $b_{i}<src<b_{i+1}$.

We can achieve the order-preserving property on top of unique decodability by assigning monotonically increasing codes $c_{0}\!<\!c_{1}\!<\!\dots\!<\!c_{n-1}$ to the intervals. This is easy to prove. Suppose there are two source strings ($src_{1}$, $src_{2}$), where $src_{1}\!<\!src_{2}$. If $src_{1}$ and $src_{2}$ belong to the same interval $I_{i}$ in the dictionary, they must share common prefix $s_{i}$. Replacing $s_{i}$ with $c_{i}$ in each string does not affect their relative ordering. If $src_{1}$ and $src_{2}$ map to different intervals $I_{i}$ and $I_{j}$, then $Enc(src_{1})\!=\!c_{i}\boldsymbol{\cdot}Enc(src_{1_{suffix}})$, $Enc(src_{2})\!=\!c_{j}\boldsymbol{\cdot}Enc(src_{2_{suffix}})$. Since $src_{1}\!<\!src_{2}$, $I_{i}$ must preceed $I_{j}$ on the string axis. That means $c_{i}\!<\!c_{j}$. Because $c_{i}$’s are prefix codes, $c_{i}\boldsymbol{\cdot}Enc(src_{1_{suffix}})<c_{j}\boldsymbol{\cdot}Enc(src_{2_{suffix}})$.

For encoding search tree keys, we prefer schemes that are complete and order-preserving; unique decodability is implied by the latter property. Completeness allows the scheme to encode arbitrary keys, while order-preserving guarantees that the search tree supports meaningful range queries on the encoded keys.

For a dictionary encoding scheme to reduce the size of the corpus, its emitted codes must be shorter than the source strings. Given a complete, order-preserving dictionary $D:s_{i}\rightarrow c_{i},i=0,1,\dots,n\!-\!1$, let $p_{i}$ denote the probability that a dictionary entry is accessed at each step during the encoding of an arbitrary source string. Because the dictionary is complete and uniquely decodable (implied by order-preserving), $\sum_{i=0}^{n-1}p_{i}=1$. The encoding scheme achieves the best compression when the compression rate $CPR={\sum_{i=0}^{n-1}len(s_{i})p_{i}}\big{/}{\sum_{i=0}^{n-1}len(c_{i})p_{i}}$ is maximized.

According to the string axis model, we can characterize a dictionary encoding scheme in two aspects: (1) how to divide intervals and (2) what code to assign to each interval. Interval division determines the symbol lengths ($len(s_{i})$) and the access probability distribution ($p_{i}$) in a dictionary. Code assignment exploits the entropy in $p_{i}$’s by using shorter codes ($c_{i}$) for more frequently-accessed intervals.

We consider two interval-division strategies: fixed-length intervals and variable-length intervals. For code assignment, we consider two types of prefix codes: fixed-length codes and optimal variable-length codes. We, therefore, divide all complete and order-preserving dictionary encoding schemes into four categories, as shown in Figure 3.

Although VIVC schemes can have higher compression rates than the other schemes, both fixed-length intervals and fixed-length codes have performance advantages over their variable-length counterparts. Fixed-length intervals create smaller and faster dictionary structures, while fixed-length codes are more efficient to decode. Our objective is to find the best trade-off between compression rate and encoding performance for in-memory search tree keys.

Based on the above dictionary encoding models, we next introduce six compression schemes implemented in HOPE, as shown in Figure 4, We select these schemes from the three viable categories (FIVC, VIFC, and VIVC). Each scheme makes different trade-offs between compression rate and encoding performance. We first describe them at a high level and then provide their implementation details in Section 4.

ALM uses monotonically increasing fixed-length codes. Figure 4c shows an example dictionary segment. The dictionary size for ALM depends on the threshold $W$. One must binary search on $W$’s to obtain a desired dictionary size.

As shown in Figure 5, HOPE executes in two phases (i.e., Build, Encode) and has four modules: Symbol Selector, Code Assigner, Dictionary, and Encoder. A DBMS provides HOPE with a list of sample keys from the search tree. HOPE then produces a Dictionary and an Encoder as its output. We note that the size and representativeness of the sampled key list only affect the compression rate. The correctness of HOPE’s compression algorithm is guaranteed by the dictionary completeness and order-preserving properties discussed in Section 3.1. In other words, any HOPE dictionary can both encode arbitrary input keys and preserve the original key ordering.

In the first step of the build phase, the Symbol Selector counts the frequencies of the specified string patterns in the sampled key list and then divides the string axis into intervals based on the heuristics given by the target compression scheme. The Symbol Selector generates three outputs for each interval: (1) dictionary symbol (i.e., the common prefix of the interval), (2) interval boundaries, and (3) probability that a source string falls within that interval.

The framework then gives the symbols and interval boundaries to the Dictionary module. Meanwhile, it sends the probabilities to the Code Assigner to generate codes for the dictionary symbols. If the scheme uses fixed-length codes, the Code Assigner only considers the dictionary size. If the scheme uses variable-length codes, the Code Assigner examines the probability distribution to generate optimal order-preserving prefix codes (i.e., Hu-Tucker codes).

When the Dictionary module receives the symbols, the interval boundaries, and the codes, it selects an appropriate and fast dictionary data structure to store the mappings. The string lengths of the interval boundaries inform the decision; available data structures range from fixed-length arrays to general-purpose tries. The dictionary size is a tunable parameter for VIFC and VIVC schemes. Using a larger dictionary trades performance for a better compression rate.

The encode phase uses only the Dictionary and Encoder modules. On receiving an uncompressed key, the Encoder performs multiple lookups in the dictionary. Each lookup translates a part of the original key to some code as described in Section 3.1. The Encoder then concatenates the codes in order and outputs the result. This encoding process is sequential for variable-length interval schemes (i.e., VIFC and VIVC) because the remaining source string to be encoded depends on the results of earlier dictionary lookups.

We next describe the implementation details for each module. Building a decoder is optional because our target workload for search trees does not require reconstructing the original keys.

HOPE users can create new compression schemes by combining different module implementations. HOPE currently supports the six compression schemes described in Section 3.3. For Symbol Selector and Code Assigner, the goal is to generate a dictionary that leads to the maximum compression rate. We no longer need these two modules after the build phase. We spend extra effort optimizing the Dictionary and Encoder modules because they are on the critical path of every search tree query.

The ALM and ALM-Improved Symbol Selectors require an extra blending step before their interval-division algorithms. This is because the selected variable-length substrings may not satisfy the prefix property (i.e., a substring can be a prefix of another substring). For example, “sig” and “sigmod” may both appear in the frequency list, but the interval-division algorithm cannot select both of them because the two intervals on the string axis are not disjoint: “sigmod” is a sub-interval of “sig”. A blending algorithm redistributes the occurrence count of a prefix symbol to its longest extension in the frequency list (Antoshenkov, 1997). We implement this blending algorithm in HOPE using a trie data structure.

After the Symbol Selector decides the intervals, it performs a test encoding of the sample keys using the intervals as if the code for each interval has been assigned. The purpose of this step is to obtain the probability that a source string (or its remaining suffix) falls into each interval so that the Code Assigner can generate codes based on those probabilities to maximize compression. For variable-length-interval schemes, the probabilities are weighted by the symbol lengths of the intervals.

The Hu-Tucker algorithm works in four steps (www, 2005). First, it creates a leaf node for each probability and then lists the leaf nodes in interval order. Second, it recursively merges the two least-frequent nodes where there are no leaf nodes between them (unlike Huffman). This is where the algorithm guarantees order. After constructing this probability tree, it next computes the depth of each leaf node to derive the lengths of the codes. Finally, the algorithm constructs a tree by adding these leaf nodes level-by-level starting from the deepest and then connecting adjacent nodes at the same level in pairs. HOPE uses this Huffman-tree-like structure to extract the final codes. Our Hu-Tucker implementation in the Code Assigner uses an improved algorithm (Yohe, 1972) that runs in $\mathcal{O}(N^{2})$ time instead of $\mathcal{O}(N^{3})$ as in the original paper (Hu and Tucker, 1971).

We implemented three dictionary data structures in HOPE. The first is an array for the Single-Char and Double-Char schemes. Each dictionary entry includes an 8-bit integer to record the code length and a 32-bit integer to store the code. The dictionary symbols and the interval left boundaries are implied by the array offsets. For example, the $97^{\mbox{\scriptsize th}}$ entry in Single-Char has the symbol a, while the $24770^{\mbox{\scriptsize th}}$ entry in Double-Char corresponds to the symbol aa⁴⁴4 $24770=96\times(256+1)+97+1$. The $+1$’s are for the terminators $\varnothing$ . A lookup in an array-based dictionary is fast because it requires only a single memory access and the array fits in CPU cache.

The second dictionary data structure in HOPE is a bitmap-trie used by the 3-Grams and 4-Grams schemes. Figure 6 depicts the structure of a three-level bitmap-trie for 3-Grams. The nodes are stored in an array in breadth-first order. Each node consists of a 32-bit integer and a 256-bit bitmap. The bitmap records all the branches of the node. For example, if the node has a branch labeled a, the $97^{\mbox{\scriptsize th}}$ bit in the bitmap is set. The integer at the front stores the total number of set bits in the bitmaps of all the preceding nodes. Since the stored interval boundaries can be shorter than three characters, the data structure borrows the most significant bit from the 32-bit integer to denote the termination character $\varnothing$.

Given a node ($n$, $bitmap$) where $n$ is the count of the preceding set bits, its child node pointed by label $l$ at position $n+\textit{popcount}(\textit{bitmap},l)$⁵⁵5The POPCOUNT CPU instruction counts the set bits in a bit-vector. The function $\textit{popcount}(\textit{bitmap},l)$ counts the set bits up to position $l$ in bitmap. in the node array. Our evaluation shows that looking up a bitmap-trie is 2.3$\times$ faster than binary-searching the dictionary entries because it requires fewer memory probes and has better cache performance.

Finally, we use an ART-based dictionary to serve the ALM and ALM-Improved schemes. ART is a radix tree that supports variable-length keys (Leis et al., 2013). We modified three aspects of ART to make it more suitable as a dictionary. First, we added support for prefix keys in ART. This is necessary because both abc and abcd, for example, can be valid interval boundaries stored in a dictionary. We also disabled ART’s optimistic common prefix skipping that compresses paths on single-branch nodes by storing only the first few bytes. If a corresponding segment of a query key matches the stored bytes during a lookup, ART assumes that the key segment also matches the rest of the common prefix (a final key verification happens against the full tuple). HOPE’s ART-based dictionary, however, stores the full common prefix for each node since it cannot assume that there is a tuple with the original key. Lastly, we modified the ART’s leaf nodes to store the dictionary entries instead of tuple pointers.

To make the non-byte-aligned code concatenation fast, HOPE stores codes in 64-bit integer buffers. It adds a new code to the result buffer in three steps: (1) left-shift the result buffer to make room for the new code; (2) write the new code to the buffer using a bit-wise OR instruction; (3) split the new code if it spans two 64-bit integers. This procedure costs only a few CPU cycles per code concatenation.

When encoding a batch of sorted keys, the Encoder optimizes the algorithm by first dividing the batch into blocks, where each block contains a fixed number of keys. The Encoder then encodes the common prefix of the keys within a block only once, avoiding redundant work. When the batch size is two, we call this pair-encoding. Compared to encoding keys individually, pair-encoding reduces key compression overhead for the closed-range queries in a search tree. We evaluate batch encoding in Appendix B.

We first evaluate the runtime performance and compression efficacy of HOPE’s six built-in schemes listed in Table 1. HOPE compresses the keys one-at-a-time with a single thread. We vary the number of dictionary entries in each trial and measure three facets per scheme: (1) the compression rate, (2) the average encoding latency per character, and (3) the size of the dictionary. We compute the compression rate as the uncompressed dataset size divided by the compressed dataset size. We obtain the average encoding latency per character by dividing the execution time by the total number of bytes in the uncompressed dataset.

Figure 8 shows the experimental results. We vary the number of dictionary entries on the x-axis (log scaled). The Single-Char and Double-Char schemes have fixed dictionary sizes of $2^{8}$ and $2^{16}$, respectively. The 3-Grams dictionary cannot grow to $2^{18}$ because there are not enough unique three-character patterns in the sampled keys.

The figures also show that latency is stable (and even decrease slightly) in all workloads for 3-Grams and 4-Grams as their dictionary sizes increase. This is interesting because the cost of performing a lookup in the dictionary increases as the dictionary grows in size. The larger dictionaries, however, achieve higher compression rates such that it reduces lookups: larger dictionaries have shorter intervals on the string axis, and shorter intervals usually have longer common prefixes (i.e., dictionary symbols). Thus, HOPE consumes more bytes from the source string at each lookup with larger dictionaries, counteracting the higher per-lookup cost.

We next measure how long HOPE takes to construct the dictionary using each of the six compression schemes. We record the time HOPE spends in the modules from Section 4.2 when building a dictionary: (1) Symbol Selector, (2) Code Assigner, and (3) Dictionary. The last step is the time required to populate the dictionary from the key samples. We present only the Email dataset for this experiment; the results for the other datasets produce similar results and thus we omit them. For the variable-length-interval schemes, we perform the experiments using two dictionary sizes ($2^{12}$, $2^{16}$).

Figure 9 shows the time breakdown of building the dictionary in each scheme. First, the Symbol Selector dominants the cost for ALM and ALM-Improved because these schemes collect statistics for substrings of all lengths, which has a super-linear cost relative to the number of keys. For the other schemes, the Symbol Selector’s time grows linearly with the number of keys. Second, the time used by the Code Assigner rises dramatically as the dictionary size increases because the Hu-Tucker algorithm has quadratic time complexity. Finally, the Dictionary build time is negligible compared to the Symbol Selector and Code Assigner modules.

We use the YCSB-based (Cooper et al., 2010) index-benchmark framework proposed in the Hybrid Index (Zhang et al., 2016) and later used by, for example, HOT (Binna et al., 2018) and SuRF (Zhang et al., 2018). We use the YCSB workloads C and E with a Zipf distribution to generate point and range queries. Point queries are the same for all trees. Each range query for ART, HOT, B+tree, and Prefix B+tree is a start key followed by a scan length. Because SuRF is a filter, its range query is a start key and end key pair, where the end key is a copy of the start key with the last character increased by one (e.g., [“com.gmail@foo”, “com.gmail@fop”]). We replace the original YCSB keys with the keys in our email, wiki and URL datasets. We create one-to-one mappings between the YCSB keys and our keys during the replacement to preserve the Zipf distribution.⁶⁶6We omit the results for other query distributions (e.g., uniform) because they demonstrate similar performance gains/losses as in the Zipf case.

We start each experiment with the building phase using the first $1\%$ of the dataset’s keys. Next, in the loading phase, we insert the keys one-by-one into the tree (except for SuRF because it only supports batch loading). Finally, we execute 10M queries on the compressed keys with a single thread using a combination of point and range queries according to the workload. We obtain the point, range, and insert query latencies by dividing the corresponding execution time by the number of queries. We measure memory consumption (HOPE size included) after the loading phase.

Figures 10, 11 and 12 show the benchmark results. Range query and insert results for ART, HOT, B+tree, and Prefix B+tree are included in Appendix D because the performance results are similar to the corresponding point query cases for similar reasons. We first summarize the high-level observations and then discuss the results in more detail for each tree.

HOPE reduces SuRF’s query latencies by up to 41% in all workloads with non-ALM encoders. This is because compressed keys generate shorter tries, as shown in the third row of Figure 10. According to our analysis in Section 5, the performance gained by fewer levels in the trie outweighs the key encoding overhead. Although SuRF with ALM-Improved (64K) has the lowest trie height, it suffers high query latency because encoding is slow for ALM-Improved schemes.

Although the six HOPE schemes under test achieve compression rates of 1.5–2.5$\times$ in the microbenchmarks, they only provide $\sim$30% memory savings to SuRF. The reason is that compressing keys only reduces the number of internal nodes in a trie (i.e., shorter paths to the leaf nodes). The number of leaf nodes, which is often the majority of the storage cost, stays the same. SuRF with ALM-Improved (64K) consumes more memory than others because of its larger dictionary.

Section 6.1 showed that ALM-Improved (4K) achieves a better compression rate than Double-Char for email keys with a similar-sized dictionary. When we apply this scheme to SuRF, however, the memory saving is smaller than Double-Char even though it produces a shorter trie. This is because ALM-Improved favors long symbols in the dictionary. Encoding long symbols one-at-a-time can prevent prefix sharing. As an example, ALM-Improved may treat the keys “com.gmail@c” and “com.gmail@s” as two separate symbols and thus have completely different codes.

All schemes, except for Single-Char, add computational overhead in building SuRF. The dictionary build time grows quadratically with the number of entries because of the Hu-Tucker algorithm. One can reduce this overhead by shrinking the dictionary size, but this diminishes performance and memory-efficiency gains.

Finally, the HOPE-optimized SuRF achieves lower false positive rate under the same suffix-bit configurations, as shown in Figure 11. This is because each bit in the compressed keys carries more information and is, thus, more distinguishable than a bit in the uncompressed keys.

Compared to plain B+trees, we observe smaller memory saving percentages when using HOPE on Prefix B+trees. This is because prefix compression reduces the storage size for the keys, and thus making the structural components of the B+tree (e.g., pointers) relatively larger. Although HOPE provides similar compression rates when applied to a Prefix B+tree and a plain B+tree, the percentages of space reduction brought by HOPE-compressed keys in a Prefix B+tree is smaller with respect to the entire data structure size.

As a final remark, HOPE still improves the performance and memory for highly-compressed trees such as SuRF. It shows that HOPE is orthogonal to many other compression techniques and can benefit a wide range of data structures.