Shenoda Guirguis
Mohamed A. Sharaf
Alexandros Labrinidis
ABSTRACT
Data Streams Management Systems are designed to support monitoring applications, which require the processing of hundreds of Aggregate Continuous Queries (ACQs). These ACQs typically have different time granularities, with possibly different selection predicates and group-by attributes. In order to achieve scalability in the presence of heavy workloads, in this paper, we introduce the concept of 'Weaveability' as an indicator of the potential gains of sharing the processing of ACQs. We then propose Weave Share, a cost-based optimizer that exploits weaveability to optimize the shared processing of ACQs. Our experimental analysis shows that Weave Share outperforms the alternative sharing schemes generating up to four orders of magnitude better quality plans. Finally, we describe a practical implementation of the Weave Share optimizer.
- D. J. Abadi et al. Aurora: a new model and architecture for data stream management. VLDBJ, 12(2):120--139, 2003. Google Scholar
Digital Library
- D. J. Abadi et al. The design of the borealis stream processing engine. In CIDR, 2005.Google Scholar
- A. Arasu et al. STREAM: The stanford stream data manager. In SIGMOD, 2003. Google ScholarDigital Library
- E. Bach, K. Pruhs. Personal communications, June 2010.Google Scholar
- M. R. Garey, D. S. Johnson. Computers and Intractability; A Guide to the Theory of NP-Completeness. WH.Freeman & Co., 1990. Google ScholarDigital Library
- T. M. Ghanem et al. Incremental evaluation of sliding- window queries over data streams. TKDE, 19(1):57--72, 2007. Google ScholarDigital Library
- L. Golab et al. Multi-query optimization of sliding window aggregates by schedule synchronization. In CIKM, 2006. Google ScholarDigital Library
- G. Graefe, W. J. McKenna. The volcano optimizer generator: Extensibility and efficient search. In ICDE, 1993. Google ScholarDigital Library
- M. A. Hammad et al. Nile: A query processing engine for data streams. In ICDE, 2004. Google ScholarDigital Library
- R. Huebsch et al. Sharing aggregate computation for distributed queries. In SIGMOD, 2007. Google ScholarDigital Library
- R. Johnson et al. To share or not to share? In VLDB, 2007. Google ScholarDigital Library
- S. Krishnamurthy et al. On-the-fly sharing for streamed aggregation. In SIGMOD, 2006. Google ScholarDigital Library
- J. Li et al. No pane, no gain: efficient evaluation of sliding- window aggregates over data streams. SIGMOD Rec., 2005. Google ScholarDigital Library
- J. Li et al. Semantics and evaluation techniques for window aggregates in data streams. In SIGMOD, 2005. Google ScholarDigital Library
- S. Madden et al. Continuously adaptive continuous queries over streams. In SIGMOD, 2002. Google ScholarDigital Library
- H. Mistry et al. Materialized view selection and maintenance using multi-query optimization. In SIGMOD, 2001. Google ScholarDigital Library
- K. Naidu et al. Memory-constrained aggregate computation over data streams. In ICDE, 2011. Google ScholarDigital Library
- P. Roy et al. Efficient and extensible algorithms for multi query optimization. In SIGMOD, 2000. Google ScholarDigital Library
- W. Scheufele, G. Moerkotte. On the complexity of generating optimal plans with cross products. In PODS, 1997. Google ScholarDigital Library
- T. K. Sellis. Multiple-query optimization. TODS, 13(1):23--52, 1988. Google ScholarDigital Library
- Streambase, http://www.streambase.com, 2006.Google Scholar
- System S, http://domino.research.ibm.com/, 2008.Google Scholar
- S. D. Viglas, J. F. Naughton. Rate-based query optimization for streaming information sources. In SIGMOD, 2002. Google ScholarDigital Library
- S. Wang et al. State-slice: new paradigm of multi-query optimization of window-based stream queries. In VLDB, 2006. Google ScholarDigital Library
- R. Zhang et al. Multiple aggregations over data streams. In SIGMOD, 2005. Google ScholarDigital Library
- R. Zhang et al. Streaming multiple aggregations using phantoms. VLDBJ, 19(4):557--583, 2010. Google ScholarDigital Library
- J. Zhou et al. Efficient exploitation of similar subexpressions for query processing. In SIGMOD, 2007. Google ScholarDigital Library
Index Terms
- Optimized processing of multiple aggregate continuous queries
Recommendations
An Optimal Algorithm for Processing Distributed Star Queries
The problem of optimal query processing in distributed database systems was shown to be NP-hard. However, for a special type of queries called star queries, we have developed a polynomial optimal algorithm. Semijoin tactics are applied for query ...
Equivalence and minimization of conjunctive queries under combined semantics
ICDT '12: Proceedings of the 15th International Conference on Database TheoryThe problems of query containment, equivalence, and minimization are fundamental problems in the context of query processing and optimization. In their classic work [2] published in 1977, Chandra and Merlin solved the three problems for the language of ...
Continuous query processing in data streams using duality of data and queries
SIGMOD '06: Proceedings of the 2006 ACM SIGMOD international conference on Management of dataRecent data stream systems such as TelegraphCQ have employed the well-known property of duality between data and queries. In these systems, query processing methods are classified into two dual categories -- data-initiative and query-initiative -- ...
Comments