Adaptive continuous query reoptimization over data streams

A data stream is a series of massive unbounded tuples continuously generated at a rapid rate. Continuous queries for data streams should be processed continuously, so that a strict time constraint is required. In most previous research studies, in order to guarantee this constraint, the evaluation order of join predicates in a continuous query is optimized using a greedy strategy. However, because a greedy strategy traces only the first promising plan, it often finds a suboptimal plan. To reduce the possibility of producing a suboptimal plan, in this paper, we propose an improved scheme, k-Extended Greedy Algorithm (k-EGA), that simultaneously examines a set of promising plans and reoptimize an execution plan adaptively. The number of promising plans is flexibly controlled by a user-defined range variable. The scheme verifies the performance of the current plan periodically. If the plan is no longer efficient, a newly optimized plan is generated. The performance of the proposed scheme is verified through various experiments to identify its various characteristics.