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

Hi Zhenglong,

Thanks for v2. With both patches applied on master, make check
passes and every plan in your mail comes out as shown.

I did find two cases where a query that works on master gets slower
or fails with v2.

> 0002 is the window patch with the change you suggested, rebased on
> 0001.

1. Partial aggregation below a join goes away.

When a window sorts a GROUP BY column in descending order, the
partial aggregation that master does below the join off an ascending
index is gone in v2:

CREATE TABLE ea (i1 int, i2 int, x int);
INSERT INTO ea SELECT i % 100, (i / 100) % 1000, i
FROM generate_series(1, 1000000) i;
CREATE INDEX ON ea (i1, i2);
CREATE TABLE eb (k int, v int);
INSERT INTO eb SELECT i, i FROM generate_series(0, 99) i;
VACUUM ANALYZE ea, eb;
SET enable_hashagg = off;

EXPLAIN (COSTS OFF)
SELECT a.i1, a.i2, sum(a.x),
count(*) OVER (PARTITION BY a.i1 ORDER BY a.i2 DESC)
FROM ea a JOIN eb b ON a.i1 = b.k
GROUP BY a.i1, a.i2;

-- master
WindowAgg
-> Incremental Sort
Sort Key: a.i1, a.i2 DESC
Presorted Key: a.i1
-> Finalize GroupAggregate
Group Key: a.i1, a.i2
-> Merge Join
Merge Cond: (a.i1 = b.k)
-> Partial GroupAggregate
Group Key: a.i1, a.i2
-> Index Scan using ea_i1_i2_idx on ea a
...

-- v2
WindowAgg
-> Incremental Sort
Sort Key: a.i1, a.i2 DESC
Presorted Key: a.i1
-> GroupAggregate
Group Key: a.i1, a.i2
-> Merge Join
Merge Cond: (a.i1 = b.k)
-> Index Scan using ea_i1_i2_idx on ea a
...

The Incremental Sort for the window stays either way, so nothing is
gained; only the cost and the run time go up.

> 0001 lets [...] match an input pathkey with
> the same equivalence class and operator family regardless of
> direction

2. GROUP BY fails on an operator class without the reverse operator.

With a btree operator class that has only the less-than and equals
operators, a GROUP BY that works on master fails in v2 with a
"should not happen" error:

CREATE TYPE color AS ENUM ('r', 'g', 'b');
CREATE FUNCTION color_lt(color, color) RETURNS bool
LANGUAGE internal IMMUTABLE STRICT AS 'enum_lt';
CREATE FUNCTION color_eq(color, color) RETURNS bool
LANGUAGE internal IMMUTABLE STRICT AS 'enum_eq';
CREATE FUNCTION color_cmp(color, color) RETURNS int
LANGUAGE internal IMMUTABLE STRICT AS 'enum_cmp';
CREATE OPERATOR <<< (leftarg = color, rightarg = color,
function = color_lt);
CREATE OPERATOR === (leftarg = color, rightarg = color,
function = color_eq);
CREATE OPERATOR CLASS color_ops DEFAULT FOR TYPE color
USING btree AS
OPERATOR 1 <<<, OPERATOR 3 ===,
FUNCTION 1 color_cmp(color, color);
CREATE TABLE tc (c color);
INSERT INTO tc SELECT (ARRAY['r', 'g', 'b'])[1 + i % 3]::color
FROM generate_series(1, 3000) i;
CREATE INDEX ON tc (c);
ANALYZE tc;

SELECT c, count(*) FROM tc GROUP BY c;

-- master: the counts for r, g and b
-- v2: ERROR: missing operator 5(...) in opfamily ...

Such an operator class breaks the btree rules. Still, the missing
operator is needed only for one plan being considered, not for the
result, so wouldn't it be better to skip that plan than to raise an
error?

For the tests, I'd add:

- The two cases above.
- A query with two windows. None of the new queries in window.sql
has more than one OVER. For example, with two windows sorting c in
opposite directions, v2 does one sort fewer than master:

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

- The groupwin result check. The test EXPLAINs one query and runs
another, and thanks to its outer ORDER BY the one it runs has the
same plan as on master, so the result it checks does not come from
v2's change. Wrapped in a subquery, master sorts twice and v2
once, so the result comes from the plan that v2 changes. Cases
like this, where the GROUP BY keys take the window's direction,
are where results most need checking:

SELECT * FROM
(SELECT x, z, count(*) c,
sum(count(*)) OVER (PARTITION BY x
ORDER BY z DESC NULLS LAST) s
FROM groupwin GROUP BY x, z) ss
ORDER BY x, z DESC NULLS LAST;

I tried such cases with different directions in the outer ORDER
BY, joins, outer windows and LIMIT, and the results all matched
master.

Best regards,
Henson