Optimization of continuous queries with shared expensive filters

ABSTRACT

We consider the problem of optimizing and executing multiple continuous queries, where each query is a conjunction of filters and each filter may occur in multiple queries. When filters are expensive, significant performance gains are achieved by sharing filter evaluations across queries. A shared execution strategy in our scenario can either be fixed, in which filters are evaluated in the same predetermined order for all input, or adaptive, in which the next filter to be evaluated is chosen at runtime based on the results of the filters evaluated so far. We show that as filter costs increase, the best adaptive strategy is superior to any fixed strategy, despite the overhead of adaptivity. We show that itis NP-hard to find the optimal adaptive strategy, even if we are willing to approximate within any factor smaller than m where m is the number of queries. We then present a greedy adaptive execution strategy and show that it approximates the best adaptive strategy to within a factor O(log²m log n) where n is the number of distinct filters. We also give a precomputation technique that can reduce the execution overhead of adaptive strategies.

REFERENCES

• 1: A. Arasu and J. Widom. Resource sharing in continuous sliding-window aggregates. In Proc. of the 2004 Intl. Conf. on Very Large Data Bases, pages 336--347, 2004.
• 2: Ron Avnur , Joseph M. Hellerstein, Eddies: continuously adaptive query processing, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.261-272, May 15-18, 2000, Dallas, Texas, United States
• 3: 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]
• 4: Shivnath Babu , Rajeev Motwani , Kamesh Munagala , Itaru Nishizawa , Jennifer Widom, Adaptive ordering of pipelined stream filters, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007615]
• 5: Pedro Bizarro , Shivnath Babu , David DeWitt , Jennifer Widom, Content-based routing: different plans for different data, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 6: Surajit Chaudhuri , Kyuseok Shim, Optimization of queries with user-defined predicates, ACM Transactions on Database Systems (TODS), v.24 n.2, p.177-228, June 1999 [doi>10.1145/320248.320249]
• 7: Jianjun Chen , David J. DeWitt , Feng Tian , Yuan Wang, NiagaraCQ: a scalable continuous query system for Internet databases, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.379-390, May 15-18, 2000, Dallas, Texas, United States
• 8: Nilesh N. Dalvi , Sumit K. Sanghai , Prasan Roy , S. Sudarshan, Pipelining in multi-query optimization, Proceedings of the twentieth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.59-70, May 2001, Santa Barbara, California, United States [doi>10.1145/375551.375561]
• 9: Brian C. Dean , Michel X. Goemans , Jan Vondrak, Approximating the Stochastic Knapsack Problem: The Benefit of Adaptivity, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS'04), p.208-217, October 17-19, 2004 [doi>10.1109/FOCS.2004.15]
• 10: A. Deshpande, C. Guestrin, S. Madden, J. M. Hellerstein, and W. Hong. Model-driven data acquisition in sensor networks. In Proc. of the 2004 Intl. Conf. on Very Large Data Bases, 2004.
• 11: O. Madani, Efficient information gathering on the Internet, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.234, October 14-16, 1996
• 12: 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
• 13: E. Hanson. The Interval Skip List: A data structure for finding all intervals that overlap a point. In WADS, pages 153--164, 1991.
• 14: Eric N. Hanson, Rule condition testing and action execution in Ariel, Proceedings of the 1992 ACM SIGMOD international conference on Management of data, p.49-58, June 02-05, 1992, San Diego, California, United States
• 15: Joseph M. Hellerstein , Michael Stonebraker, Predicate migration: optimizing queries with expensive predicates, Proceedings of the 1993 ACM SIGMOD international conference on Management of data, p.267-276, May 25-28, 1993, Washington, D.C., United States
• 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: Rajeev Motwani , Prabhakar Raghavan, Randomized algorithms, Cambridge University Press, New York, NY, 1995
• 18: K. Munagala, U. Srivastava, and J. Widom. Optimization of continuous queries with shared expensive filters. Technical report, Stanford University, 2005. Available at http://dbpubs.stanford.edu/pub/2005-36.
• 19: Open source computer vision library. http://sourceforge.net/projects/ opencvlibrary.
• 20: Martin Skutella , Marc Uetz, Scheduling precedence-constrained jobs with stochastic processing times on parallel machines, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.589-590, January 07-09, 2001, Washington, D.C., United States
• 21: R. Strom et al. Gryphon: An information flow based approach to message brokering. In Intl. Symp. on Software Reliability Engineering, 1998.
• 22: Vijay V. Vazirani, Approximation algorithms, Springer-Verlag New York, Inc., New York, NY, 2001
• 23: Tak W. Yan , Hector Garcia-Molina, The SIFT information dissemination system, ACM Transactions on Database Systems (TODS), v.24 n.4, p.529-565, Dec. 1999 [doi>10.1145/331983.331992]

INDEX TERMS

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

General Terms:
Algorithms, Performance

Keywords:
expensive predicates, query optimization, shared execution