Compressed Key Sort and Fast Index Reconstruction

In this paper we propose an index key compression scheme based on the notion of distinction bits by proving that the distinction bits of index keys are sufficient information to determine the sorted order of the index keys correctly. While the actual compression ratio may vary depending on the characteristics of datasets (an average of 2.76 to one compression ratio was observed in our experiments), the index key compression scheme leads to significant performance improvements during the reconstruction of large-scale indexes. Our index key compression can be effectively used in database replication and index recovery of modern main-memory database systems.


Introduction
Main-memory database systems have been widely used for many applications such as OLTP and OLAP, which are required to keep the latency low and the transaction throughput high. In such a main-memory database system, indexes are often deployed without on-disk representations [1,2,3,4]. By letting the indexes reside solely in memory, it can sustain the best attainable performance of the indexes, which are already critical to query and data processing performance, even in the presence of many updates. Insertions, deletions and updates made to a database table will be reflected to all the indexes associated with the table as well as the table itself. However, none of those update operations will incur any disk accesses for keeping the indexes up to date, because all the corresponding changes will only be applied to the table and the associated indexes residing in the main memory. The changes applied to the indexes will not even be written to the log or checkpointed to disk, as the most recent copy of each index can always be restored from its base table [5].
Since none of the index updates are propagated to disk, however, all the indexes have to be reconstructed from scratch when the database system restarts from a failure, an anti-cached table is loaded back from disk to memory, or an entire database is replicated from the master node to a slave node. For a table that has many indexes associated with it, the cost of loading the table may be significantly increased due to the additional cost of constructing the indexes from the rows of the table. Therefore, it is practically an important challenge to limit the cost of index reconstruction so that the database loading time and the restart time can be kept to its minimum. Table 1 shows the times taken to build a B-tree index for each of the six memory-resident tables. The times are broken down to two separate stages, namely, sort and build. Both the sort and build phases of index construction were performed by a single-core implementation. Just for the sake of comparison, the second column of the table shows the times taken to load the indexed columns from disk to memory. In all the six cases reported in Table 1, the cost of internal sort was approximately 90 percent of the total cost. Evidently, the internal sort was the dominant factor load index construction time of the B-tree index construction, and hence fast construction of memory resident B-tree indexes cannot be achieved without reducing the cost of internal sort drastically.
In this paper, we propose a new sort approach relying on the distinction bits among the keys. We call this method a compressed key sort, as utilizing only the distinction bits of the keys can be considered a kind of compressing the keys. The experimental evaluation demonstrates that the overall cost of B-tree construction can be reduced by 21-54 percent for real-world datasets. Our experiments also show that the compressed key sort is readily parallelizable for multi-core processors, yields near-linear speedup, and can actually build a B-tree index faster than loading its image from disk or even enterprise-class SSD.
The key question we pose in this paper is "What is the minimum amount of information required (in terms of the number of bits in the index keys) to determine the sorted order among the index keys correctly?" Whoever can determine it will extract the minimum number of bits from index keys and sort them still correctly but more efficiently. Once the keys are sorted, the B-tree index will be built by following the standard bulk-load procedure. This process is illustrated in Figure 1, where the top flow shows the conventional steps for index construction while the bottom one shows the proposed compressed key sort applied to index construction.
We now formally define the distinction bits of two index keys to be the most significant bits that are different between the keys. We will prove that the distinction bits of index keys are sufficient information to determine the sorted order of the index keys correctly. Consequently, we can extract only the distinction bits of index keys into compressed form and sort the compressed keys in order to construct a B-tree index quickly.
Index keys for database tables can be as short as a 4-byte word but they can also be longer than a few dozen bytes in business applications. Hence index trees and all related algorithms (sorting index keys, building the index, searching with a query key, etc.) should be able to handle long keys as well as short keys. Our compressed key sort approach assumes this wide range of index key sizes. To speed up the index construction process further, we exploit parallelism in building an index tree. This paper is organized as follows. In Section 2 we discuss related work. In Section 3 we introduce our compressed key sort. In Section 4 we describe the index key formats we use for various data types and present the metadata information to keep for efficient index rebuilding. In Section 5 we explain the procedure of rebuilding the index. Section 6 shows the results of our experiments, and we conclude in Section 7.

