ZStream: a cost-based query processor for adaptively detecting composite events

ABSTRACT

Composite (or Complex) event processing (CEP) systems search sequences of incoming events for occurrences of user-specified event patterns. Recently, they have gained more attention in a variety of areas due to their powerful and expressive query language and performance potential. Sequentiality (temporal ordering) is the primary way in which CEP systems relate events to each other. In this paper, we present a CEP system called ZStream to efficiently process such sequential patterns. Besides simple sequential patterns, ZStream is also able to detect other patterns, including conjunction, disjunction, negation and Kleene closure.

Unlike most recently proposed CEP systems, which use non-deterministic finite automata (NFA's) to detect patterns, ZStream uses tree-based query plans for both the logical and physical representation of query patterns. By carefully designing the underlying infrastructure and algorithms, ZStream is able to unify the evaluation of sequence, conjunction, disjunction, negation, and Kleene closure as variants of the join operator. Under this framework, a single pattern in ZStream may have several equivalent physical tree plans, with different evaluation costs. We propose a cost model to estimate the computation costs of a plan. We show that our cost model can accurately capture the actual runtime behavior of a plan, and that choosing the optimal plan can result in a factor of four or more speedup versus an NFA based approach. Based on this cost model and using a simple set of statistics about operator selectivity and data rates, ZStream is able to adaptively and seamlessly adjust the order in which it detects patterns on the fly. Finally, we describe a dynamic programming algorithm used in our cost model to efficiently search for an optimal query plan for a given pattern.

REFERENCES

• 1: Event Processing Workshop, March 2008. http://complexevents.com/?page_id=87.
• 2: StreamBase corporate homepage, 2009. http://www.streambase.com/.
• 3: Coral8 corporate homepage, 2009. http://www.coral8.com/.
• 4: Jagrati Agrawal , Yanlei Diao , Daniel Gyllstrom , Neil Immerman, Efficient pattern matching over event streams, Proceedings of the 2008 ACM SIGMOD international conference on Management of data, June 09-12, 2008, Vancouver, Canada [doi>10.1145/1376616.1376634]
• 5: Sharma Chakravarthy , V. Krishnaprasad , Eman Anwar , S.-K. Kim, Composite Events for Active Databases: Semantics, Contexts and Detection, Proceedings of the 20th International Conference on Very Large Data Bases, p.606-617, September 12-15, 1994
• 6: U. Dayal , B. Blaustein , A. Buchmann , U. Chakravarthy , M. Hsu , R. Ledin , D. McCarthy , A. Rosenthal , S. Sarin , M. J. Carey , M. Livny , R. Jauhari, The HiPAC project: combining active databases and timing constraints, ACM SIGMOD Record, v.17 n.1, p.51-70, March, 1988 [doi>10.1145/44203.44208]
• 7: A. Demers, J. Gehrke, B. Panda, M. Riedewald, V. Sharma, and W. White. Cayuga: A general purpose event monitoring system. In CIDR, January 2007.
• 8: Françoise Fabret , H. Arno Jacobsen , François Llirbat , Joăo Pereira , Kenneth A. Ross , Dennis Shasha, Filtering algorithms and implementation for very fast publish/subscribe systems, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.115-126, May 21-24, 2001, Santa Barbara, California, United States
• 9: S. Gatziu and K. Dittrich. Events in an active ob ject--oriented database. In Workshop on Rules in Database Systems, 1994.
• 10: Narain H. Gehani , H. V. Jagadish, Ode as an Active Database: Constraints and Triggers, Proceedings of the 17th International Conference on Very Large Data Bases, p.327-336, September 03-06, 1991
• 11: 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]
• 12: Anirban Majumder , Rajeev Rastogi , Sriram Vanama, Scalable regular expression matching on data streams, Proceedings of the 2008 ACM SIGMOD international conference on Management of data, June 09-12, 2008, Vancouver, Canada [doi>10.1145/1376616.1376635]
• 13: Reza Sadri , Carlo Zaniolo , Amir Zarkesh , Jafar Adibi, Expressing and optimizing sequence queries in database systems, ACM Transactions on Database Systems (TODS), v.29 n.2, p.282-318, June 2004 [doi>10.1145/1005566.1005568]
• 14: P. Griffiths Selinger , M. M. Astrahan , D. D. Chamberlin , R. A. Lorie , T. G. Price, Access path selection in a relational database management system, Proceedings of the 1979 ACM SIGMOD international conference on Management of data, May 30-June 01, 1979, Boston, Massachusetts [doi>10.1145/582095.582099]
• 15: Eugene Wu , Yanlei Diao , Shariq Rizvi, High-performance complex event processing over streams, Proceedings of the 2006 ACM SIGMOD international conference on Management of data, June 27-29, 2006, Chicago, IL, USA [doi>10.1145/1142473.1142520]
• 16: Yali Zhu , Elke A. Rundensteiner , George T. Heineman, Dynamic plan migration for continuous queries over data streams, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007617]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.4 INFORMATION SYSTEMS APPLICATIONS
      H.4.m Miscellaneous

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.8 Metrics
          Subjects: Performance measures; Complexity measures

General Terms:
Algorithms, Design, Experimentation, Performance

Keywords:
algorithm, complex event processing, optimization, streaming