Re: v17 Possible Union All Bug

Hey,

The attached pg_dumpall file creates some test roles and some views, two of
which show the expected and problem behaviors. There is a lot going on
beneath these views but suffice to say I've granted admin of
g6c_service_manager_su to u6_green_leader_su twice, once with the bootstrap
superuser as the grantor and once with the cr_admin role as the grantor.
The query is supposed to notice that the otherwise identical grants have
two different grantors and combine them into a single newline separated
presentation. Note that both v16 examples below show this expected output
as does the "working" view in v17. The "broken" view in v17 decides not to
place them on separate lines.

I appreciate this is a bit of a messy test case. I'm willing to work on
simplifying it further but figured I'd at least get confirmation of
reproducibility and maybe someone will have an ah-ha! moment.

The only difference from the broken view to the working view is the entire
first union all subquery block beginning with the " 'mou' || " string be
prepended is removed. I.e., inside of the ARRAY there is no "union all" in
the working version, there is one (two subqueries) in the broken version.
Note that with this test data the "mou" subquery does not return any rows,
all output rows are coming from the "mog" one.

Results on a clean v17 head build from today:

psql (17devel)
Type "help" for help.

postgres=# select * from rolegraph.role_graph_broken;
oid | role_type | rolname | rolsuper |
administration
-------+-----------+--------------------+----------+-----------------------------------------------
16390 | User | u6_green_leader_su | f | mog of
g6a_fixedops_manager_su from superuser+
| | | | mog of
g6c_service_manager_su from superuser +
| | | | mog of
g6d_service_advisor_su from superuser +
| | | | mog of
g6e_service_tech_su from superuser +
| | | | mog of
g6c_service_manager_su from cr_admin
(1 row)

postgres=# select * from rolegraph.role_graph_working;
oid | role_type | rolname | rolsuper |
administration
-------+-----------+--------------------+----------+-----------------------------------------------
16390 | User | u6_green_leader_su | f | mog of
g6a_fixedops_manager_su from superuser+
| | | | mog of
g6c_service_manager_su from superuser +
| | | |
cr_admin +
| | | | mog of
g6d_service_advisor_su from superuser +
| | | | mog of
g6e_service_tech_su from superuser
(1 row)

Results on a clean v16 stable build from today:

postgres=# select * from rolegraph.role_graph_working;
oid | role_type | rolname | rolsuper |
administration
-------+-----------+--------------------+----------+-----------------------------------------------
16390 | User | u6_green_leader_su | f | mog of
g6a_fixedops_manager_su from superuser+
| | | | mog of
g6c_service_manager_su from superuser +
| | | |
cr_admin +
| | | | mog of
g6d_service_advisor_su from superuser +
| | | | mog of
g6e_service_tech_su from superuser
(1 row)

postgres=# select * from rolegraph.role_graph_broken;
oid | role_type | rolname | rolsuper |
administration
-------+-----------+--------------------+----------+-----------------------------------------------
16390 | User | u6_green_leader_su | f | mog of
g6a_fixedops_manager_su from superuser+
| | | | mog of
g6c_service_manager_su from superuser +
| | | |
cr_admin +
| | | | mog of
g6d_service_advisor_su from superuser +
| | | | mog of
g6e_service_tech_su from superuser
(1 row)

As an additional observation - I could swear I ran this last week on v17
without this particular error showing up so it seems like a recent thing.
Might end up giving me a chance to do my first git bisect...

I'm also attaching the explain analyze plans for the collapse (broken) and
no-collapse cases, from the v17 build.

David J.

On Tue, Jan 23, 2024 at 4:51 PM David G. Johnston <
david(dot)g(dot)johnston(at)gmail(dot)com> wrote:

> I appreciate this is a bit of a messy test case. I'm willing to work on
> simplifying it further but figured I'd at least get confirmation of
> reproducibility and maybe someone will have an ah-ha! moment.
>
>
Decided to focus on simplifying the query first. I figured this out:

