FPGA ACCELERATION WINDOW JOINS OVER MULTIPLE DATA STREAMS

Abstract

Recently there has been a growing interest in window joins for scenarios in which data streams arrive at very high rates and a DSMS is registered with many simultaneous queries. Most of the algorithms proposed in the literature are implemented by software. In contrast, we present a novel algorithm named M3Join which can be implemented by software or hardware. M3Join is based on a join architecture which contains a join-routing-table and several half-join architectures. The join architecture is initialized or updated according to the simultaneous queries. Each tuple in the data streams extended with a route tag searches the join-routing-table and switches into the proper half-join architecture to perform join operations or return to end users. The generated join tuples whose route tags have been updated iterate the above search and join procedures until there is no join tuples produced. The algorithm needs only one scan over the data streams since different join queries share the intermediate results. The FPGA implementation of M3Join is presented in detail. The experimental results show that the algorithm is effective and hardware can accelerate join processing vastly.