Distributed complex event processing with query rewriting

ABSTRACT

The nature of data in enterprises and on the Internet is changing. Data used to be stored in a database first and queried later. Today timely processing of new data, represented as events, is increasingly valuable. In many domains, complex event processing (CEP) systems detect patterns of events for decision making. Examples include processing of environmental sensor data, trades in financial markets and RSS web feeds. Unlike conventional database systems, most current CEP systems pay little attention to query optimisation. They do not rewrite queries to more efficient representations or make decisions about operator distribution, limiting their overall scalability.

This paper describes the NEXT CEP system that was especially designed for query rewriting and distribution. Event patterns are specified in a high-level query language and, before being translated into event automata, are rewritten in a more efficient form. Automata are then distributed across a cluster of machines for detection scalability. We present algorithms for query rewriting and distributed placement. Our experiments on the Emulab test-bed show a significant improvement in system scalability due to rewriting and distribution.

REFERENCES

• 1: D. Abadi, D. Camey, U. Cetintemel, M. Chemiack, et al. Aurora: A New Model and Architecture for Data Stream Management. VLDB Journal, 2003.
• 2: D. J. Abadi, Y. Ahmad, M. Balazinska, U. Cetintemel, et al. The Design of the Borealis Stream Processing Engine. In CIDR, Asilomar, CA, January 2005.
• 3: Y. Ahmad and U. Çetintemel. Network-Aware Query Processing for Stream-based App. In VLDB, 2004.
• 4: M. Akdere, U. Çetintemel, and N. Tatbul. Plan-based Complex Event Detection across Distributed Event Sources. In VLDB, 2008.
• 5: A. Arasu, B. Babcock, S. Babu, J. Cieslewicz, et al. STREAM: The Stanford Data Stream Management System, http://infolab.stanford.edu/stream, 2004.
• 6: A. Arasu, S. Babu, and J. Widom. The CQL Continuous Query Language: Semantic Foundations and Query Execution. VLDB Journal, 15(2), 2006.
• 7: M. Balazinska, H. Balakrishnan, and M. Stonebraker. Contract-Based Load Management in Federated Distributed Systems. In Proc. of NSDI'04, San Francisco, CA, Mar. 2004.
• 8: D. Carney, U. Çetintemel, M. Cherniack, C. Convey, et al. Monitoring Streams - A New Class of Data Management Applications. In VLDB, 2002.
• 9: S. Chakravarthy and D. Mishra. Snoop: an Expressive Event Specification Language for Active Databases. Data Knowledge Engineering, 14(1):1--26, 1994.
• 10: S. Chandrasekaran et al. TelegraphCQ: Continuous Dataflow Processing for an Uncertain World. In CIDR, 2003.
• 11: M. Cherniack, H. Balakrishnan, M. Balazinska, D. Carney, et al. Scalable Distributed Stream Processing. In CIDR, Asilomar, CA, January 2003.
• 12: T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. Introduction to Algorithms. The MIT Press and McGraw-HilDyanl, 2nd edition, 2003.
• 13: A. Demers, J. Gehrke, M. Hong, B. Panda, et al. Towards Expressive Publish/Subscribe Systems. In EDBT, 2006.
• 14: A. Demers, J. Gehrke, M. Hong, B. Panda, et al. Cayuga: A Genaral Purpose Event Monitoring System. In CIDR, pages 412--422, 2007.
• 15: Emulab's homepage. http://www.emulab.net/.
• 16: R. S. Epstein and M. Stonebraker. Analysis of Distributed Data Base Processing Strategies. In VLDB, pages 92--101, 1980.
• 17: Esper's homepage. http://esper.codehaus.org.
• 18: Federal Bureau of Investigation. Financial Crimes Report to the Public Fiscal Year 2007. Technical report, Federal Bureau of Investigation, 2007.
• 19: L. Fiege, G. Muhl, and P. R. Pietzuch. Distributed Event-based Systems. Springer-Verlag Berlin and Heidelberg GmbH & Co. K, 2006.
• 20: S. Gatziu and K. R. Dittrich. Detecting Composite Events in Active Database Systems Using Petri Nets. In RIDE-ADS, pages 2--9, 1994.
• 21: J. E. Hopcroft, R. Motwani, Rotwani, and J. D. Ullman. Introduction to Automata Theory, Languages and Computability. Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA, 2000.
• 22: L. Lamport. Time, Clocks, and the Ordering of Events in a Distributed System. Commun. ACM, 21(7):558--565, 1978.
• 23: P. Pietzuch, J. Ledlie, J. Shneidman, M. Roussopoulos, et al. Network-Aware Operator Placement for Stream-Processing Sys. In ICDE, 2006.
• 24: P. R. Pietzuch, B. Shand, and J. Bacon. A Framework for Event Composition in Distributed Systems. In Middleware, Rio de Janeiro, Brazil, jun 2003.
• 25: S. Seshadri, V. Kumar, and B. F. Cooper. Optimizing Multiple Queries in Distributed Data Stream Systems. In NetDB, page 25, 2006.
• 26: Visa Inc. Operational Performance Data. http://corporate.visa.com/md/st/, 2008.
• 27: Walker White and Mirek Riedewald and Johannes Gehrke and Alan Demers. What is "Next" in Event Processing? In SIGMOD-SIGACT-SIGART, 2007.
• 28: Y. Xing, S. Zdonik, and J.-H. Hwang. Dynamic Load Distribution in the Borealis Stream Processor. In ICDE, pages 791--802, 2005.
• 29: M. T. Özsu and P. Valduriez. Principles of Distributed Databases. Prentice-Hall Inc., 2nd edition, 1999.

INDEX TERMS

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

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems

  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Query formulation

General Terms:
Algorithms, Design, Experimentation, Measurement, Performance