Related Work
There has been extensive research on efficient index structures for database tables, where efficiency measures are index size, search time, concurrency control, etc. Especially the following work focused on reducing index sizes and/or search time: Bayer [22]. See Graefe and Larson [23] and Graefe [24] for surveys.
Our work reduces the sizes of sort keys by compressing them, from which the speedups in sorting and index rebuilding are obtained. Hence our work is orthogonal to the previous work on efficient index structures, and it can be applied to many index structures. Compressing keys by distinction bits can also be applied to big data file formats. Popular self-described file formats such as ORC [25] and Parquet [26] adopt columnar storage structures to cope with read-heavy analytic workloads against large-scale distributed datasets. Compression by distinction bits can accelerate such common analytic tasks as sorting data and generating unique keys.
Kim et al.'s FAST [17] proposed a key compression technique which extracts bits of index keys in the bit positions where the index keys are not the same (which are called variant bits). We go one step further and use distinction bits to determine the sorted order of index keys correctly.
There has been research on order-preserving compression [27,28,29,30,31] which maps index keys into encoded values such that the order of index keys is the same as the order of encoded values. In order-preserving compression, index keys are replaced by encoded values. In our compression scheme, however, there is no encoding. We simply extract part of index keys (i.e., distinction bits) to speed up sorting and index building. The index tree built by our compression scheme will be a conventional B-tree index without any encoding of index keys.
For sorting in multi-core CPUs, there have recently been many results exploiting SIMD parallelism [32,33,34]. In our target applications which require a wide range of index key sizes, however, the size of index keys is too big to exploit SIMD parallelism. Thus we implemented our own parallel sorting algorithm called the row-column sort, which relies only on the operation of comparing two elements during sorting. The comparison operator is called a comparator. Therefore, the row-column sort works with any key sizes. (In contrast, sorting on SIMD needs quite different algorithmic techniques such as merging networks [32,33,34].) In our experiments we compared the row-column sort with GCC STL parallel sort [35], which is an available parallel sort code on multi-core CPUs in which a custom comparator can be used. Experiments show that the row-column sort shows a better speedup than GCC STL sort, and it is 31.4% faster than GCC STL sort when the number of cores is 16.

Compressed Key Sort
In this section we first prove that the distinction bits of index keys are sufficient information to determine the sorted order of the index keys correctly, and then present our compressed key sort based on distinction bits, which is the central idea in rebuilding main-memory indexes efficiently.

Definitions
We first introduce some terms to describe the compressed key sort. We consider key values as binary strings throughout this paper. Note that bit positions start with 0, and the bit of a key in bit position i will be called the (i + 1)-st bit of the key (i.e., the bit in bit position 0 is the first bit, the bit in bit position 1 is the second bit, etc.). The first bit (i.e., in bit position 0) is the most significant bit in the keys.
The distinction bit position of two keys is defined as the most significant bit position where the two keys differ (the bits themselves are called distinction bits). The name distinction bit 1 is from [8], but the main focus of this paper is sorting based on distinction bits 2 . Suppose that there are n+1 keys key 0 , key 1 , . . . , key n and they are in lexicographic order (sorted order), i.e., key 0 < key 1 < · · · < key n . The distinction bit position of two keys key i and key j is denoted by D-bit(key i , key j ). Let D i = D-bit(key i−1 , key i ) for 1 ≤ i ≤ n, i.e., the distinction bit position of two adjacent keys in sorted order. We prove that the set of distinction bit positions of all possible key pairs is the same as the set {D 1 , D 2 , . . . , D n }. First, we need a lemma.
Proof. We prove by induction on d = j − i. When d = 1, the lemma holds trivially. For induction hypothesis, assume that the lemma holds for d ≥ 1.
We now prove the lemma for d + 1. Let D = D-bit(key i , key j−1 ). Because (j − 1) − i = d, D = min i<k≤j−1 D k by induction hypothesis, which means that the first D bits of key i , key i+1 , . . . , key j−1 are the same. Consider D and D j (= D-bit(key j−1 , key j )).
• If D < D j , then D is D-bit(key i , key j ) because the (D + 1)-st bit of key j is the same as that of key j−1 which is different from that of key i , while the first D bits of key i , key i+1 , . . . , key j are the same. Since D = min i<k≤j−1 D k and D < D j , D = min i<k≤j D k .
• If D j < D, then D j is D-bit(key i , key j ) because the (D j + 1)-st bit of key j is different from that of key j−1 which is the same as that of key i , while the first D j bits of key i , key i+1 , . . . , key j are the same. Since D = min i<k≤j−1 D k and D j < D, D j = min i<k≤j D k .
For example, D-bit(key 1 , key 3 ) = 1 because D 2 = 1 < D 3 = 7, and D-bit(key 0 , key 2 ) = 1 because D 1 = 5 > D 2 = 1 in Figure 2 (a). Note that D cannot be equal to D j because we have only two possibilities, 0 and 1, in a bit position. Proof. Since adjacent key pairs are part of all key pairs, we have D adj ⊆ D all .
To prove D all ⊆ D adj , we show that the distinction bit position of any pair (say, key i and key j ) belongs to D adj . Without loss of generality, assume that i < j. By Lemma 1, D-bit(key i , key j ) = min i<k≤j D k . Since D k is in D adj , so is D-bit(key i , key j ). By Theorem 1, all possible distinction bit positions for n + 1 keys are D 1 , . . . , D n (i.e., there are at most n distinction bit positions), which is a crucial fact in our compressed key sort. Since some of D i values may be the same (e.g., D 1 = D 4 = 5 in Figure 2), the number of distinction bit positions can be much less than n. In Figure 2

