pg.ddx.io  pgsql-bugs@postgresql.org mailing list archive  
help / color / mirror / Atom feed
From: PG Bug reporting form <noreply@postgresql.org>
To: pgsql-bugs@lists.postgresql.org
Cc: alpkeles99@gmail.com
Subject: BUG #19787: "could not find pathkey item to sort" for Gather Merge over a merge join below reordered LEFT JOINs
Date: Wed, 21 Oct 2026 22:37:01 +0000
Message-ID: <19787-d14d7f0f320f4495@postgresql.org> (raw)

The following bug has been logged on the website:

Bug reference:      19787
Logged by:          Alperen Keles
Email address:      alpkeles99@gmail.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








Message-ID: <19787-d14d7f0f320f4495@postgresql.org>
Permalink:  ../19787-d14d7f0f320f4495@postgresql.org/
Also on:    postgresql.org/message-id/19787-d14d7f0f320f4495@postgresql.org

 · 

reply

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Reply to all the recipients from your mail client; the link fills in
  the headers below: reply via email
  Some clients, webmail especially, drop In-Reply-To and References from
  a link, and the reply then starts a new thread: use the mbox below.

  To: pgsql-bugs@postgresql.org
  Cc: noreply@postgresql.org, alpkeles99@gmail.com
  Subject: Re: BUG #19787: "could not find pathkey item to sort" for Gather Merge over a merge join below reordered LEFT JOINs
  In-Reply-To: <19787-d14d7f0f320f4495@postgresql.org>
  References: <19787-d14d7f0f320f4495@postgresql.org>

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

This inbox is served by DDX for PostgreSQL; see mirroring instructions
for how to clone and mirror all data and code used for this inbox