Hi Zhenglong, Thanks for v3. With both patches applied on master, make check passes. The window query from my last mail does the partial aggregation off the index again, and both queries from that mail now return the same results as master.
This time I built a test matrix and audited v3 against it with AI
tools: plain, partial, eager, partitionwise and parallel
aggregation, DISTINCT, grouping sets, merge joins, postgres_fdw and
windows, plus operator classes missing an operator, and random
queries whose results were compared with master. The numbers
below come from those runs.
Overall, I think the patch is a clear win. Of about 170 queries
without windows, mostly GROUP BY, 43 change plans with 0001. Run
time relative to master (release build; "same" is within 3%):
changed faster same slower
ORDER BY 15 14 0.26-0.93 1 -
ORDER BY + LIMIT 8 8 0.63-0.85 - -
ordered aggregate 2 2 0.46-0.57 - -
count(DISTINCT) 1 1 0.54 - -
partitionwise 5 3 0.46-0.57 - 2 1.10-1.34
postgres_fdw (*) 1 1 0.18 - -
join 2 - - 2 1.08
small work_mem 2 1 0.76 1 -
ORDER BY, 2M rows 7 - 2 5 1.10-2.28
total 43 30 4 9
(*) assert-enabled build; the aggregate and the LIMIT are now
pushed down to the remote side.
The "same" one under ORDER BY is a near tie in cost: its plan
changes in the assert-enabled build but not in the release build.
The attached cf7150-matrix.sql builds the data and runs these 43
queries, so the plans and ratios can be checked on master and with
the patch. Ratios close to 1.0 can move between columns from run
to run.
- The slower ones mostly come from the existing cost model, which
I think belongs in a separate patch rather than this one
(item 4).
- Your window and ORDER BY queries on ea/eb also reproduce: with
enable_hashagg = off as in my last mail, about 250 -> 105 ms and
185 -> 105 ms (assert-enabled build).
- One large loss, where a window takes away master's better plan
(item 2 below). I think it can be fixed as suggested there.
- Planning takes a bit longer, which I see as a trade-off worth
accepting (item 3).
There is also one error left (item 1).
> In v3,
> group_keys_reorder_by_pathkeys() looks up the operator before adding
> the key to the reordered list.
1. The missing operator error still happens with eager aggregation.
If the operator class also has FUNCTION 4, so that the GROUP BY can
be pushed below a join, the same error comes back, with every setting
at its default:
CREATE TYPE col3 AS ENUM ('r', 'g', 'b');
CREATE FUNCTION col3_lt(col3, col3) RETURNS bool
LANGUAGE internal IMMUTABLE STRICT AS 'enum_lt';
CREATE FUNCTION col3_eq(col3, col3) RETURNS bool
LANGUAGE internal IMMUTABLE STRICT AS 'enum_eq';
CREATE FUNCTION col3_cmp(col3, col3) RETURNS int
LANGUAGE internal IMMUTABLE STRICT AS 'enum_cmp';
CREATE OPERATOR <<< (leftarg = col3, rightarg = col3,
function = col3_lt);
CREATE OPERATOR === (leftarg = col3, rightarg = col3,
function = col3_eq);
CREATE OPERATOR CLASS col3_ops DEFAULT FOR TYPE col3
USING btree AS
OPERATOR 1 <<<, OPERATOR 3 ===,
FUNCTION 1 col3_cmp(col3, col3),
FUNCTION 4 btequalimage(oid);
CREATE TABLE ec3 (c col3, d int, x int);
INSERT INTO ec3
SELECT (ARRAY['r', 'g', 'b'])[1 + i % 3]::col3, i % 50, i
FROM generate_series(1, 60000) i;
CREATE INDEX ON ec3 (c DESC) INCLUDE (d, x);
CREATE TABLE es3 (k int);
INSERT INTO es3 SELECT generate_series(0, 49);
VACUUM ANALYZE ec3, es3;
SELECT t.c, sum(t.x)
FROM ec3 t JOIN es3 s ON t.d = s.k
GROUP BY t.c;
-- master: 3 rows
-- v3: ERROR: missing operator 5(...) in opfamily ...
As before, such an operator class breaks the btree rules. Still,
the query works on master, so this is a regression.
I'd add a test like this next to the color one: the same kind of
operator class, with FUNCTION 4 and a join.
> 0002 merely brings the window queries into the same situation by
> giving i2 the window's direction.
2. Giving the GROUP BY the window's direction can lose a better plan.
When the window sorts the leading GROUP BY column in descending
order, master's plan from an ascending index is gone in v3:
CREATE TABLE ts (a int, b int, c int);
INSERT INTO ts
SELECT i % 5, CASE WHEN i % 4 = 0 THEN NULL ELSE i % 3 END,
i % 2
FROM generate_series(1, 300) i;
ANALYZE ts;
CREATE TABLE tb (a int, b int, c int);
INSERT INTO tb SELECT i % 7, (i * 7) % 11, i % 5
FROM generate_series(1, 1000000) i;
CREATE INDEX ON tb (a, b);
VACUUM ANALYZE tb;
EXPLAIN (COSTS OFF)
SELECT tb.a, count(*), sum(count(*)) OVER (ORDER BY tb.a DESC)
FROM tb JOIN ts ON tb.a = ts.a AND tb.b = ts.b
GROUP BY tb.a;
-- master (cost 38261)
WindowAgg
-> Sort
Sort Key: tb.a DESC
-> Finalize GroupAggregate
Group Key: tb.a
-> Gather Merge
-> Partial GroupAggregate
Group Key: tb.a
-> Merge Join
Merge Cond: ((tb.a = ts.a) AND
(tb.b = ts.b))
-> Parallel Index Only Scan
using tb_a_b_idx on tb
-> Sort
Sort Key: ts.a, ts.b
-> Seq Scan on ts
-- v3 (cost 67642)
WindowAgg
-> Sort
Sort Key: tb.a DESC
-> HashAggregate
Group Key: tb.a
-> Nested Loop
-> Seq Scan on ts
-> Memoize
-> Index Only Scan
using tb_a_b_idx on tb
The Sort for the window stays in both plans, so v3 gains nothing
here, and the query takes about twice as long as on master: 191-194
ms against 95-101 ms (5 runs each, assert-enabled build).
The window's direction is applied to the GROUP BY keys before any
paths are built, so the ascending plan is never considered. Would
it work to offer the window's ordering as one more candidate, next
to the orderings that get_useful_group_keys_orderings() already
returns, and let the cost decide? If that works, I'd expect a
query like this to keep master's plan, while your queries can still
choose the window's ordering when it is cheaper.
I'd add this query as a test as well.
3. Planning time.
With 0001, more paths with the reverse direction survive, so
planning takes a bit longer. Measured on the ea/eb tables from
item 1 of my last mail, the same data you timed v3 on (median of 20
EXPLAINs in one session, best of 5 sessions; execution best to
worst of 5 runs; default settings; assert-enabled build):
planning (ms) execution (ms)
master v3-0001 v3 master v3
GROUP BY 0.022 0.027 0.027 120-126 120-122
+ ORDER BY DESC 0.024 0.031 0.032 113-119 114-120
+ window DESC 0.025 0.031 0.034 165-171 134-139
-- GROUP BY:
SELECT a.i1, a.i2, sum(a.x)
FROM ea a JOIN eb b ON a.i1 = b.k
GROUP BY a.i1, a.i2;
-- + ORDER BY a.i1, a.i2 DESC, or
-- + count(*) OVER (PARTITION BY a.i1 ORDER BY a.i2 DESC)
That is 23-36% more, but only 5-9 microseconds. Considering more
orderings means more paths to build and compare, so I don't think
it can be avoided. And window functions are mostly used for
analytic queries, where spending microseconds more on planning to
save tens of milliseconds of execution, as in the last row, is a
good trade. So I don't see this as a problem.
4. The slower cases come from the existing cost model.
Most of the slower queries in the table pick an Index Scan over an
index that covers only part of the GROUP BY keys, followed by an
Incremental Sort. This pair is estimated cheaper than the other
plans but runs slower than some of them. master already makes the
same choice today:
CREATE TABLE big AS
SELECT i % 1000 AS a, i % 77 AS b, i % 5 AS c
FROM generate_series(1, 2000000) i;
CREATE INDEX ON big (a, b);
VACUUM ANALYZE big;
SELECT a, b, c, count(*) FROM big WHERE a < 500
GROUP BY a, b, c ORDER BY a, b, c;
default incremental sort off
master, ORDER BY a, b, c 282-304 ms 149-154 ms
v3, ORDER BY a, b DESC, c 290-308 ms 150-157 ms
On master (assert-enabled build):
cost actual
Index Scan + Incremental Sort (chosen) 108972 304 ms
Parallel Seq Scan + Sort, 2 workers 137517 164 ms
Bitmap Heap Scan + HashAggregate + Sort 137207 134 ms
Seq Scan + Sort, serial 166861 395 ms
The two plans in the middle run about twice as fast as the chosen
one but lose on the estimate. The nodes of the two serial plans
(own cost and time, up to the end of each node; 3 runs):
cost actual per 1000 cost
Index Scan 64510 162-165 ms 2.5 ms
Incremental Sort 32479 110-112 ms 3.4 ms
Seq Scan 35816 62-63 ms 1.7 ms
Sort (*) 119062 296-311 ms 2.5 ms
(*) external merge, 21616kB on disk with work_mem = 4MB
Per unit of cost, the Index Scan takes about 1.5 times as long as
the Seq Scan, and the Incremental Sort, over 19250 groups of
about 52 rows, about 1.3 times as long as the full Sort. So both
are underestimated. Correcting both would make the chosen plan
lose its 28235 lead, and most of that comes from the Index Scan.
0001 only lets mixed-direction queries reach the same plan as the
ascending ones, plus a final Incremental Sort for the ORDER BY. On
this small example master already picks a similar plan for the DESC
query too, so v3 is only about 10% slower here (259-279 ms on
master). So I think this should be fixed not in this patch
but in a separate one on the cost estimate of the Index Scan and
the Incremental Sort above it.
Once items 1 and 2 are addressed, I'll move on to a line-by-line
review of the code.
Best regards,
Henson
cf7150-matrix.sql
Description: Binary data