Key Compression
Extended distinction bit positions mean all distinction bit positions plus some other (zero or more) bit positions. Let Compress(key i ) be the concatenation of the bits of key i in extended distinction bit positions. The distinction bit slice (or D-bit slice) is defined as the set {Compress(key 0 ), . . . , Compress(key n )}. See Figure 2 (b). The distinction bit slice is simply a set of Compress(key i )'s, not necessarily sorted by Compress(key i ).
Theorem 2. The distinction bit slice is sufficient information to determine the sorted order of the keys.
Proof. We first prove the theorem for the distinction bit positions. We prove that the following relation holds: for all i and j. Let D = D-bit(key i , key j ). Since the first D bits of key i and key j are the same, the order of key i and key j is determined by the bits in bit position D. By Lemma 1, bits in bit position D are in Compress (and thus in the distinction bit slice). Hence, the order between key i and key j is determined by the order between Compress(key i ) and Compress(key j ). Due to the relation above, we can correctly determine the sorted order of the keys by the distinction bit slice. Similarly, we can prove the theorem for extended distinction bit positions.
When we maintain an index for a database table, index keys may be inserted, deleted, or updated by database operations. Then distinction bit positions may be changed at runtime. For example, if key 3 is deleted in Figure 2, position 7 is no longer a distinction bit position (but it is still a variant bit position). If key 0 is also deleted, distinction bit positions don't change, but position 7 becomes an invariant bit position. If an index key is inserted, a new distinction bit position may be added. It is quite expensive to maintain the distinction bit positions accurately when delete operations are allowed. Theorem 2 allows us to lazily update distinction bit positions without affecting the correctness of sorting by letting some invalidated bit positions stay.
The scheme of extracting distinction bits of key i into Compress(key i ) for all i and sorting Compress(key i )'s rather than sorting full key values is called compressed key sort. In order to extract compressed keys from index keys, we need to keep only (extended) distinction bit positions as a bitmap. Compressed key sort is the main reason for the speedup of index reconstruction.

Remark 1.
To build an index, the sorting of index keys is necessary, which requires O(n log n) time. To compute distinction bit positions additionally, our compressed key sort needs O(n) time to compare adjacent keys in sorted order. However, our key compression is not optimal in terms of the number of bit positions if an unlimited time is allowed. For the given keys in Figure 3, our key compression selects bit positions 0, 1, and 3 as distinction bit positions, but the bit slice in bit positions 2 and 3 can correctly determine the sorted order of the keys, and this is the

