Re: Re: [COMMITTERS] pgsql: Rewrite GEQO's gimme_tree function so that it always finds a

Robert Haas <robertmhaas(at)gmail(dot)com> writes:
> I guess it's somewhat unsurprising that you can make the planner get
> into trouble with the above settings - we've been over that ground
> before. But it might be possibly interesting that such a simple
> schema is capable of generating so many paths.

It's not so much so-many-paths as so-many-join-relations that's killing
it. I put some instrumentation into join_search_one_level to count the
number of joinrels it was creating, and got this before getting bored:

join_search_one_level(2): 36 total, 36 by clause, 0 by clauseless, 0 bushy, 0 lastditch; paths/rel min 1 max 4 avg 3.06
join_search_one_level(3): 192 total, 384 by clause, 0 by clauseless, 0 bushy, 0 lastditch; paths/rel min 1 max 6 avg 4.70
join_search_one_level(4): 865 total, 2373 by clause, 0 by clauseless, 222 bushy, 0 lastditch; paths/rel min 1 max 8 avg 6.20
join_search_one_level(5): 3719 total, 12637 by clause, 0 by clauseless, 2239 bushy, 0 lastditch; paths/rel min 2 max 10 avg 7.81
join_search_one_level(6): 15387 total, 62373 by clause, 0 by clauseless, 14562 bushy, 0 lastditch; paths/rel min 3 max 12 avg 9.43
join_search_one_level(7): 59857 total, 283371 by clause, 0 by clauseless, 75771 bushy, 0 lastditch; paths/rel min 4 max 15 avg 10.92

So the number of paths per relation seems to be staying manageable, but
the number of join relations is going through the roof. On the other
hand, you've got 37 base relations here, and (37 choose 7) is 10295472,
so the planner is doing reasonably well at pruning the search tree.

Anyway, the immediate problem is that list_concat_unique_ptr is a bad
way of forming the lists of relations with a certain number of members.
It strikes me that that's easily fixable given that we know when we are
constructing a new RelOptInfo how many members it has. We could add the
rel to the right list at that time, instead of waiting until we get back
up to join_search_one_level. It implies making the joinrels[] array
part of the planner's global state instead of local to make_one_rel and
join_search_one_level, but for the sorts of list lengths we're seeing
here it seems clearly worthwhile. Maybe I'll go try that while I'm
sitting here digesting leftover turkey.

regards, tom lane