Re: Can we rely on the ordering of paths in pathlist?

On Tue, Apr 11, 2023 at 11:43 AM Andy Fan <zhihui.fan1213@gmail.com> wrote:

On Tue, Apr 11, 2023 at 11:03 AM Richard Guo <guofenglinux@gmail.com> wrote:

As the comment above add_path() says, 'The pathlist is kept sorted by
total_cost, with cheaper paths at the front.'  And it seems that
get_cheapest_parallel_safe_total_inner() relies on this ordering
(without being mentioned in the comments, which I think we should do).

I think the answer for ${subject} should be yes. Per the comments in
add_partial_path, we have

 * add_partial_path
 *
 *  As in add_path, the partial_pathlist is kept sorted with the cheapest
 *  total path in front.  This is depended on by multiple places, which
 *  just take the front entry as the cheapest path without searching.
 *

I'm not sure about this conclusion.  Surely we can depend on that the
partial_pathlist is kept sorted by total_cost ASC.  This is emphasized
in the comment of add_partial_path, and also leveraged in practice, such
as in many places we just use linitial(rel->partial_pathlist) as the
cheapest partial path.

But get_cheapest_parallel_safe_total_inner works on pathlist not
partial_pathlist.  And for pathlist, I'm not sure if it's a good
practice to depend on its ordering.  Because

1) the comment of add_path only mentions that add_path_precheck relies
on this ordering, but it does not mention that other functions also do;

2) other than add_path_precheck, I haven't observed any other functions
that rely on this ordering.  The only exception as far as I notice is
get_cheapest_parallel_safe_total_inner.

On the other hand, if we declare that we can rely on the pathlist being
sorted in ascending order by total_cost, we should update the comment
for add_path to highlight this aspect.  We should also include a comment
for get_cheapest_parallel_safe_total_inner to clarify why an early exit
is possible, similar to what we do for add_path_precheck.  Additionally,
in several places, we can optimize our code by taking advantage of this
fact and terminate the iteration through the pathlist early when looking
for the cheapest path of a certain kind.

Thanks
Richard