BUG #19787: "could not find pathkey item to sort" for Gather Merge over a merge join below reordered LEFT JOINs

The following bug has been logged on the website:

Bug reference: 19787
Logged by: Alperen Keles
Email address: alpkeles99(at)gmail(dot)com
PostgreSQL version: 18.6
Operating system: Ubuntu 24.04 x86_64
Description:

Hello,

This query fails at plan time on empty tables, once a few cost settings
make a parallel merge join attractive:

CREATE TABLE a(x int);
CREATE TABLE b(x int);
CREATE TABLE c(x int);
CREATE TABLE d(x int);
VACUUM b, d;
SET cpu_tuple_cost = 1;
SET parallel_tuple_cost = 0;
SET min_parallel_table_scan_size = 0;
SELECT 1 FROM a LEFT JOIN b ON true LEFT JOIN c ON c.x = b.x
LEFT JOIN d ON d.x = c.x;
ERROR: could not find pathkey item to sort

EXPLAIN fails with the same error. With SELECT c.x instead of SELECT 1,
or with enable_mergejoin, enable_gathermerge or enable_sort off, or
with join_collapse_limit = 1, the query returns no rows as expected.

Reproduced on master a261fc2b722, 19rc1 (REL_19_STABLE 1212d5d33b1)
and 18.6 (REL_18_STABLE dfbc1507cdb), with --enable-cassert, on
Ubuntu 24.04 x86_64. 14.24 (REL_14_STABLE 14904052e65) plans it with
hash joins and returns no rows. Bisecting on master gives 9df8f903eb6
("Fix some issues with improper placement of outer join clauses") as
the first commit that fails; its parent 867be9c0738 returns no rows.

From a debugger, the chosen path is

Nested Loop Left Join
-> a
-> Material
-> Gather Merge (pathkey c.x)
-> Merge Left Join (d.x = c.x)
-> Sort (c.x) -> b LEFT JOIN c
-> Sort (d.x) -> d

i.e. the joins are reordered to a LEFT JOIN (b LEFT JOIN c LEFT JOIN d).
Nothing above the {b,c,d} join needs c.x, so that joinrel's reltarget
is empty, but the partial merge join path keeps its outer ordering c.x
as pathkeys, and generate_gather_paths() puts a Gather Merge with those
pathkeys on it. In create_gather_merge_plan(), prepare_sort_from_pathkeys()
gets the merge join's empty tlist and cannot find or compute c.x.

As far as I can tell, c.x survives as a pathkey because of the clone
clauses for the commuted outer joins. The {b,c,d} joinrel's joininfo
still holds the is_clone copies "c.x = b.x(nulled by the a/b join)"
and "d.x = c.x(nulled by the b/c join)". Since 9df8f903eb6 the
commuted joinrel does not include those outer joins' relids yet, so
these clones are not considered applied, although their non-clone
versions were already applied inside it. pathkeys_useful_for_merging()
finds the first clone in rel->joininfo, whose left_ec is the c.x
pathkey's EC, so truncate_useless_pathkeys() keeps c.x, although no
later join can use that clause.

Found with a query fuzzer.

Regards,
Alperen Keles