BOUNCE: Memory-Efficient SIMD Approach for Lightweight Integer Compression
Juliana Hildebrandt, Dirk Habich, Wolfgang Lehner · 2022
Integer compression plays an important role in columnar database systems to reduce the main memory footprint as well as to speedup query processing. To keep the additional computational effort of (de)compression as low as possible, the powerful Single Instruction Multiple Data (SIMD) extensions of modern CPUs are heavily applied. While a scalar compression algorithm usually compresses a block of$N$consecutive integers, the state-of-the-art SIMD implementation scales the block size to$k$*$N$with$k$as the number of elements which could be simultaneously processed in an SIMD register. On the one hand, this scaling SIMD approach improves the performance of (de)compression but can lead to a degradation of the compression ratio compared to the scalar variant on the other hand. Within this paper, we analyze this degradation effect for an heavily applied and well-performing integer compression algorithm called BitPacking (BP) and present a novel SIMD concept to overcome that effect. Our novel SIMD idea called BOUNCE is to concurrently compress$k$different blocks of size$N$within SIMD registers achieving the same compression rate as the scalar variant. As we are going to show, our proposed SIMD idea works well for BP and may offer a new generalized approach to optimize further algorithms.