WITH cte_role_graph AS (
SELECT leaf_role.oid,
leaf_role.role_type,
leaf_role.rolname,
leaf_role.rolsuper,
array_to_string(ARRAY(

SELECT 'false' where false
UNION ALL

SELECT format('%I from %s'::text, 'test',
string_agg('test', '---'::text
ORDER BY grant_instance.level,
grant_instance.grantor, grant_instance.grantor_path
))

FROM unnest(leaf_role.memberof_groups) other(other)
JOIN pg_roles other_role ON other_role.oid =
other.other
JOIN rolegraph.role_relationship grant_instance ON
grant_instance.leaf_node = leaf_role.oid AND grant_instance.group_node =
other.other
JOIN pg_roles grant_role ON grant_role.oid =
grant_instance.grantor
GROUP BY other_role.rolname, grant_instance.via
), E'\n'::text) AS administration
FROM rolegraph.role_graph_detail leaf_role
where rolname ~ 'u6_green'
)
select * from cte_role_graph;

Running this query against the previously supplied dump file on HEAD should
produce the broken result. Simply commenting out the ORDER BY clause in
the string_agg causes the correct result to appear, even with the UNION ALL
present. Removing the union all and leaving the order by likewise still
produces the correct result.

psql (17devel)
Type "help" for help.

postgres=# \i tmp3.sql
oid | role_type | rolname | rolsuper | administration
-------+-----------+--------------------+----------+----------------
16405 | User | u6_green_leader_su | f | test from test+
| | | | test from test+
| | | | test from test+
| | | | test from test+
| | | | test from test
(1 row)

postgres=# \i tmp3.sql
oid | role_type | rolname | rolsuper | administration
-------+-----------+--------------------+----------+-----------------------
16405 | User | u6_green_leader_su | f | test from test +
| | | | test from test---test+
| | | | test from test +
| | | | test from test
(1 row)

David J.

On Sat, 27 Jan 2024 at 11:33, David G. Johnston
<david(dot)g(dot)johnston(at)gmail(dot)com> wrote:
> Simply commenting out the ORDER BY clause in the string_agg causes the correct result to appear, even with the UNION ALL present. Removing the union all and leaving the order by likewise still produces the correct result.

Are the results correct if you SET enable_presorted_aggregate=0;?

David

On Sat, 27 Jan 2024 at 13:19, David Rowley <dgrowleyml(at)gmail(dot)com> wrote:
> Are the results correct if you SET enable_presorted_aggregate=0;?

For the record, I don't get the same results as you. Perhaps you have
some other roles that I don't have.

I see:
oid | role_type | rolname | rolsuper | administration
-------+-----------+--------------------+----------+----------------
42077 | User | u6_green_leader_su | f |
(1 row)

It might be worth trying to make the repro more self-contained. Can
you swap out the auth table with a mockup of it?

David

On Fri, Jan 26, 2024 at 5:36 PM David Rowley <dgrowleyml(at)gmail(dot)com> wrote:

> On Sat, 27 Jan 2024 at 13:19, David Rowley <dgrowleyml(at)gmail(dot)com> wrote:
> > Are the results correct if you SET enable_presorted_aggregate=0;?
>
>
Apparently I didn't reply-all...

Yes, the problem goes away when I disabled presorted_aggregate

I'll see if that knowledge can help build a better reproducer.

I'm using a stock desktop install of Ubuntu 22.04 and compiling without icu
support.

David J.

On Mon, Jan 29, 2024 at 9:19 AM David G. Johnston <
david(dot)g(dot)johnston(at)gmail(dot)com> wrote:

> On Fri, Jan 26, 2024 at 5:36 PM David Rowley <dgrowleyml(at)gmail(dot)com> wrote:
>
>> On Sat, 27 Jan 2024 at 13:19, David Rowley <dgrowleyml(at)gmail(dot)com> wrote:
>> > Are the results correct if you SET enable_presorted_aggregate=0;?
>>
>>
> Apparently I didn't reply-all...
>
> Yes, the problem goes away when I disabled presorted_aggregate
>
> I'll see if that knowledge can help build a better reproducer.
>
>
I've deferred doing a better reproducer for the moment, I reliably got:
initdb
psql --file ~/unionall-repro.sql
psql -c 'select * from rolegraph.role_graph_broken;'

