Re: Eager aggregation, take 3

On Tue, Oct 29, 2024 at 3:57 AM Richard Guo <guofenglinux(at)gmail(dot)com> wrote:
> On Fri, Oct 18, 2024 at 10:22 PM jian he <jian(dot)universality(at)gmail(dot)com> wrote:
> > So overall I doubt here BTEQUALIMAGE_PROC flag usage is correct.
>
> The BTEQUALIMAGE_PROC flag is used to prevent eager aggregation for
> types whose equality operators do not imply bitwise equality, such as
> NUMERIC.
>
> After a second thought, I think it should be OK to just check the
> equality operator specified by the SortGroupClause for btree equality.
> I’m not very sure about this point, though, and would appreciate any
> inputs.

Well, the key thing here is the reasoning, which you don't really
spell out either here or in the patch. The patch's justification for
the use of BTEQUALIMAGE_PROC Is that, if we use non-equal-image
operators, "we may lose some information that could be needed to
evaluate upper qual clauses." But there's no explanation of why that
would happen, and I think that makes it difficult to have a good
discussion.

Here's an example from the optimizer README:

# 3. (A leftjoin B on (Pab)) leftjoin C on (Pbc)
# = A leftjoin (B leftjoin C on (Pbc)) on (Pab)
#
# Identity 3 only holds if predicate Pbc must fail for all-null B rows
# (that is, Pbc is strict for at least one column of B). If Pbc is not
# strict, the first form might produce some rows with nonnull C columns
# where the second form would make those entries null.

This isn't the clearest justification for a rule that I've ever read,
but it's something. Someone reading this can think about whether the
two sentences of justification are a correct argument that Pbc must be
strict in order for the identity to hold.

I think you should be trying to offer similar (or better)
justifications, and perhaps similar identities as well. It's a little
bit hard to think about how to write the identities for this patch,
although you could start with aggregate(X) =
finalizeagg(partialagg(X)) and then explain how the partialagg can be
commuted with certain joins and what is required for it to do so. The
argument needs to be detailed enough that we can evaluate whether it's
correct or not.

Personally, I'm still stuck on the point I wrote about yesterday. When
you partially aggregate a set of rows, the resulting row serves as a
proxy for the original set of rows. So, all of those rows must have
the same destiny. As I mentioned then, if you ever partially aggregate
a row that should ultimately be filtered out with one that shouldn't,
that breaks everything. But also, I need all the rows that feed into
each partial group to be part of the same set of output rows. For
instance, suppose I run a report like this:

SELECT o.order_number, SUM(l.quantity) FROM orders o, order_lines l
WHERE o.order_id = l.order_id GROUP BY 1;

If I'm thinking of executing this as FinalizeAgg(order JOIN
PartialAgg(order_lines)), what must be true in order for that to be a
valid execution plan? I certainly can't aggregate on some unrelated
column, say part_number. If I do, then first of all I don't know how
to get an order_id column out so that I can still do the join. But
even if that were no issue, you might have two rows with different
values of the order_id column and the same value for part_number, and
that the partial groups that you've created on the order_lines table
don't line up properly with the groups that you need to create on the
orders table. Some particular order_id might need some of the rows
that went into a certain part_number group and not others; that's no
good.

After some thought, I think the process of deduction goes something
like this. We ultimately need to aggregate on a column in the orders
table, but we want to partially aggregate the order_lines table. So we
need a set of columns in the order_lines table that can act as a proxy
for o.order_number. Our proxy should be all the columns that appear in
the join clauses between orders and order_lines. That way, all the
rows in a single partially aggregate row will have the "same" order_id
according to the operator class implementing the = operator, so for a
given row in the "orders" table, either every row in the group has
o.order_id = l.order_id or none of them do; hence they're all part of
the same set of output rows.

It doesn't matter, for example, whether o.order_number is unique. If
it isn't, then we'll flatten together some different rows from the
orders table -- but each of those rows will match all the rows in
partial groupings where o.order_id = partially_grouped_l.order_id and
none of the rows where that isn't the case, so the optimization is
still valid. Likewise it doesn't matter whether o.order_id is unique:
if order_id = 1 occurs twice, then both of the rows will match the
partially aggregated group with order_id = 1, but that's fine. The
only thing that's a problem is if the same row from orders was going
to match some but not all of the partially aggregate rows from some
order_lines group, and that won't happen here.

