Re: left-deep plans?

Neil Conway <neilc(at)samurai(dot)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