oid | role_type | rolname | rolsuper |
administration
-------+-----------+--------------------+----------+-----------------------------------------------
16390 | User | u6_green_leader_su | f | mog of
g6a_fixedops_manager_su from superuser+
| | | | mog of
g6c_service_manager_su from superuser +
| | | | mog of
g6d_service_advisor_su from superuser +
| | | | mog of
g6e_service_tech_su from superuser +
| | | | mog of
g6c_service_manager_su from cr_admin
(1 row)

to be produced for the bad bisect result and the correct nested result for
*manager* to produce on the good result.

❯ git bisect bad
0452b461bc405e6d35d8a14c02813c15e28ae516 is the first bad commit
commit 0452b461bc405e6d35d8a14c02813c15e28ae516
Author: Alexander Korotkov <akorotkov(at)postgresql(dot)org>
Date: Sun Jan 21 22:21:36 2024 +0200

Explore alternative orderings of group-by pathkeys during optimization.

When evaluating a query with a multi-column GROUP BY clause, we can
minimize
sort operations or avoid them if we synchronize the order of GROUP BY
clauses
with the ORDER BY sort clause or sort order, which comes from the
underlying
query tree. Grouping does not imply any ordering, so we can compare
the keys in arbitrary order, and a Hash Agg leverages this. But for
Group Agg,
we simply compared keys in the order specified in the query. This commit
explores alternative ordering of the keys, trying to find a cheaper one.

The ordering of group keys may interact with other parts of the query,
some of
which may not be known while planning the grouping. For example, there
may be
an explicit ORDER BY clause or some other ordering-dependent operation
higher up
in the query, and using the same ordering may allow using either
incremental
sort or even eliminating the sort entirely.

The patch always keeps the ordering specified in the query, assuming
the user
might have additional insights.

This introduces a new GUC enable_group_by_reordering so that the
optimization
may be disabled if needed.

Discussion:
https://postgr.es/m/7c79e6a5-8597-74e8-0671-1c39d124c9d6%40sigaev.ru
Author: Andrei Lepikhov, Teodor Sigaev
Reviewed-by: Tomas Vondra, Claudio Freire, Gavin Flower, Dmitry Dolgov
Reviewed-by: Robert Haas, Pavel Borisov, David Rowley, Zhihong Yu
Reviewed-by: Tom Lane, Alexander Korotkov, Richard Guo, Alena Rybakina

src/backend/optimizer/path/equivclass.c | 13 +-
src/backend/optimizer/path/pathkeys.c | 252 +++++++++++++++
src/backend/optimizer/plan/planner.c | 424
++++++++++++--------------
src/backend/utils/misc/guc_tables.c | 10 +
src/backend/utils/misc/postgresql.conf.sample | 1 +
src/include/nodes/pathnodes.h | 10 +
src/include/optimizer/paths.h | 2 +
src/test/regress/expected/aggregates.out | 202 ++++++++++++
src/test/regress/expected/sysviews.out | 3 +-
src/test/regress/sql/aggregates.sql | 75 +++++
src/tools/pgindent/typedefs.list | 1 +
11 files changed, 770 insertions(+), 223 deletions(-)

