Modular Pipeline Architecture for Accelerating Join Operation in RDBMS

This brief proposes a join algorithm based on a top k-sorter. The algorithm applies a filter to remove tuples having no potential matches with the aim of reducing the number of comparisons during join operations between two tables (Ta, Tb). Based on this algorithm, we designed a modular pipeline join architecture that comprises k cascaded processing units. The resource consumption of the architecture is unaffected by the table size such that a join operation between tables with arbitrary sizes is supported. The join process includes a loop in which the k “largest” tuples of the table with smaller size (Ta) are identified to match and filter the tuples of the other table (Tb). Each tuple of Tb is compared with the k largest tuples in turn and discarded if a “smaller” tuple is encountered. After each iterative cycle, the k largest tuples of Ta are also removed. The loop terminates once either of the two tables becomes empty. The experimental results show that the proposed join architecture is not only resource efficient but also achieves high throughput on a state-of-the-art Field Programmable Gate Array (FPGA).