Abstract
Continuous queries over data streams, particularly the joins of streams, have gained popularity as the scope of their applications has increased in the past years. Applications range from network monitoring to sensor processing for environmental monitoring or inventory tracking. The cost of evaluating such queries over streaming sources may vary according to the order in which the joins of streams are processed. In order to lower the cost of executing a query, the query optimizer needs to generate an execution plan that better fits the current conditions of the environment. Existing optimizers try to resolve the above problem by finding a better probing order for multi-way join operators or choosing a better sequence for the binary join operators. However, there are cases where the performance of a hybrid plan (query plan containing both types of operators) exceeds the performance of query plans composed of a single multi-way operator or trees binary join operators. We address the problem of finding a low-cost execution plan in order to execute continuous multi-way join queries over infinite data streams. The search space encompasses plans consisting of a single multi-way operator, plans composed of binary join operators, and hybrid plans. We propose heuristics with a partial cost-based optimization technique to address the three main components of a query optimizer, namely the search space, the cost model and the search strategy. The cost model is used to evaluate all feasible query plans and the heuristics are used to prune the candidates that cannot lead us to good plans. In our work, we evaluate the performance of the proposed approach by comparing the time needed to produce the low-cost query execution plan and quality of our result with the optimum solution and the single multi-way operator with probing order. The result shows that our methodology can find a better plan for the current environment and that is close to the optimal query plan.