Algorithms for distributional and adversarial pipelined filter ordering problems

ABSTRACT

Pipelined filter ordering is a central problem in database query optimization. The problem is to determine the optimal order in which to apply a given set of commutative filters (predicates) to a set of elements (the tuples of a relation), so as to find, as efficiently as possible, the tuples that satisfy all of the filters. Optimization of pipelined filter ordering has recently received renewed attention in the context of environments such as the Web, continuous high-speed data streams, and sensor networks. Pipelined filter ordering problems are also studied in areas such as fault detection and machine learning under names such as learning with attribute costs, minimum-sum set cover, and satisficing search. 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 present two related algorithms for solving (1), both running in time O(n²), which improve on the O(n3 log n) algorithm of Kodialam. We use techniques from our algorithms for (1) to obtain an algorithm for (2).

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 , T. Leighton, A simple local-control approximation algorithm for multicommodity flow, Proceedings of the 1993 IEEE 34th Annual Foundations of Computer Science, p.459-468, November 03-05, 1993 [doi>10.1109/SFCS.1993.366841]
• 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: Burge, J., Mungala, K., and Srivastava, U. 2005. Ordering pipelined query operators with precedence constraints. Tech. rep. 2005-40, Stanford University.
• 6: 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
• 7: Coffman, E., and Mitrani, I. 1980. A characterization of waiting time performance realizable by single server queues. Oper. Res. 20, 810--821.
• 8: 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
• 9: Anne Condon , Amol Deshpande , Lisa Hellerstein , Ning Wu, Flow algorithms for two pipelined filter ordering problems, Proceedings of the twenty-fifth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 26-28, 2006, Chicago, IL, USA [doi>10.1145/1142351.1142379]
• 10: Amol Deshpande , Carlos Guestrin , Wei Hong , Samuel Madden, Exploiting Correlated Attributes in Acquisitional Query Processing, Proceedings of the 21st International Conference on Data Engineering, p.143-154, April 05-08, 2005 [doi>10.1109/ICDE.2005.63]
• 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: 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]
• 13: Fleischer, L., and Wayne, K. 2002. Fast and simple approximation schemes for generalized flow. Math. Program. 91, 2, 215--238.
• 14: Garey, M. 1973. Optimal task scheduling with precedence constraints. Discrete Math. 4, 37--56.
• 15: Gelenbe, E., and Mitrani, I. 1980. Analysis and Synthesis of Computer Systems. Academic Press.
• 16: 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
• 17: Grigoriadis, M., and Khachiyan, L. 1994. Fast approximation schemes for convex programs with many blocks and coupling constraints. SIAM J. Optimiz. 4, 86--107.
• 18: Toshihide Ibaraki , Tiko Kameda, On the optimal nesting order for computing N-relational joins, ACM Transactions on Database Systems (TODS), v.9 n.3, p.482-502, Sept. 1984 [doi>10.1145/1270.1498]
• 19: 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]
• 20: 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
• 21: 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
• 22: Munagala, K., Babu, S., Motwani, R., and Widom, J. 2005. The pipelined set cover problem. In Proceedings of the 10th International Conference on Database Theory (ICDT), vol. 3363. Lecture Notes in Computer Science, Springer, 83--98.
• 23: Patrick O'Neil , Goetz Graefe, Multi-table joins through bitmapped join indices, ACM SIGMOD Record, v.24 n.3, p.8-11, Sept. 1995 [doi>10.1145/211990.212001]
• 24: Serge A. Plotkin , David B. Shmoys , Éva Tardos, Fast approximation algorithms for fractional packing and covering problems, Mathematics of Operations Research, v.20 n.2, p.257-301, May 1995 [doi>10.1287/moor.20.2.257]
• 25: Shayman, M., and Fernandez-Gaucherand, E. 2001. Risk-Sensitive decision-theoretic diagnosis. IEEE Trans. Autom. Control 46, 1166--1171.
• 26: Simon, H., and Kadane, J. 1975. Optimal problem-solving search: All-or-None solutions. Artif. Intell. 6, 235--247.
• 27: Utkarsh Srivastava , Kamesh Munagala , Jennifer Widom , Rajeev Motwani, Query optimization over web services, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
• 28: Andreas Weininger, Efficient execution of joins in a star schema, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564754]

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.2 Nonnumerical Algorithms and Problems

General Terms:
Algorithms

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