Efficient exploitation of similar subexpressions for query processing

ABSTRACT

Complex queries often contain common or similar subexpressions, either within a single query or among multiple queries submitted as a batch. If so, query execution time can be improved by evaluating a common subexpression once and reusing the result in multiple places. However, current query optimizers do not recognize and exploit similar subexpressions, even within the same query.

We present an efficient, scalable, and principled solution to this long-standing optimization problem. We introduce a light-weight and effective mechanism to detect potential sharing opportunities among expressions. Candidate covering subexpressions are constructed and optimization is resumed to determine which, if any, such subexpressions to include in the final query plan. The chosen subexpression(s) are computed only once and the results are reused to answer other parts of queries. Our solution automatically applies to optimization of query batches, nested queries, and maintenance of multiple materialized views. It is the first comprehensive solution covering all aspects of the problem: detection, construction, and cost-based optimization. Experiments on Microsoft SQL Server show significant performance improvements with minimal overhead.

REFERENCES

• 1: Sanjay Agrawal , Surajit Chaudhuri , Vivek R. Narasayya, Automated Selection of Materialized Views and Indexes in SQL Databases, Proceedings of the 26th International Conference on Very Large Data Bases, p.496-505, September 10-14, 2000
• 2: David DeHaan , Per-Ake Larson , Jingren Zhou, Stacked indexed views in microsoft SQL server, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066179]
• 3: Sheldon Finkelstein, Common expression analysis in database applications, Proceedings of the 1982 ACM SIGMOD international conference on Management of data, June 02-04, 1982, Orlando, Florida [doi>10.1145/582353.582400]
• 4: Nathan Folkert , Abhinav Gupta , Andrew Witkowski , Sankar Subramanian , Srikanth Bellamkonda , Shrikanth Shankar , Tolga Bozkaya , Lei Sheng, Optimizing refresh of a set of materialized views, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 5: J. Goldstein and P. #&197;. Larson. Optimizing queries using materialized views: A practical, scalable solution. In Proceedings of SIGMOD Conference, 2001.
• 6: G. Graefe. The Cascades framework for query optimization. Data Engineering Bulletin, 18(3), 1995.
• 7: G. Graefe and W. J. McKenna. The Volcano optimizer generator: Extensibility and efficient search. In Proceeding of ICDE Conference, 1993.
• 8: W. Lehner, R. Cochrane, H. Pirahesh, and M. Zaharioudakis. fAST refresh using mass query optimization. In Proc. of ICDE Conference, 2001.
• 9: Hoshi Mistry , Prasan Roy , S. Sudarshan , Krithi Ramamritham, Materialized view selection and maintenance using multi-query optimization, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.307-318, May 21-24, 2001, Santa Barbara, California, United States
• 10: J. Park and A. Segev. Using common subexpressions to optimize multiple queries. In Proceedings of ICDE Conference, 1988.
• 11: J. Rao and K. A. Ross. Reusing invariants: A new strategy for correlated queries. In Proceedings of SIGMOD Conference, 1998.
• 12: K. A. Ross, D. Srivastava, and S. Sudarshan. Materialized view maintenance and integrity constraint checking: Trading space for time. In Proceedings of SIGMOD Conference, 1996.
• 13: P. Roy, S. Seshadri, S. Sudarshan, and S. Bhobe. Efficient and extensible algorithms for multi query optimization. In Proc. of SIGMOD Conference, 2000.
• 14: T. Sellis , S. Ghosh, On the Multiple-Query Optimization Problem, IEEE Transactions on Knowledge and Data Engineering, v.2 n.2, p.262-266, June 1990 [doi>10.1109/69.54724]
• 15: 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]
• 16: S. N. Subramanian and S. Venkataraman. Cost-based optimization of decision support queries using transient views. In Proceedings of SIGMOD Conference, 1998.

INDEX TERMS

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

General Terms:
Algorithms

Keywords:
query optimization, query processing, similar subexpressions