Compression can sometimes improve performance by making more of the data available to the processors faster. We consider the compression of integer keys in a B+-tree index. For this purpose, systems such as IBM DB2 use variable-byte compression over differentially coded keys. We revisit this problem with various compression alternatives such as Google's VarIntGB, Binary Packing and Frame-of-Reference. In all cases, we describe algorithms that can operate directly on compressed data. Many of our alternatives exploit the single-instruction-multiple-data (SIMD) instructions supported by modern CPUs. We evaluate our techniques in a database environment provided by Upscaledb, a production-quality key-value database. Our best techniques are SIMD accelerated: they simultaneously reduce memory usage while improving single-threaded speeds. In particular, a differentially coded SIMD binary-packing techniques (BP128) can offer a superior query speed (e.g., 40 better than an uncompressed database) while providing the best compression (e.g., by a factor of ten). For analytic workloads, our fast compression techniques offer compelling benefits. Our software is available as open source.
Jin and Chung improve the CST-Trees by using FOR compression @cite_18 . Similarly, @cite_12 propose a SIMD-accelerated in-memory tree index (FAST) where they use FOR @. In related work, @cite_13 propose the VAST-Tree: it improves upon FAST in several ways. In particular, it offers better compression ratios of the keys than FAST by using differential coding and the PFOR compression scheme @cite_42 . Though fast, PFOR does not exploit SIMD instructions: Lemire and Boytsov @cite_35 found that SIMD-accelerated binary packing (i.e., BP128) could be 2 to 3 times faster with little difference in the compression ratios.
@cite_35 @cite_18 @cite_42 @cite_13 @cite_12
1791987072 2099958087 1991780427 2151224499
In many important applications-such as search engines and relational database systems-data are stored in the form of arrays of integers. Encoding and, most importantly, decoding of these arrays consumes considerable CPUtime. Therefore, substantial effort has been made to reduce costs associated with compression and decompression. In particular, researchers have exploited the superscalar nature of modern processors and single-instruction, multiple-data SIMD instructions. Nevertheless, we introduce a novel vectorized scheme called SIMD-BP128i¾? that improves over previously proposed vectorized approaches. It is nearly twice as fast as the previously fastest schemes on desktop processors varint-G8IU and PFOR. At the same time, SIMD-BP128i¾? saves up to 2bits int. For even better compression, we propose another new vectorized scheme SIMD-FastPFOR that has a compression ratio within 10 of a state-of-the-art scheme Simple-8b while being two times faster during decoding. Copyright © 2013 John Wiley & Sons, Ltd. Cache-conscious indices have been researched for a decade. These index structures can enhance data locality and reduce cache misses. Cache-Sensitive B+-tree (CSB+-tree) is a state-of-the-art, high performance index tree for main-memory database systems. However, in the worst case, the space utilization of CSB+-tree can fall to 25 . The main contribution of this paper is to improve space efficiency of CSB+-tree by using compression mechanisms. We have conducted experimental studies. Results show that the compressed CSB+-trees can yield significant space savings with additional benefits for search and delete operations by utilizing the superiority of modern hardware. We propose a compact and efficient index structure for massive data sets. Several indexing techniques are widely-used and well-known such as binary trees and B+trees. Unfortunately, we find that these techniques suffer major two shortcomings when applied to massive sets; first, their indices are so large they could overflow regular main memory, and, second, they suffer from a variety of penalties (e.g., conditional branches, low cache hits, and TLB misses), which restricts the number of instructions executed per processor cycle. Our state-of-the-art index structure, called VAST-Tree, classifies branch nodes into multiple layers. It applies existing techniques such as cache-conscious, aligned, and branch-free structures to the top layers of branch nodes in trees. Next, it applies the adaptive compression technique to save space and harness data parallelism with SIMD instructions to the middle and bottom layers of branch nodes. Moreover, a processor-friendly compression technique is applied to leaf nodes. The end result is that trees are much more compact and traversal efficiency is high. We implement a prototype and show its resulting index size and performance as compared to binary trees, and the hardware-conscious technique called FAST which currently offers the highest performance. Compared to current alternatives, VAST-Tree compacts the branch nodes by more than 95 , and the overall index size by 47-84 given that there are 230 keys. With 228 keys, it has roughly 6.0-times and 1.24-times throughput and saves the memory consumption by more than 94.7 and 40.5 as compared to binary trees and FAST, respectively. In-memory tree structured index search is a fundamental database operation. Modern processors provide tremendous computing power by integrating multiple cores, each with wide vector units. There has been much work to exploit modern processor architectures for database primitives like scan, sort, join and aggregation. However, unlike other primitives, tree search presents significant challenges due to irregular and unpredictable data accesses in tree traversal. In this paper, we present FAST, an extremely fast architecture sensitive layout of the index tree. FAST is a binary tree logically organized to optimize for architecture features like page size, cache line size, and SIMD width of the underlying hardware. FAST eliminates impact of memory latency, and exploits thread-level and datalevel parallelism on both CPUs and GPUs to achieve 50 million (CPU) and 85 million (GPU) queries per second, 5X (CPU) and 1.7X (GPU) faster than the best previously reported performance on the same architectures. FAST supports efficient bulk updates by rebuilding index trees in less than 0.1 seconds for datasets as large as 64Mkeys and naturally integrates compression techniques, overcoming the memory bandwidth bottleneck and achieving a 6X performance improvement over uncompressed index search for large keys on CPUs.