Re: Try a presorted outer path when referenced by an ORDER BY prefix

Hi,

While working on this patch, I continued to receive user complaints and had to
fix several corner cases: keeping parameterised paths away from the Sort, and
reconciling the PG19 changes to semi-join unique-ification with earlier
versions. Planning overhead has been an ongoing problem too. Each of these
problems came from building the sorted outer inside join planning, duplicating
what the pathlist machinery already does. That looked like a red flag that join
planning is the wrong place for it, so I went back to the literature and our code.

After reviewing the literature and the current code, I concluded that we can
simplify the approach.

Simmen et al. [1] call this technique "sort-ahead": a sort required by ORDER BY
(or GROUP BY/DISTINCT) is pushed down into the join tree, and the optimiser
keeps it only where it is cheaper. The main price the planner pays is in the
join search: subtrees with different orders cannot be pruned against each other,
so each extra sort-ahead order multiplies the work. In our case there is only
one order, the one defined by query_pathkeys, so the overhead is a constant factor.

The new version therefore adds the sorted path once per base relation. It then
competes in add_path() as an index path with the same ordering would: it
survives only if no cheaper path provides that order, and it may displace a more
expensive index path.

In the previous version, only the outer side of a NestLoop could use the
presorted path. Now merge joins, Merge Append and ordered Append over
partitions, unique-ification of a semi-join input, and sort-based grouping can
use it too. The regression tests whose plans changed illustrate multiple use cases.

A few extra benefits:

1. When a join multiplies rows, the Sort operator on the base relation handles
fewer and narrower tuples than it would after the join, so it is cheaper and
less likely to spill.
2. The sort is costed on a base relation, whose cardinality we estimate much
more reliably than that of a join result. So the cost of the sort itself,
including the risk of spilling to disk, is less exposed to join misestimation
than a Sort placed above the joins.
3. A Sort on a prefix below the join, completed by an Incremental Sort above it,
can be cheaper than a single full Sort at the top.

Note:
The sort key is now evaluated below a join more often, including on rows the
join later removes. This is existing behaviour of Gather Merge and Merge Append
(see [2]); the create_am test had to stop casting relname to regclass for that
reason.

The patch is attached. An addition to pg_plan_advice as well.

Thoughts?

[1] Simmen, Shekita, Malkemus. Fundamental Techniques for Order Optimization.
SIGMOD 1996.
https://cs.uwaterloo.ca/~gweddell/cs798/p57-simmen.pdf

[2] issues with eager aggregation
https://www.postgresql.org/message-id/6e3bb6d2-e981-49a4-9e7d-f18ee06e94a1%40gmail.com

-- AL