Design and experimental evaluation of a multiple query optimizer
Ahmet Coşar · 1996
In certain database applications such as deductive databases, batch query processing, and recursive query processing etc., usually a single query gets transformed into a set of closely related database queries. Also, great benefits can be obtained by executing a group of related queries all together in a single unified multi-plan instead of executing each query separately. In order to achieve this, Multiple Query Optimization (MQO) identifies common task(s) (e.g. common subexpressions, joins, etc.) among a set of query plans and creates a single unified plan (multi-plan) which can be executed to obtain the required outputs for all queries at once. In this thesis we develop new heuristic functions for speeding the alternative plan selection for a multi-plan such that the resulting multi-plan is optimal. We also develop approximate algorithms and compare their performance with that of optimal algorithms in terms of both the quality of the multi-plans and the optimization time. Finally, we develop algorithms for automatically generating promising alternative plans to augment a single query optimizer with MQO capabilities. In order to evaluate the benefits obtainable from MQO we randomly generate query sets which are represented as Relational Algebra (RA) trees. These RA trees are transformed so as to maximize the sharings between queries in a given query set and alternative plans are obtained. Then, we compare the quality (i.e. execution cost) of the multi-plans obtained from these generated alternative plans with that of original RA trees. As the search space for alternative plans is large we develop and experimentally evaluate heuristic algorithms for generating alternative plans for a given query set.