Minimizing latency and memory in DSMS: a unified approach to quasi-optimal scheduling

ABSTRACT

Data Stream Management Systems (DSMSs) must support optimized execution scheduling of multiple continuous queries on massive, and frequently bursty, data streams. Previous approaches on optimizing memory consumption or response time (i.e., latency) usually produce very different algorithms. In this paper, we extend the popular chart-partitioning procedure, which was previously used for memory optimization on simple operator paths, to minimize latency as well as memory on complex query-graphs with tuple-sharing forks. Furthermore, we test the performance of algorithms that only assume knowledge of the average behavior of tuples and operators, against a theoretical one that assumes detailed knowledge on the behavior of individual tuples. These experiments show that the practical algorithms closely approximate the performance of the optimal ones.

REFERENCES

• 1: Brian Babcock , Shivnath Babu , Mayur Datar , Rajeev Motwani , Jennifer Widom, Models and issues in data stream systems, Proceedings of the twenty-first ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 03-05, 2002, Madison, Wisconsin [doi>10.1145/543613.543615]
• 2: 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]
• 3: Yijian Bai , Hetal Thakkar , Haixun Wang , Chang Luo , Carlo Zaniolo, A data stream language and system designed for power and extensibility, Proceedings of the 15th ACM international conference on Information and knowledge management, November 06-11, 2006, Arlington, Virginia, USA [doi>10.1145/1183614.1183664]
• 4: Yijian Bai, Hetal Thakkar, Haixun Wang, and Carlo Zaniolo. Optimizing timestamp management in data stream management systems. In ICDE, 2007.
• 5: Sirish Chandrasekaran , Michael J. Franklin, Streaming queries over streaming data, Proceedings of the 28th international conference on Very Large Data Bases, p.203-214, August 20-23, 2002, Hong Kong, China
• 6: 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]
• 7: 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
• 8: Lisa Amini , Navendu Jain , Anshul Sehgal , Jeremy Silber , Olivier Verscheure, Adaptive Control of Extreme-scale Stream Processing Systems, Proceedings of the 26th IEEE International Conference on Distributed Computing Systems, p.71, July 04-07, 2006 [doi>10.1109/ICDCS.2006.13]
• 9: 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
• 10: Mohamed F. Mokbel , Xiaopeng Xiong , Moustafa A. Hammad , Walid G. Aref, Continuous Query Processing of Spatio-Temporal Data Streams in PLACE, Geoinformatica, v.9 n.4, p.343-365, December 2005 [doi>10.1007/s10707-005-4576-7]
• 11: Nesime Tatbul , Uğur Çetintemel , Stan Zdonik , Mitch Cherniack , Michael Stonebraker, Load shedding in a data stream manager, Proceedings of the 29th international conference on Very large data bases, p.309-320, September 09-12, 2003, Berlin, Germany
• 12: R. Motwani et. al. Query processing, approximation, and resource management in a data stream management system. In CIDR, Asilomar, CA, 2003.
• 13: Sirish Chandrasekaran , Owen Cooper , Amol Deshpande , Michael J. Franklin , Joseph M. Hellerstein , Wei Hong , Sailesh Krishnamurthy , Samuel R. Madden , Fred Reiss , Mehul A. Shah, TelegraphCQ: continuous dataflow processing, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872857]
• 14: Theodore Johnson , S. Muthukrishnan , Vladislav Shkapenyuk , Oliver Spatscheck, A heartbeat mechanism and its application in gigascope, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 15: Lukasz Golab , M. Tamer Özsu, Issues in data stream management, ACM SIGMOD Record, v.32 n.2, p.5-14, June 2003 [doi>10.1145/776985.776986]
• 16: Qingchun Jiang and Sharma Chakravarthy. Scheduling strategies for processing continuous queries over streams. In BNCOD, pages 16--30, 2004.
• 17: 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
• 18: 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]
• 19: Yi-Cheng Tu , Song Liu , Sunil Prabhakar , Bin Yao, Load shedding in stream databases: a control-based approach, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
• 20: 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]

INDEX TERMS

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

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sequencing and scheduling

General Terms:
Algorithms, Design, Performance

Keywords:
data stream management systems, operator scheduling