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

• Published in: IEEE transactions on circuits and systems. II, Express briefs Express briefs, 2020-11, Vol.67 (11), p.2502-2506
• Main Authors: Wu, Wen-Qi, Xue, Mei-Ting, Zhu, Tian-Qi, Ma, Zhen-Guo, Yu, Feng
• Format: Article
• Language: English
• Subjects: Associative memory; Cams; Computer architecture; Database operation; Field programmable gate arrays; FPGA; hardware acceleration; Hash based algorithms; Hash functions; hash join; Indexes; parallel pipelined; Pipelines; Probes; Static random access memory; Throughput
• ISSN: 1549-7747; 1558-3791
• DOI: 10.1109/TCSII.2020.2980420

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%.