Re: Eager aggregation, take 3

On Sun, Jan 19, 2025 at 7:53 AM Richard Guo <guofenglinux(at)gmail(dot)com> wrote:
> If, at last, the conclusion of this discussion is that we should not
> apply this change until we fix those problems in aggregate estimates,
> I'd be very sad. This conclusion is absolutely correct, for sure, in
> an ideal world, but in the real world, it feels like a death sentence
> for this patch, and for any future patches that attempt to apply some
> optimizations above aggregate nodes - unless, of course, the day
> arrives when we finally fix those aggregate estimate problems, which
> doesn't seem likely in the near future.

Well, such conclusions should be based on evidence. So far, the
evidence you've presented suggests that the optimization works, so
there's no reason to leap to the conclusion that we shouldn't move
forward. On the other hand, the amount of evidence you've presented
does not seem to me to be all that large. And I'm not sure that you've
gone looking for adversarial cases.

> And if that's the case, can I then argue that the same principle
> should apply to joins? Specifically, should we refrain from applying
> any optimizations above join nodes until we've fixed the join estimate
> problems, particularly in cases where we fall back on default
> selectivity estimates?

I am having a hard time figuring out how to write back to this. I
mean, I don't think that what you write here is a serious proposal,
and I think you already know that I was not proposing any such thing.
But it upsets me that you think that this hypothetical argument is
equivalent to the ones I've actually been making. Apparently, you
consider my concerns quite groundless and foolish.

> Yeah, one of the basic assumptions in the planner is that all paths
> for a given RelOptInfo return the same set of rows. One exception
> to this is parameterized paths.

Good point. I had not considered this parallel.

> Now we have the grouped paths. I had previously considered further
> revising this assumption to that all paths for a RelOptInfo of the
> same parameterization and the same location of partial aggregation
> return the same set of rows. That's why, back in November, I proposed
> the idea of introducing a GroupPathInfo into the Path structure to
> store the location of the partial aggregation and the estimated
> rowcount for each grouped path, similar to how ParamPathInfo functions
> for parameterized paths.

Interesting.

> However, I gave up on this idea in December after realizing an
> important difference from the parameterized path case. For a
> parameterized path, the fewer the required outer rels, the better, as
> more outer rels imply more join restrictions. In other words, the
> number of required outer rels is an important factor when comparing
> two paths in add_path(). For a grouped path, however, the location of
> partial aggregation does not impose such restrictions for further
> planning. As long as one grouped path is cheaper than another based
> on the current merits of add_path(), we don't really care where the
> partial aggregation is placed within the path tree.
>
> I can take up the idea of GroupPathInfo again. Before I start
> implementing it (which is not trivial), I'd like to hear others'
> thoughts on this approach - whether it's necessary and whether this is
> the right direction to pursue.

Yes, I would, too. Tom, do you have any thoughts on this point? Anybody else?

An advantage of this approach could be that it would avoid any
explosion in the number of RelOptInfo structures, since presumably all
the partially aggregated paths could be attached to the same
RelOptInfo as the unaggregated paths, just with a GroupPathInfo to
mark them as partially aggregated. I have to admit that I'm not sure
it was the right idea to mix parameterized and unparameterized paths
in the same path list, and I'm even less sure that it would be a good
idea to mix in partially-aggregated paths. That's because a
parameterized path behaves like a regular path with a join
order/method restriction: as long as we only create valid joins from
parameterized paths, we'll eventually end up with unparameterized
paths without doing anything else. A partially aggregated path behaves
more like a partial path, which requires a Gather or Gather Merge node
to terminate parallelism. Likewise, a partially aggregated path will
require a FinalizeAggregate step to complete the aggregation. Maybe
that's the wrong way of thinking about it, though, since the
FinalizeAggregate node must (I think) go at the top of the join tree,
whereas a Gather can go anywhere.

