Algorithms and metrics for processing multiple heterogeneous continuous queries

ABSTRACT

The emergence of monitoring applications has precipitated the need for Data Stream Management Systems (DSMSs), which constantly monitor incoming data feeds (through registered continuous queries), in order to detect events of interest. In this article, we examine the problem of how to schedule multiple Continuous Queries (CQs) in a DSMS to optimize different Quality of Service (QoS) metrics. We show that, unlike traditional online systems, scheduling policies in DSMSs that optimize for average response time will be different from policies that optimize for average slowdown, which is a more appropriate metric to use in the presence of a heterogeneous workload. Towards this, we propose policies to optimize for the average-case performance for both metrics. Additionally, we propose a hybrid scheduling policy that strikes a fine balance between performance and fairness, by looking at both the average- and worst-case performance, for both metrics. We also show how our policies can be adaptive enough to handle the inherent dynamic nature of monitoring applications. Furthermore, we discuss how our policies can be efficiently implemented and extended to exploit sharing in optimized multi-query plans and multi-stream CQs. Finally, we experimentally show using real data that our policies consistently outperform currently used ones.

REFERENCES

• 1: Swarup Acharya , S. Muthukrishnan, Scheduling on-demand broadcasts: new metrics and algorithms, Proceedings of the 4th annual ACM/IEEE international conference on Mobile computing and networking, p.43-54, October 25-30, 1998, Dallas, Texas, United States [doi>10.1145/288235.288248]
• 2: Demet Aksoy , Michael Franklin, R × W: a scheduling approach for large-scale on-demand data broadcast, IEEE/ACM Transactions on Networking (TON), v.7 n.6, p.846-860, Dec. 1999 [doi>10.1109/90.811450]
• 3: Ron Avnur , Joseph M. Hellerstein, Eddies: continuously adaptive query processing, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.261-272, May 15-18, 2000, Dallas, Texas, United States
• 4: Brian Babcock , Shivnath Babu , Rajeev Motwani , Mayur Datar, Chain: operator scheduling for memory minimization in data stream systems, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872789]
• 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: Nikhil Bansal , Kirk Pruhs, Server scheduling in the L_p norm: a rising tide lifts all boat, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA [doi>10.1145/780542.780580]
• 7: Michael A. Bender , Soumen Chakrabarti , S. Muthukrishnan, Flow and stretch metrics for scheduling continuous job streams, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.270-279, January 25-27, 1998, San Francisco, California, United States
• 8: Don Carney , Uǧur Çetintemel , Mitch Cherniack , Christian Convey , Sangdon Lee , Greg Seidman , Michael Stonebraker , Nesime Tatbul , Stan Zdonik, Monitoring streams: a new class of data management applications, Proceedings of the 28th international conference on Very Large Data Bases, p.215-226, August 20-23, 2002, Hong Kong, China
• 9: Don Carney , Uğur Çetintemel , Alex Rasin , Stan Zdonik , Mitch Cherniack , Mike Stonebraker, Operator scheduling in a data stream manager, Proceedings of the 29th international conference on Very large data bases, p.838-849, September 09-12, 2003, Berlin, Germany
• 10: Chandrasekaran, S., Cooper, O., Deshpande, A., Franklin, M. J., Hellerstein, J. M., Hong, W., Krishnamurthy, S., Madden, S., Raman, V., Reiss, F., and Shah, M. A. 2003. TelegraphCQ: Continuous Dataflow Processing for an Uncertain World. In Proceedings of the Biennial Conference on Innovative Data Systems Research (CIDR).
• 11: Design and Evaluation of Alternative Selection Placement Strategies in Optimizing Continuous Queries, Proceedings of the 18th International Conference on Data Engineering, p.345, February 26-March 01, 2002
• 12: 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]
• 13: Ronald Fagin , Amnon Lotem , Moni Naor, Optimal aggregation algorithms for middleware, Proceedings of the twentieth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.102-113, May 2001, Santa Barbara, California, United States [doi>10.1145/375551.375567]
• 14: Lukasz Golab , M Tamer Özsu, Processing sliding window multi-joins in continuous queries over data streams, Proceedings of the 29th international conference on Very large data bases, p.500-511, September 09-12, 2003, Berlin, Germany
• 15: Moustafa A. Hammad , Michael J. Franklin , Walid G. Aref , Ahmed K. Elmagarmid, Scheduling for shared window joins over data streams, Proceedings of the 29th international conference on Very large data bases, p.297-308, September 09-12, 2003, Berlin, Germany
• 16: 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
• 17: V. Jacobson, Congestion avoidance and control, Symposium proceedings on Communications architectures and protocols, p.314-329, August 16-18, 1988, Stanford, California, United States
• 18: Kang, J., Naughton, J. F., and Viglas, S. D. 2003. Evaluating window joins over unbounded streams. In Proceedings of the International Conference on Data Engineering (ICDE).
• 19: 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]
• 20: 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]
• 21: Manish Mehta , David J. DeWitt, Dynamic Memory Allocation for Multiple-Query Workloads, Proceedings of the 19th International Conference on Very Large Data Bases, p.354-367, August 24-27, 1993
• 22: Motwani, R., Widom, J., Arasu, A., Babcock, B., Babu, S., Datar, M., Manku, G., Olston, C., Rosenstein, J., and Varma, R. 2003. Query processing, resource management, and approximation in a data stream management system. In Proceedings of the Biennial Conference on Innovative Data Systems Research (CIDR).
• 23: S. Muthukrishnan , Rajmohan Rajaraman , Anthony Shaheen , Johannes E. Gehrke, Online Scheduling to Minimize Average Stretch, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.433, October 17-18, 1999
• 24: 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]
• 25: Mohamed A. Sharaf, Metrics and algorithms for processing multiple continuous queries, University of Pittsburgh, Pittsburgh, PA, 2007
• 26: M. A. Sharaf , P. K. Chrysanthis , A. Labrinidis, Preemptive rate-based operator scheduling in a data stream management system, Proceedings of the ACS/IEEE 2005 International Conference on Computer Systems and Applications, p.46-I, January 03-06, 2005
• 27: Mohamed A. Sharaf , Panos K. Chrysanthis , Alexandros Labrinidis , Kirk Pruhs, Efficient scheduling of heterogeneous continuous queries, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
• 28: Sharaf, M. A., Labrinidis, A., Chrysanthis, P. K., and Pruhs, K. 2005. Freshness-aware scheduling of continuous queries in the dynamic web. In Proceedings of the International Workshop on Web and Databases (WebDB).
• 29: Timothy M. Sutherland , Bradford Pielech , Yali Zhu , Luping Ding , Elke A. Rundensteiner, An Adaptive Multi-Objective Scheduling Selection Framework for Continuous Query Processing, Proceedings of the 9th International Database Engineering & Application Symposium, p.445-454, July 25-27, 2005 [doi>10.1109/IDEAS.2005.9]
• 30: Feng Tian , David J. DeWitt, Tuple routing strategies for distributed eddies, Proceedings of the 29th international conference on Very large data bases, p.333-344, September 09-12, 2003, Berlin, Germany
• 31: Tolga Urhan , Michael J. Franklin, Dynamic Pipeline Scheduling for Improving Interactive Query Performance, Proceedings of the 27th International Conference on Very Large Data Bases, p.501-510, September 11-14, 2001
• 32: Stratis D. Viglas , Jeffrey F. Naughton, Rate-based query optimization for streaming information sources, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564697]
• 33: Carl A. Waldspurger , William E. Weihl, Lottery scheduling: flexible proportional-share resource management, Proceedings of the 1st USENIX conference on Operating Systems Design and Implementation, p.1-es, November 14-17, 1994, Monterey, California
• 34: Annita N. Wilschut , Peter M. G. Apers, Dataflow query execution in a parallel main-memory environment, Proceedings of the first international conference on Parallel and distributed information systems, p.68-77, December 1991, Miami, Florida, United States

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing

General Terms:
Algorithms, Design, Performance

Keywords:
Data stream management system, continuous queries, operator scheduling