Efficient and Extensible Algorithms for Multi Query Optimization
<|reference_start|>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-expressions, either within a single query, or across multiple such queries run as a batch. Multi-query optimization aims at exploiting common sub-expressions to reduce evaluation cost. Multi-query optimization has hither-to been viewed 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-based heuristic algorithms: Volcano-SH and Volcano-RU, which are based on simple 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 optimizers. We present a performance study comparing the algorithms, using workloads 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.<|reference_end|>
@article{roy1999efficient,
    title={Efficient and Extensible Algorithms for Multi Query Optimization},
    author={Prasan Roy, S. Seshadri, S. Sudarshan, Siddhesh Bhobe},
    journal={arXiv preprint arXiv:cs/9910021},
    year={1999},
    archivePrefix={arXiv},
    eprint={cs/9910021},
    primaryClass={cs.DB}
}