EUVIMEDEUVIMED entdecken
Crossref

The FastLanes Compression Layout: Decoding > 100 Billion Integers per Second with Scalar Code

Azim Afroozeh, Peter Boncz

Proceedings of the VLDB Endowment · 2023-05 · 16 (9) · 2132-2144

DOI: 10.14778/3598581.3598587 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Proceedings of the VLDB Endowment, online erschienen am 10.07.2023. Verfasst von Azim Afroozeh und 1 weiteren Autor:innen. Die Arbeit wurde bisher 39-mal zitiert (Crossref) und nennt 39 Literaturangaben.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

The open-source FastLanes project aims to improve big data formats, such as Parquet, ORC and columnar database formats, in multiple ways. In this paper, we significantly accelerate decoding of all common Light-Weight Compression (LWC) schemes: DICT, FOR, DELTA and RLE through better data-parallelism. We do so by re-designing the compression layout using two main ideas: (i) generalizing the value interleaving technique in the basic operation of bit-(un)packing by targeting a virtual 1024-bits SIMD register, (ii) reordering the tuples in all columns of a table in the same Unified Transposed Layout that puts tuple chunks in a common "04261537" order (explained in the paper); allowing for maximum independent work for all possible basic SIMD lane widths: 8, 16, 32, and 64 bits. We address the software development, maintenance and future-proofness challenges of increasing hardware diversity, by defining a virtual 1024-bits instruction set that consists of simple operators supported by all SIMD dialects; and also, importantly, by scalar code. The interleaved and tuple-reordered layout actually makes scalar decoding faster, extracting more data-parallelism from today's wide-issue CPUs. Importantly, the scalar version can be fully auto-vectorized by modern compilers, eliminating technical debt in software caused by platform-specific SIMD intrinsics. Micro-benchmarks on Intel, AMD, Apple and AWS CPUs show that FastLanes accelerates decoding by factors (decoding >40 values per CPU cycle). FastLanes can make queries faster, as compressing the data reduces bandwidth needs, while decoding is almost free.

Zitieren

APA

Afroozeh, A., & Boncz, P. (2023). The FastLanes Compression Layout: Decoding > 100 Billion Integers per Second with Scalar Code. Proceedings of the VLDB Endowment, 16(9), 2132-2144. https://doi.org/10.14778/3598581.3598587

Vancouver

Afroozeh A, Boncz P. The FastLanes Compression Layout: Decoding > 100 Billion Integers per Second with Scalar Code. Proceedings of the VLDB Endowment. 2023;16(9):2132-2144. doi:10.14778/3598581.3598587

BibTeX
@article{Afroozeh2023,
  author = {Afroozeh, Azim and Boncz, Peter},
  title = {The FastLanes Compression Layout: Decoding > 100 Billion Integers per Second with Scalar Code},
  journal = {Proceedings of the VLDB Endowment},
  year = {2023},
  volume = {16},
  number = {9},
  pages = {2132--2144},
  doi = {10.14778/3598581.3598587}
}
Kostenlos starten →