High-Throughput Parallel SRAM-Based Hash Join Architecture on FPGA

摘要

The hash join operator is one of the most important relational operations used in database. The offloading and acceleration of this operation on hardware has been a technique of growing interest for a long time. However, the non-uniform distribution of data caused by hash collisions negatively affects the throughput of the hash join algorithm, owing the variation in the number of hash table accesses required for each lookup. To resolve this issue, a non-collision parallel static random-access memory (SRAM)-based hash join architecture is presented. This architecture utilizes multiple hash functions and content addressable memories (CAMs) to eliminate hash collision, thereby ensuring a worst constant memory access for each phase in the hash join algorithm and consequently improving the hash join throughput. The proposed architecture was implemented on a Xilinx field programmable gate array (FPGA), and the experimental results show that our design achieved a high hash join throughput of 153.6 million tuples per second, and a speedup factor of at least 2.5 with the best existing FPGA-based hash join architecture and a match rate of 50%.