Efficient and extensible algorithms for multi query optimization

Complex queries are becoming commonplace, with the growing use of decision support systems. These complex queries often have a lot of common sub-expre ssions, either within a single query, or across multiple such queries run a s a batch. Multiquery optimization aims at exploiting common sub-expression s to reduce evaluation cost. Multi-query optimization has hither-to been vi ewed as impractical, since earlier algorithms were exhaustive, and explore a doubly exponential search space. In this paper we demonstrate that multi-query optimization using heuristics is practical, and provides significant benefits. We propose three cost-bas ed heuristic algorithms: Volcano-SH and Volcano-RU, which are based on simp le modifications to the Volcano search strategy and a greedy heuristic. Our greedy heuristic incorporates novel optimizations that improve efficiency greatly Our algorithms are designed to be easily added to existing optimize rs. We present a performance study comparing the algorithms, using workload s consisting of queries from the TPC-D benchmark. The study shows that our algorithms provide significant benefits over traditional optimization, at a very acceptable overhead in optimization time.