Presently the planner considers left-deep, right-deep, and bushy plans
(i.e. it will consider plans in which the outer operand of a join is a
join, the inner operand is a join, or both operands are joins). It is a
fairly standard heuristic in the literature to restrict the search to
left-deep plans, on the grounds that this significantly reduces the set
of plans to consider, and the more efficient plans are _usually_ found
in the set of left-deep plans (since we can do pipelining more
efficiently). Has there been any thought about applying this optimization?

(I doubt it would be wise to unconditionally restrict the search to
left-deep plans, but there may be situations in which applying this
heuristic would allow the regular planner to be used instead of GEQO.
Perhaps a GUC variable?)

-Neil

---------------------------(end of broadcast)---------------------------
TIP 1: subscribe and unsubscribe commands go to majordomo@postgresql.org

Neil Conway <neilc@samurai.com> writes:
> Presently the planner considers left-deep, right-deep, and bushy plans
> (i.e. it will consider plans in which the outer operand of a join is a
> join, the inner operand is a join, or both operands are joins). It is a
> fairly standard heuristic in the literature to restrict the search to
> left-deep plans, on the grounds that this significantly reduces the set
> of plans to consider, and the more efficient plans are _usually_ found
> in the set of left-deep plans (since we can do pipelining more
> efficiently). Has there been any thought about applying this optimization?

Yes, and it's been rejected. The notion is obviously bogus; it amounts
to assuming that every database is a star schema with only one core table.

The left-deep vs right-deep case is more tricky, since on its face
that's redundant; but I believe we have things fixed so that we aren't
considering redundant plans wholesale. (Note the elimination of
match_unsorted_inner in joinpath.c.)

Once we get into GEQO territory, we are using the left-deep-only
heuristic because that's the only kind of plan GEQO can construct.
But at that point you've already given up any notion of exhaustive
search.

regards, tom lane

---------------------------(end of broadcast)---------------------------
TIP 9: the planner will ignore your desire to choose an index scan if your
joining column's datatypes do not match

Tom Lane wrote:
> Yes, and it's been rejected. The notion is obviously bogus; it amounts
> to assuming that every database is a star schema with only one core table.

Interesting; yes, I suppose that's true.

> Once we get into GEQO territory, we are using the left-deep-only
> heuristic because that's the only kind of plan GEQO can construct.
> But at that point you've already given up any notion of exhaustive
> search.

I think most applications would prefer an exhaustive, deterministic
search of a subset of the search space over a non-exhaustive,
non-deterministic search of the same subset, given approximately the
same performance. In other words, if confining the search to left-deep
plans allows people to use the normal planner in situations where they
would normally be forced to use GEQO to get acceptable performance, I
think that would be a win.

Speaking of which, why does GEQO restrict its search to left-deep plans
only?

-Neil

---------------------------(end of broadcast)---------------------------
TIP 8: explain analyze is your friend

Neil Conway <neilc@samurai.com> writes:
> Tom Lane wrote:
>> Once we get into GEQO territory, we are using the left-deep-only
>> heuristic because that's the only kind of plan GEQO can construct.

> I think most applications would prefer an exhaustive, deterministic
> search of a subset of the search space over a non-exhaustive,
> non-deterministic search of the same subset, given approximately the
> same performance.

I am not by any means standing up to defend GEQO as being the best
way to do partial searches ;-). Just saying that in the regime where
we can hope to do complete searches, we shouldn't exclude bushy plans.

> Speaking of which, why does GEQO restrict its search to left-deep plans
> only?

Well, because it's really a traveling-salesman algorithm, and it models
the "find a good join tree" problem as "find a good tour". I've
commented before that I don't believe this is a particularly good model
--- intuitively it doesn't seem that the cost functions have the same
structure. But I've not had time to look for a better heuristic
algorithm. Just one of the many things on the TODO list ...

regards, tom lane

---------------------------(end of broadcast)---------------------------
TIP 7: don't forget to increase your free space map settings

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.

> 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?

-Neil

---------------------------(end of broadcast)---------------------------
TIP 1: subscribe and unsubscribe commands go to majordomo@postgresql.org

On Tue, Feb 22, 2005 at 05:40:40PM +1100, Neil Conway wrote:
> Tom Lane wrote:
> >Yes, and it's been rejected. The notion is obviously bogus; it amounts
> >to assuming that every database is a star schema with only one core table.
>
> Interesting; yes, I suppose that's true.
>
> >Once we get into GEQO territory, we are using the left-deep-only
> >heuristic because that's the only kind of plan GEQO can construct.
> >But at that point you've already given up any notion of exhaustive
> >search.
>
> I think most applications would prefer an exhaustive, deterministic
> search of a subset of the search space over a non-exhaustive,
> non-deterministic search of the same subset, given approximately the
> same performance. In other words, if confining the search to left-deep
> plans allows people to use the normal planner in situations where they
> would normally be forced to use GEQO to get acceptable performance, I
> think that would be a win.
>

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. Most users really are only concerned with
final execution time and if the "subset" is mis-chosen the resulting
exhaustive search would completely and possibly disasterously miss the
optimal execution time.

In a paper on join-order optimization that I read recently, it was shown
that non-uniform sampling, with the application of cost-based pruning of
the search space, provided good results with quick convergence to within
a delta of the optimum plan. This has the nice property that you can
balence result quality with the amount of time spent optimizing the join
order. The piece missing from the current GECO algorithm is to ensure
that once the cost of a join plan is larger (or a piece of a plan), never
visit that plan again. The memory/learning piece is what provided the
ability to explore much more of the desirable (low execution time) search
space.

Since purely random selection, with learning, works so well, it may be
worth developing a new random join-order optimization algorithm, particularly
since most of the "genetic" features of the GECO we are not using.

Ken

---------------------------(end of broadcast)---------------------------
TIP 5: Have you checked our extensive FAQ?

http://www.postgresql.org/docs/faq

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/publica...=WaPe:BNCOD:00

Ken

---------------------------(end of broadcast)---------------------------
TIP 2: you can get off all lists at once with the unregister command
(send "unregister YourEmailAddressHere" to majordomo@postgresql.org)