Update-pattern-aware modeling and processing of continuous queries

ABSTRACT

A defining characteristic of continuous queries over on-line data streams, possibly bounded by sliding windows, is the potentially infinite and time-evolving nature of their inputs and outputs. New items continually arrive on the input streams and new results are continually produced. Additionally, inputs expire by falling out of range of their sliding windows and results expire when they cease to satisfy the query. This impacts continuous query processing in two ways. First, data stream systems allow tables to be queried alongside data streams, but in terms of query semantics, it is not clear how updates of tables are different from insertions and deletions caused by the movement of the sliding windows. Second, many interesting queries need to store state, which must be kept up-to-date as time goes on. Therefore, query processing efficiency depends highly on the amount of overhead involved in state maintenance.In this paper, we show that the above issues can be solved by understanding the update patterns of continuous queries and exploiting them during query processing. We propose a classification that defines four types of update characteristics. Using our classification, we present a definition of continuous query semantics that clearly states the role of relations. We then propose the notion of update-pattern-aware query processing, where physical implementations of query operators, including the data structures used for storing intermediate state, vary depending on the update patterns of their inputs and outputs. When tested on IP traffic logs, our update-pattern-aware query plans routinely outperform the existing techniques by an order of magnitude.

REFERENCES

• 1: Daniel J. Abadi , Don Carney , Ugur Çetintemel , Mitch Cherniack , Christian Convey , Sangdon Lee , Michael Stonebraker , Nesime Tatbul , Stan Zdonik, Aurora: a new model and architecture for data stream management, The VLDB Journal — The International Journal on Very Large Data Bases, v.12 n.2, p.120-139, August 2003 [doi>10.1007/s00778-003-0095-z]
• 2: Arvind Arasu , Brian Babcock , Shivnath Babu , Jon McAlister , Jennifer Widom, Characterizing memory requirements for queries over continuous data streams, ACM Transactions on Database Systems (TODS), v.29 n.1, p.162-194, March 2004 [doi>10.1145/974750.974756]
• 3: A. Arasu, S. Babu, and J. Widom. The CQL continuous query language: Semantic foundations and query execution. The VLDB Journal, 14(1), 2005, to appear.
• 4: Ahmed M. Ayad , Jeffrey F. Naughton, Static optimization of conjunctive queries with sliding windows over infinite streams, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007616]
• 5: Brian Babcock , Shivnath Babu , Mayur Datar , Rajeev Motwani , Dilys Thomas, Operator scheduling in data stream systems, The VLDB Journal — The International Journal on Very Large Data Bases, v.13 n.4, p.333-353, December 2004 [doi>10.1007/s00778-004-0132-6]
• 6: Shivnath Babu , Rajeev Motwani , Kamesh Munagala , Itaru Nishizawa , Jennifer Widom, Adaptive ordering of pipelined stream filters, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007615]
• 7: Shivnath Babu , Utkarsh Srivastava , Jennifer Widom, Exploiting k-constraints to reduce memory overhead in continuous queries over data streams, ACM Transactions on Database Systems (TODS), v.29 n.3, p.545-580, September 2004 [doi>10.1145/1016028.1016032]
• 8: R. Brown, Calendar queues: a fast 0(1) priority queue implementation for the simulation event set problem, Communications of the ACM, v.31 n.10, p.1220-1227, Oct. 1988 [doi>10.1145/63039.63045]
• 9: D. Carney, U. Cetintemel, A. Rasin, S. Zdonik, M. Cherniack, and M. Stonebraker. Operator scheduling in a data stream manager. VLDB 2003, pages 838--849.
• 10: L. Golab and M. T. Özsu. Processing sliding window multi-joins in continuous queries over data streams. VLDB 2003, pages 500--511.
• 11: M. Hammad, W. Aref, M. Franklin, M. Mokbel, and A. Elmagarmid. Efficient execution of sliding window queries over data streams. Technical Report CSD TR 03-medulla035, Purdue University, 2003.
• 12: M. A. Hammad , M. F. Mokbel , M. H. Ali , W. G. Aref , A. C. Catlin , A. K. Elmagarmid , M. Eltabakh , M. G. Elfeky , T. M. Ghanem , R. Gwadera , I. F. Ilyas , M. Marzouk , X. Xiong, Nile: A Query Processing Engine for Data Streams, Proceedings of the 20th International Conference on Data Engineering, p.851, March 30-April 02, 2004
• 13: Q. Jiang and S. Chakravarthy. Scheduling strategies for processing continuous queries over streams. BNCOD 2004, pages 16--30.
• 14: J. Kang, J. Naughton, and S. Viglas. Evaluating windows joins over unbounded streams. ICDE 2003, pages 341--352.
• 15: J. Krämer and B. Seeger. A temporal foundation for continuous queries over data streams. COMAD 2005, pages 70--82.
• 16: Y.-N. Law, H. Wang, and C. Zaniolo. Query languages and data models for database sequences and data streams. VLDB 2004, pages 492--503.
• 17: S. Madden and M. J. Franklin. Fjording the stream: An architecture for queries over streaming sensor data. ICDE 2002, pages 555--566.
• 18: R. Motwani et al. Query processing, approximation, and resource management in a data stream management system. CIDR 2003, pages 245--256.
• 19: Vern Paxson , Sally Floyd, Wide area traffic: the failure of Poisson modeling, IEEE/ACM Transactions on Networking (TON), v.3 n.3, p.226-244, June 1995 [doi>10.1109/90.392383]
• 20: Utkarsh Srivastava , Jennifer Widom, Flexible time management in data stream systems, Proceedings of the twenty-third ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 14-16, 2004, Paris, France [doi>10.1145/1055558.1055596]
• 21: Douglas Terry , David Goldberg , David Nichols , Brian Oki, Continuous queries over append-only databases, Proceedings of the 1992 ACM SIGMOD international conference on Management of data, p.321-330, June 02-05, 1992, San Diego, California, United States
• 22: Peter A. Tucker , David Maier , Tim Sheard , Leonidas Fegaras, Exploiting Punctuation Semantics in Continuous Data Streams, IEEE Transactions on Knowledge and Data Engineering, v.15 n.3, p.555-568, March 2003 [doi>10.1109/TKDE.2003.1198390]
• 23: S. Viglas, J. Naughton, and J. Burger. Maximizing the output rate of multi-join queries over streaming information sources. VLDB 2003, pages 285--296.