A Hardware-Accelerated Solution for Hierarchical Index-Based Merge-Join

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review

6 Scopus Citations
View graph of relations

Related Research Unit(s)


Original languageEnglish
Pages (from-to)91-104
Journal / PublicationIEEE Transactions on Knowledge and Data Engineering
Issue number1
Online published3 Apr 2018
Publication statusPublished - Jan 2019


Hardware acceleration through field programmable gate arrays (FPGAs) has recently become a technique of growing interest for many data-intensive applications. Join query is one of the most fundamental database query types useful in relational database management systems. However, the available solutions so far have been beset by higher costs in comparison to other query types. In this paper, we develop a novel solution to accelerate the processing of sort-merge join queries with low match rates. Specifically, our solution makes use of hierarchical indexes to identify result-yielding regions in the solution space in order to take advantage of result sparseness. Further, in addition to one-dimensional equi-join query processing, our solution supports processing of multidimensional similarity join queries. Experimental results show that our solution is superior to the best existing method in a low match rate setting; the method achieves a speedup factor of 4.8 for join queries with a match rate of 5%.

Research Area(s)

  • Sort-merge join, hardware acceleration, FPGA, B+-tree, low-selectivity join