postgres-head (0452b46) (BISECTING)
❯ git bisect log
# bad: [97287bdfae41b8ea16b27dccb63771fcc196a55a] Move is_valid_ascii() to
ascii.h.
# good: [aa817c7496575b37fde6ea5e0cd65b26f29ea532] Avoid useless
ReplicationOriginExitCleanup locking
git bisect start '97287bdfae' 'aa817c7496'
# bad: [752533d40fd50de0b09d4b956cc32c38f5df2f05] Test EXPLAIN (FORMAT
JSON) ... XMLTABLE
git bisect bad 752533d40fd50de0b09d4b956cc32c38f5df2f05
# good: [7b1dbf0a8d1d4e1e6d01a76dc45a3216e8a16d94] More documentation
updates for incremental backup.
git bisect good 7b1dbf0a8d1d4e1e6d01a76dc45a3216e8a16d94
# good: [c64086b79dbad19e4ee0af8d19e835111aa87bd5] Reorder actions in
ProcArrayApplyRecoveryInfo()
git bisect good c64086b79dbad19e4ee0af8d19e835111aa87bd5
# good: [7ab80ac1caf9f48064190802e1068ef89e2883c4] Generalize the common
code of adding sort before processing of grouping
git bisect good 7ab80ac1caf9f48064190802e1068ef89e2883c4
# bad: [49cd2b93d7dbceefdf9a71cc301d284a2dd234c3] Add test module
injection_points
git bisect bad 49cd2b93d7dbceefdf9a71cc301d284a2dd234c3
# bad: [c03d91d9be378975bcdbfa3e5d40e17288e6f13f] Fix table name collision
in tests in 0452b461bc
git bisect bad c03d91d9be378975bcdbfa3e5d40e17288e6f13f
# bad: [0452b461bc405e6d35d8a14c02813c15e28ae516] Explore alternative
orderings of group-by pathkeys during optimization.
git bisect bad 0452b461bc405e6d35d8a14c02813c15e28ae516
# first bad commit: [0452b461bc405e6d35d8a14c02813c15e28ae516] Explore
alternative orderings of group-by pathkeys during optimization.

David J.

On Mon, Jan 29, 2024 at 11:32 PM David G. Johnston
<david(dot)g(dot)johnston(at)gmail(dot)com> wrote:
>
> On Mon, Jan 29, 2024 at 9:19 AM David G. Johnston <david(dot)g(dot)johnston(at)gmail(dot)com> wrote:
>>
>> On Fri, Jan 26, 2024 at 5:36 PM David Rowley <dgrowleyml(at)gmail(dot)com> wrote:
>>>
>>> On Sat, 27 Jan 2024 at 13:19, David Rowley <dgrowleyml(at)gmail(dot)com> wrote:
>>> > Are the results correct if you SET enable_presorted_aggregate=0;?
>>>
>>
>> Apparently I didn't reply-all...
>>
>> Yes, the problem goes away when I disabled presorted_aggregate
>>
>> I'll see if that knowledge can help build a better reproducer.
>>
>
> I've deferred doing a better reproducer for the moment, I reliably got:
> initdb
> psql --file ~/unionall-repro.sql
> psql -c 'select * from rolegraph.role_graph_broken;'
>
> oid | role_type | rolname | rolsuper | administration
> -------+-----------+--------------------+----------+-----------------------------------------------
> 16390 | User | u6_green_leader_su | f | mog of g6a_fixedops_manager_su from superuser+
> | | | | mog of g6c_service_manager_su from superuser +
> | | | | mog of g6d_service_advisor_su from superuser +
> | | | | mog of g6e_service_tech_su from superuser +
> | | | | mog of g6c_service_manager_su from cr_admin
> (1 row)
>
> to be produced for the bad bisect result and the correct nested result for *manager* to produce on the good result.

Thank you for noticing. I'm investigating this.

------
Regards,
Alexander Korotkov

