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

Hi Zhenglong,

> v4 is attached.

Thanks for v4. With both patches applied on master, make check
passes, the eager aggregation query from my last mail returns its
rows again, and the tb/ts query keeps master's merge join over the
index. To wrap up my review, here is what the patch changes,
including the small incremental patch attached.

Sorting is one of the expensive steps of a plan. It grows
faster than its input and spills to disk once it exceeds work_mem.
A query with GROUP BY, window functions and ORDER BY may sort up to
three times, and a sort goes away when the output order of one step
already satisfies the order the next step needs. Grouping itself
only needs equal values to be adjacent, so choosing the grouping
order well costs nothing and can save sorts. Today the grouping
order is matched only to the query's ORDER BY, and its sort
direction is taken from ORDER BY as well. So an index sorted in
the other direction can't be used for grouping, and with window
functions one more sort happens for the window right above the
grouping step.

With the patch, users see three changes.

- An index or an already sorted input can be used for grouping even
if its direction differs from ORDER BY. For example, with an
index on (b, c), "GROUP BY b, c ORDER BY b, c DESC" can group
straight off the index and sort only the (typically far fewer)
groups for ORDER BY, when grouping by sort is chosen over
hashing. The same goes for the partial aggregation that eager
aggregation pushes below a join.
- With window functions, one sort can serve both the grouping and
the first window. "GROUP BY a, b" with "OVER (PARTITION BY b)"
used to sort twice when grouping by sort, by (a, b) and by (b);
now it sorts once, by (b, a). In parallel plans the workers
share this sort.
- This is only an option. The planner compares the old and the new
orderings and takes the cheaper one, and turning
enable_group_by_reordering off gives the old plans.

To do this, a grouping key and a sort key are taken to match if they
are on the same column with the same comparison semantics (the same
equivalence class and operator family), even if their sort direction
and NULLS position differ. When another direction is taken, it goes
only into the planner's own copy of the grouping clause, so the query
as written is unchanged, and so is the output of view definitions. The
window-matched ordering is an extra candidate that puts the first
window's PARTITION BY and ORDER BY keys first and keeps the remaining
keys in ORDER BY order. The ordering used to plan the scans and joins
below stays as before, so an index that provides the old ordering
cheaply is not lost. In parallel plans the workers sort in either
ordering before the results are gathered.

The incremental patch changes two things, and adds tests.

> - The window ordering now follows enable_group_by_reordering, like the
> other reorderings. In v3 it was applied always.

Not only the window ordering. With the setting off, v4 still does
the direction-insensitive matching in truncate_useless_pathkeys()
and adjust_group_pathkeys_to_input(), so the d1/d2 query in
eager_aggregate.sql gets a different plan from master. The
incremental patch checks the setting there too, and adds that query
with the setting off to the test.

> 1. The missing operator error still happens with eager aggregation.

> Fixed. The check in v3 was only in group_keys_reorder_by_pathkeys(),
> but the partial aggregation goes through adjust_group_pathkeys_to_input(),
> which took the input's DESC pathkey without checking the operator. Now
> it stops there if the opfamily don't have the operator for that
> direction.

Here I take back my request from the last mail. The guard covers
only one path: with the same operator class, a merge join over the
backward index path still fails on v4 with "missing operator". On
the other hand, a btree operator class must provide all five
comparison operators (btree.sgml), and master already fails on such
a class with ORDER BY c DESC. So the incremental patch removes the
guard and its two tests, and the eager aggregation query from my
last mail fails again (it works with enable_group_by_reordering
off).

But that isn't mine to decide, so I'd like to know where the
consensus among committers is: should the planner keep working with
a btree operator class missing an operator, or can it be treated as
unsupported?

As for the tests, I wanted to know which parts of the patch the
regression tests actually pin, so I changed the patched code one
place at a time (mutation testing) and ran make check. Of 11 such
changes only one, dropping the window candidate in
get_useful_group_keys_orderings(), made a test fail. The
incremental patch adds tests that catch most of the others that
change a plan.

As for performance, these are from a release build, alternating
with master on a shared machine, so please read them as ranges.

master v4
your tb/ts query 74-86 ms 56-63 ms
ea/eb, hashagg off 181-192 ms 82-88 ms

43 queries from my last mail 42 change plans: 30 faster
(0.18-0.94x), 3 within 3%,
9 slower (1.05-2.28x)
planning time +2-6 us without windows (up to
+22 us on two join queries),
+3-8 us with windows

The window gains all come from 0002. The incremental patch doesn't
change plans with default settings, so these numbers still hold.

The nine slower ones get the same plans with 0001 alone; they are
mostly the Index Scan + Incremental Sort shape, the existing cost
estimate problem we agreed to leave for a separate patch. CREATE
STATISTICS (ndistinct) on the grouping columns fixes two of them
(2.2x and 1.25x). For three (1.1-1.3x) it only makes master pick
the same slower plan, and four (1.03-1.16x) stay, mostly because
uncorrelated Index Scans and Incremental Sort over many small groups
are costed too low.

One slower case is not in the matrix and comes from 0002: a window
query over 2M rows goes from HashAggregate + Sort (~220 ms) to Sort +
GroupAggregate (~900 ms), because x % 4 is estimated through x (2M
groups expected, 77k actual). CREATE STATISTICS ON (x % 4) fixes it;
ndistinct on the plain columns doesn't. With enable_hashagg off, the
window ordering can also put a low-cardinality key first in a large
sort, which runs 25-40% slower at the same cost, as the sort cost
doesn't depend on key order; master has the same weakness with
ORDER BY.

To sum up, the gains are broad and large, and I found no wrong
results. The losses are rare and come not from the patch's logic
but from existing limits of the planner's estimates and cost model:
group count estimates, a sort cost that ignores key order, and Index
Scans and Incremental Sorts costed too low. The patch does give
those limits more chances to show, since it offers more orderings,
and a badly wrong estimate can make a query several times slower at
default settings. Some cases are fixed by extended statistics; the
rest need cost model work, which I'd keep separate.

Based on the above, with the attached incremental patch, +1 from
me.

Best regards,
Henson