Optimizing away joins on data streams

ABSTRACT

Monitoring aggregates on network traffic streams is a compelling application of data stream management systems. Often, streaming aggregation queries involve joining multiple inputs (e.g., client requests and server responses) using temporal join conditions (e.g., within 5 seconds), followed by computation of aggregates (e.g., COUNT) over temporal windows (e.g., every 5 minutes). These types of queries help identify malfunctioning servers (missing responses), malicious clients (bursts of requests during a denial-of-service attack), or improperly configured protocols (short timeout intervals causing many retransmissions). However, while such query expression is natural, its evaluation over massive data streams is inefficient.

In this paper, we develop rewriting techniques for streaming aggregation queries that join multiple inputs. Our techniques identify conditions under which expensive joins can be optimized away, while providing error bounds for the results of the rewritten queries. The basis of the optimization is a powerful but decidable theory in which constraints over data streams can be formulated. We show the efficiency and accuracy of our solutions via experimental evaluation on real-life IP network data using the Gigascope stream processing engine.

REFERENCES

• 1: A. Artale, E. Franconi, and F. Mandreoli. Description Logics for Modelling Dynamic Information. In Logics for Emerging Applications of Databases. Lecture Notes in Computer Science, Springer-Verlag, 2003.
• 2: Ahmed M. Ayad , Jeffrey F. Naughton, Static optimization of conjunctive queries with sliding windows over infinite streams, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007616]
• 3: 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]
• 4: Shivnath Babu , Utkarsh Srivastava , Jennifer Widom, Exploiting k-constraints to reduce memory overhead in continuous queries over data streams, ACM Transactions on Database Systems (TODS), v.29 n.3, p.545-580, September 2004 [doi>10.1145/1016028.1016032]
• 5: Claudio Bettini , Sushil G. Jajodia , Sean X. Wang, Time Granularities in Databases, Data Mining and Temporal Reasoning, Springer-Verlag New York, Inc., Secaucus, NJ, 2000
• 6: J. R. Büchi. On a Decision Method in Restricted Second Order Arithmetic. In International Congress on Logic, Methodology, and Philosophy of Science, pages 1--11, 1962.
• 7: Ashok K. Chandra , Harry R. Lewis , Johann A. Makowsky, Embedded implicational dependencies and their inference problem, Proceedings of the thirteenth annual ACM symposium on Theory of computing, p.342-354, May 11-13, 1981, Milwaukee, Wisconsin, United States [doi>10.1145/800076.802488]
• 8: Jan Chomicki, Efficient checking of temporal integrity constraints using bounded history encoding, ACM Transactions on Database Systems (TODS), v.20 n.2, p.149-186, June 1995 [doi>10.1145/210197.210200]
• 9: J. Chomicki and D. Toman. Temporal Databases. In Handbook of Temporal Reasoning in Artificial Intelligence. Elsevier, 2005.
• 10: 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]
• 11: D. DeHaan, D. Toman, and G. E. Weddell. Rewriting Aggregate Queries using Description Logics. In Description Logics, pages 103--112. CEUR-WS vol. 81, 2003.
• 12: Hector Garcia-Molina , Jennifer Widom , Jeffrey D. Ullman, Database System Implementation, Prentice-Hall, Inc., Upper Saddle River, NJ, 1999
• 13: 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
• 14: Ashish Gupta , Venky Harinarayan , Dallan Quass, Aggregate-Query Processing in Data Warehousing Environments, Proceedings of the 21th International Conference on Very Large Data Bases, p.358-369, September 11-15, 1995
• 15: Information Sciences Institute. RFC 793, 1981.
• 16: Christian S. Jensen , Richard Thomas Snodgrass , Michael D. Soo, Extending Existing Dependency Theory to Temporal Databases, IEEE Transactions on Knowledge and Data Engineering, v.8 n.4, p.563-582, August 1996 [doi>10.1109/69.536250]
• 17: T. Johnson, S. Muthukrishnan, O. Spatscheck, and D. Srivastava. Streams, security and scalability. In IFIP Data and Applications Security, LNCS 3654, pages 1--15, 2005.
• 18: F. Kabanza , J.-M. Stévenne , P. Wolper, Handling infinite temporal data, Journal of Computer and System Sciences, v.51 n.1, p.3-17, Aug. 1995
• 19: J. Kang, J. F. Naughton, and S. Viglas. Evaluating Window Joins over Unbounded Streams. In lCDE, pages 341--352, 2003.
• 20: Ramana Rao Kompella , Sumeet Singh , George Varghese, On scalable attack detection in the network, IEEE/ACM Transactions on Networking (TON), v.15 n.1, p.14-25, February 2007 [doi>10.1109/TNET.2006.890115]
• 21: Flip Korn , S. Muthukrishnan , Yunyue Zhu, Checks and balances: monitoring data quality problems in network traffic databases, Proceedings of the 29th international conference on Very large data bases, p.536-547, September 09-12, 2003, Berlin, Germany
• 22: M. Mellia, I. Stoica, and H. Zhang. TCP Model for Short Lived Flows. IEEE Communcations Letters, 6(2): 85--87, 2002.
• 23: G. N. Paulley , Per-Åke Larson, Exploiting Uniqueness in Query Optimization, Proceedings of the Tenth International Conference on Data Engineering, p.68-79, February 14-18, 1994
• 24: V. Shkapenyuk, T. Johnson, S. Muthukrishnan, and O. Spatscheck. Query-aware sampling for data streams. In Int. Workshop on Scalable Stream Processing Systems (SSPS), 2007.
• 25: Divesh Srivastava , Shaul Dar , H. V. Jagadish , Alon Y. Levy, Answering Queries with Aggregation Using Views, Proceedings of the 22th International Conference on Very Large Data Bases, p.318-329, September 03-06, 1996
• 26: Utkarsh Srivastava , Jennifer Widom, Memory-limited execution of windowed stream joins, Proceedings of the Thirtieth international conference on Very large data bases, p.324-335, August 31-September 03, 2004, Toronto, Canada
• 27: 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
• 28: Stratis D. Viglas , Jeffrey F. Naughton , Josef Burger, Maximizing the output rate of multi-way join queries over streaming information sources, Proceedings of the 29th international conference on Very large data bases, p.285-296, September 09-12, 2003, Berlin, Germany
• 29: Haining Wang , Danlu Zhang , Kang G. Shin, Change-Point Monitoring for the Detection of DoS Attacks, IEEE Transactions on Dependable and Secure Computing, v.1 n.4, p.193-208, October 2004 [doi>10.1109/TDSC.2004.34]
• 30: X. Sean Wang , Claudio Bettini , Alexander Brodsky , Sushil Jajodia, Logical design for temporal databases with multiple granularities, ACM Transactions on Database Systems (TODS), v.22 n.2, p.115-170, June 1997 [doi>10.1145/249978.249979]
• 31: Jef Wijsen, Temporal FDs on complex objects, ACM Transactions on Database Systems (TODS), v.24 n.1, p.127-176, March 1999 [doi>10.1145/310701.310715]

INDEX TERMS

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

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.4 Knowledge Representation Formalisms and Methods
          Subjects: Temporal logic

General Terms:
Algorithms, Performance, Theory

Keywords:
data stream integrity constraints, data stream joins, data stream query rewriting