Re: left-deep plans?

On Wed, Feb 23, 2005 at 10:02:22AM +1100, Neil Conway wrote:
> Kenneth Marshall wrote:
> >GEQO is an attempt to provide a near-optimal join order without using
> >an exhaustive search. "An exhaustive, deterministic search of a subset
> >of the search space" has a non-zero probability of finding only a local
> >minimum in execution time.
>
> I'm not sure what you mean. By an "exhaustive, deterministic search of a
> subset of the search space", I was referring to using the normal
> planner, but restricting the search space to only left-deep plans. Since
> GEQO will also only consider left-deep plans, ISTM there is no issue of
> "local minima" that does not apply to an equal degree to GEQO itself.

That is just a direct quote from your text. That is true, that this will
have the same "local minima" problem as GEQO.

>
> >Since purely random selection, with learning, works so well, it may be
> >worth developing a new random join-order optimization algorithm
>
> Yeah, I agree. I've read a few papers on randomized algorithms for join
> order selection, but none of them really seemed to be clear winners. Do
> you have a reference for the paper you read?
>

Here is one article that I found relevent in my literature search to find
research on join-order optimization. It is appealing in that it should be
fairly straightforward to implement and would allow us to consider bushy
plans:

http://www.cwi.nl/htbin/ins1/publications?request=pdfgz&key=WaPe:BNCOD:00

Ken