Re: join ordering via Simulated Annealing

=?UTF-8?B?SmFuIFVyYmHFhHNraQ==?= <wulczer(at)wulczer(dot)org> writes:
> I've been playing with using a Simulated Annealing-type algorithm for
> determinig join ordering for relations.

Cool.

> The code I have now creates the initial plan by doing something similar
> to what gimme_tree does in GEQO, but without any kind of heuristic to
> try to favour joins with join restrictions (the idea is that it doesn't
> matter, since we only want to get *any* plan and we only do it once),
> but ideally it would be somehow chosen randonly from the space of all
> possible join orderings.

FWIW, I think that's probably a bad idea. In a query where there are a
lot of join order constraints, you can waste enormous amounts of time
trying to find a join order that is even legal at all, let alone any
good. Pure randomness is not as nice as it seems. You might want to
study the CVS history of GEQO a bit and try to avoid falling into some
of the traps we already fell into with that ;-)

> o) each swap needs a full recalcualtion of the whole solution
> (geqo_eval does that, for instance), maybe it's possible to leave the
> subtrees of swapped nodes intact and only recalculate the nodes above
> the two swapped nodes?

Even if you could make this work, it'd probably be an infeasible
space-for-time tradeoff, because you'd have to keep around all the Path
infrastructure of the lower nodes in order to not start from scratch.
As we were forcibly reminded a few months ago, one of the important
properties of the GEQO code is to be able to do planning with a limited
amount of memory even for very large relation sets.

regards, tom lane