Re: How to retain lesser paths at add_path()?

2019年8月1日(木) 1:41 Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us>:
>
> Robert Haas <robertmhaas(at)gmail(dot)com> writes:
> > Yeah, but I have to admit that this whole design makes me kinda
> > uncomfortable. Every time somebody comes up with a new figure of
> > merit, it increases not only the number of paths retained but also the
> > cost of comparing two paths to possibly reject one of them. A few
> > years ago, you came up with the (good) idea of rejecting some join
> > paths before actually creating the paths, and I wonder if we ought to
> > try to go further with that somehow. Or maybe, as Peter Geoghegan, has
> > been saying, we ought to think about planning top-down with
> > memoization instead of bottom up (yeah, I know that's a huge change).
> > It just feels like the whole idea of a list of paths ordered by cost
> > breaks down when there are so many ways that a not-cheapest path can
> > still be worth keeping. Not sure exactly what would be better, though.
>
> Yeah, I agree that add_path is starting to feel creaky. I don't
> know what to do instead though. Changing to a top-down design
> sounds like it would solve some problems while introducing others
> (not to mention the amount of work and breakage involved).
>
Hmm... It looks the problem we ought to revise about path construction
is much larger than my expectation, and uncertain for me how much works
are needed.

Although it might be a workaround until fundamental reconstruction,
how about to have a margin of estimated cost to reject paths?
Current add_path() immediately rejects lesser paths if its cost is
even a little more expensive than the compared one. One the other hands,
a little cost difference may turn back final optimizer decision in some cases.
For example, if we retain lesser paths that have less then 10% expensive
cost than the current cheapest path in the same level, we may be able to
keep the number of lesser paths retained and still use simple cost comparison
for path survive decision.

I understand it is not an essential re-design of path-construction logic, and
may have limitation. However, amount of works are reasonable and no side-
effect. (current behavior = 0% threshold).
How about your opinions?

Best regards,
--
HeteroDB, Inc / The PG-Strom Project
KaiGai Kohei <kaigai(at)heterodb(dot)com>