Now consider this example:

SELECT o.order_number, SUM(l.quantity) FROM orders o, order_lines l
WHERE o.order_id = l.order_id AND o.something < l.something GROUP BY
1;

Here, we cannot partially group order_lines on just l.order_id,
because we might have a row in the orders table with order_id = 1 and
something = 1 and two rows in the order_lines table that both have
order_id = 1 but one has something = 0 and the other has something =
2. The orders row needs to join to one of those but not the other, so
we can't put them in the same partial group. However, it seems like it
would be legal to group order_lines on (order_id, something), provided
that the operator classes we use for the grouping operation matches
the operator classes of the operators in the join clause - i.e. we
group on order_id using the operator class of = and on something using
the operator class of <. If the operator classes don't match in this
way, then it could happen that the grouping operator thinks the values
are the same but the join operator thinks they're different.
(Everything is also OK if the grouping operator tests
bitwise-equality, because then nothing can ever get merged that
shouldn't; but other notions of equality are also fine as long as
they're compatible with the operator actually used.)

Now let's consider this example, using an imaginary user-defined operator:

SELECT o.order_number, SUM(l.quantity) FROM orders o, order_lines l
WHERE o.order_id = l.order_id AND o.something ?!?! l.something GROUP
BY 1;

Here, we can partially aggregate order_lines by (order_id, something)
as long as order_id is grouped using bitwise equality OR the same
operator class as the = operator used in the query, and something has
to use bitwise equality.

What about this:

SELECT o.order_number, SUM(l.quantity) FROM orders o LEFT JOIN
order_lines l ON o.order_id = l.order_id AND l.something = 1 GROUP BY
1;

It's really important that we don't try to aggregate on just
l.order_id here. Some rows in the group might have l.something = 1 and
others not. It would be legal (but probably not efficient) to
aggregate order_lines on (order_id, something).

So it seems to me that the general rule here is that when the table
for which we need a surrogate key is directly joined to the table
where the original grouping column is located, we need to group on all
columns involved in the join clause, using either compatible operators
or bitwise equality operators. As a practical matter, we probably only
want to do the optimization when all of the join clauses are
equijoins. Then we don't need to worry about bitwise equality at all,
AFAICS; we just group using the operator class that contains the
operator specified by the user.

What if there are more than two tables involved, like this:

SELECT o.order_number, MAX(n.creation_time) FROM orders o, order_lines
l, order_line_notes n WHERE o.order_id = l.order_id AND o.note_id =
n.note_id GROUP BY 1;

Here, there's no direct connection between the table with the original
grouping column and the table we want to aggregate. Using the rule
mentioned above, we can deduce that l.order_id is a valid grouping
column for order_lines. Applying the same rule again, we can then
deduce that n.note_id is a valid grouping column for note_id. We could
either group note_id on n and then perform the remaining joins; or we
could join order_lines and note_id and then partially aggregate the
result on l.order_id.

What if there are multiple grouping columns, like this:

SELECT foo.x, bar.y, SUM(baz.z) FROM foo, bar, baz WHERE foo.a = baz.a
AND bar.b = baz.b GROUP BY 1, 2;

In this case, we need to find a surrogate grouping column for foo.x
and also a surrogate grouping column for bar.y. We can group baz on a,
b; but not just on a or just on b.

Finally, I think this example is interesting:

SELECT p.title, SUM(c.stuff) FROM parent p, link l, child c WHERE p.x
= l.x AND l.y = c.y AND p.z = c.z GROUP BY 1;

Based on the rule that I articulated earlier, you might think we can
just look at the join clauses between parent and child and group the
child on c.z. However, that's not correct -- we'd have to group on
both c.x and c.z. I'm not sure how to adjust the rule so that it
produces the right answer here.

--
Robert Haas
EDB: http://www.enterprisedb.com