Multi-Query Optimization of Sliding Window Aggregates by Schedule Synchronization

Data stream systems process persistent queries, typically posed over sliding windows and re-evaluated periodically as the windows slide forward. Due to their long-running nature, a number of similar persistent queries may run in parallel at any given time, therefore multiquery optimization is particularly important. In traditional multi-query optimization, one of the primary goals is to detect common parts across multiple queries issued at the same time and perform the common task only once. Another related goal is to check if a new query may be answered using the answer of a related query which has been computed previously (and is stored as a materialized view). In this paper, we argue that in the context of periodically re-evaluated queries, multi-query optimization requires an additional step beyond common sub-expression matching. This is because queries that have been identified as similar may be re-evaluated with different frequencies and therefore may be scheduled at different times. Thus, the additional step must attempt to synchronize the re-execution times of similar queries in order to take advantage of computation sharing. The solution presented in this paper focuses on periodically-evaluated aggregates ove