Flow algorithms for two pipelined filter ordering problems

ABSTRACT

Pipelined filter ordering is a central problem in database query optimization, and has received renewed attention recently in the context of environments such as the web, continuous high-speed data streams and sensor networks. We present algorithms for two natural extensions of the classical pipelined filter ordering problem: (1) a distributional type problem where the filters run in parallel and the goal is to maximize throughput, and (2) an adversarial type problem where the goal is to minimize the expected value of multiplicative regret. We show that both problems can be solved using similar flow algorithms, which find an optimal ordering scheme in time O(n²), where n is the number of filters. Our algorithm for (1) improves on an earlier O(n³ log n) algorithm of Kodialam.

REFERENCES

• 1: 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
• 2: B. Awerbuch and F. T. Leighton. A simple local-control approximation algorithm for multicommodity flow. In Proceedings of the 34th IEEE Symposium on Foundations of Computer Science, pages 459--468. IEEE Computer Society, 1993.
• 3: 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]
• 4: Amotz Bar-Noy , Mihir Bellare , Magnús M. Halldórsson , Hadas Shachnai , Tami Tamir, On chromatic sums and distributed resource allocation, Information and Computation, v.140 n.2, p.183-202, Feb. 1, 1998 [doi>10.1006/inco.1997.2677]
• 5: Surajit Chaudhuri , Umeshwar Dayal , Tak W. Yan, Join queries with external text sources: execution and optimization techniques, Proceedings of the 1995 ACM SIGMOD international conference on Management of data, p.410-422, May 22-25, 1995, San Jose, California, United States
• 6: E. Coffman and I. Mitrani. A characterization of waiting time performance realizable by single server queues. Operations Research, 20:810--821, 1980.
• 7: Edith Cohen , Amos Fiat , Haim Kaplan, Efficient sequences of trials, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 8: Amol Deshpande , Carlos Guestrin , Wei Hong , Samuel Madden, Exploiting Correlated Attributes in Acquisitional Query Processing, Proceedings of the 21st International Conference on Data Engineering (ICDE'05), p.143-154, April 05-08, 2005 [doi>10.1109/ICDE.2005.63]
• 9: 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
• 10: Uriel Feige , Prasad Tetali, Approximating Min Sum Set Cover, Algorithmica, v.40 n.4, p.219-234, September 2004 [doi>10.1007/s00453-004-1110-5]
• 11: L. Fleischer and K. Wayne. Fast and simple approximation schemes for generalized flow. Mathematical Programming, 91(2):215--238, 2002.
• 12: M. Garey. Optimal task scheduling with precedence constraints. Discrete Mathematics, 4:37--56, 1973.
• 13: E. Gelenbe and I. Mitrani. Analysis and synthesis of computer systems. Academic Press, 1980.
• 14: Roy Goldman , Jennifer Widom, WSQ/DSQ: a practical approach for combined querying of databases and the Web, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.285-296, May 15-18, 2000, Dallas, Texas, United States
• 15: Haim Kaplan , Eyal Kushilevitz , Yishay Mansour, Learning with attribute costs, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060644]
• 16: S. Karlin. Mathematical Methods and Theory in Games, Programming, and Economics. Dover, 2003.
• 17: Murali S. Kodialam, The Throughput of Sequential Testing, Proceedings of the 8th International IPCO Conference on Integer Programming and Combinatorial Optimization, p.280-292, June 13-15, 2001
• 18: Ravi Krishnamurthy , Haran Boral , Carlo Zaniolo, Optimization of Nonrecursive Queries, Proceedings of the 12th International Conference on Very Large Data Bases, p.128-137, August 25-28, 1986
• 19: K. Munagala, S. Babu, R. Motwani, and J. Widom. The pipelined set cover problem. In Tenth Intl. Conf. on Database Theory, pages 83--98, 2005.
• 20: M.A. Shayman and E. Fernandez-Gaucherand. Risk-sensitive decision-theoretic diagnosis. IEEE Transactions on Automatic Control, 46:1166--1171, 2001.
• 21: H. Simon and J. Kadane. Optimal problem-solving search: All-or-none solutions. Artificial Intelligence, 6:235--247, 1975.

INDEX TERMS

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

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.0 General
      F.2.1 Numerical Algorithms and Problems

General Terms:
Algorithms

Keywords:
flow algorithms, pipelined filter ordering, query optimization, selection ordering