Index Key Format
The B+ tree and its variants are widely used as indexes in modern DBMSs to enable fast access to data with a search key. If an index is defined on columns A 1 , . . . , A k of a table, its key can be represented as a tuple of column values, of the form (a 1 , . . . , a k ) [37]. The ordering of the tuples is the lexicographic ordering. When k = 2, for example, the order of two tuples (a 1 , a 2 ) and (b 1 , b 2 ) is determined as follows: In this section we describe how to make actual index keys from the tuples of column values so as to keep the lexicographic ordering of the tuples. We first explain how to make index keys from different data types and then explain how to make an index key from multiple columns.
For each data type (int, float, decimal, string, etc.), its index key format can be defined so that a lexicographic binary comparison in the index key format is equivalent to a comparison of original data values. For the mappings of data types int and float to index key formats, we refer readers to [20]. Here we describe the mappings of decimal and string to index key formats.
A. decimal: A decimal number x is represented by a 1-byte header and a decimal part. The last bit of the header is the sign of the decimal number (1 for negative), and the second-to-last bit indicates whether the entry is null or not (0 for null). The decimal part contains a binary number corresponding to x in log 2 (x + 1)/8 bytes. The location of the decimal point is stored in the metadata of the column. For mapping, if the sign bit is 1 (i.e., x is negative), toggle the sign bit and all bits of the decimal part; otherwise, toggle the sign bit only. Then the order of the mapped values corresponds to that of the decimal numbers. See Figure 4, where decimal(m, n) means m total digits, of which n digits are to the right of the decimal point. B. fixed-size string: We use a fixed-size string as it is. C. variable-size string with maximum length: A variable-size string with maximum length n is denoted by varchar(n). We assume that the null character (denoted by ∅) is not allowed in the variable-size string. (In the case that null characters are allowed, we need to use some (15)  encoding of characters so that the encoded string doesn't have null characters.) We attach one null character at the end of the variable-size string to make the index key value. Then the lexicographic order of index key values corresponds to that of variable-size strings as follows.
If two index keys have the same lengths, the order between them is trivially the order of the strings. If two index keys have different lengths (let k be the length of the shorter key) and their first k − 1 bytes have different values, their order is determined by the first k − 1 bytes. If two keys have different lengths and their first k − 1 bytes have the same values, the shorter one is smaller in lexicographic order because it has a null character in the k-th byte and the longer one has a non-null character in the k-th byte. For instance, if two keys are AB∅ and ABA∅, then AB∅ is smaller than ABA∅ due to the 3rd bytes and this is the lexicographic order between two strings AB and ABA. Furthermore, the distinction bit position takes place in the null character of the shorter key.
In each data type, the order between two index keys can be determined by a lexicographic binary comparison of them. We now explain how to make an index key from multiple columns. An index key on multiple columns is defined as the concatenations of index keys from the multiple columns. Suppose that an index key is defined on the following five columns: PART (int), NAME (varchar(30)), XXX (int), YYY (int), and ZZZ (varchar (15)). Example column values in some rows are shown in Figure 5 (a), and the index keys of the three rows are in Figure 5 The distinction bit positions in Section 3.1 are defined on these full index keys. If the data types of index columns have fixed lengths (as in int, float, decimal, and fixed-size string), the column values are aligned in the index keys, and the order between index keys are determined by the lexicographic order of the column values.
If the data types of index columns have variable lengths (as in variable-size string), however, the column values may not be aligned in the index keys, as shown in Figure 5 (b). Still we define distinction bit positions on these full index keys. If two rows have variable-size strings of different lengths in a column (e.g., column NAME in Figure 5), the distinction bit position takes place in that column as described above if previous columns have the same values as in Figure 5, and the order between the two index keys are determined by the lexicographic order of the variable-size strings in that column.
To compare two index keys, we make a binary comparison (by word sizes) of the two keys. If

Index Tree and DS-metadata
Although our compressed key sort can work with any variant of the B+ tree index structure, available codes for indexes have a small and fixed length for index keys (4 bytes for FAST [38] and CSB+ tree [39], and 4 or 8 bytes for k-ary search tree [14]) or some restrictions in building indexes (e.g., no parallel index building for ART [20]). Therefore, we use a full-fledged index tree which is being used in SAP HANA database system, and apply our compressed key sort to it. Figure 6 shows the structure of the index tree, which is a variant of the partial-key B+ tree [9]. To define partial keys on key values key 0 , key 1 , . . . , key n in sorted order, a parameter pk is introduced. The partial key of key i is the pk bits following the distinction bit position D i [9]. In Figure 2, the partial key of key 1 when pk = 4 is 1010, because D 1 = 5. The distinction bit position D i is also called the offset of the partial key of key i [9].
We describe the structure of the index tree in Figure 6 which is relevant to this paper. A leaf node of the index tree contains a list of entries, one for each index key, plus a pointer to the next node. An entry in a leaf node consists of a partial key, a distinction bit position, an index key length, and a record ID. The header of a leaf node contains a pointer to the last (i.e., highest) index key of the entries in the leaf node. A non-leaf node contains a list of entries, one for each child. The index key corresponding to an entry is the highest index key in the descendant leaves of the child corresponding to the entry. An entry in a non-leaf node consists of a partial key, a distinction bit position, an index key length, a pointer to the child node, and a pointer to the highest index key (where the partial key and the index key length are those of the highest index key, and the distinction bit position is that of the highest index key against the highest index key of the previous entry).
In addition, we keep the following information persistently for each index tree, which will be called the DS-metadata (DS stands for D-bit Slice). Note that we use extended distinction bit positions to define the D-bitmap. We maintain the variant bitmap and a reference key value in order to obtain partial keys when we rebuild our index tree. If partial keys are not needed in an index, the variant bitmap and a reference key value are not necessary, and we need only maintain the D-bitmap, which is the main information to keep for efficient index rebuilding.

Search and Update Operations
We describe how to perform search/insert/delete operations with the index tree and DSmetadata.
• Search: Given a search key value K, we search down the index tree for K as follows.
In a non-leaf node, we need to compare K with an index key in a non-leaf node entry. Since the entry has a pointer to the highest index key (say, A), we make a binary comparison of two full key values K and A.
A leaf node contains a list of partial keys, and thus we need to compare search key K with a list of partial keys. The procedure to compare K with a list of partial keys is the same as the one described in Bohannon et al. [9].
• Insert: Given an insert key value K, insert K into the index tree as follows.
1. Search down the index tree with K and find the right place for insertion (say, between two keys A and B). • Delete: Given a delete key value K, delete K from the index tree as follows.
We delete K as a usual deletion is done in the index tree, and simply leave the D-bitmap and the variant bitmap without changes. We need to show that the D-bitmap is valid after deleting K. Let A and B be the previous key value and the next key value of K, respectively. After An update operation is done by a delete operation followed by an insert operation. Note that if there are only insert operations (i.e., no delete operations), the D-bitmap represents the distinction bit positions exactly.
As the data in a database table change, the DS-metadata is updated incrementally as above. When an insertion occurs, at most one distinction bit position is added to the D-bitmap, and some variant bit positions may be added to the variant bitmap. This operation never reverts even if there is a delete or rollback, because implementing the revert exactly is quite expensive. Hence there may be positions in the D-bitmap whose values are 1, but which are not distinction bit positions. Also the variant bitmap may have positions whose values are 1, but which are not variant bit positions. However, they do not affect the correctness as shown in Theorem 2. Such bit positions can be removed by scanning the index and computing the DS-metadata occasionally. If we rebuild the index anew, then certainly there will be no such bit positions.
With the current DS-metadata, we can rebuild the index tree (which will be described in the next section) when it is lost or unavailable. Even after the index tree is rebuilt, we may use the current DS-metadata as the DS-metadata. However, index rebuilding is an opportune time to compute the DS-metadata anew. We compute the new DS-metadata from the current DS-metadata as follows.
1. D-bitmap: Extract compressed keys from index keys by the current D-bitmap, sort the compressed keys, and compute the distinction bit positions between adjacent compressed keys (all three steps are part of index reconstruction), which make the new D-bitmap. Note that the bit positions where the current D-bitmap had 0 remain 0 in the new D-bitmap. 2. Reference key value: Take an arbitrary index key as the reference key value. 3. Variant bitmap: Initially the variant bitmap is all 0, and we take index keys one by one (say, K) and do the following. Perform a bitwise XOR on K and the reference key value, followed by a bitwise OR on the variant bitmap and the result of the bitwise XOR (as in the insert operation above).
If we build an index tree for the first time (i.e., there is no DS-metadata at all), then we compute the D-bitmap as above, but with full index keys rather than compressed keys.

Remark 2.
Our key compression per se requires O(n) time to compute the DS-metadata initially (other than sorting) and O(1) time to update the DS-metadata for an insertion (other than O(log n) search time to find the right place to insert). Note that sorting is needed anyway to build an index tree and a search is needed anyway to find the place to insert. For the optimal algorithm described in Remark 1, finding the minimum number of bit positions after an insertion is very expensive. Any practical compression scheme should have low complexities in computing compression information such as the DS-metadata and updating the information.

Index Reconstruction
We now describe how to build the index tree in parallel from a database table loaded in memory by using the DS-metadata on the fly. We extract only the bits from the index key values whose positions are set in the D-bitmap. Figure 7 shows the overall procedure of parallel index reconstruction.
1. To collect index keys in parallel, data pages of the target table are evenly distributed to the cores. 2. Each core scans the assigned data pages and extracts compressed keys and corresponding record IDs. A pair of a compressed key and the corresponding record ID makes a sort key. The record ID is included in the sort key so that each pair of a compressed key and a record ID can be directly used to fill its corresponding leaf node entry without causing many cache misses. 3. Sort the pairs of compressed key and record ID by a parallel sorting algorithm. 4. Build the index tree in a bottom-up fashion.

Extracting Compressed Keys
Sort key compression can be done by extracting the bits in the positions which have value 1 in the D-bitmap. We now describe how to get compressed keys from index keys. (Though the examples in Figure 8 are shown in the big endian format for readability, the actual implementation was done in the little endian format due to Intel processors.) 1. Separate one-word long (8 bytes) masks from the D-bitmap. The first mask starts from the byte which contains the first 1 in the bitmap, and it is 8 bytes long. The second mask starts from the byte which contains the first 1 after the first mask, and it is 8 bytes long, and so on. In the example of Figure 8, we get three masks from the D-bitmap. See Figure 8 (c). 2. By BMI instruction PEXT [40] (which copies selected bits from the source to contiguous low-order bits of the destination), extract bits from an index key which are located in the positions where the masks have value 1. See Figure 8

Parallel Sorting
In our target applications which require a wide range of index key sizes, the size of sort keys is usually too big to exploit SIMD parallelism. Thus we implemented our own parallel sorting algorithm called the row-column sort, which is a comparison sort [41] (i.e., it relies only on the operation of comparing two elements during sorting; the comparison operator is called a comparator ). Hence the row-column sort works for any key sizes. The details of the row-column sort are described in Appendix.

Parallel Index Construction
Once the pairs of compressed index key and record ID are sorted in lexicographic order, the index tree can be built in a bottom-up fashion. First, we build leaf nodes from the sorted compressed keys and record IDs. To compute distinction bit positions, we make an array D-offset[i] from the D-bitmap, which stores the position of the (i+1)-st 1 in the D-bitmap. Then the distinction bit position of key i and key i+1 is D-offset[D-bit(Compress(key i ), Compress(key i+1 ))]. Next, we build nonleaf nodes in a bottom-up fashion. For two adjacent entries in a non-leaf node whose highest keys are key i and key j , the distinction bit position is D-offset[D-bit(Compress(key i ), Compress(key j ))].
In the case of our index tree, the leaf nodes and non-leaf nodes contain partial keys of a predefined length pk. Given the offset (i.e., distinction bit position) of a partial key and the predefined partial key length pk, the bits of the partial key are determined as follows.
A. If a bit position of the partial key is included in the compressed key, the bit value can be directly copied from the compressed key. B. If a bit position is a position which has value 0 in the variant bitmap (i.e., an invariant bit position), the bit value can be copied from the reference key value. C. Otherwise (i.e., a bit position which has value 0 in the D-bitmap and value 1 in the variant bitmap), we have two options. a) Add the bits required for partial key construction (pk bits following the distinction bit position) to the compressed key and use them here for index construction. b) Since the record ID is also contained in the sort key, necessary bits can be copied from the record, for which a dereferencing is required. To build an index, we maintain two parameters: max fanout and a fill factor. Each (leaf or non-leaf) node is of size 256B, and it has a header (24B). A leaf node also has a pointer to the next node (8B). Since each entry in a leaf node takes 16B, the max fanout (i.e., maximum number of entries) in a leaf node is (256 − 32)/16 = 14. Since each entry in a non-leaf node takes 24B, the max fanout in a non-leaf node is 9. The fill factor is defined for each index during index building, and leaf and non-leaf nodes are filled up to max fanout × fill factor [41]. Given the number of records, the max fanouts, and the fill factor (default value is 0.9), the height of the index tree can be determined.
Index construction can be parallelized by partitioning the sorted pairs of index key and record ID and constructing subtrees in parallel. That is, n sort keys are divided into p blocks of n p sort keys each, and one block is assigned to a thread (which is the situation at the end of the row-column sort). Thread i (1 ≤ i ≤ p) constructs a subtree consisting of all sort keys in the i-th block. When all the subtrees are constructed, they are merged into one tree such that the height of the resulting tree can be minimized. Since the fanouts of the root nodes of the subtrees can be much less than the max fanout, just linking the root nodes of the subtrees may increase the height of the whole tree unnecessarily. Hence we remove the root nodes of the subtrees, and build the top layers of the whole tree by linking the children of the root nodes of the subtrees. In this way the height of the whole tree can be minimized.

