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

Поиск
Список
Период
Сортировка
Искать

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

От:
PG Bug reporting form <noreply@postgresql.org>
Дата:
The following bug has been logged on the website:

Bug reference:      19800
Logged by:          chunling qin
Email address:      303677365@qq.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.




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

От:
Tender Wang <tndrwang@gmail.com>
Дата:
PG Bug reporting form  于2026年10月27日周二 17:04写道:
>
> 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.
>

Thanks for the report. I agree that this is a correctness issue.

The special property of grouping sets here is that two grouping items
whose underlying expressions are equal do not necessarily produce equal
output values. Each grouping set can independently replace a grouping
item with NULL.

Before SJE, s1.a and s2.a are distinct grouping items:

GROUP BY CUBE (s1.a, s2.a)

In particular, the expanded grouping sets include both (s1.a) and
(s2.a), so the output can contain (value, NULL) and (NULL, value).

SJE removes one side of the join and rewrites references to the removed
relation to reference the kept relation. After that rewrite, the two
grouping items appear to contain the same Var. Consequently, their
ORDER BY keys can be considered equivalent and the second one is
discarded as redundant. That reasoning would be valid for ordinary
rows, but it is not valid after grouping sets have independently
nullified the two grouping items.

The simplest fix I can think of for now is to skip SJE when the current
query level contains grouping sets. For example, in
remove_useless_self_joins():

if (!enable_self_join_elimination ||
    root->parse->groupingSets != NIL ||
    joinlist == NIL ||
    (list_length(joinlist) == 1 && !IsA(linitial(joinlist), List)))
    return joinlist;

This is conservative, since some queries containing grouping sets could
still safely use SJE. However, it avoids changing the grouping-item
identity, and the affected combination of grouping sets and a removable
self join seems uncommon. It may therefore be a reasonable quick fix,
particularly for back-patching to v18.

A more selective fix would need to determine whether the SJE
substitution makes two distinct grouping items identical while some
grouping set contains one but not the other. That seems considerably
more complicated, so I think the conservative check is a useful
starting point.


-- 
Thanks,
Tender Wang


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

От:
Narayanan Venkateswaran <narayananvpostgres@gmail.com>
Дата:
Вложения:
Hi,


On Tue, Oct 27, 2026 at 2:58 PM Tender Wang  wrote:
>
> PG Bug reporting form  于2026年10月27日周二 17:04写道:
> >
> > 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.
> >
>
> Thanks for the report. I agree that this is a correctness issue.
>
> The special property of grouping sets here is that two grouping items
> whose underlying expressions are equal do not necessarily produce equal
> output values. Each grouping set can independently replace a grouping
> item with NULL.
>
> Before SJE, s1.a and s2.a are distinct grouping items:
>
> GROUP BY CUBE (s1.a, s2.a)
>
> In particular, the expanded grouping sets include both (s1.a) and
> (s2.a), so the output can contain (value, NULL) and (NULL, value).
>
> SJE removes one side of the join and rewrites references to the removed
> relation to reference the kept relation. After that rewrite, the two
> grouping items appear to contain the same Var. Consequently, their
> ORDER BY keys can be considered equivalent and the second one is
> discarded as redundant. That reasoning would be valid for ordinary
> rows, but it is not valid after grouping sets have independently
> nullified the two grouping items.
>

Your analysis is spot on.

When self-join elimination (SJE) removes one side of a self-join on a
unique key,
references to the removed relation are rewritten via ChangeVarNodes().

When both sides of the self-join are referenced in grouping items
under grouping sets
(CUBE, ROLLUP, or GROUPING SETS), the rewrite causes two distinct grouping items
to become the exact same Var expression. Downstream in
make_pathkeys_for_sortclauses(),
pathkey_is_redundant() assumes members of the same Equivalence Class cannot
distinguish tied rows, and silently drops the second ORDER BY key,
resulting in arbitrary row
ordering.

> The simplest fix I can think of for now is to skip SJE when the current
> query level contains grouping sets. For example, in
> remove_useless_self_joins():
>
> if (!enable_self_join_elimination ||
>     root->parse->groupingSets != NIL ||
>     joinlist == NIL ||
>     (list_length(joinlist) == 1 && !IsA(linitial(joinlist), List)))
>     return joinlist;

