Abstract
The query optimization problem faced by everyday query optimizers gets more and more complex with the ever increasing complexity of user queries. The NP-hard join ordering problem is a central problem that an optimizer must deal with in order to produce optimal plans. Fairly small queries, involving less than 10 relations, can be handled by existing algorithms such as the classic Dynamic Programming optimization algorithm. However, for complex queries or queries involving multiple execution sites in a distributed setting the optimization problem becomes much more challenging and the existing optimization algorithms find it difficult to cope with the complexity.
