BOUNCE: Memory-Efficient SIMD Approach for Lightweight Integer Compression.
Research output: Contribution to book/Conference proceedings/Anthology/Report › Conference contribution › Contributed › peer-review
Contributors
Abstract
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 simultane-
ously 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.
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 simultane-
ously 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.
Details
Original language | English |
---|---|
Title of host publication | Proceedings of the 38th International Conference on Data Engineering Workshops (ICDEW) |
Pages | 123-128 |
Number of pages | 6 |
ISBN (electronic) | 9781665481045 |
Publication status | Published - 2022 |
Peer-reviewed | Yes |
External IDs
Scopus | 85134880989 |
---|---|
Mendeley | a7c40734-473a-3159-8a1a-d16123b7a2dc |
ORCID | /0000-0001-8107-2775/work/142253555 |
Keywords
Research priority areas of TU Dresden
DFG Classification of Subject Areas according to Review Boards
Subject groups, research areas, subject areas according to Destatis
Keywords
- SIMD, integer compression, memory-efficiency