Re: MergeAppend could consider sorting cheapest child path

On 07.09.2025 14:26, Alexander Korotkov wrote:
> On Fri, Sep 5, 2025 at 11:45 AM Andrei Lepikhov <lepihov@gmail.com> wrote:
>> On 1/9/2025 22:26, Alexander Korotkov wrote:
>>> On Thu, Jul 31, 2025 at 5:20 PM Andrei Lepikhov <lepihov@gmail.com> wrote:
>>>> See this minor correction in the attachment. postgres_fdw tests are
>>>> stable now.
>>> I have another idea.  What if we allow MergeAppend paths only when at
>>> least one subpath is preordered.  This trick also allow us to exclude
>>> MergeAppend(Sort) dominating Sort(Append).  I see the regression tests
>>> changes now have much less volume and looks more reasonable.  What do
>>> you think?
>> I believe a slight mistake has been made with the total_has_ordered /
>> startup_has_ordered parameters, which has caused unnecessary test
>> changes in inherit.out (See updated patch in the attachment). Although
>> not the best test in general (it depends on the autovacuum), it
>> highlighted the case where a startup-optimal strategy is necessary, even
>> when a fractional-optimal path is available, which may lead to continue
>> of the discussion [1].>
>>> Also, do you think get_cheapest_fractional_path_for_pathkeys_ext() and
>>> get_cheapest_path_for_pathkeys_ext() should consider incremental sort?
>>>    The revised patch teaches them to do so.
>> Following 55a780e9476 [2] it should be considered, of course.
> Great, thank you for catching this.  The diff of costs is attached.  I
> see the costs now are better or within the fuzz factor.
>
Hi! I looked at regression test changes but one of them confused me.

Example where the plan shape changed:

EXPLAIN (COSTS OFF)
SELECT t1.a, t2.b
FROM (SELECT * FROM prt1 WHERE a < 450) t1
LEFT JOIN (SELECT * FROM prt2 WHERE b > 250) t2
   ON t1.a = t2.b
WHERE t1.b = 0
ORDER BY t1.a, t2.b;

-- before
                         QUERY PLAN
-----------------------------------------------------------
  Incremental Sort
    Sort Key: prt1.a, prt2.b
    Presorted Key: prt1.a
    ->  Merge Left Join
          Merge Cond: (prt1.a = prt2.b)
          ->  Sort
                Sort Key: prt1.a
                ->  Append
                      ->  Seq Scan on prt1_p1 prt1_1
                            Filter: ((a < 450) AND (b = 0))
                      ->  Seq Scan on prt1_p2 prt1_2
                            Filter: ((a < 450) AND (b = 0))
          ->  Sort
                Sort Key: prt2.b
                ->  Append
                      ->  Seq Scan on prt2_p2 prt2_1
                            Filter: (b > 250)
                      ->  Seq Scan on prt2_p3 prt2_2
                            Filter: (b > 250)
(19 rows)

-- now
                            QUERY PLAN
-----------------------------------------------------------------
  Sort
    Sort Key: prt1.a, prt2.b
    ->  Merge Right Join
          Merge Cond: (prt2.b = prt1.a)
          ->  Append
                ->  Sort
                      Sort Key: prt2_1.b
                      ->  Seq Scan on prt2_p2 prt2_1
                            Filter: (b > 250)
                ->  Sort
                      Sort Key: prt2_2.b
                      ->  Seq Scan on prt2_p3 prt2_2
                            Filter: (b > 250)
          ->  Materialize
                ->  Append
                      ->  Sort
                            Sort Key: prt1_1.a
                            ->  Seq Scan on prt1_p1 prt1_1
                                  Filter: ((a < 450) AND (b = 0))
                      ->  Sort
                            Sort Key: prt1_2.a
                            ->  Seq Scan on prt1_p2 prt1_2
                                  Filter: ((a < 450) AND (b = 0))
(23 rows)

Previously we had incremental sort on (t1.a, t2.b) with prt1.a already
presorted; now we sort both t1.a and t2.b after a merge right join. It
looks inefficiently or I missed something?

Other tests looked fine for me.