Fast and robust hashing for database operators
Kaan Kara, Gustavo Alonso · 2016
Hashing is an essential part of many database operators, such as joins or aggregation, especially when executed in parallel. Often, database engines resort to using easily computed hash functions like modulo to prevent that hashing becomes a bottleneck. The disadvantage of simple hash functions is that they produce imperfect data distributions, particularly when the data is skewed. Robust hash functions produce balanced distributions but they are computationally expensive. Our purpose in this paper is to break the present trade-off between robustness and performance. We achieve this by showing how to implement robust hash functions suitable for database operators on an FPGA. Our target platform (Intel QuickAssist QPI-FPGA) provides a shared memory architecture between the CPU and the FPGA, enabling database engines to use the hardware hashing without any modifications to their memory layout. Depending on the hash function, we achieve 6.6× improvement over pure software implementations. We also show how to integrate hardware hashing in a hybrid hash table without any acceleration overhead.