Factorizing complex predicates in queries to exploit indexes

ABSTRACT

Decision-support applications generate queries with complex predicates. We show how the factorization of complex query expressions exposes significant opportunities for exploiting available indexes. We also present a novel idea of relaxing predicates in a complex condition to create possibilities for factoring. Our algorithms are designed for easy integration with existing query optimizers and support multiple optimization levels, providing different trade-offs between plan complexity and optimization time.

REFERENCES

• 1: S. D. Bay. The UCI KDD archive {http://kdd.ics.uci.edu}. Irvine, CA: University of California, Department of Information and Computer Science, 1999.
• 2: C. Blake and C. Merz. UCI repository of machine learning databases, 1998.
• 3: R. K. Brayton, Factoring logic functions, IBM Journal of Research and Development, v.31 n.2, p.187-198, March 1987
• 4: R. K. Brayton, R. Rudell, A. Sangiovanni-Vincentelli, and A. Wang. MIS: A multiple-level logic optimization system. IEEE Transactions on CAD/ICAS, CAD-6, 1987.
• 5: Surajit Chaudhuri , Luis Gravano, Optimizing queries over multimedia repositories, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.91-102, June 04-06, 1996, Montreal, Quebec, Canada
• 6: Efficient Evaluation of Queries with Mining Predicates, Proceedings of the 18th International Conference on Data Engineering, p.529, February 26-March 01, 2002
• 7: 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]
• 8: Sophie Cluet , Claude Delobel, A general framework for the optimization of object-oriented queries, Proceedings of the 1992 ACM SIGMOD international conference on Management of data, p.383-392, June 02-05, 1992, San Diego, California, United States
• 9: Umeshwar Dayal, Of Nests and Trees: A Unified Approach to Processing Queries That Contain Nested Subqueries, Aggregates, and Quantifiers, Proceedings of the 13th International Conference on Very Large Data Bases, p.197-208, September 01-04, 1987
• 10: Goetz Graefe, Query evaluation techniques for large databases, ACM Computing Surveys (CSUR), v.25 n.2, p.73-169, June 1993 [doi>10.1145/152610.152611]
• 11: Michael Z. Hanani, An optimal evaluation of Boolean expressions in an online query system, Communications of the ACM, v.20 n.5, p.344-347, May 1977 [doi>10.1145/359581.359600]
• 12: 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
• 13: A. Kemper , G. Moerkotte , K. Peithner , M. Steinbrunn, Optimizing disjunctive queries with expensive predicates, Proceedings of the 1994 ACM SIGMOD international conference on Management of data, p.336-347, May 24-27, 1994, Minneapolis, Minnesota, United States
• 14: Alfons Kemper , Guido Moerkotte , Michael Steinbrunn, Optimizing Boolean Expressions in Object-Bases, Proceedings of the 18th International Conference on Very Large Data Bases, p.79-90, August 23-27, 1992
• 15: Harry Leslie , Rohit Jain , Dave Birdsall , Hedieh Yaghmai, Efficient Search of Multi-Dimensional B-Trees, Proceedings of the 21th International Conference on Very Large Data Bases, p.710-719, September 11-15, 1995
• 16: Martin C. Golumbic , Aviad Mintz, Factoring logic functions using graph partitioning, Proceedings of the 1999 IEEE/ACM international conference on Computer-aided design, p.195-199, November 07-11, 1999, San Jose, California, United States
• 17: C. Mohan , Donald J. Haderle , Yun Wang , Josephine M. Cheng, Single Table Access Using Multiple Indexes: Optimization, Execution, and Concurrency Control Techniques, Proceedings of the International Conference on Extending Database Technology: Advances in Database Technology, p.29-43, March 26-30, 1990
• 18: M. Muralikrishna , David J. DeWitt, Optimization of multiple-relation multiple-disjunct queries, Proceedings of the seventh ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.263-275, March 1988, Austin, Texas, United States [doi>10.1145/308386.308452]
• 19: R. Brayton, G. Hachtel, and A.L. Sangiovanni-Vincentelli. Multilevel logic synthesis. Proceedings of the IEEE, 78:264--300, 1990.
• 20: Lewis T. Reinwald , Richard M. Soland, Conversion of Limited-Entry Decision Tables to Optimal Computer Programs I: Minimum Average Processing Time, Journal of the ACM (JACM), v.13 n.3, p.339-358, July 1966 [doi>10.1145/321341.321343]
• 21: P. Griffiths Selinger , M. M. Astrahan , D. D. Chamberlin , R. A. Lorie , T. G. Price, Access path selection in a relational database management system, Proceedings of the 1979 ACM SIGMOD international conference on Management of data, May 30-June 01, 1979, Boston, Massachusetts [doi>10.1145/582095.582099]
• 22: Wolfgang Scheufele , Guido Moerkotte, Efficient Dynamic Programming Algorithms for Ordering Expensive Joins and Selections, Proceedings of the 6th International Conference on Extending Database Technology: Advances in Database Technology, p.201-215, March 23-27, 1998

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Query formulation

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing
  H.4 INFORMATION SYSTEMS APPLICATIONS
      H.4.2 Types of Systems
          Subjects: Decision support (e.g., MIS)

General Terms:
Algorithms, Design, Experimentation, Performance