I felt it best when implementing parallel query to put partial paths
into a separate list, rather than mixing them into the regular path
list. I am vaguely under the impression that Tom thinks that was a
poor decision on my part. And I can sort of see that there is a
problem brewing here. If we handled this case like that one, then we'd
go from 2 lists to 4: normal paths, paths needing a FinalizeAggregate,
paths needing a Gather(Merge), paths needing both. And if we handled
one more future thing in the same way, then the number of combinations
doubles again to 8. Clearly, that way lies madness. On the other hand,
there's another kind of madness in thinking that we can just stick a
whole bunch of paths that are different from each other in an
increasing number of ways into a single path list and suffer no
adverse consequences. The growing complexity of add_path() is one
fairly obvious one.

So I don't quite know which way to jump here. It now seems to me that
we have three similar features with three different designs.
Parameterization added non-comparable paths to the same path list;
parallel query added them to a different path list in the same
RelOptInfo; and this patch currently adds them a separate RelOptInfo.
That's quite a bit of diversity. Really, if we wanted to stick
strictly to the idea of paths associated with the same RelOptInfo
being directly comparable, then parameterization should have spawned a
separate RelOptInfo for each workable parameterization, but that
wasn't done, possibly (though I'm not sure) for the same reasons that
you don't want to do it here.

> Regarding whether we should use a single RelOptInfo or separate
> RelOptInfos for the same grouped relation: If we choose to separate
> the grouped paths of the same grouped relation into different
> RelOptInfos based on the location of the partial aggregation within
> the path tree, then, based on my calculation from the previous email,
> for a relation containing n base rels, we would need to create 2^(n-1)
> different RelOptInfos, not to mention that this can also lead to more
> paths. I still struggle to see how this is feasible. Could you
> please elaborate on why you believe this is a viable option?

I agree that creating an exponential number of RelOptInfos is not
going to work out well. I haven't been quite as certain as you seem to
be that it's an unavoidable reality, but maybe it is. For instance, my
intuition is that if PartialAgg(t1) JOIN t2 and PartialAgg(t1 JOIN t2)
produce very different numbers of rows, we could probably just take
the one with the smaller row count regardless of cost, because the
whole selling point of this optimization is that we reduce the number
of rows that are being fed to higher level plan nodes. I don't quite
see how it can make sense to keep a less costly path that produces
more rows on the theory that maybe it's going to work out better later
on. Why is the path cheaper, after all? It feels like the savings must
come from not reducing the row count so much, but that is a cost we're
going to have to repay at a higher plan level. Moreover, we'll be
repaying it with interest, because more rows will have filtered
through every level of plan over which we postponed partial
aggregation.

I admit it's not so clear-cut when the row counts are close. If
PartialAgg(t1 JOIN t2) JOIN t3 has a very similar to PartialAgg(t1
JOIN t3) JOIN t2, can we categorically pick whichever one has the
lower row count and forget about the other? I'm not sure. But I have
an uncomfortable feeling that if we can't, we're going to have an
explosion in the number of paths we have to generate even if we avoid
an explosion in the number of RelOptInfos we generate.

For example, consider:

SELECT ... FROM fact f, dim1, dim2, dim3, dim4
WHERE f.dim1_id = dim1.id AND f.dim2_id = dim2.id
AND f.dim3_id = dim3.id AND f.dim4_id = dim4.id
GROUP BY f.something;

Let's assume that each dimN table has PRIMARY KEY (id). Because of the
primary keys, it's only sensible to consider partial aggregation for
subsets of rels that include f; and it doesn't make sense to consider
partially aggregating after joining all 5 tables because at that point
we should just do a single-step aggregation. So, the partially
grouped-rel for {f,dim1,dim2,dim3,dim4} can contain paths generated in
15 different ways, because we can join f to any proper subset of
{dim1,dim2,dim3,dim4} before partially aggregating and then to the
remainder after partially aggregating. But that feels like we're
re-performing essentially the same join search 16 times which seems
super-expensive. I can't quite say that the work is useless or that I
have a better idea, but I guess there will be a lot of cases where all
16 join searches produce the same results, or most of them do. It
doesn't feel to me like checking through all of those possibilities is
a good expenditure of planner effort.

I took a look at the paper you linked in the original post, but
unfortunately it doesn't seem to say much about how to search the plan
space efficiently. I wonder if other systems perform a search that as
exhaustive as the one that you are proposing to perform here or
whether they apply some heuristics to limit the search space, and if
so, what those heuristics are.

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