Fighting the duplicates in hashing: Conflict Detection-aware Vectorization of Linear Probing
Publikation: Beitrag in Buch/Konferenzbericht/Sammelband/Gutachten › Beitrag in Konferenzband › Beigetragen › Begutachtung
Beitragende
Abstract
Hash tables are a core data structure in database systems, because they are fundamental for many database operators like hash-based join and aggregation. In recent years, the efficient vectorized implementation using SIMD (Single Instruction Multiple Data) instructions has attracted a lot of attention. Generally, all hash table implementations need to address what happens when collisions occur. In order to do that, the collisions have to be detected first. There are two types of collisions: (i) key duplicates and (ii) hash value duplicates. The second type is more complicated than the first type. In this paper, we investigate linear probing as a heavily applied hash table implementation and we present an extension of the state-of-the-art vectorized implementation with a hardware-supported duplicate or collision detection. For that, we use novel SIMD instructions which have been introduced with Intel's SIMD instruction set extension AVX-512. As we are going to show, our approach outperforms the state-of-the-art vectorized version for the key handling, but introduces novel challenges for the value handling. We conclude the paper with some ideas how to tackle that challenge.
Details
Originalsprache | Englisch |
---|---|
Titel | Datenbanksysteme fur Business, Technologie und Web, BTW 2019 and 18. Fachtagung des GI-Fachbereichs "Datenbanken und Informationssysteme", DBIS 2019 |
Redakteure/-innen | Torsten Grust, Felix Naumann, Alexander Bohm, Wolfgang Lehner, Theo Harder, Erhard Rahm, Andreas Heuer, Meike Klettke, Holger Meyer |
Herausgeber (Verlag) | Gesellschaft fur Informatik (GI) |
Seiten | 35-53 |
Seitenumfang | 19 |
ISBN (elektronisch) | 9783885796831 |
Publikationsstatus | Veröffentlicht - 2019 |
Peer-Review-Status | Ja |
Publikationsreihe
Reihe | GI-Edition : lecture notes in informatics. Proceedings |
---|---|
Band | P-289 |
ISSN | 1617-5468 |
Konferenz
Titel | Datenbanksysteme fur Business, Technologie und Web, BTW 2019 and 18. Fachtagung des GI-Fachbereichs "Datenbanken und Informationssysteme", DBIS 2019 - Database Systems for Business, Technology and Web, BTW 2019 and 18th Symposium of the GI Department "Databases and Information Systems", DBIS 2019 |
---|---|
Dauer | 4 - 8 März 2019 |
Stadt | Rostock |
Land | Deutschland |
Externe IDs
Scopus | 85072105068 |
---|---|
ORCID | /0000-0001-8107-2775/work/142253467 |
Schlagworte
ASJC Scopus Sachgebiete
Schlagwörter
- Conflict Detection, Hashing, Linear Probing, Vectorization