Experimental Settings
We conduct experiments to measure the performance improvements due to our compressed key sort. In the experiments we compare the compressed key sort against the full key sort with respect to the time for sorting and index building. We use five real datasets and one TPC-H dataset: a database table in SAP HANA that records items in sales documents (which we call INDBTAB), a complete EST (expressed sequence tag) database of Human Chromosome 14 from Genome Assembly Gold-standard Evaluations [42], Wikipedia titles [43], external links of DBpedia [44], Wikipedia links of DBpedia [44], and Part load full key sort -sort full key sort -build compressed key sort -extract compressed key sort -sort compressed key sort -build The computer used in our experiments is equipped with four Intel R Xeon R E7-8880 v4 (2.20GHz) processors, each of which contains 22 cores. The computer has 1TB DRAM memory. (Since we used no more than 16 cores in our experiments of parallelization, the experiments were done in a single processor.) Table 2 presents the basic statistics of the six datasets such as the sizes of each database table and its index tree as well as a few important characteristics and measurements relevant to our proposed scheme. The full sort key refers to the combination of an uncompressed key taken from a dataset and the corresponding record ID. The record ID is 8 bytes long, and either the whole or only the variant bits of a record ID can be used as part of a sort key. In the latter case, the variant bitmap in the DS-metadata should be expanded to include the variant bits of the record IDs. The compressed sort key consists of distinction bits in a key and variant bits in the corresponding record ID. Table 2 also shows the number of keys in a dataset, the lengths of the shortest, average, and longest keys, the number of bits in a full key, the number of distinction bits in keys, the number of variant bits in record IDs, the size of full sort keys (i.e., full key + record ID), the size of compressed sort keys (i.e., distinction bits in key + variant bits in record ID). The length of a sort key -full or compressed -is presented in the unit of 8B because sort keys are stored in words.

