  Window aggregates are ubiquitous in stream processing. In Azure Stream
Analytics (ASA), a stream processing service hosted by Microsoft's Azure cloud,
we see many customer queries that contain aggregate functions (such as MIN and
MAX) over multiple correlated windows (e.g., tumbling windows of length five
minutes and ten minutes) defined on the same event stream. In this paper, we
present a cost-based optimization framework for optimizing such queries by
sharing computation among multiple windows. In particular, we introduce the
notion of factor windows, which are auxiliary windows that are not in the input
query but may nevertheless help reduce the overall computation cost, and our
cost-based optimizer can produce rewritten query plans that have lower costs
than the original query plan by utilizing factor windows. Since our
optimization techniques are at the level of query (plan) rewriting, they can be
implemented on any stream processing system that supports a declarative,
SQL-like query language without changing the underlying query execution engine.
We formalize the shared computation problem, present the optimization
techniques in detail, and report evaluation results over both synthetic and
real datasets. Our results show that, compared to the original query plans, the
rewritten plans output by our cost-based optimizer can yield significantly
higher (up to 16.8x) throughput.
