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

... BTW, a question I think we're going to be forced to face up to
if we put a hook here is: is path cost/FOM comparison guaranteed
transitive? That is, if we find that path A dominates path B
and that path B dominates path C, is it guaranteed that comparing
A directly to C would conclude that A dominates C? add_path()
currently assumes that such transitivity holds, because if the
new_path dominates an old_path, we immediately discard old_path.
This is unjustifiable if new_path later gets rejected because it
is dominated by some later list element: we just lost a path and
replaced it with nothing. (Presumably, that can only happen if
neither existing list entry dominates the other.)

TBH, I'm not entirely convinced that transitivity is guaranteed
even today, now that we've got things like parallel safety in
the mix. For sure I doubt that we should assume that injecting
multiple hook functions each with their own agendas will result
in transitivity-preserving comparisons.

The most honest way to deal with that would be to convert
add_path to a two-pass implementation. In the first pass,
see if new_path is dominated by any existing list entry;
if so, stop immediately, discarding new_path. If we get
through that, we will add new_path, so now identify which
old paths it dominates and remove them. We could avoid
running path_compare() twice by retaining state from the
first pass to the second, but that's hardly free. On the
other hand, if you assume that most add_path calls end in
rejecting new_path, having a streamlined route to determining
that could be a win.

A possibly-cheaper answer could be to say that if new_path is
found to dominate any old_path, add it, even if it's later found
to be dominated. This'd only require some rejiggering of the way
the accept_new flag is tracked, I think. On the other hand this
way might be penny wise and pound foolish, if it ends in keeping
more paths than we really need.

Thoughts?

regards, tom lane