Wrong results with grouping sets
I think I've come across a wrong result issue with grouping sets, as
shown by the query below.
-- result is correct with only grouping sets
select a, b
from (values (1, 1), (2, 2)) as t (a, b) where a = b
group by grouping sets((a, b), (a));
a | b
---+---
1 | 1
1 |
2 | 2
2 |
(4 rows)
-- result is NOT correct with grouping sets and distinct on
select distinct on (a, b) a, b
from (values (1, 1), (2, 2)) as t (a, b) where a = b
group by grouping sets((a, b), (a));
a | b
---+---
1 | 1
2 | 2
(2 rows)
The distinct on expressions include both 'a' and 'b', so rows (1, 1) and
(1, NULL) should not be considered equal. (The same for rows (2, 2) and
(2, NULL).)
I think the root cause is that when we generate distinct_pathkeys, we
failed to realize that Var 'b' might be nullable by the grouping sets,
so it's no longer always equal to Var 'a'. It's not correct to deem
that the PathKey for 'b' is redundant and thus remove it from the
pathkeys list.
We have the same issue when generating sort_pathkeys. As a result, we
may have the final output in the wrong order. There were several
reports about this issue before, such as [1]/messages/by-id/CAMbWs48AtQTQGk37MSyDk_EAgDO3Y0iA_LzvuvGQ2uO_Wh2muw@mail.gmail.com[2]/messages/by-id/17071-24dc13fbfa29672d@postgresql.org.
To fix this issue, I'm thinking that we mark the grouping expressions
nullable by grouping sets with a dummy RTE for grouping sets, something
like attached. In practice we do not need to create a real RTE for
that, what we need is just a RT index. In the patch I use 0, because
it's not a valid outer join relid, so it would not conflict with the
outer-join-aware-Var infrastructure.
If the grouping expression is a Var or PHV, we can just set its
nullingrels, very straightforward. For an expression that is neither a
Var nor a PHV, I'm not quite sure how to set the nullingrels. I tried
the idea of wrapping it in a new PHV to carry the nullingrels, but that
may cause some unnecessary plan diffs. In the patch for such an
expression I just set the nullingrels of Vars or PHVs that are contained
in it. This is not really 'correct' in theory, because it is the whole
expression that can be nullable by grouping sets, not its individual
vars. But it works in practice, because what we need is that the
expression can be somehow distinguished from the same expression in ECs,
and marking its vars is sufficient for this purpose. But what if the
expression is variable-free? This is the point that needs more work.
Fow now the patch just handles variable-free expressions of type Const,
by wrapping it in a new PHV.
There are some places where we need to artificially remove the RT index
of grouping sets from the nullingrels, such as when we generate
PathTarget for initial input to grouping nodes, or when we generate
PathKeys for the grouping clauses, because the expressions there are
logically below the grouping sets. We also need to do that in
set_upper_references when we update the targetlist of an Agg node, so
that we can perform exact match for nullingrels, rather than superset
match.
Since the fix depends on the nullingrels stuff, it seems not easy for
back-patching. I'm not sure what we should do in back branches.
Any thoughts?
[1]: /messages/by-id/CAMbWs48AtQTQGk37MSyDk_EAgDO3Y0iA_LzvuvGQ2uO_Wh2muw@mail.gmail.com
/messages/by-id/CAMbWs48AtQTQGk37MSyDk_EAgDO3Y0iA_LzvuvGQ2uO_Wh2muw@mail.gmail.com
[2]: /messages/by-id/17071-24dc13fbfa29672d@postgresql.org
/messages/by-id/17071-24dc13fbfa29672d@postgresql.org
Thanks
Richard
Attachments:
v1-0001-Mark-expressions-nullable-by-grouping-sets.patchapplication/octet-stream; name=v1-0001-Mark-expressions-nullable-by-grouping-sets.patchDownload+379-28
On Mon, Sep 25, 2023 at 3:11 PM Richard Guo <guofenglinux@gmail.com> wrote:
I think the root cause is that when we generate distinct_pathkeys, we
failed to realize that Var 'b' might be nullable by the grouping sets,
so it's no longer always equal to Var 'a'. It's not correct to deem
that the PathKey for 'b' is redundant and thus remove it from the
pathkeys list.We have the same issue when generating sort_pathkeys. As a result, we
may have the final output in the wrong order. There were several
reports about this issue before, such as [1][2].To fix this issue, I'm thinking that we mark the grouping expressions
nullable by grouping sets with a dummy RTE for grouping sets, something
like attached.
Hi Tom, I'm wondering if you've got a chance to look into this issue.
What do you think about the fix?
Thanks
Richard
Hi! Thank you for your work on the subject.
On 25.09.2023 10:11, Richard Guo wrote:
I think I've come across a wrong result issue with grouping sets, as
shown by the query below.-- result is correct with only grouping sets
select a, b
from (values (1, 1), (2, 2)) as t (a, b) where a = b
group by grouping sets((a, b), (a));
a | b
---+---
1 | 1
1 |
2 | 2
2 |
(4 rows)-- result is NOT correct with grouping sets and distinct on
select distinct on (a, b) a, b
from (values (1, 1), (2, 2)) as t (a, b) where a = b
group by grouping sets((a, b), (a));
a | b
---+---
1 | 1
2 | 2
(2 rows)The distinct on expressions include both 'a' and 'b', so rows (1, 1) and
(1, NULL) should not be considered equal. (The same for rows (2, 2) and
(2, NULL).)
I noticed that this query worked correctly in the main branch with the
inequality operator:
postgres=# select distinct on (a, b) a, b from (values (3, 1), (2, 2))
as t (a, b) where a > b group by grouping sets((a, b), (a)); a | b
---+--- 3 | 1 3 | (2 rows)
So, I think you are right)
I think the root cause is that when we generate distinct_pathkeys, we
failed to realize that Var 'b' might be nullable by the grouping sets,
so it's no longer always equal to Var 'a'. It's not correct to deem
that the PathKey for 'b' is redundant and thus remove it from the
pathkeys list.We have the same issue when generating sort_pathkeys. As a result, we
may have the final output in the wrong order. There were several
reports about this issue before, such as [1][2].To fix this issue, I'm thinking that we mark the grouping expressions
nullable by grouping sets with a dummy RTE for grouping sets, something
like attached. In practice we do not need to create a real RTE for
that, what we need is just a RT index. In the patch I use 0, because
it's not a valid outer join relid, so it would not conflict with the
outer-join-aware-Var infrastructure.If the grouping expression is a Var or PHV, we can just set its
nullingrels, very straightforward. For an expression that is neither a
Var nor a PHV, I'm not quite sure how to set the nullingrels. I tried
the idea of wrapping it in a new PHV to carry the nullingrels, but that
may cause some unnecessary plan diffs. In the patch for such an
expression I just set the nullingrels of Vars or PHVs that are contained
in it. This is not really 'correct' in theory, because it is the whole
expression that can be nullable by grouping sets, not its individual
vars. But it works in practice, because what we need is that the
expression can be somehow distinguished from the same expression in ECs,
and marking its vars is sufficient for this purpose. But what if the
expression is variable-free? This is the point that needs more work.
Fow now the patch just handles variable-free expressions of type Const,
by wrapping it in a new PHV.There are some places where we need to artificially remove the RT index
of grouping sets from the nullingrels, such as when we generate
PathTarget for initial input to grouping nodes, or when we generate
PathKeys for the grouping clauses, because the expressions there are
logically below the grouping sets. We also need to do that in
set_upper_references when we update the targetlist of an Agg node, so
that we can perform exact match for nullingrels, rather than superset
match.Since the fix depends on the nullingrels stuff, it seems not easy for
back-patching. I'm not sure what we should do in back branches.Any thoughts?
[1]
/messages/by-id/CAMbWs48AtQTQGk37MSyDk_EAgDO3Y0iA_LzvuvGQ2uO_Wh2muw@mail.gmail.com
[2]
/messages/by-id/17071-24dc13fbfa29672d@postgresql.org
I looked at your patch and noticed a few things:
1. I think you should add a test with the cube operator, because I
noticed that the order of the query in the result has also changed:
master:
postgres=# select a,b from (values(1,1),(2,2)) as t (a,b) where a=b
group by cube (a, (a,b)) order by b,a; a | b ---+--- 1 | 1 1 | 1 1 | 2 |
2 2 | 2 2 | | (7 rows)
with patch:
postgres=# select a, b from (values (1, 1), (2, 2)) as t (a, b) where a
= b group by cube(a, (a, b)) order by b,a; a | b ---+--- 1 | 1 1 | 1 2 |
2 2 | 2 1 | 2 | | (7 rows)
--
Regards,
Alena Rybakina
On Thu, Nov 16, 2023 at 11:25 PM Alena Rybakina <lena.ribackina@yandex.ru>
wrote:
I noticed that this query worked correctly in the main branch with the
inequality operator:postgres=# select distinct on (a, b) a, b from (values (3, 1), (2, 2)) as
t (a, b) where a > b group by grouping sets((a, b), (a)); a | b ---+--- 3 |
1 3 | (2 rows)So, I think you are right)
Thanks for taking an interest in this patch and verifying it.
I looked at your patch and noticed a few things:
1. I think you should add a test with the cube operator, because I noticed
that the order of the query in the result has also changed:
Hmm, I'm not sure if that's necessary. The wrong result order you saw
here is caused by the same reason explained above: the planner fails to
realize that Var 'a' and 'b' are nullable by the grouping sets, making
them no longer always equal to each other. This issue should have been
covered in the tests added by v1 patch.
Thanks
Richard
On Mon, Sep 25, 2023 at 3:11 PM Richard Guo <guofenglinux@gmail.com> wrote:
If the grouping expression is a Var or PHV, we can just set its
nullingrels, very straightforward. For an expression that is neither a
Var nor a PHV, I'm not quite sure how to set the nullingrels. I tried
the idea of wrapping it in a new PHV to carry the nullingrels, but that
may cause some unnecessary plan diffs. In the patch for such an
expression I just set the nullingrels of Vars or PHVs that are contained
in it. This is not really 'correct' in theory, because it is the whole
expression that can be nullable by grouping sets, not its individual
vars. But it works in practice, because what we need is that the
expression can be somehow distinguished from the same expression in ECs,
and marking its vars is sufficient for this purpose. But what if the
expression is variable-free? This is the point that needs more work.
Fow now the patch just handles variable-free expressions of type Const,
by wrapping it in a new PHV.
For a variable-free expression, if it contains volatile functions, SRFs,
aggregates, or window functions, it would not be treated as a member of
EC that is redundant (see get_eclass_for_sort_expr()). That means it
would not be removed from the pathkeys list, so we do not need to set
the nullingrels for it. Otherwise we can just wrap the expression in a
PlaceHolderVar. Attached is an updated patch to do that.
BTW, this wrong results issue has existed ever since grouping sets was
introduced in v9.5, and there were field reports complaining about this
issue. I think it would be great if we can get rid of it. I'm still
not sure what we should do in back branches. But let's fix it at least
on v16 and later.
Thanks
Richard
Attachments:
v2-0001-Mark-expressions-nullable-by-grouping-sets.patchapplication/octet-stream; name=v2-0001-Mark-expressions-nullable-by-grouping-sets.patchDownload+377-28
Richard Guo <guofenglinux@gmail.com> writes:
For a variable-free expression, if it contains volatile functions, SRFs,
aggregates, or window functions, it would not be treated as a member of
EC that is redundant (see get_eclass_for_sort_expr()). That means it
would not be removed from the pathkeys list, so we do not need to set
the nullingrels for it. Otherwise we can just wrap the expression in a
PlaceHolderVar. Attached is an updated patch to do that.
I don't think this is going in quite the right direction. We have
many serious problems with grouping sets (latest one today at [1]/messages/by-id/CAEzk6fcgXWabEG+RFDaG6tDmFX6g1h7LPGUdrX85Pb0XB3B76g@mail.gmail.com),
and I don't believe that hacking around EquivalenceClasses is going
to fix them all.
I think that what we really need to do is invent a new kind of RTE
representing the output of the grouping step, with columns that
are the Vars or expressions being grouped on. Then we would make
the parser actually replace subexpressions in the tlist with Vars
referencing this new RTE (that is, change check_ungrouped_columns
into something that modifies the expression tree into something that
contains no Vars that aren't grouping-RTE Vars). In this way the
output of the parser directly expresses the semantic requirement that
certain subexpressions be gotten from the grouping output rather than
computed some other way.
The trick is to do this without losing optimization capability.
We could have the planner replace these Vars with the underlying
Vars in cases where it's safe to do so (perhaps after adding a
nullingrel bit that references the grouping RTE). If a grouping
column is an expression, we might be able to replace the reference
Vars with PHVs as you've done here ... but I think we need the
parser infrastructure fixed first.
regards, tom lane
[1]: /messages/by-id/CAEzk6fcgXWabEG+RFDaG6tDmFX6g1h7LPGUdrX85Pb0XB3B76g@mail.gmail.com
On Thu, 7 Dec 2023 at 13:52, Richard Guo <guofenglinux@gmail.com> wrote:
On Mon, Sep 25, 2023 at 3:11 PM Richard Guo <guofenglinux@gmail.com> wrote:
If the grouping expression is a Var or PHV, we can just set its
nullingrels, very straightforward. For an expression that is neither a
Var nor a PHV, I'm not quite sure how to set the nullingrels. I tried
the idea of wrapping it in a new PHV to carry the nullingrels, but that
may cause some unnecessary plan diffs. In the patch for such an
expression I just set the nullingrels of Vars or PHVs that are contained
in it. This is not really 'correct' in theory, because it is the whole
expression that can be nullable by grouping sets, not its individual
vars. But it works in practice, because what we need is that the
expression can be somehow distinguished from the same expression in ECs,
and marking its vars is sufficient for this purpose. But what if the
expression is variable-free? This is the point that needs more work.
Fow now the patch just handles variable-free expressions of type Const,
by wrapping it in a new PHV.For a variable-free expression, if it contains volatile functions, SRFs,
aggregates, or window functions, it would not be treated as a member of
EC that is redundant (see get_eclass_for_sort_expr()). That means it
would not be removed from the pathkeys list, so we do not need to set
the nullingrels for it. Otherwise we can just wrap the expression in a
PlaceHolderVar. Attached is an updated patch to do that.BTW, this wrong results issue has existed ever since grouping sets was
introduced in v9.5, and there were field reports complaining about this
issue. I think it would be great if we can get rid of it. I'm still
not sure what we should do in back branches. But let's fix it at least
on v16 and later.
I have changed the status of the patch to "Waiting on Author" as Tom
Lane's comments have not yet been addressed, feel free to address them
and update the commitfest entry accordingly.
Regards,
Vignesh
On 11 Jan 2024, at 20:10, vignesh C <vignesh21@gmail.com> wrote:
I have changed the status of the patch to "Waiting on Author" as Tom
Lane's comments have not yet been addressed, feel free to address them
and update the commitfest entry accordingly.
This CF entry seems to be a fix for actually unexpected behaviour. But seems like we need another fix.
Richard, Alena, what do you think? Should we mark CF entry [0]https://commitfest.postgresql.org/47/4583/ "RwF" or leave it to wait for better fix?
Best regards, Andrey Borodin.
On Sun, Jan 7, 2024 at 4:59 AM Tom Lane <tgl@sss.pgh.pa.us> wrote:
I don't think this is going in quite the right direction. We have
many serious problems with grouping sets (latest one today at [1]),
and I don't believe that hacking around EquivalenceClasses is going
to fix them all.I think that what we really need to do is invent a new kind of RTE
representing the output of the grouping step, with columns that
are the Vars or expressions being grouped on. Then we would make
the parser actually replace subexpressions in the tlist with Vars
referencing this new RTE (that is, change check_ungrouped_columns
into something that modifies the expression tree into something that
contains no Vars that aren't grouping-RTE Vars). In this way the
output of the parser directly expresses the semantic requirement that
certain subexpressions be gotten from the grouping output rather than
computed some other way.The trick is to do this without losing optimization capability.
We could have the planner replace these Vars with the underlying
Vars in cases where it's safe to do so (perhaps after adding a
nullingrel bit that references the grouping RTE). If a grouping
column is an expression, we might be able to replace the reference
Vars with PHVs as you've done here ... but I think we need the
parser infrastructure fixed first.
Sorry it takes me some time to get back to this thread.
I think you're right. To fix the cases where there are subqueries in
the grouping sets, as in Geoff's example, it seems that we'll have to
fix the parser infrastructure by inventing a new RTE for the grouping
step and replacing the subquery expressions with Vars referencing this
new RTE, so that there is only one instance of the subquery in the
parser output.
I have experimented with this approach, and here is the outcome. The
patch fixes Geoff's query, but it's still somewhat messy as I'm not
experienced enough in the parser code. And the patch has not yet
implemented the nullingrel bit manipulation trick. Before proceeding
further with this patch, I'd like to know if it is going in the right
direction.
Thanks
Richard
Attachments:
v3-0001-Introduce-a-RTE-for-the-grouping-step.patchapplication/octet-stream; name=v3-0001-Introduce-a-RTE-for-the-grouping-step.patchDownload+610-10
On Thu, May 16, 2024 at 5:43 PM Richard Guo <guofenglinux@gmail.com> wrote:
I have experimented with this approach, and here is the outcome. The
patch fixes Geoff's query, but it's still somewhat messy as I'm not
experienced enough in the parser code. And the patch has not yet
implemented the nullingrel bit manipulation trick. Before proceeding
further with this patch, I'd like to know if it is going in the right
direction.
I've spent some more time on this patch, and now it passes all the
regression tests. But I had to hack explain.c and ruleutils.c to make
the varprefix stuff work as it did before, which is not great.
One thing I'm not sure about is whether we need to also replace
subexpressions in the arguments of GroupingFunc nodes with Vars
referencing the new GROUP RTE. These arguments would not be executed at
runtime, so it seems that we can just replace them. I tried to do that
and found several plan changes in the regression tests. Such as
explain (verbose, costs off)
select grouping(ss.x)
from int8_tbl i1
cross join lateral (select (select i1.q1) as x) ss
group by ss.x;
QUERY PLAN
------------------------------------------------
GroupAggregate
Output: GROUPING((SubPlan 1)), ((SubPlan 2))
Group Key: ((SubPlan 2))
-> Sort
Output: ((SubPlan 2)), i1.q1
Sort Key: ((SubPlan 2))
-> Seq Scan on public.int8_tbl i1
Output: (SubPlan 2), i1.q1
SubPlan 2
-> Result
Output: i1.q1
(11 rows)
If we substitute the subquery expression in the argument of GroupingFunc
with the GROUP RTE's Var, the final plan would contain only one SubPlan
instead of two.
Also the patch has not yet manipulated the nullingrel stuff. Maybe that
can be done with the code in my v2 patch. But I think we'd better get
the parser fixed first before stepping into that.
Also please ignore the comment and code format things in the patch as I
haven't worked on them.
Thanks
Richard
Attachments:
v4-0001-Introduce-a-RTE-for-the-grouping-step.patchapplication/octet-stream; name=v4-0001-Introduce-a-RTE-for-the-grouping-step.patchDownload+624-22
On Fri, May 17, 2024 at 5:41 PM Richard Guo <guofenglinux@gmail.com> wrote:
I've spent some more time on this patch, and now it passes all the
regression tests. But I had to hack explain.c and ruleutils.c to make
the varprefix stuff work as it did before, which is not great.
I've realized that I made a mistake in the v4 patch: If there are join
alias vars in the targetlist and HAVING clause, we should first flatten
them before replacing the grouped variables involved there with
grouping-RTE Vars. To fix this issue, I decide to merge the newly added
function substitute_group_exprs into check_ungrouped_columns by changing
check_ungrouped_columns to also perform the replacement, which is Tom's
initial suggestion I think.
Now it seems that 'check_ungrouped_columns' is no longer an appropriate
name for the function. So I rename it to 'substitute_grouped_columns'.
But I'm open to other names if there are any suggestions.
I've also worked on the comments.
Thanks
Richard
Attachments:
v5-0001-Introduce-a-RTE-for-the-grouping-step.patchapplication/octet-stream; name=v5-0001-Introduce-a-RTE-for-the-grouping-step.patchDownload+576-80
On the basis of the parser infrastructure fixup, 0002 patch adds the
nullingrel bit that references the grouping RTE to the grouping
expressions.
However, it seems to me that we have to manually remove this nullingrel
bit from expressions in various cases where these expressions are
logically below the grouping step, such as when we generate groupClause
pathkeys for grouping sets, or when we generate PathTarget for initial
input to grouping nodes.
Furthermore, in set_upper_references, the targetlist and quals of an Agg
node should have nullingrels that include the effects of the grouping
step, ie they will have nullingrels equal to the input Vars/PHVs'
nullingrels plus the nullingrel bit that references the grouping RTE.
In order to perform exact nullingrels matches, I think we also need to
manually remove this nullingrel bit.
Thanks
Richard
Attachments:
v6-0001-Introduce-a-RTE-for-the-grouping-step.patchapplication/octet-stream; name=v6-0001-Introduce-a-RTE-for-the-grouping-step.patchDownload+576-80
v6-0002-Mark-expressions-nullable-by-grouping-sets.patchapplication/octet-stream; name=v6-0002-Mark-expressions-nullable-by-grouping-sets.patchDownload+337-39
On Fri, May 24, 2024 at 9:08 PM Richard Guo <guofenglinux@gmail.com> wrote:
On the basis of the parser infrastructure fixup, 0002 patch adds the
nullingrel bit that references the grouping RTE to the grouping
expressions.
I found a bug in the v6 patch. The following query would trigger the
Assert in make_restrictinfo that the given subexpression should not be
an AND clause.
select max(a) from t group by a > b and a = b having a > b and a = b;
This is because the expression 'a > b and a = b' in the HAVING clause is
replaced by a Var that references the GROUP RTE. When we preprocess the
columns of the GROUP RTE, we do not know whether the grouped expression
is a havingQual or not, so we do not perform make_ands_implicit for it.
As a result, after we replace the group Var in the HAVING clause with
the underlying grouping expression, we will have a havingQual that is an
AND clause.
As we know, in the planner we need to first preprocess all the columns
of the GROUP RTE. We also need to replace any Vars in the targetlist
and HAVING clause that reference the GROUP RTE with the underlying
grouping expressions. To fix the mentioned issue, I choose the perform
this replacement before we preprocess the targetlist and havingQual, so
that the make_ands_implicit would be performed when we preprocess the
havingQual.
One problem with this is, when we preprocess the targetlist and
havingQual, we would see already-planned tree, which is generated by the
preprocessing work for the grouping expressions and then substituted for
the GROUP Vars in the targetlist and havingQual. This would break the
Assert 'Assert(!IsA(node, SubPlan))' in flatten_join_alias_vars_mutator
and process_sublinks_mutator. I think we can just return the
already-planned tree unchanged when we see it in the preprocessing
process.
Hence here is the v7 patchset. I've also added detailed commit messages
for the two patches.
Thanks
Richard
Attachments:
v7-0001-Introduce-a-RTE-for-the-grouping-step.patchapplication/octet-stream; name=v7-0001-Introduce-a-RTE-for-the-grouping-step.patchDownload+608-102
v7-0002-Mark-expressions-nullable-by-grouping-sets.patchapplication/octet-stream; name=v7-0002-Mark-expressions-nullable-by-grouping-sets.patchDownload+353-39
On Wed, Jun 5, 2024 at 5:42 PM Richard Guo <guofenglinux@gmail.com> wrote:
Hence here is the v7 patchset. I've also added detailed commit messages
for the two patches.
This patchset does not apply any more. Here is a new rebase.
While at it, I added more checks for 'root->group_rtindex', and also
added a new test case to verify that we generate window_pathkeys
correctly with grouping sets.
Thanks
Richard
Attachments:
v8-0001-Introduce-a-RTE-for-the-grouping-step.patchapplication/octet-stream; name=v8-0001-Introduce-a-RTE-for-the-grouping-step.patchDownload+608-102
v8-0002-Mark-expressions-nullable-by-grouping-sets.patchapplication/octet-stream; name=v8-0002-Mark-expressions-nullable-by-grouping-sets.patchDownload+399-39
On Mon, Jun 10, 2024 at 5:05 PM Richard Guo <guofenglinux@gmail.com> wrote:
This patchset does not apply any more. Here is a new rebase.
Here is an updated version of this patchset. I've run pgindent for it,
and also tweaked the commit messages a bit.
In principle, 0001 can be backpatched to all supported versions to fix
the cases where there are subqueries in the grouping expressions; 0002
can be backpatched to 16 where we have the nullingrels stuff. But both
patches seem to be quite invasive. I'm not sure if we want to backpatch
them to stable branches. Any thoughts about backpatching?
Thanks
Richard
Attachments:
v9-0002-Mark-expressions-nullable-by-grouping-sets.patchapplication/octet-stream; name=v9-0002-Mark-expressions-nullable-by-grouping-sets.patchDownload+400-30
v9-0001-Introduce-an-RTE-for-the-grouping-step.patchapplication/octet-stream; name=v9-0001-Introduce-an-RTE-for-the-grouping-step.patchDownload+676-103
On Mon, Jul 1, 2024 at 1:59 PM Richard Guo <guofenglinux@gmail.com> wrote:
On Mon, Jun 10, 2024 at 5:05 PM Richard Guo <guofenglinux@gmail.com> wrote:
This patchset does not apply any more. Here is a new rebase.
Here is an updated version of this patchset. I've run pgindent for it,
and also tweaked the commit messages a bit.In principle, 0001 can be backpatched to all supported versions to fix
the cases where there are subqueries in the grouping expressions; 0002
can be backpatched to 16 where we have the nullingrels stuff. But both
patches seem to be quite invasive. I'm not sure if we want to backpatch
them to stable branches. Any thoughts about backpatching?
I don't have any specific thoughts on backpatching, but I have started
reviewing the patches.
The first patch in the set adds a new RTEKind for GROUP. From prologue
of RangeTblEntry structure I can not understand what an RTE represents
especially when the RTE represents something other than a FROM clause
item.
```
* This is because we only need the RTE to deal with SQL features
* like outer joins and join-output-column aliasing.) Other special
* RTE types also exist, as indicated by RTEKind.
```
I can not use this description to decide whether a GROUP BY construct
should have an RTE for itself or not. It looks like the patch adds a
new RTE (kind) here so that its rtindex can be used to differentiate
between a and b from VALUES clause and those from the GroupingSet
result in the query mentioned in the first email in this thread. But I
don't see any discussion of other alternatives. For example, how about
infrastructure in EC to tell which stages this EC is valid for/upto? I
see Tom suggesting use of RTE instead of changing EC but I don't see
why that's better. We do mark a RestrictInfo with relids above which
it can be computed. Similarly we assess validity of EC by stages or
relations being computed. That might open some opportunities for using
broken ECs? We are almost reimplementing parts of the GROUPING set
feature, so may be it's worth spending time thinking about it.
Assuming new RTEkind is the right approach, I am wondering whether
there are other things that should have been represented by RTE for
the same reason. For example, a HAVING clause changes the
characteristics of results by introducing new constraints on the
aggregated results. Should that have an RTE by itself? Will the
RTEKind introduced by this patch cover HAVING clause as well? Will
that open opportunities for more optimizations E.g.
```
explain select sum(a), sum(b), stddev(a + b) from (values (1, 1), (2,
2)) as t(a, b) group by a, b having sum(a) = sum(b) order by 1, 2;
QUERY PLAN
-------------------------------------------------------------------------
Sort (cost=0.10..0.10 rows=1 width=56)
Sort Key: (sum("*VALUES*".column1)), (sum("*VALUES*".column2))
-> HashAggregate (cost=0.06..0.09 rows=1 width=56)
Group Key: "*VALUES*".column1, "*VALUES*".column2
Filter: (sum("*VALUES*".column1) = sum("*VALUES*".column2))
-> Values Scan on "*VALUES*" (cost=0.00..0.03 rows=2 width=8)
(6 rows)
```
Sort Key can be just (sum("*VALUES*".column1)) instead of both
(sum("*VALUES*".column1)), (sum("*VALUES*".column2)) because of HAVING
clause?
Some code level random comments
1.
```
if (rte->rtekind == RTE_GROUP)
{
es->rtable_size--;
break;
```
because of the variable name, it would be interpreted as the size of
es->rtable and will be expected to be the same as
list_length(es->rtable) which it is not. The comment at the member
declaration won't help much for a quick reader. All that variable is
doing is to tell us whether to use alias as prefix or not;
`useprefix = es->rtable_size > 1;` OR useprefix = (es->rtable_size > 1
|| es->verbose);.
Instead of rtable_size, we could let the new member track the fact
whether there are multiple aliases in the query (requiring multiple
prefixes) instead of size of rtable. However, the fact that the GROUP
RTE requires special handling indicates that the new RTEKind doesn't
quite fit the rest of the set. No other RTE, even if outside FROM
clause, required this special handling.
2. expandRecordVariable: The comment below the change should be
updated to explain why an output of GROUPing can not have RECORD or at
least mention GROUPING there.
3. I see code like below in get_eclass_for_sort_expr() and
mark_rels_nulled_by_join()
```
/* ignore GROUP RTE */
if (i == root->group_rtindex)
continue;
```
I assume that rel for this RTE index would be NULL, so "if" block just
below this code would get executed. I think we should just change
Assert() in that code block rather than adding a new "if" block to
avoid confusion.
4. Looking at parse_clause.c most (if not all) addRangeTableEntry*
function calls are from transform* functions. On those lines, I
expected addRangeTableEntryForGroup() to be called from
transformGroupClause(). Why are we calling
addRangeTableEntryForGroup() from parseCheckAggregates()?
5. In the parseCheckAggregates, we are replacing expressions from
targetlist and havingQual with Vars pointing to GROUP RTE. But we are
not doing that to sortClause, the remaining SQL construct. That's
because sortClause is just a list of entries pointing back to
targetlist. So there's nothing to change there. Am I right?
6. I think ParseState::p_grouping_nsitem should be collocated with
other ParseNamespaceItem members or lists in ParseState. I think it
serves a similar purpose as them. Similarly PlannerInfo::group_rtindex
should be placed next to outer_join_rels?
7. Do we need RangeTblEntry::groupexprs as a separate member? They are
the same as GROUP BY or GROUPING SET expressions. So the list can be
constructed from groupClause whenever required. Do we need to maintain
the list separately? I am comparing with other RTEs, say Subquery RTE.
We don't copy all the targetlist expressions from subquery to
subquery's RTE. I noticed that groupexprs are being treated on lines
similar to joinaliasvars. But they are somewhat different. The latter
is a unified representation of columns of joining relations different
from those columns and hence needs a new representation. That doesn't
seem to be the case with RangeTblEntry::groupexpr.
8. The change in process_sublinks_mutator() appears to be related to
the fact that GROUPING() may have subqueries which were not being
handled earlier. That change seems to be independent of the bug being
fixed here. Am I right? If yes, having those changes in a separate
patch will help.
--
Best Wishes,
Ashutosh Bapat
On 2024-07-01 16:29:16 +0800, Richard Guo wrote:
On Mon, Jun 10, 2024 at 5:05 PM Richard Guo <guofenglinux@gmail.com> wrote:
This patchset does not apply any more. Here is a new rebase.
Here is an updated version of this patchset. I've run pgindent for it,
and also tweaked the commit messages a bit.In principle, 0001 can be backpatched to all supported versions to fix
the cases where there are subqueries in the grouping expressions; 0002
can be backpatched to 16 where we have the nullingrels stuff. But both
patches seem to be quite invasive. I'm not sure if we want to backpatch
them to stable branches. Any thoughts about backpatching?
As-is they can't be backpatched, unless I am missing something? Afaict they
introduce rather thorough ABI breaks? And API breaks, actually?
Greetings,
Andres Freund
On Thu, Jul 4, 2024 at 6:02 PM Ashutosh Bapat
<ashutosh.bapat.oss@gmail.com> wrote:
On Mon, Jul 1, 2024 at 1:59 PM Richard Guo <guofenglinux@gmail.com> wrote:
Here is an updated version of this patchset. I've run pgindent for it,
and also tweaked the commit messages a bit.In principle, 0001 can be backpatched to all supported versions to fix
the cases where there are subqueries in the grouping expressions; 0002
can be backpatched to 16 where we have the nullingrels stuff. But both
patches seem to be quite invasive. I'm not sure if we want to backpatch
them to stable branches. Any thoughts about backpatching?I don't have any specific thoughts on backpatching, but I have started
reviewing the patches.
Thanks for reviewing this patchset!
The first patch in the set adds a new RTEKind for GROUP. From prologue
of RangeTblEntry structure I can not understand what an RTE represents
especially when the RTE represents something other than a FROM clause
item.
```
* This is because we only need the RTE to deal with SQL features
* like outer joins and join-output-column aliasing.) Other special
* RTE types also exist, as indicated by RTEKind.
```
I can not use this description to decide whether a GROUP BY construct
should have an RTE for itself or not. It looks like the patch adds a
new RTE (kind) here so that its rtindex can be used to differentiate
between a and b from VALUES clause and those from the GroupingSet
result in the query mentioned in the first email in this thread. But I
don't see any discussion of other alternatives. For example, how about
infrastructure in EC to tell which stages this EC is valid for/upto? I
see Tom suggesting use of RTE instead of changing EC but I don't see
why that's better. We do mark a RestrictInfo with relids above which
it can be computed. Similarly we assess validity of EC by stages or
relations being computed. That might open some opportunities for using
broken ECs? We are almost reimplementing parts of the GROUPING set
feature, so may be it's worth spending time thinking about it.
The reason why we need a new RTE for the grouping step is to address
cases where there are subqueries in the grouping expressions. In such
cases, each of these subqueries in the targetlist and HAVING clause is
expanded into distinct SubPlan nodes. Only one of these SubPlan nodes
would be converted to reference to the grouping key column output by
the Agg node; others would have to get evaluated afresh, and might not
go to NULL when they are supposed to. I do not think this can be
addressed by changing ECs.
Assuming new RTEkind is the right approach, I am wondering whether
there are other things that should have been represented by RTE for
the same reason. For example, a HAVING clause changes the
characteristics of results by introducing new constraints on the
aggregated results. Should that have an RTE by itself? Will the
RTEKind introduced by this patch cover HAVING clause as well?
AFAIU, HAVING clauses are just quals applied to the grouped rows after
groups and aggregates are computed. I cannot see why and how to add a
new RTE for HAVING.
```
explain select sum(a), sum(b), stddev(a + b) from (values (1, 1), (2,
2)) as t(a, b) group by a, b having sum(a) = sum(b) order by 1, 2;
QUERY PLAN
-------------------------------------------------------------------------
Sort (cost=0.10..0.10 rows=1 width=56)
Sort Key: (sum("*VALUES*".column1)), (sum("*VALUES*".column2))
-> HashAggregate (cost=0.06..0.09 rows=1 width=56)
Group Key: "*VALUES*".column1, "*VALUES*".column2
Filter: (sum("*VALUES*".column1) = sum("*VALUES*".column2))
-> Values Scan on "*VALUES*" (cost=0.00..0.03 rows=2 width=8)
(6 rows)
```
Sort Key can be just (sum("*VALUES*".column1)) instead of both
(sum("*VALUES*".column1)), (sum("*VALUES*".column2)) because of HAVING
clause?
This looks like an optimization that can be achieved by hacking around
ECs. I'm not sure. But I think adding new RTEs does not help here.
Some code level random comments
1.
```
if (rte->rtekind == RTE_GROUP)
{
es->rtable_size--;
break;
```
because of the variable name, it would be interpreted as the size of
es->rtable and will be expected to be the same as
list_length(es->rtable) which it is not. The comment at the member
declaration won't help much for a quick reader. All that variable is
doing is to tell us whether to use alias as prefix or not;
`useprefix = es->rtable_size > 1;` OR useprefix = (es->rtable_size > 1
|| es->verbose);.
Instead of rtable_size, we could let the new member track the fact
whether there are multiple aliases in the query (requiring multiple
prefixes) instead of size of rtable. However, the fact that the GROUP
RTE requires special handling indicates that the new RTEKind doesn't
quite fit the rest of the set. No other RTE, even if outside FROM
clause, required this special handling.
AFAIU we want to print prefixes on Vars when there are more than one
RTE entries to indicate which column is from which RTE entry. If
there is only one RTE (and not verbose), we try to avoid the prefixes.
This patch adds a new dummy RTE, resulting in plans that previously
had one RTE now having two and starting to print prefixes. This has
caused a lot of plan diffs in regression tests. That's why this patch
has to hack explain.c and ruleutils.c to make the varprefix stuff work
as it did before.
But I do not think this is alone for the new RTE. Consider
explain (costs off)
select sum(a) from (select * from t) having sum(a) = 1;
QUERY PLAN
--------------------------
Aggregate
Filter: (sum(t.a) = 1)
-> Seq Scan on t
(3 rows)
BTW, not related to the discussion here, I noticed an inconsistency
regarding the varprefix in the qual and targetlist. Look at:
explain (verbose, costs off)
select sum(a) from t having sum(a) = 1;
QUERY PLAN
----------------------------
Aggregate
Output: sum(a)
Filter: (sum(t.a) = 1)
-> Seq Scan on public.t
Output: a
(5 rows)
In the 'Filter' we add the prefix while in the 'Output' we do not.
Does anyone think this is something worth investigating?
2. expandRecordVariable: The comment below the change should be
updated to explain why an output of GROUPing can not have RECORD or at
least mention GROUPING there.
Thanks. Will add some comments here.
3. I see code like below in get_eclass_for_sort_expr() and
mark_rels_nulled_by_join()
```
/* ignore GROUP RTE */
if (i == root->group_rtindex)
continue;
```
I assume that rel for this RTE index would be NULL, so "if" block just
below this code would get executed. I think we should just change
Assert() in that code block rather than adding a new "if" block to
avoid confusion.
Actually I initially coded it as you suggested, and then moved the
check for the RTE_GROUP RTE out of the 'if' block later, in order to
maintain separate logic for GROUP RTE and outer joins. I'm not quite
sure which is better.
4. Looking at parse_clause.c most (if not all) addRangeTableEntry*
function calls are from transform* functions. On those lines, I
expected addRangeTableEntryForGroup() to be called from
transformGroupClause(). Why are we calling
addRangeTableEntryForGroup() from parseCheckAggregates()?
I think this is the most handy place to add the RTE_GROUP RTE, as the
join_flattened grouping expressions are available here.
5. In the parseCheckAggregates, we are replacing expressions from
targetlist and havingQual with Vars pointing to GROUP RTE. But we are
not doing that to sortClause, the remaining SQL construct. That's
because sortClause is just a list of entries pointing back to
targetlist. So there's nothing to change there. Am I right?
Well, it's not about that. Actually groupClause is also 'a list of
entries pointing back to targetlist'. The primary reason is that the
grouping step may result in some grouping expressions being set to
NULL, whereas the sorting step does not have this behavior.
6. I think ParseState::p_grouping_nsitem should be collocated with
other ParseNamespaceItem members or lists in ParseState. I think it
serves a similar purpose as them. Similarly PlannerInfo::group_rtindex
should be placed next to outer_join_rels?
I agree that ParseState.p_grouping_nsitem should be moved to a more
proper place, and we should mention it in the comment for ParseState
too. But I'm not sure about the root.group_rtindex. I will give it
another thought later.
7. Do we need RangeTblEntry::groupexprs as a separate member? They are
the same as GROUP BY or GROUPING SET expressions. So the list can be
constructed from groupClause whenever required. Do we need to maintain
the list separately? I am comparing with other RTEs, say Subquery RTE.
We don't copy all the targetlist expressions from subquery to
subquery's RTE. I noticed that groupexprs are being treated on lines
similar to joinaliasvars. But they are somewhat different. The latter
is a unified representation of columns of joining relations different
from those columns and hence needs a new representation. That doesn't
seem to be the case with RangeTblEntry::groupexpr.
We need to preprocess the grouping expressions first and then
substitute them back into the targetlist and havingQual. I don't
think this can be achieved without keeping groupexprs as a separate
member.
8. The change in process_sublinks_mutator() appears to be related to
the fact that GROUPING() may have subqueries which were not being
handled earlier. That change seems to be independent of the bug being
fixed here. Am I right? If yes, having those changes in a separate
patch will help.
No, I don't think so. Without this patch we should never see a
SubPlan/AlternativeSubPlan expression in process_sublinks_mutator,
because this is where SubPlans are created.
Thanks
Richard
On Fri, Jul 5, 2024 at 5:51 AM Andres Freund <andres@anarazel.de> wrote:
On 2024-07-01 16:29:16 +0800, Richard Guo wrote:
Here is an updated version of this patchset. I've run pgindent for it,
and also tweaked the commit messages a bit.In principle, 0001 can be backpatched to all supported versions to fix
the cases where there are subqueries in the grouping expressions; 0002
can be backpatched to 16 where we have the nullingrels stuff. But both
patches seem to be quite invasive. I'm not sure if we want to backpatch
them to stable branches. Any thoughts about backpatching?As-is they can't be backpatched, unless I am missing something? Afaict they
introduce rather thorough ABI breaks? And API breaks, actually?
Indeed, you're correct. I did not think about this. This patchset
modifies certain struct definitions in src/include/ and also changes
the signature of several functions, resulting in definite ABI and API
breaks.
BTW, from catversion.h I read:
* Another common reason for a catversion update is a change in parsetree
* external representation, since serialized parsetrees appear in stored
* rules and new-style SQL functions. Almost any change in primnodes.h or
* parsenodes.h will warrant a catversion update.
Since this patchset changes the querytree produced by the parser, does
this indicate that a catversion bump is needed?
Thanks
Richard
Richard Guo <guofenglinux@gmail.com> writes:
BTW, from catversion.h I read:
* Another common reason for a catversion update is a change in parsetree
* external representation, since serialized parsetrees appear in stored
* rules and new-style SQL functions. Almost any change in primnodes.h or
* parsenodes.h will warrant a catversion update.
Since this patchset changes the querytree produced by the parser, does
this indicate that a catversion bump is needed?
Yes, it would.
regards, tom lane
