Computer Science – Databases
Scientific paper
1999-10-25
Computer Science
Databases
Scientific paper
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.
Bhobe Siddhesh
Roy Prasan
Seshadri Sridhar
Sudarshan S.
No associations
LandOfFree
Efficient and Extensible Algorithms for Multi Query Optimization does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Efficient and Extensible Algorithms for Multi Query Optimization, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Efficient and Extensible Algorithms for Multi Query Optimization will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-2427