Re: [HACKERS] Optimizer speed and GEQO (was: nested loops in joins)

>> Why are we maintaining this huge Path List for every RelOptInfo
>> structure if we only need the cheapest?

I think Bruce is onto something here... keep only the best-so-far
not everything ever generated.  That'd get rid of the O(N^2)
comparison behavior.

The only thing I can think of that we might possibly *need* the
whole list for is if it is used as a recursion stopper.
("Oh, I already investigated that alternative, no need to go down
that path again.")  It did not look to me like the optimizer does
such a thing, but I don't claim to understand the code.

It seems to me that the search space of possible paths is
well-structured and can be enumerated without generation of duplicates.
You've got a known set of tables involved in a query, a fixed set of
possible access methods for each table, and only so many ways to
combine them.  So the real question here is why does the optimizer
even need to check for duplicates --- should it not never generate
any to begin with?  The profiles I ran a few days ago show that indeed
most of the generated paths are not duplicates, but a small fraction
are duplicates.  Why is that?  I'd feel a lot closer to understanding
what's going on if we could explain where the duplicates come from.

"Thomas G. Lockhart" <lockhart@alumni.caltech.edu> writes:
> Perhaps having the entire list of plans available makes it easier to
> debug, especially when the stuff was in lisp (since in that environment
> it is easy to traverse and manipulate these lists interactively)...

The optimizer's Lisp heritage is pretty obvious, and in that culture
building a list of everything you're interested in is just The Way To
Do Things.  I doubt anyone realized that keeping the whole list would
turn out to be a performance bottleneck.
        regards, tom lane