On 30/1/2024 04:45, Alexander Korotkov wrote:
> On Mon, Jan 29, 2024 at 11:32 PM David G. Johnston
> <david(dot)g(dot)johnston(at)gmail(dot)com> wrote:
>>
>> On Mon, Jan 29, 2024 at 9:19 AM David G. Johnston <david(dot)g(dot)johnston(at)gmail(dot)com> wrote:
>>>
>>> On Fri, Jan 26, 2024 at 5:36 PM David Rowley <dgrowleyml(at)gmail(dot)com> wrote:
>>>>
>>>> On Sat, 27 Jan 2024 at 13:19, David Rowley <dgrowleyml(at)gmail(dot)com> wrote:
>>>>> Are the results correct if you SET enable_presorted_aggregate=0;?
>>>>
>>>
>>> Apparently I didn't reply-all...
>>>
>>> Yes, the problem goes away when I disabled presorted_aggregate
>>>
>>> I'll see if that knowledge can help build a better reproducer.
>>>
>>
>> I've deferred doing a better reproducer for the moment, I reliably got:
>> initdb
>> psql --file ~/unionall-repro.sql
>> psql -c 'select * from rolegraph.role_graph_broken;'
>>
>> oid | role_type | rolname | rolsuper | administration
>> -------+-----------+--------------------+----------+-----------------------------------------------
>> 16390 | User | u6_green_leader_su | f | mog of g6a_fixedops_manager_su from superuser+
>> | | | | mog of g6c_service_manager_su from superuser +
>> | | | | mog of g6d_service_advisor_su from superuser +
>> | | | | mog of g6e_service_tech_su from superuser +
>> | | | | mog of g6c_service_manager_su from cr_admin
>> (1 row)
>>
>> to be produced for the bad bisect result and the correct nested result for *manager* to produce on the good result.
>
>
> Thank you for noticing. I'm investigating this.
Very curious bug. I simplified the test a bit (see in attachment), but
still can't replace system tables, like pg_authid, with a plain table.
Will try further.

--
regards,
Andrei Lepikhov
Postgres Professional

On 1/2/2024 11:06, Andrei Lepikhov wrote:
>> Thank you for noticing.  I'm investigating this.
> Very curious bug. I simplified the test a bit (see in attachment), but
> still can't replace system tables, like pg_authid, with a plain table.
> Will try further.
Just for speedup the bug scrutiny - new replay script attached.

--
regards,
Andrei Lepikhov
Postgres Professional

On 1/2/2024 16:53, Andrei Lepikhov wrote:
> On 1/2/2024 11:06, Andrei Lepikhov wrote:
>>> Thank you for noticing.  I'm investigating this.
>> Very curious bug. I simplified the test a bit (see in attachment), but
>> still can't replace system tables, like pg_authid, with a plain table.
>> Will try further.
> Just for speedup the bug scrutiny - new replay script attached.
A bit closer to the end. The symptom of the problem in incorrect order
of the columns in IncrementalSort, look:

