F1: Accelerating the optimization of Aggregate Continuous Queries
DocUID: 2015-005 Full Text:
PDF Author: Anatoli U. Shein, Panos K. Chrysanthis, Alexandros Labrinidis
Abstract: Data Stream Management Systems performing on-line analytics rely on the efficient execution of large numbers of Aggregate Continuous Queries (ACQs). The state-of-the-art WeaveShare optimizer uses the Weavability concept in order to selectively combine ACQs for partial aggregation and produce high quality execution plans. However, WeaveShare does not scale well with the number of ACQs. In this paper we propose a novel closed formula, F1, that accelerates Weavability calculations, and thus allows WeaveShare to achieve exceptional scalability in systems with heavy workloads. In general, F1 can reduce the computation time of any technique that combines partial aggregations within composite slides of multiple ACQs. We theoretically analyze the Bit Set approach currently used by WeaveShare and show that F1 is superior in both time and space complexities. We show that F 1 performs ∼ 10^62 times less operations compared to Bit Set to produce the same execution plan for the same input. We experimentally show that F1 executes up to 60,000 times faster and can handle 1,000,000 ACQs in a setting where the limit for the current technique is 550.
Published In: Proceedings of the 24th ACM International Conference on Information and Knowledge Management
Pages: 1151-1160
Place Published: Melbourne, Australia
Year Published: 2015
Project: AQSIOS Subject Area: Data Streams
Publication Type: Conference Paper
Sponsor: NSF CBET-1250171