Comparison of Genetic and Tabu Search Algorithms in Multiquery Optimization in Advanced Database Systems

摘要

In several database applications sets of related queries are submitted together to be processed as a single unit. In all these cases the queries usually have some degree of overlap, i.e. may have common subqueries. Therefore a significant performance improvement can be obtained by optimizing and executing the entire group of queries as a whole, thus avoiding to duplicate the optimization and processing effort for common parts. This has suggested an approach, termed multiquery optimization (MQO) that has been proposed and studied by several authors. In this paper we suggest a new approach to multiple-query optimization based on Genetic and Tabu Search algorithms that ensure the tractability of the problem even for very large size of the queries. To analyze the performance of the algorithms, we have run a set of experiments that allow to understand how the different approaches are sensitive to the main workload parameters.