Query Rewriting and Search in CROQUE

In query optimization, a given query will be transformed by rewrite rules into an equivalent execution plan that is cheaper than the straightforwardly assigned plan according to some cost model. Finding the cheapest of all equivalent execution plans is a challenge since the rewriting of complex queries on the basis of a large set of rewriting rules may potentially span a very large space of equivalent plans. Consequently, one has to either use search strategies to explore (parts of) the search space or some heuristics to prune this space thus making it efficiently traversable. This paper presents the use of search strategies in the CROQUE project. The adaptation of some common strategies led to the development of a simple but powerful heuristics which is demonstrated by examples executed in the CROQUE prototype. The proposed heuristics can support any random-based search strategy or can be used stand-alone. It may be integrated seamlessly into most of the present query optimizers without almost any effort.