On-the-fly sharing for streamed aggregation

ABSTRACT

Data streaming systems are becoming essential for monitoring applications such as financial analysis and network intrusion detection. These systems often have to process many similar but different queries over common data. Since executing each query separately can lead to significant scalability and performance problems, it is vital to share resources by exploiting similarities in the queries. In this paper we present ways to efficiently share streaming aggregate queries with differing periodic windows and arbitrary selection predicates. A major contribution is our sharing technique that does not require any up-front multiple query optimization. This is a significant departure from existing techniques that rely on complex static analyses of fixed query workloads. Our approach is particularly vital in streaming systems where queries can join and leave the system at any point. We present a detailed performance study that evaluates our strategies with an implementation and real data. In these experiments, our approach gives us as much as an order of magnitude performance improvement over the state of the art.

REFERENCES

• 1: A. Arasu et al.. Resource sharing in continuous sliding-window aggregates. In VLDB. 2004.
• 2: Arvind Arasu , Shivnath Babu , Jennifer Widom, The CQL continuous query language: semantic foundations and query execution, The VLDB Journal — The International Journal on Very Large Data Bases, v.15 n.2, p.121-142, June 2006 [doi>10.1007/s00778-004-0147-z]
• 3: François Bancilhon , Ted Briggs , Setrag Khoshafian , Patrick Valduriez, FAD, a Powerful and Simple Database Language, Proceedings of the 13th International Conference on Very Large Data Bases, p.97-105, September 01-04, 1987
• 4: D. Carney, et al.. Monitoring streams - a new class of data management applications. In VLDB. 2002.
• 5: S. Chandrasekaran et al.. Streaming queries over streaming data. In VLDB. 2002.
• 6: S. Chandrasekaran, et al.. TelegraphCQ: Continuous dataflow processing for an uncertain world. In CIDR. 2003.
• 7: Jianjun Chen , David J. DeWitt , Feng Tian , Yuan Wang, NiagaraCQ: a scalable continuous query system for Internet databases, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.379-390, May 15-18, 2000, Dallas, Texas, United States
• 8: Chuck Cranor , Theodore Johnson , Oliver Spataschek , Vladislav Shkapenyuk, Gigascope: a stream database for network applications, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872838]
• 9: Matthew Denny , Michael J. Franklin, Predicate result range caching for continuous queries, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066231]
• 10: Prasad M. Deshpande , Karthikeyan Ramasamy , Amit Shukla , Jeffrey F. Naughton, Caching multidimensional queries using chunks, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.259-270, June 01-04, 1998, Seattle, Washington, United States
• 11: C. L. Forgy. Rete: A fast algorithm for the many pattern/many object match problem. Artifical Intelligence, 19(1):17--37, September 1982.
• 12: M. J. Franklin, et al.. Design considerations for high fan-in systems: The HiFi approach. In CIDR. 2005.
• 13: Lukasz Golab , M. Tamer Özsu, Update-pattern-aware modeling and processing of continuous queries, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066232]
• 14: Goetz Graefe, Query evaluation techniques for large databases, ACM Computing Surveys (CSUR), v.25 n.2, p.73-169, June 1993 [doi>10.1145/152610.152611]
• 15: Jim Gray , Adam Bosworth , Andrew Layman , Hamid Pirahesh, Data Cube: A Relational Aggregation Operator Generalizing Group-By, Cross-Tab, and Sub-Total, Proceedings of the Twelfth International Conference on Data Engineering, p.152-159, February 26-March 01, 1996
• 16: M. A. Hammad, et al.. Efficient pipelined execution of sliding window queries over data streams. Technical Report CSD TR#03-035, Purdue, 2003.
• 17: M. A. Hammad, et al.. Scheduling for shared window joins over data streams. In vldb. 2003.
• 18: Venky Harinarayan , Anand Rajaraman , Jeffrey D. Ullman, Implementing data cubes efficiently, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.205-216, June 04-06, 1996, Montreal, Quebec, Canada
• 19: M. Jarke. Common subexpression isolation in multiple query optimization. In Query Processing in Database Systems. Springer Verlag, 1985.
• 20: S. Krishnamurthy, et al.. TelegraphCQ: An architectural status report. IEEE DE. Bull., 26(1), 2003.
• 21: S. Krishnamurthy, et al.. The case for precision sharing. In VLDB. 2004.
• 22: Jin Li , David Maier , Kristin Tufte , Vassilis Papadimos , Peter A. Tucker, No pane, no gain: efficient evaluation of sliding-window aggregates over data streams, ACM SIGMOD Record, v.34 n.1, March 2005 [doi>10.1145/1058150.1058158]
• 23: Samuel Madden , Mehul Shah , Joseph M. Hellerstein , Vijayshankar Raman, Continuously adaptive continuous queries over streams, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564698]
• 24: Samuel Madden , Michael J. Franklin , Joseph M. Hellerstein , Wei Hong, TAG: a Tiny AGgregation service for Ad-Hoc sensor networks, Proceedings of the 5th symposium on Operating systems design and implementation

  Due to copyright restrictions we are not able to make the PDFs for this conference available for downloading

  , December 09-11, 2002, Boston, Massachusetts [doi>10.1145/1060289.1060303]
• 25: R. Motwani, et al.. Query processing, resource management, and approximation in a data stream management system. In CIDR. 2003.
• 26: NASDAQ. NASTRAQ: North American Securities Tracking and Quantifying System. http://www.nastraq.com/description.htm.
• 27: NYSE. NYSE TAQ: Daily Trades and Quotes Database. http://www.nysedata.com/info/productdetail.asp?dpbid=13.
• 28: Prasan Roy , S. Seshadri , S. Sudarshan , Siddhesh Bhobe, Efficient and extensible algorithms for multi query optimization, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.249-260, May 15-18, 2000, Dallas, Texas, United States
• 29: Timos K. Sellis, Multiple-query optimization, ACM Transactions on Database Systems (TODS), v.13 n.1, p.23-52, March 1988 [doi>10.1145/42201.42203]
• 30: Rui Zhang , Nick Koudas , Beng Chin Ooi , Divesh Srivastava, Multiple aggregations over data streams, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066192]
• 31: N. Tatbul, et al.. Load shedding in a data stream manager. In VLDB. 2003.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT

General Terms:
Design, Management, Performance

Keywords:
aggregation, multiple-query optimization, shared processing, streaming data