BUG #19800: 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: 19800
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.

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

Reproduction (N = NULL):

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;

Actual output:
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 - 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. 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.

Tested on:
- PostgreSQL 18.6, official Docker image postgres:latest (Debian
18.6-1.pgdg13+2)
- PostgreSQL 18.6, build of REL_18_STABLE tip (commit 606f3db)
- PostgreSQL 20devel, build of master
All three reproduce. enable_hashagg=off does not change the result.