Re: MergeAppend could consider sorting cheapest child path

On 4/25/25 11:16, Alexander Pyhalov wrote:
> Andrei Lepikhov писал(а) 2025-04-24 16:01:
>> On 3/28/25 09:19, Alexander Pyhalov wrote:
>> In the attachment, see the patch written according to the idea. There
>> are I introduced two new routines:
>> get_cheapest_path_for_pathkeys_ext
>> get_cheapest_fractional_path_for_pathkeys_ext
>
> Hi. I'm a bit confused that
Thanks for the participation!

> get_cheapest_fractional_path_for_pathkeys_ext() looks only on sorting
> cheapest fractional path, and get_cheapest_path_for_pathkeys_ext() in
> STARTUP_COST case looks only on sorting cheapest_startup_path.
At first, at the moment, I don't understand why we calculate the
cheapest_startup path at all. In my opinion, after commit 6b94e7a [1,
2], the min-fractional path totally covers the case. I began this
discussion in [3] - maybe we need to scrutinise that issue beforehand.

Looking into the min-fractional-path + Sort, we propose a path for the
case when extracting minor part of tuples with sorting later is cheaper
than doing a massive job of non-selective index scan. You also may
imagine the case of a JOIN as a subpath: non-sorted, highly selective
parameterised NestLoop may be way more optimal than MergeJoin, which
fits the pathkeys.

> Usually, sorted cheapest_total_path will be cheaper than sorted
> fractional/startup path at least by startup cost (as after sorting it
> includes total_cost of input path). But we ignore this case when
> selecting cheapest_startup and cheapest_fractional subpaths. As result
> selected cheapest_startup and cheapest_fractional can be not cheapest
> for startup or selecting a fraction of rows.
I don't know what you mean by that. The cheapest_total_path is
considered when we chose optimal cheapest_total path. The same works for
the fractional path - get_cheapest_fractional_path gives us the most
optimal fractional path and probes cheapest_total_path too.
As above, not sure about min-startup case for now. I can imagine
MergeAppend over sophisticated subquery: non-sorted includes highly
parameterised JOINs and the alternative (with pathkeys) includes
HashJoin, drastically increasing startup cost. It is only a theory, of
course. So, lets discover how min-startup works.

At the end, when the sorted path already estimated, we each time compare
it with previously selected pathkeys-cheapest. So, if the sorted path is
worse, we end up with the original path and don't lose anything.

[1]
https://www.postgresql.org/message-id/e8f9ec90-546d-e948-acce-0525f3e92773%40enterprisedb.com
[2]
https://www.postgresql.org/message-id/1581042da8044e71ada2d6e3a51bf7bb%40index.de
[3]
https://www.postgresql.org/message-id/f0206ef2-6b5a-4d07-8770-cfa7cd30f685@gmail.com

--
regards, Andrei Lepikhov