Fast, Randomized Join-Order Selection - Why Use Transformations?

We study the effectiveness of probabilistic selection of join-query evaluation plans, without reliance on tree transformation rules. Instead, each candidate plan is chosen uniformly at random from the space of valid evaluation orders. This leads to a transformation-free strategy where a sequence of random plans is generated and the plans are compared on their estimated costs. The success of this strategy depends on the ratio of ``good'' evaluation plans in the space of alternatives, the efficient generation of random candidates, and an accurate estimation of their cost. To avoid a biased exploration of the space, we solved the open problem of efficiently generating random, uniformly-distributed evaluation orders, for queries with acyclic graphs. This benefits any optimization or sampling scheme in which a random choice of (initial) query plans is required. A direct comparison with iterative improvement and simulated annealing, using a proven cost-evaluator, shows that our transformation-free strategy converges faster and yields solutions of comparable cost.