Prefilter: predicate pushdown at streaming speeds

ABSTRACT

This paper presents the prefilter: a predicate pushdown framework for a Data Stream Management System (DSMS). Though early predicate evaluation is a well-known query optimization strategy, novel problems arise in a high-performance DSMS. In particular, (i) query invocation costs are high as compared to the cost of evaluating simple predicates that are often used in high-speed stream analysis; (ii) selectivity estimates may become inaccurate over time; and (iii) multiple queries, possibly containing common subexpressions, must be processed continuously. The prefilter addresses these issues by constructing appropriate predicates for early evaluation as soon as new data arrive and before any queries are invoked. It also compresses the bit vector representing the outcomes of pushed-down predicates over newly arrived tuples, and uses the compressed bitmap to efficiently check which queries do not have to be invoked. Using a set of network monitoring queries, we show that the performance of the Gigascope DSMS is significantly improved by the prefilter.

REFERENCES

• 1: Rakesh Agrawal , Tomasz Imieliński , Arun Swami, Mining association rules between sets of items in large databases, ACM SIGMOD Record, v.22 n.2, p.207-216, June 1, 1993
• 2: Brian Babcock , Surajit Chaudhuri, Towards a robust query optimizer: a principled and practical approach, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066172]
• 3: Brian Babcock , Mayur Datar , Rajeev Motwani, Load Shedding for Aggregation Queries over Data Streams, Proceedings of the 20th International Conference on Data Engineering, p.350, March 30-April 02, 2004
• 4: Sirish Chandrasekaran , Michael J. Franklin, PSoup: a system for streaming queries over streaming data, The VLDB Journal — The International Journal on Very Large Data Bases, v.12 n.2, p.140-156, August 2003 [doi>10.1007/s00778-003-0096-y]
• 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: Jianjun Chen , David J. DeWitt , Feng Tian , Yuan Wang, NiagaraCQ: a scalable continuous query system for Internet databases, ACM SIGMOD Record, v.29 n.2, p.379-390, June 2000
• 7: Graham Cormode , Theodore Johnson , Flip Korn , S. Muthukrishnan , Oliver Spatscheck , Divesh Srivastava, Holistic UDAFs at streaming speeds, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007575]
• 8: Chuck Cranor , Yuan Gao , Theodore Johnson , Vlaidslav Shkapenyuk , Oliver Spatscheck, Gigascope: high performance network monitoring with an SQL interface, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564777]
• 9: Matthew Denny , Michael J. Franklin, Predicate result range caching for continuous queries, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066231]
• 10: 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
• 11: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 12: M. Karnaugh. The map method for synthesis of combinational logic circuits. Journal of Symbolic Logic, 20(2):197, 1955.
• 13: Sailesh Krishnamurthy , Michael J. Franklin , Joseph M. Hellerstein , Garrett Jacobson, The case for precision sharing, Proceedings of the Thirtieth international conference on Very large data bases, p.972-984, August 31-September 03, 2004, Toronto, Canada
• 14: Hyo-Sang Lim , Jae-Gil Lee , Min-Jae Lee , Kyu-Young Whang , Il-Yeol Song, Continuous query processing in data streams using duality of data and queries, Proceedings of the 2006 ACM SIGMOD international conference on Management of data, June 27-29, 2006, Chicago, IL, USA [doi>10.1145/1142473.1142509]
• 15: 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]
• 16: R. Motwani et al. Query processing, approximation, and resource management in a data stream management system. CIDR 2003, 245--256.
• 17: Kamesh Munagala , Utkarsh Srivastava , Jennifer Widom, Optimization of continuous queries with shared expensive filters, Proceedings of the twenty-sixth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 11-13, 2007, Beijing, China [doi>10.1145/1265530.1265561]
• 18: S. Muthukrishnan, Data streams: algorithms and applications, Foundations and Trends® in Theoretical Computer Science, v.1 n.2, p.117-236, August 2005 [doi>10.1561/0400000002]
• 19: Prasan Roy , S. Seshadri , S. Sudarshan , Siddhesh Bhobe, Efficient and extensible algorithms for multi query optimization, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.249-260, May 15-18, 2000, Dallas, Texas, United States
• 20: Timos K. Sellis, Multiple-query optimization, ACM Transactions on Database Systems (TODS), v.13 n.1, p.23-52, March 1988 [doi>10.1145/42201.42203]
• 21: 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
• 22: Kun-Lung Wu , Shyh-Kwei Chen , Philip S. Yu, Interval query indexing for efficient stream processing, Proceedings of the thirteenth ACM international conference on Information and knowledge management, November 08-13, 2004, Washington, D.C., USA [doi>10.1145/1031171.1031188]
• 23: Rui Zhang , Nick Koudas , Beng Chin Ooi , Divesh Srivastava, Multiple aggregations over data streams, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066192]

INDEX TERMS

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

General Terms:
Algorithms, Design, Performance

Keywords:
data stream management systems, data stream query optimization, multi-query optimization