Re: [PATCH] Consider window functions when reordering GROUP BY items

Hi Henson,

Thanks for the careful review and the test cases.

> Could the patch let the GROUP BY items take the direction of the
> window's ORDER BY when it matches them against the window's keys,
> so that the DESC case would also need only one sort?

Yes. v2 is attached. preprocess_groupclause() now matches a GROUP BY
item to a sort clause when both refer to the same targetlist entry and
use the same equality operator, and the GROUP BY item then takes on the
sort operator and NULLS ordering of that clause. A copy is made, so the
parse tree is left untouched. With that, your queries become:

-- c DESC in the window, no ORDER BY outside
WindowAgg
-> Group
Group Key: b, c, a
-> Sort
Sort Key: b, c DESC, a
-> Seq Scan on t

-- c DESC in the window, ORDER BY b, c outside
Incremental Sort
Sort Key: b, c
Presorted Key: b
-> WindowAgg
-> Group
Group Key: b, c, a
-> Sort
Sort Key: b, c DESC, a
-> Seq Scan on t

so the second case loses one of its two incremental sorts.

> One thing to watch out for when implementing this: in this query the
> GROUP BY item c has already taken the ascending direction from the
> ORDER BY outside the window.

Right. The relaxed matching applies to the whole list being matched
(the first window's PARTITION BY, its ORDER BY, then the query's ORDER
BY), so it doesn't matter where the GROUP BY item or the PARTITION BY
item got its direction from. One consequence is that the list can now
refer to the same column more than once, e.g. c DESC from the window
and c from the ORDER BY outside it. A later reference with the same
equality operator is redundant, so it's skipped. This affects queries
without window functions too, e.g. "ORDER BY x USING ~<~, x, y", where
the items after the second x can now be matched as well.

> Also, if the ORDER BY outside the window brought in a different
> equality operator (ORDER BY ... USING), that changes what counts as
> a group, so the GROUP BY item should follow the window's direction
> only when the equality operator is the same.

Agreed, and that is what v2 does: when the equality operators differ,
matching stops as before. There's a test for this using record's *<,
whose equality operator *= differs from the default =. v2 also requires
the sort operator to come from the same btree operator family as the
GROUP BY item's own, so only the direction and NULLS ordering can
change. A family sharing the equality operator isn't enough, since its
ordering need not agree with that operator; see the text_pattern_ops
case at the end.

While testing this I found a regression. Once the GROUP BY keys follow
the window's direction, an input path sorted in the original direction
can no longer be used for grouping. With an index on (b, c):

SELECT b, c, count(*), count(*) OVER (PARTITION BY b ORDER BY c DESC)
FROM t GROUP BY b, c;

master groups straight off the index and then sorts only the groups for
the window. With the change alone, the planner instead sorted the whole
input by b, c DESC before grouping, which was about 3x slower on 2M rows.

The cause is older than this patch. group_keys_reorder_by_pathkeys(),
and the GROUP BY check in truncate_useless_pathkeys(), match the input
pathkeys to the GROUP BY pathkeys by pointer, so the sort direction has
to agree too. Master already shows the same problem without any window
functions:

CREATE INDEX ON t (b, c);
SELECT b, c, count(*) FROM t GROUP BY b, c ORDER BY b, c DESC;

This sorts all of the input by b, c DESC incrementally, when it could
group off the index and then sort only the groups.

So the series is now:

0001 lets group_keys_reorder_by_pathkeys() match an input pathkey with
the same equivalence class and operator family regardless of
direction, adjusting a copy of the GROUP BY clause to agree with
it, and makes truncate_useless_pathkeys() keep such pathkeys. In
the query above, on 2M rows, the estimated cost goes from 280732
to 52878 and the run time from 333 ms to 98 ms. Aggregate
pathkeys are still matched exactly, as an aggregate's ORDER BY
does depend on direction. No existing regression test output
changes.

0002 is the window patch with the change you suggested, rebased on
0001. The index case above again groups off the index.

For testing, beyond the regression tests, I compared results between
sorted and hashed grouping on a few tens of thousands of randomly
generated queries. They covered GROUP BY, one to three windows with
random directions, NULLS ordering, USING and COLLATE, and optional
ORDER BY, LIMIT, HAVING and DISTINCT. I also ran targeted cases with
partitionwise and eager aggregation, parallel plans, prepared
statements with generic plans, and grouping sets. No result differences
or assertion failures turned up.

Unrelated to this patch, but noticed along the way: for text_pattern_ops
under a nondeterministic collation, "=" is collation-aware whereas ~<~
compares bytes, so the two disagree on which values are equal. Since the
parser copies ~<~ into the GROUP BY item, sorted grouping on master
already returns wrong results:

CREATE COLLATION ci (provider = icu, locale = 'und-u-ks-level2',
deterministic = false);
CREATE TABLE ct (x text COLLATE ci);
INSERT INTO ct VALUES ('a'), ('B'), ('A'), ('b'), ('a');
SET enable_hashagg = off;
SELECT x, count(*) FROM ct GROUP BY x ORDER BY x USING ~<~;

This returns four groups (A, B, a, b) instead of two (a, b), because 'A'
and 'a' are not adjacent in ~<~ order; hashed grouping gets it right.
An earlier version of v2 let the GROUP BY item adopt ~<~ from a
window's ORDER BY as well, which is why v2 now stays within the same
operator family, and there's a test for that in collate.icu.utf8. I'll
start a separate thread for the issue on master.

Best regards,
Zhenglong

