Re: Eager aggregation, take 3

On Tue, Sep 24, 2024 at 11:20 PM Richard Guo <guofenglinux(at)gmail(dot)com> wrote:
> The reason is that it is very tricky to set the size estimates for a
> grouped join relation. For a non-grouped join relation, we know that
> all its paths have the same rowcount estimate (well, in theory). But
> this is not true for a grouped join relation. Suppose we have a
> grouped join relation for t1/t2 join. There might be two paths for
> it:

What exactly do you mean by "well, in theory" here? My understanding
of how things work today is that every relation is supposed to produce
a specific set of rows and every unparameterized path must produce
that set of rows. The order of the rows may vary but the set of rows
may not. With your proposed design here, that's no longer true.
Instead, what's promised is that the row sets will become equivalent
after a later FinalizeAggregate step. In a sense, this is like
parameterization or partial paths. Suppose I have:

SELECT * FROM foo, bar WHERE foo.x = bar.x;

While every unparameterized path for bar has the same row count,
there's also the possibility of performing an index scan on bar.x
parameterized by foo.x, and that path will have a far lower row count
than the unparameterized paths. Instead of producing all the same rows
as every other path, the parameterized path promises only that if run
repeatedly, with all relevant values of foo.x, you'll eventually get
all the same rows you would have gotten from the unparameterized path.
Because of this difference, parameterized paths need special handling
in many different parts of the code.

And the same thing is true of partial paths. They also do not promise
to generate all the same rows -- instead, they promise that when run
simultaneously across multiple workers, the total set of rows returned
across all invocations will be equal to what a normal path would have
produced. Here again, there's a need for special handling because
these paths behave differently than standard paths.

I think what you're doing here is roughly equivalent to either of
these two cases. It's more like the parameterized path case. Instead
of having a path for a relation which is parameterized by some input
parameter, you have a path for a relation, say bar, which is partially
aggregated by some grouping column. But there's no guarantee of how
much partial aggregation has been done. In your example, PartialAgg(t1
JOIN t2) is "more aggregated" than t1 JOIN PartialAgg(t2), so the row
counts are different. This makes me quite nervous. You can't compare a
parameterized path to an unparameterized path, but you can compare it
to another parameterized path if the parameterizations are the same.
You can't compare a partial path to a non-partial path, but you can
compare partial paths to each other. But with this work,
unparameterized, non-partial paths in the same RelOptInfo don't seem
like they are truly comparable. Maybe that's OK, but I'm not sure that
it isn't going to break other things.

You might for example imagine a design where PartialAgg(t1 JOIN t2)
and t1 JOIN PartialAgg(t2) get separate RelOptInfos. After all, there
are probably multiple ways to generate paths for each of those things,
and paths in each category can be compared to each other apples to
apples. What's less clear is whether it's fair to compare across the
two categories, and how many assumptions will be broken by doing so.
I'm not sure that it's right to have separate RelOptInfos; we
definitely don't want to create more RelOptInfos than necessary. At
the same time, if we mix together all of those paths into a single
RelOptInfo, we need to be confident that we're neither going to break
anything nor introduce too many special cases into hot code paths. For
instance, set_joinpath_size() represents an unwelcome complexity
increase that could impact performance generally, even apart from the
cases this patch intends to handle.

It's tempting to wonder if there's some way that we can avoid
generating paths for both PartialAgg(t1 JOIN t2) and t1 JOIN
PartialAgg(t2). Either the former has lower cardinality, or the latter
does. It seems likely that the lower-cardinality set is the winning
strategy. Even if the path has higher cost to generate, we save work
at every subsequent join level and at the final aggregation step. Are
there counterexamples where it's better to use a path from the
higher-cardinality set?

By the way, the work of figuring out what target list should be
produced by partial grouping is done by init_grouping_targets(), but
the comments seem to take it for granted that I know what result we're
trying to produce, and I don't. I think some more high-level
explanation of the goals of this code would be useful. It seems to me
that if I'm looking at a path for an ungrouped relation and it
produces a certain target list, then every column of that target list
is needed somewhere. If those columns are group keys, cool: we pass
those through. If they're inputs to the aggregates, cool: we feed them
to the aggregates. But if they are neither, then what? In the patch,
you either group on those columns or add them to the
possibly_dependent list depending on the result of
is_var_needed_by_join(). I can believe that there are some cases where
we can group on such columns and others where we can't, but find it
difficult to believe that this test reliably distinguishes between
those two cases. If it does, I don't understand why it does. Don't I
need to know something about how those columns are used in the upper
joins? Like, if those columns are connected by a chain of
binary-equality operators back to the user's choice of grouping
columns, that sounds good, but this test doesn't distinguish between
that case and an upper join on the < operator.
create_grouping_expr_infos() does reason based on whether there's an
equal-image operator available, but AIUI that's only reasoning about
the group columns the user mentioned, not the sort of implicit
grouping columns that init_grouping_targets() is creating.

I spent a lot of time thinking today about what makes it safe to push
down grouping or not. I'm not sure that I have a solid answer to that
question even yet. But it seems to me that there are at least two
cases that clearly won't fly. One is the case where the partial
aggregation would merge rows that need to be included in the final
aggregation with rows that should be filtered out. If the
partially-grouped relation simply has a filter qual, that's fine,
because it will be evaluated before the aggregation. But there might
be a qual that has to be evaluated later, either because (a) it
involves another rel, like this_rel.x + that_rel.y > 10 or (b) it
appears in the ON clause of an outer join and thus needs to be
deferred to the level of the OJ, e.g. A LEFT JOIN B ON a.x = b.x AND
b.y = 42. I wonder if you can comment on how these cases are handled.
Perhaps this coding around functional dependencies has something to do
with it, but it isn't clear to me.

Thanks,

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