Evaluation with Real and Synthetic Datasets
The compression ratio and the sort key ratio are computed by the following formulas: compression ratio = # full key bits / # distinction bits in keys sort key ratio = full sort key size / compressed sort key size.
The compression ratio of our key compression scheme is 2.76 on average for the six datasets. (The percentage of distinction bit positions in full index keys is 39.8% on average.) The sort key ratio is 2.34 on average for the six datasets. (The word comparison ratio will be explained in the next subsection.) In all the experiments, comparison of two sort keys is made in the unit of 8-byte words.
Thus, for example, if two sort keys are 24B long, at most three word-comparisons will be required. Figure 9 shows the performance results from all the six datasets. The execution times of the full key sort and the compressed key sort are summarized in three bars for each dataset in the figure.
The first bar (in the white color) of each group shows the time taken to load the key column of each database table from disk. The load time is common to both sort methods and is included in the figure to show how the I/O cost is compared with the sort cost. The second and third bars of each group represent the total cost of building an index, excluding the load time, required by the  full key sort and the compressed key sort, respectively. While the second bar is broken down to two phases, sort and build, the third bar is broken down to three phases, extract, sort, and build. This is because the extract phase is needed only for the compressed key sort to obtain compressed keys by extracting bits from full keys in positions of 1s in the D-bitmap. Despite the extra phase of bit extraction, however, as is shown clearly in Figure 9, our compressed key sort reduced the total index building time substantially by expediting both the sort and build phases. The improvement ratio was 34.0% on average for the six datasets. Note that all the measurements in the figure are normalized to the same scale for the ease of presentation and comparison. The total time of building an index by the full key sort is 4.59, 21.12, 5.68, 17.63, 19.36, and 0.70 seconds for INDBTAB, Human, Wikititle, ExURL, WikiURL, and Part, respectively.
To better understand the performance differential, we looked into the distribution of distinction bit positions. Table 3 shows the distinction bit positions of INDBTAB, where distinction bit positions are set by 1. As is shown in the table, the distinction bit positions are distributed widely over many bytes of full index keys, and extracting distinction bits into a compressed key can make it shorter and improve the performance of sorting and index building. In the case of full key sort, a single key comparison will have to examine up to 22 bytes of each key (i.e., sort by distinguishing prefixes), because the last distinction bit position is in the 22nd byte in the table. In the case of compressed key sort, however, a single key comparison can be done by examining no more than 7 bytes, because there are only 56 distinction bits, which can be stored in 7 bytes. Although a compressed sort key is actually 16 bytes long due to the 27 variant bits in the record IDs, a comparison of two compressed sort keys finishes in one word-comparison because all distinction bits belong to the first word of a compressed sort key.

