Multi-way Hash Join Based on FPGAs

Abstract

The multi-way hash join is one of the commonly used and time-consuming database operations. Many algorithms have been developed to accelerate this operation, some of which use accelerators such as field programmable gate arrays (FPGAs). However, most of the previous work was focused on computation-intensive operations such as (de)compression, because the interface between the FPGA and the host can only provide relatively low bandwidth.\par

However, new generation high-bandwidth, low-latency interfaces to interconnect host processors and accelerators such as the open coherent accelerator processor interface(OpenCAPI) provide FPGAs with new opportunities to accelerate database operations. In this thesis, we explore the potential of using OpenCAPI-attached FPGAs to accelerate multi-way joins. Via the OpenCAPI, the FPGA can obtain a high-bandwidth communicating with CPUs and the main memory at 25.6GB/s. We first investigate the previous research in software-based multi-way joins and observe that this operation is limited by the bandwidth of main memory. Thus, the main challenge of designing the accelerator emerges as avoiding unnecessary memory accesses. We partition the build relations into the size that can build a hash table in Block RAMs (BRAMs), and avoid multiple-pass memory accesses. In our design, the intermediate join phase is pipelined with a partition phase to reduce the size of the intermediate results. The proposed design is configurable for the attached bandwidth, and it can achieve a throughput of 5 GB/s when a 25.6 GB/s bandwidth is provided.