BUG #19805: Wrong results: self-join elimination drops an ORDER BY sort key with GROUPING SETS / CUBE / ROLLUP

The following bug has been logged on the website:

Bug reference: 19805
Logged by: chunling qin
Email address: 303677365(at)qq(dot)com
PostgreSQL version: 18.6
Operating system: Linux x86_64
Description:

Self-join elimination (SJE, new in v18) rewrites the Vars of the removed
relation to the kept one. When both sides of a grouping-sets query are
joined on a unique key, the two output columns end up as the *same* Var, so
their two ORDER BY keys land in the same equivalence class and the second
key is discarded as redundant (pathkey_is_redundant()).

That reasoning assumes EC members are always equal. After grouping sets it
is false: grouping sets emit NULLs per set, so two columns that share an
expression do NOT share values. Losing the second key leaves rows that tie
on the first key in an arbitrary order, which violates ORDER BY.

Note this is not a "tie is unspecified" case: in the example below the tied
rows are distinguishable on the remaining sort key ((NULL,3) vs (NULL,8)),
so the required order is fully determined.

Reproduction (self-contained, works on the official postgres:latest Docker
image):

docker run --rm -d --name pgv -e POSTGRES_PASSWORD=x -e POSTGRES_USER=tbase
-p 15440:5432 postgres:latest
docker exec -i pgv psql -U tbase -d postgres <<'SQL'
CREATE TABLE m2 (a int UNIQUE);
INSERT INTO m2 VALUES (1), (2);
ANALYZE m2;

SET enable_self_join_elimination = on; -- default
SELECT s1.a, s2.a FROM m2 s1 JOIN m2 s2 ON s1.a = s2.a
GROUP BY CUBE (s1.a, s2.a) ORDER BY 1, 2;

SET enable_self_join_elimination = off;
SELECT s1.a, s2.a FROM m2 s1 JOIN m2 s2 ON s1.a = s2.a
GROUP BY CUBE (s1.a, s2.a) ORDER BY 1, 2;
SQL

Actual output (N = NULL):

SJE on : (1,N) (1,1) (2,2) (2,N) (N,N) (N,1) (N,2)
SJE off: (1,1) (1,N) (2,2) (2,N) (N,1) (N,2) (N,N)

Expected: the SJE-off ordering. With ORDER BY 1, 2 (ASC, NULLS LAST) the
pair (1,1) must precede (1,N), and (N,N) must come after (N,1) and (N,2).
The SJE-on output inverts both.

Plans (EXPLAIN (COSTS OFF, VERBOSE)):

SJE on : Sort Key: s2.a Output: s2.a, s2.a <- one key, both
columns are the same Var
SJE off: Sort Key: s1.a, s2.a Output: s1.a, s2.a

With 10 rows the effect is unambiguous: the group whose first column is NULL
comes out as "3 8 10 9 7 1 5 4 2 6" with SJE on, and "1 2 3 4 5 6 7 8 9 10"
with SJE off. The sequence is deterministic - it is identical across
sessions and across all three builds tested.

Impact is not limited to cosmetic ordering: with LIMIT 1 OFFSET 4 on the
2-row example, SJE on returns (NULL,NULL) and SJE off returns (NULL,1) -
different rows, so paging and any INSERT ... SELECT ... ORDER BY ... LIMIT
can materialise wrong data.

Source: remove_self_join_rel() in analyzejoins.c rewrites root->parse via
ChangeVarNodes() without awareness of grouping-set semantics; the key is
then dropped by make_pathkeys_for_sortclauses() -> pathkey_is_redundant() in
pathkeys.c.

Related: the same underlying hazard was reported in 2021 ("Sort keys are
omitted incorrectly after grouping sets", Richard Guo, pgsql-hackers), where
the hand-written form

SELECT a, b FROM foo WHERE a = b GROUP BY CUBE (a,b) ORDER BY a, b

lost a sort key. That form is fixed today - I verified it produces "Sort
Key: a, b" and correct output on all three builds tested (official 18.6
Docker image, REL_18_STABLE tip 606f3db, and master 20devel). The
grouping-sets special case in pathkeys.c does not appear to cover the shape
SJE produces, so v18 can silently transform a safe query into the unsafe
one.

Not verified: branches 17 and below (SJE does not exist there), and whether
MERGE / INSERT ... SELECT persist wrong rows in practice (the ordering
difference is confirmed; the data-persistence variant I did not execute).