Sensitivity Analysis
We conduct a sensitivity analysis to see how our sort key compression scheme performs under various circumstances. The main parameters that affect the performance are the sort key ratio defined in the previous section and the word comparison ratio defined as follows: where wcc f ull is the average count of word comparisons required by a single full key comparison, and wcc comp is the average count of word comparisons required by a single compressed key comparison. We used Zipf distribution [46] to generate synthetic datasets of various configurations. Each dataset is generated by a custom function, denoted by Zipf(s, n, m), so that it contains 10 million keys of n bytes each, the first m bytes of each 8 byte word in a key have the same arbitrary ASCII value, and the remaining 8 − m bytes of each word have lower case ASCII characters following the Zipf distribution Zipf (s, 26). The parameter s is the value of the exponent characterizing the Zipf distribution. For example, Zipf(s, 16, 3) generates keys of type aaaZZZZZ aaaZZZZZ, where a is an arbitrary fixed character and Z is a byte having one of 'a' to 'z' by the Zipf distribution (s, 26).    Table 4 shows the statistics of the synthetic datasets used in the sensitivity analysis. As can be seen in the table, the datasets are generated such that they conform to the default parameter settings: word comparison ratio = 1.30 and sort key ratio = 2.00 or 3.00. In datasets 1-9, the word comparison ratio is fixed to 1.30 and the sort key ratio changes as the key size changes. In datasets 10-14 (resp. 15-20), the sort key ratio is fixed to 2.00 (resp. 3.00) and the word comparison ratio changes as m changes in Zipf(s, n, m). Figure 10 shows the index construction times by the compressed key sort in comparison with those by the full key sort. The measurements are the ratio of the former to the latter. So, the higher the ratio is, the larger the margin of improvement is by the compressed key sort. In datasets 1-9, as the sort key ratio increases, the advantage of our compressed key sort scheme grows proportionally. This is because the size of compressed sort keys gets smaller, which leads to a smaller amount of work in sorting and index building.
In datasets 10-14 (also in datasets 15-20) the number of distinction bits in each dataset is about the same, and thus the sort key ratios are identical. However, as m in Zipf(1.5, 40, m) increases, the distinction bits are more widely spread in full keys. Hence, our compression scheme has the effect of compacting widely spread distinction bits in full keys into compressed keys, which leads to a smaller number of word-comparisons in a comparison of two compressed keys. As m increases, therefore, the word comparison ratio gets bigger, which results in an improvement especially in sorting time, even though the sort key ratios remain the same. Therefore, our compression scheme improves the performance of index building in two ways: 1. by making compressed keys shorter than full keys, which leads to a smaller amount of work in sorting and index building, and 2. by compacting distinction bits in full keys into compressed keys, which leads to a smaller number of word-comparisons in a comparison of two compressed keys.
For example, whereas the sort key ratio of WikiURL is smaller than that of INDBTAB (in Table 2), the improvement of WikiURL is larger than that of INDBTAB (in Figure 9) because the word comparison ratio of WikiURL is larger than that of INDBTAB. Finally, we compare the sensitivity analysis to the experimental results with the six datasets with respect to (sort key ratio, word comparison ratio, total time ratio

Parallelization and Loading
In Section 6.2, we have shown that our compressed key sort can reduce times for both sort and index-build phases considerably. Nonetheless, the sort time still remains as the dominant portion of total index reconstruction time. In this section, we show that the sort time could be further full key sort -sort full key sort -build compressed key sort -extract compressed key sort -sort compressed key sort -build  reduced by parallelizing it on a multi-core computing platform. The choice of our sort algorithm was the row-column sort. Refer to Appendix A for the detailed description of the algorithm. Table 5 shows the detailed performance measurements from the full key sort and the compressed key sort with a varying number of cores used. Figure 11 presents the speedups observed in this experiment in the log-log scale. It clearly shows near-linear speedup in all measurements from both the full key sort and compressed key sort except for the index-building time with 16 cores, in which the speedup deteriorated because memory write (390MB in Table 2) became dominant and was not accelerated by using multiple cores. When sixteen cores were used, the speedups in the total index reconstruction time were 13.3 and 13.8 for the full key sort and the compressed key sort, respectively.
In the case of sixteen cores, the tree index of INDBTAB was reconstructed from the preloaded database table in just 0.207 seconds. Given that the memory footprint of the index tree of INDBTAB is 390MB (see Table 2), this is approximately equivalent to 1.88 GB/sec bandwidth. This level of bandwidth is higher than the peak bandwidth of enterprise class magnetic disk drives and most commodity solid state drives. We present this result as an evidence that a tree index can be reconstructed from the pre-loaded database table on the fly much more efficiently than loading the materialized image from disk.

Conclusion
We have defined the notion of distinction bit positions and proved that the bit slices of index keys in distinction bit positions are sufficient information to determine the sorted order of the index keys correctly. Consequently, utilizing only those bit slices is in effect equivalent to compressing keys losslessly in regard to sorting the keys. The key compression ratio achieved by the proposed method was 2.76:1 on average in our experiment.
We have then proposed the compressed key sort based on the distinction bit positions in order to expedite the reconstruction of a tree index from the base table in memory. The compressed key sort reduced the index reconstruction time by 34.0% on average in our experiment carried out on a single core platform. The proposed method based on distinction bit positions is essentially a lightweight key compression scheme. Thus it can be adopted in any application that involves sorting keys longer than the word size and is expected to deliver significant performance benefit. 4 28 11 15 24 16 17 29 26 31 3 22 19 2 0 23 25 18 13 8 5 21 7 12 14 20 27 6 10 1 30 9   4 28 11 15 24 16 17 29   26 31 3 22 19 2 0 23   25 18 13 8 5 21 7 12   14 20 27 6 10 1 30 9   4 11 15 16 17 24 28 29   0 2 3 19 22 23 26 31   5 7 8 12 13 18 21 25   1 6 9 10 14 20 27 30   4 11 15 16 17 24 28  n: number of elements (i.e., sort keys) p: number of threads e: size of an element (in bytes) C: last level cache size (in bytes) per thread (i.e., available L3 cache size / number of threads in our experiments) For the dataset of INDBTAB in Section 6, for instance, n is 16.39 million, and e is 48 bytes for full sort keys. Typically in our target applications, the size of sort keys is too big to exploit SIMD parallelism. Hence, the row-column sort does not rely on SIMD instructions, but it is a comparison sort [41] (i.e., it relies on the operation of comparing two elements). Algorithm 1 shows the pseudo-code of the row-column sort. The details of the algorithm are as follows.
1. (lines 2-3) Compute two parameters which are used in the algorithm: c is the number of elements that can be included in C bytes, and t is set such that n tpc ≈ tp in order to balance the workloads of line 13 and line 18. In Figure 12, n = 32 and p = 4. For simplicity, we assume in this toy example that e = 1 and c = 2. Then t is set to 1.  Figure 12. For simplicity of presentation, we assume that n tp , n tpc , and n p are integers. In Algorithm 1, each block is represented by the first position and the last position in its array (but in actual implementation only one of the first and last positions is necessary because the whole array is partitioned into blocks without overlaps). For example, init block [1] is represented by (1, n tp [1..n] by the following basic sort. The basic sort is essentially Quicksort with insertion sort as the recursion base. The Quicksort partitions around the median of the medians of three samples, each of three elements (also called the pseudo-median of 9 elements) [49]. This basic sort is fast when all the input elements are within the last level cache [49,50].

The row-column sort uses two arrays
sorting times of GCC STL sort and the row-column sort for full sort keys of INDBTAB, and Figure 13 shows the speedups of the two sorting algorithms with multiple cores. The row-column sort shows a better speedup than GCC STL sort, and it is 31.4% faster than GCC STL sort when the number of cores is 16.