Efficient and Extensible Algorithms for Multi Query Optimization
| dc.creator | Roy, Prasan | |
| dc.creator | Seshadri, S. | |
| dc.creator | Sudarshan, S. | |
| dc.creator | Bhobe, Siddhesh | |
| dc.date | 1999-10-25 | |
| dc.date.accessioned | 2026-07-07T03:24:25Z | |
| dc.date.available | 2026-07-07T03:24:25Z | |
| dc.description | 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. | |
| dc.identifier | https://arxiv.org/abs/cs/9910021 | |
| dc.identifier | http://arxiv.org/abs/cs/9910021 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/33320 | |
| dc.subject | Databases | |
| dc.subject | H.2.4;H.2.7 | |
| dc.title | Efficient and Extensible Algorithms for Multi Query Optimization | |
| dc.type | text |