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

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
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