A Locality-Aware Hash-Join Algorithm

Abstract (2016)

Authors

Fang Fang Computer Engineering - EEMCS
Hidders Hidders Vrije Universiteit Brussel
Bertels Bertels Quantum & Computer Engineering , FTQC/Bertels Lab
Lee Lee IBM Austin Research Laboratory
Hofstee Hofstee Computer Engineering - EEMCS , IBM Austin Research Laboratory
Research Group
Computer Engineering (EEMCS) (TU Delft)
Acceleration FPGAs Join Databases Locality-Aware
More Info
expand_more

Published Date

2016

Language

English

Reuse Rights

Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.

Faculty

Electrical Engineering, Mathematics and Computer Science

Department

Quantum & Computer Engineering

Research Group

Computer Engineering

Abstract

The join is a commonly used operation in databases systems. As data volumes explode, join operations between two large relations become challenging. To overcome this challenge, some research adopts FPGAs (field programmable gate arrays) to accelerate this operation. However, increasing the bandwidth between accelerators and main memory provides additional opportunity for improvement. In this paper, we propose a locality-aware hash-join algorithm, and apply this to explore the potential of using FPGAs to accelerate hash-join operations in databases. The tuples in the input tables are partitioned into small buckets such that each bucket can fit into BRAM (Block RAM) of the FPGA. Hash-join probe operations are only performed on buckets with the same bucket number in these two tables. Analysis shows that the proposed method can take advantage of large memory bandwidth and thus provide a high throughput.