A Multiple Continuous Query Optimization Method Based on Query Execution Pattern Analysis

摘要

Many data streams are provided through the network today, and continuous queries are often used to extract useful information from data streams. When a system must process many queries continuously, query optimization is quite important for their efficient execution. In this paper, we propose a novel multiple query optimization method for continuous queries based on query execution pattern analysis. In the advanced stream processing environment assumed in the paper, we use window operators to specify time intervals to select information of interest and the execution time specification to designate when the query should be evaluated. Queries having the same operators may share many intermediate results when they are executed at close instants, but may involve only disjoint data when executed at completely different instants. Thus, query execution timing as well as common subexpressions is a key to deciding an efficient query execution plan. The basic idea of the proposed method is to identify query execution patterns from data arrival logs of data streams and to make the most of the information in deciding an efficient query execution plan. The proposed query optimization scheme first analyzes data arrival logs and extracts query execution patterns. It then forms clusters of continuous queries such that queries in the same cluster are likely to be executed at close instants. Finally, it extracts common subexpressions from among queries in each cluster and decides the query execution plan. We also show experiment results using the prototype implementation, and discuss effectiveness of the proposed approach.