BOUNCE: Memory-Efficient SIMD Approach for Lightweight Integer Compression.

Publikation: Beitrag in Buch/Konferenzbericht/Sammelband/GutachtenBeitrag in KonferenzbandBeigetragenBegutachtung



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.


TitelProceedings of the 38th International Conference on Data Engineering Workshops (ICDEW)
ISBN (elektronisch)9781665481045
PublikationsstatusVeröffentlicht - 2022

Externe IDs

Scopus 85134880989
Mendeley a7c40734-473a-3159-8a1a-d16123b7a2dc
ORCID /0000-0001-8107-2775/work/142253555


Forschungsprofillinien der TU Dresden

Fächergruppen, Lehr- und Forschungsbereiche, Fachgebiete nach Destatis


  • SIMD, integer compression, memory-efficiency