Reconfigurable SPJ Query Processor For Data Streams

Load shedding strategies are adopted in some real-time systems when CPUs arein saturation. Therefore, one of the key problems of many data stream systems is toimprove processing speed. With the rapid development of hardware technology,much more researchers realize that the hardware technology can greatly promote dataprocessing speed. A co-processor can speedup processing, but generally the co-processor maintains the same circuit, which makes the performance of the co-processor is not always optimal. In order to improve resource utilization andaccelerate processing speed, this paper proposes a novel reconfigurable processor,which changes its hard wired circuit according to the query. This research mainlyincludes the following aspects:(1)This paper proposes a reconfigurable SPJ (select-project-join) queryprocessor framework by analyzing reconfigurable hard wired idea. Under thisframework, the submitted query will be transformed into the corresponding querytree. Each node of the query tree is seemed as an atomic operation, and each atomicoperation is associated with a processing module. Then the program calls thecorresponding processing module according to the query tree, compiles the modulesand downloads them to the FPGA development board.(2) This paper proposes several reconfigurable SPJ query processing modules,which using Verilog HDL to design select, projection and join modules as well astheir corresponding instruction set. Queries are transformed into correspondinginstruction sequences after optimizing and compiling, and are processed inprocessing modules. Therefore, the processor could provide high-performance queryprocessing to meet different continuous queries needs. A large number ofexperiments have done to compare the SPJ processor with software method. Theresults show that the processor is not only correct, but also with high-speed andflexibility.(3)This paper proposes optimization algorithms for multi-join queries onmultiprocessors. In that scenario, one of the key problems is how to arrange thestreams’ probe sequences. Two algorithms are presented in this paper. One isheuristic-adjusting algorithm with the minimum spanning tree as the heuristic rules.The other is a static-solving algorithm using the idea of greedy algorithm. Both of the two algorithms are based on the premise that the join rates remain constant. Theexperimental results show that both the two algorithms can preferably improve thethroughput of the system.