The Use of Randomized Search Strategies for Complex Parallel Relational Query Optimization

This article proposes a complete parallel relational optimization methodology based on randomized search strategies from the theoretical basics to the experimental validation. This methodology is based on a survey-like analysis of related search techniques. We defend why randomized search strategies are an effective technique, both in output quality and optimization effort, for complex parallel query optimization. The traditional techniques are tuned and parallized versions are developed. Furthermore we describe how the transformation rules of the search strategy could interact with the resource allocation and present an allocation model. A series of experiments performed on a 100 relation database with 18 randomly chosen queries demonstrate that an excellent tradeoff between optimization time and optimization quality can be achieved