Abstract: Now a day, it is very common to see that complex queries are being vastly used in the real time database applications. 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 often been viewed as impractical, since earlier algorithms were exhaustive, and explore a doubly exponential search space. This work demonstrates that multi-query optimization using heuristics is practical, and provides significant benefits. The cost-based heuristic algorithms: basic Volcano-SH and Volcano-RU, which are based on simple modifications to the Volcano search strategy. The algorithms are designed to be easily added to existing optimizers. The study shows that the presented algorithms provide significant benefits over traditional optimization, at a very acceptable overhead in optimization time.

Keywords: Heuristics, Volcano-SH and Volcano-RU.