-> GroupAggregate (actual time=1.136..1.157 rows=5 loops=1)
Output: format('%I from %s'::text, other_role.rolname,...
Group Key: grant_instance.via, other_role.rolname
-> Incremental Sort (actual time=1.098..1.102 rows=5 loops=1)
Output: other_role.rolname, grant_instance.via,...
Sort Key: grant_instance.grantor, other_role.rolname,...
Presorted Key: grant_instance.grantor
-> Merge Join (rows=5 loops=1)
Output: other_role.rolname, grant_instance.via,...
Merge Cond: (grant_role.oid = grant_instance.grantor)

Correct variant (without changing grouping order):

-> GroupAggregate (actual time=0.638..0.655 rows=4 loops=1)
Output: format('%I from %s'::text, other_role.rolname, ...
Group Key: other_role.rolname, grant_instance.via
-> Sort (actual time=0.626..0.630 rows=5 loops=1)
Output: other_role.rolname, grant_instance.via, ...
Sort Key: other_role.rolname, grant_instance.via, ...
-> Merge Join (rows=5 loops=1)
Output: other_role.rolname, grant_instance.via, ...
Merge Cond: (grant_role.oid = grant_instance.grantor)

But it is only a symptom. I can fix it easily, but what is the source?
As I see, we have the same value of sortref for the grouping column
other_role.rolname and for EquivalenceClass "grant_role.oid =
grant_instance.grantor".
We create sortref for other_role.rolname and grant_instance.via in
adjust_group_pathkeys_for_groupagg, because aggregate string_agg() in
the aggref->aggorder list contains both these columns.
I don't see ORDER BY for these columns in the query.
So Why is it happened? May it be a core bug?

--
regards,
Andrei Lepikhov
Postgres Professional

And finally, I've got the synthetic test:

CREATE TABLE mess_grouping (x integer, y integer, z integer, w integer,
f integer);
INSERT INTO mess_grouping (x,y,z,w,f) (SELECT x%10, x % 2, x%2, 2, x%10
FROM generate_series(1,100) AS x);
ANALYZE mess_grouping;
SET enable_nestloop = 'off';
SET enable_hashjoin = 'off';
SET enable_hashagg = 'off';
SET enable_group_by_reordering = 'on';
SELECT c1.z, c1.w, string_agg(''::text, repeat(''::text, c1.f) ORDER BY
c1.x,c1.y)
FROM mess_grouping c1 JOIN mess_grouping c2 ON (c1.x = c2.f)
GROUP BY c1.w, c1.z;
SET enable_group_by_reordering = 'off';
SELECT c1.z, c1.w, string_agg(''::text, repeat(''::text, c1.f) ORDER BY
c1.x,c1.y)
FROM mess_grouping c1 JOIN mess_grouping c2 ON (c1.x = c2.f)
GROUP BY c1.w, c1.z;
DROP TABLE IF EXISTS mess_grouping CASCADE;

You can see here, that first query execution produces:
z | w | string_agg
---+---+------------
0 | 2 |
1 | 2 |
0 | 2 |
1 | 2 |
0 | 2 |
1 | 2 |
0 | 2 |
1 | 2 |
0 | 2 |
1 | 2 |
(10 rows)

and second execution gives correct result:
z | w | string_agg
---+---+------------
0 | 2 |
1 | 2 |
(2 rows)

The simple fix is in the attachment. But I'm not sure we should fix
GROUP-BY optimization instead of the more general issue.
The source of the problem is root->group_pathkeys, which contains
grouping pathkeys and aggregate pathkeys. For now, their 'sortref'
values could intersect, and we can differ which one references the query
target list and which one the target list of the aggregate.
So, I would like to get advice here: should we make a quick fix here, or
is such a mess in the sortref values not a mess and designed for some
purposes?

--
regards,
Andrei Lepikhov
Postgres Professional

On Sun, Feb 4, 2024 at 6:57 AM Andrei Lepikhov
<a(dot)lepikhov(at)postgrespro(dot)ru> wrote:
> The simple fix is in the attachment. But I'm not sure we should fix
> GROUP-BY optimization instead of the more general issue.
> The source of the problem is root->group_pathkeys, which contains
> grouping pathkeys and aggregate pathkeys. For now, their 'sortref'
> values could intersect, and we can differ which one references the query
> target list and which one the target list of the aggregate.
> So, I would like to get advice here: should we make a quick fix here, or
> is such a mess in the sortref values not a mess and designed for some
> purposes?

Thank you, Andrei. I think we should apply this fix for now, while
better refactoring could be done in future. I've revised your fix
with more comments and a commit message. I'm going to push it if
there are no objections.

------
Regards,
Alexander Korotkov

On 7/2/2024 16:28, Alexander Korotkov wrote:
> On Sun, Feb 4, 2024 at 6:57 AM Andrei Lepikhov
> <a(dot)lepikhov(at)postgrespro(dot)ru> wrote:
>> The simple fix is in the attachment. But I'm not sure we should fix
>> GROUP-BY optimization instead of the more general issue.
>> The source of the problem is root->group_pathkeys, which contains
>> grouping pathkeys and aggregate pathkeys. For now, their 'sortref'
>> values could intersect, and we can differ which one references the query
>> target list and which one the target list of the aggregate.
>> So, I would like to get advice here: should we make a quick fix here, or
>> is such a mess in the sortref values not a mess and designed for some
>> purposes?
>
> Thank you, Andrei. I think we should apply this fix for now, while
> better refactoring could be done in future. I've revised your fix
> with more comments and a commit message. I'm going to push it if
> there are no objections.
I looked into the patch and found only one typo, 'pahtkeys'.

--
regards,
Andrei Lepikhov
Postgres Professional