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

Hi Richard Guo
Is it necessary to add some comments here？

+ if (!innerpath->parallel_safe ||
+ !bms_is_empty(PATH_REQ_OUTER(innerpath)))
+ continue;
+
+ if (matched_path != NULL &&
+ compare_path_costs(matched_path, innerpath, TOTAL_COST) <= 0)
+ continue;
+
+ matched_path = innerpath;

Richard Guo <guofenglinux(at)gmail(dot)com> 于2024年1月10日周三 15:08写道：

>
> On Tue, Apr 11, 2023 at 11:43 AM Andy Fan <zhihui(dot)fan1213(at)gmail(dot)com>
> wrote:
>
>> On Tue, Apr 11, 2023 at 11:03 AM Richard Guo <guofenglinux(at)gmail(dot)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
>