Henson Choi <assam258(at)gmail(dot)com> 于2026年10月27日周二 15:11写道：

> Hi Zhenglong,
>
> Thanks for the patch. I applied v1 on master and looked at the
> plan shapes. The queries below return the same results as master.
>
> The patch matches the GROUP BY items against the window's keys
> from the front, and stops at the first key whose sort direction
> is not the same as well. But the two sides get their directions
> from different ORDER BY clauses. So when the window's ORDER BY
> has a descending key, matching stops at that key, unless the
> ORDER BY outside the window gives that column the same direction.
>
> GROUP BY and PARTITION BY do not need any particular sort direction;
> they only bring equal values together. So when the same column also
> appears in an ORDER BY, they simply take its direction: GROUP BY
> from the ORDER BY outside the window, PARTITION BY from the window's
> ORDER BY. Either way, one sort is enough even with DESC.
>
> There is no such relation between GROUP BY and the window's
> ORDER BY, though. Could the patch let the GROUP BY items take the
> direction of the window's ORDER BY when it matches them against the
> window's keys, so that the DESC case would also need only one sort?
>
> CREATE TABLE t (a int, b int, c int);
> INSERT INTO t SELECT i % 100, i % 10, i % 1000
> <https://www.google.com/maps/search/100,+i+%25+10,+i+%25+1000?entry=gmail&source=g>
> FROM generate_series(1, 100000) i;
> ANALYZE t;
> SET enable_hashagg = off;
>
> When the window's ORDER BY is ascending, the
> patch works as described; two sorts become one:
>
> EXPLAIN (COSTS OFF)
> SELECT a, b, c, count(*) OVER (PARTITION BY b ORDER BY c)
> FROM t GROUP BY a, b, c;
>
> -- master
> WindowAgg
> Window: w1 AS (PARTITION BY b ORDER BY c)
> -> Sort
> Sort Key: b, c
> -> Group
> Group Key: a, b, c
> -> Sort
> Sort Key: a, b, c
> -> Seq Scan on t
>
> -- patched
> WindowAgg
> Window: w1 AS (PARTITION BY b ORDER BY c)
> -> Group
> Group Key: b, c, a
> -> Sort
> Sort Key: b, c, a
> -> Seq Scan on t
>
> But if only c is changed to c DESC, the patch matches b and
> stops at c, and the window still needs an incremental sort:
>
> EXPLAIN (COSTS OFF)
> SELECT a, b, c, count(*) OVER (PARTITION BY b ORDER BY c DESC)
> FROM t GROUP BY a, b, c;
>
> -- master
> WindowAgg
> Window: w1 AS (PARTITION BY b ORDER BY c)
> -> Sort
> Sort Key: b, c DESC
> -> Group
> Group Key: a, b, c
> -> Sort
> Sort Key: a, b, c
> -> Seq Scan on t
>
> -- patched
> WindowAgg
> Window: w1 AS (PARTITION BY b ORDER BY c)
> -> Incremental Sort
> Sort Key: b, c DESC
> Presorted Key: b
> -> Group
> Group Key: b, a, c
> -> Sort
> Sort Key: b, a, c
> -> Seq Scan on t
>
> If ORDER BY b, c DESC is added outside the window
> to the same query, the GROUP BY item c takes that
> DESC, and even master does it with one sort:
>
> EXPLAIN (COSTS OFF)
> SELECT a, b, c, count(*) OVER (PARTITION BY b ORDER BY c DESC)
> FROM t GROUP BY a, b, c ORDER BY b, c DESC;
>
> -- master and patched
> WindowAgg
> Window: w1 AS (PARTITION BY b ORDER BY c)
> -> Group
> Group Key: b, c, a
> -> Sort
> Sort Key: b, c DESC, a
> -> Seq Scan on t
>
> That grouping sort, b, c DESC, a, is exactly the order
> the window needs. It would be nice if the patch could
> pick it without the ORDER BY outside the window.
>
> Please also consider the case where the ORDER BY outside
> the window has a different direction from the window's.
> With c DESC in the window and b, c outside, both master
> and the patch do one full sort and two incremental sorts:
>
> EXPLAIN (COSTS OFF)
> SELECT a, b, c, count(*) OVER (PARTITION BY b ORDER BY c DESC)
> FROM t GROUP BY a, b, c ORDER BY b, c;
>
> -- patched (master differs only in grouping on b, c, a)
> Incremental Sort
> Sort Key: b, c
> Presorted Key: b
> -> WindowAgg
> Window: w1 AS (PARTITION BY b ORDER BY c)
> -> Incremental Sort
> Sort Key: b, c DESC
> Presorted Key: b
> -> Group
> Group Key: b, a, c
> -> Sort
> Sort Key: b, a, c
> -> Seq Scan on t
>
> Right now the plan sorts c ascending for the grouping,
> descending for the window, and ascending again for the
> ORDER BY outside the window. If the grouping sort followed the
> window's sort, one of the incremental sorts would go away.
>
> One thing to watch out for when implementing this: in this
> query the GROUP BY item c has already taken the ascending
> direction from the ORDER BY outside the window. So this cannot
> be solved by looking only at the relation between the window's
> ORDER BY and GROUP BY; the relations with the ORDER BY outside
> the window and with PARTITION BY have to be taken into account
> as well. Also, if the ORDER BY outside the window brought in a
> different equality operator (ORDER BY ... USING), that changes
> what counts as a group, so the GROUP BY item should follow the
> window's direction only when the equality operator is the same.
>
> Best regards,
> Henson
>