High-Parallelism Hash-Merge Architecture for Accelerating Join Operation on FPGA

Join is a data-intensive and compute-intensive operation in database systems. As most existing solutions to accelerate the hash join operation on field programmable gate array (FPGA) are focused on N-to-1 join relationships, their performances rapidly decline on N-to-M joins. To resolve this shortcoming, this brief proposes a novel architecture combining hash and sort-merge algorithms for join acceleration. In the build phase, the architecture utilizes a single hash function to build hash tables for two data tables, and the hash collisions are addressed by building ordered linked lists according to their join attributes. In the merge phase, mapped buckets in two hash tables are merged one-to-one to find matching tuples. This architecture lends itself to high parallelism to improve its performance. Experimental results show that the design on a FPGA achieved a high join throughput of 194.0 million tuples per second, which is better than the reported FPGA implementations. Moreover, the architecture is perfectly compatible with both N-to-1 and N-to-M join relationships.