Lemire, Daniel et Rupp, Christoph (2017). Upscaledb: Efficient Integer-Key Compression in a Key-Value Store using SIMD Instructions. Information Systems, 66, 13–23. 10.1016/j.is.2017.01.002
Fichier(s) associé(s) à ce document :|
PDF
- upscaledb.pdf
Contenu du fichier : Manuscrit soumis (avant évaluation) Licence : Creative Commons CC BY. |
|
| Catégorie de document : | Articles de revues |
|---|---|
| Évaluation par un comité de lecture : | Oui |
| Étape de publication : | Publié |
| Résumé : | 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. |
| Déposant: | Lemire, Daniel |
| Responsable : | Daniel Lemire |
| Dépôt : | 05 janv. 2017 18:03 |
| Dernière modification : | 16 janv. 2017 20:36 |
|
RÉVISER |
