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.