TY - GEN
T1 - Efficient exploitation of similar subexpressions for query processing
AU - Zhou, Jingren
AU - Larson, Per Ake
AU - Freytag, Johann Christoph
AU - Lehner, Wolfgang
PY - 2007
Y1 - 2007
N2 - 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.
AB - 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.
KW - Query optimization
KW - Query processing
KW - Similar subexpressions
UR - https://www.scopus.com/pages/publications/35548986654
U2 - 10.1145/1247480.1247540
DO - 10.1145/1247480.1247540
M3 - Article in proceeding
AN - SCOPUS:35548986654
SN - 1595936866
SN - 9781595936868
T3 - Proceedings of the ACM SIGMOD International Conference on Management of Data
SP - 533
EP - 544
BT - SIGMOD 2007
T2 - SIGMOD 2007: ACM SIGMOD International Conference on Management of Data
Y2 - 12 June 2007 through 14 June 2007
ER -