Truly Adaptive Optimization: the Basic Ideas

A new approach to query optimization, truly adaptive optimization (TAO), is presented. TAO is a general optimization strategy and is composed of three elements: 1. a fast solution space search algorithm, derived from A*, which uses an informed heuristic lookahead; 2. a relaxation technique which allows to specify a tolerance on the quality of the resulting query execution plan; 3. a paradigm to prove the suboptimality of search subspaces. Nonprocedural pruning rules can be used to describe specific problem knowledge, and can be easily added to the optimizer, as the specific problem becomes better understood. The main contribution over previous research is the use of relaxation techniques and that TAO provides a unifying framework for query optimization problems, which models a complexity continuum going from fast heuristic searches to exponential optimal searches while guaranteeing a selected plan quality. In addition, problem knowledge can be exploited to speed the search up. As a preliminary example, the method is applied to query optimization for databases distributed over a broadcast network. Simulation results are reported.