Dynamic plan migration for continuous queries over data streams

ABSTRACT

Dynamic plan migration is concerned with the on-the-fly transition from one continuous query plan to a semantically equivalent yet more efficient plan. Migration is important for stream monitoring systems where long-running queries may have to withstand fluctuations in stream workloads and data characteristics. Existing migration methods generally adopt a pause-drain-resume strategy that pauses the processing of new data, purges all old data in the existing plan, until finally the new plan can be plugged into the system. However, these existing strategies do not address the problem of migrating query plans that contain stateful operators, such as joins. We now develop solutions for online plan migration for continuous stateful plans. In particular, in this paper, we propose two alternative strategies, called the moving state strategy and the parallel track strategy, one exploiting reusability and the second employs parallelism to seamlessly migrate between continuous join plans without affecting the results of the query. We develop cost models for both migration strategies to analytically compare them. We embed these migration strategies into the CAPE [7], a prototype system of a stream query engine, and conduct a comparative experimental study to evaluate these two strategies for window-based join plans. Our experimental results illustrate that the two strategies can vary significantly in terms of output rates and intermediate storage spaces given distinct system configurations and stream workloads.

REFERENCES

• 1: Gennady Antoshenkov, Dynamic Optimization of Index Scans Restricted by Booleans, Proceedings of the Twelfth International Conference on Data Engineering, p.430-440, February 26-March 01, 1996
• 2: 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]
• 3: D. Carney, U. Cetintemel, M. Cherniack, and et al. Monitoring streams - a new class of data management applications. In Proceedings of VLDB Conference, pages 215--226, 2002.
• 4: S. Chandrasekaran and M. J. Franklin. Streaming queries over streaming data. In Proceedings of VLDB Conference, pages 203--214, 2002.
• 5: 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
• 6: 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]
• 7: DatabaSe Research Group(DSRG), Worcester Polytechnic Institute. Cape: Continuous adaptive processing engine, http://davis.wpi.edu/dsrg/CAPE.
• 8: L. Ding, N. Mehta, E. A. Rundensteiner, and G. T. Heineman. Joining punctuated streams. In EDBT Conference, pages 587--604, March 2004.
• 9: Richard L. Cole , Goetz Graefe, Optimization of dynamic query evaluation plans, Proceedings of the 1994 ACM SIGMOD international conference on Management of data, p.150-160, May 24-27, 1994, Minneapolis, Minnesota, United States
• 10: M. A. Hammad, M. J. Franklin, W. G. Aref, and A. K. Elmagarmid. Scheduling for shared window joins over data streams. In Proceedings of VLDB Conference, pages 297--308, 2003.
• 11: Peter J. Haas , Joseph M. Hellerstein, Ripple joins for online aggregation, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.287-298, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
• 12: Yannis E. Ioannidis , Raymond T. Ng , Kyuseok Shim , Timos K. Sellis, Parametric Query Optimization, Proceedings of the 18th International Conference on Very Large Data Bases, p.103-114, August 23-27, 1992
• 13: Zachary G. Ives , A. Y. Halevy , D. S. Weld, An XML query engine for network-bound data, The VLDB Journal — The International Journal on Very Large Data Bases, v.11 n.4, p.380-402, December 2002 [doi>10.1007/s00778-002-0078-5]
• 14: Navin Kabra , David J. DeWitt, Efficient mid-query re-optimization of sub-optimal query execution plans, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.106-117, June 01-04, 1998, Seattle, Washington, United States
• 15: J. Kang, J. F. Naughton, and S. D. Viglas. Evaluating window joins over unbounded streams. In Proceedings of ICDE Conference, pages 341--352, 2003.
• 16: 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]
• 17: Kenneth W. Ng , Zhenghao Wang , Richard R. Muntz , Silvia Nittel, Dynamic Query Re-Optimization, Proceedings of the 11th International Conference on Scientific on Scientific and Statistical Database Management, p.264, July 28-30, 1999 [doi>10.1109/SSDM.1999.787642]
• 18: On Reconfiguring Query Execution Plans in Distributed Object-Relational DBMS, Proceedings of the 1998 International Conference on Parallel and Distributed Systems, p.59, December 14-16, 1998
• 19: R. Notwani, J. Widom, A. Arasu, and et al. Query processing, approximation, and resource management in a data stream management system. In Proceedings of CIDR Conference, pages 1--16, January 2002.
• 20: 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]
• 21: 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]
• 22: Annita N. Wilschut , Peter M. G. Apers, Dataflow query execution in a parallel main-memory environment, Distributed and Parallel Databases, v.1 n.1, p.103-128, Jan. 1993 [doi>10.1007/BF01277522]