I have implemented and tested the Approach you suggested above. I have
also added comprehensive
unit tests covering different permutations.
>
> This is conservative, since some queries containing grouping sets could
> still safely use SJE. However, it avoids changing the grouping-item
> identity, and the affected combination of grouping sets and a removable
> self join seems uncommon. It may therefore be a reasonable quick fix,
> particularly for back-patching to v18.

I agree with you that this approach looks conservative, although I
think this is the best approach due to
its simplicity and safety.

>
> A more selective fix would need to determine whether the SJE
> substitution makes two distinct grouping items identical while some
> grouping set contains one but not the other. That seems considerably
> more complicated, so I think the conservative check is a useful
> starting point.

I also want to explore the following two approaches and present a
comparative evaluation of alternatives

Approach 2 (Selective SJE check): Instead of skipping SJE query-wide,
check if the candidate relations
(toRemove / toKeep) appear in root->parse->groupClause. If neither
relation is referenced in the grouping
items, SJE can still safely eliminate the join.

Approach 3 (Pathkey level): Relaxing the redundancy assumption in
pathkey_is_redundant() when two
sort keys originate from distinct grouping items (tleSortGroupRef) in
the presence of grouping sets.

I need to deep-dive into whether the above two will have any broader
implications I am missing.

>
>
> --
> Thanks,
> Tender Wang
>

Thank you,
Narayanan

>

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

От:
Tender Wang <tndrwang@gmail.com>
Дата:
Вложения:
Narayanan Venkateswaran  于2026年10月29日周四 14:41写道:
>
> Approach 2 (Selective SJE check): Instead of skipping SJE query-wide,
> check if the candidate relations
> (toRemove / toKeep) appear in root->parse->groupClause. If neither
> relation is referenced in the grouping
> items, SJE can still safely eliminate the join.
>

Skipping SJE query-wide seems too strict; I'm also thinking about
approach 2. As in the attached v2.

In the attached v2, I collect the relids referenced by the grouping
expressions and skip only an SJE candidate whose toRemove or toKeep
relation overlaps that set.  The relid set is computed once in
remove_useless_self_joins(), so the per-candidate check only requires
bitmap overlap tests.

-- 
Thanks,
Tender Wang

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

От:
Narayanan Venkateswaran <narayananvpostgres@gmail.com>
Дата:
Вложения:
Hi Tender,

On Wed, Nov 11, 2026 at 12:08 PM Tender Wang  wrote:
>
> Skipping SJE query-wide seems too strict; I'm also thinking about
> approach 2. As in the attached v2.
>
> In the attached v2, I collect the relids referenced by the grouping
> expressions and skip only an SJE candidate whose toRemove or toKeep
> relation overlaps that set.  The relid set is computed once in
> remove_useless_self_joins(), so the per-candidate check only requires
> bitmap overlap tests.

Thanks for the v2 patch! I like this approach much better than skipping
SJE for the entire query.

While testing it further, I noticed a couple of small things,

1. In remove_useless_self_joins(), I passed NULL as the root to
pull_varnos(NULL, (Node *) tle->expr). When a grouping set contains a
constant (like GROUP BY ROLLUP(1)), mark_nullable_by_grouping() wraps the
constant in a PlaceHolderVar whose phrels includes all relations in the
jointree. Passing NULL tells pull_varnos() to look inside the
PlaceHolderVar's expression rather than returning ph_eval_at, so SJE can
still optimize self-joins in those queries.

2. In remove_self_joins_one_group(), since r and k are base relation IDs,
I moved the check for r to the outer loop using bms_is_member(r,
grouping_relids) and used bms_is_member(k, grouping_relids) in the inner
loop.

3. I also noticed that the underlying issue can cause wrong results even
without ORDER BY: if the second grouping column is used in HAVING (e.g.,
HAVING t2.a IS NULL) or in an expression like COALESCE(t2.a, -1), SJE
rewrites t1.a and t2.a to the same Var and setrefs.c ends up binding both
to the first column. Skipping SJE for relations in grouping_relids fixes
this case as well.

4. Added the commit message and regression tests in join.sql covering
both cases where SJE should be skipped and cases where SJE should still
apply.

Please find the patch with the above changes attached.

Thank you,
Narayanan
FAQ