Re: Memory-Bounded Hash Aggregation

Hi Jeff,

On Mon, Jul 01, 2019 at 12:13:53PM -0700, Jeff Davis wrote:
>This is for design review. I have a patch (WIP) for Approach 1, and if
>this discussion starts to converge on that approach I will polish and
>post it.
>

Thanks for working on this.

>Let's start at the beginning: why do we have two strategies -- hash
>and sort -- for aggregating data? The two are more similar than they
>first appear. A partitioned hash strategy writes randomly among the
>partitions, and later reads the partitions sequentially; a sort will
>write sorted runs sequentially, but then read the among the runs
>randomly during the merge phase. A hash is a convenient small
>representation of the data that is cheaper to operate on; sort uses
>abbreviated keys for the same reason.
>

What does "partitioned hash strategy" do? It's probably explained in one
of the historical discussions, but I'm not sure which one. I assume it
simply hashes the group keys and uses that to partition the data, and then
passing it to hash aggregate.

>Hash offers:
>
>* Data is aggregated on-the-fly, effectively "compressing" the amount
> of data that needs to go to disk. This is particularly important
> when the data contains skewed groups (see below).
>
>* Can output some groups after the first pass of the input data even
> if other groups spilled.
>
>* Some data types only support hashing; not sorting.
>
>Sort+Group offers:
>
>* Only one group is accumulating at once, so if the transition state
> grows (like with ARRAY_AGG), it minimizes the memory needed.
>
>* The input may already happen to be sorted.
>
>* Some data types only support sorting; not hashing.
>
>Currently, Hash Aggregation is only chosen if the optimizer believes
>that all the groups (and their transition states) fit in
>memory. Unfortunately, if the optimizer is wrong (often the case if the
>input is not a base table), the hash table will
>keep growing beyond work_mem, potentially bringing the entire system
>to OOM. This patch fixes that problem by extending the Hash
>Aggregation strategy to spill to disk when needed.
>

OK, makes sense.

>Previous discussions:
>
>
>https://www.postgresql.org/message-id/1407706010.6623.16.camel@jeff-desktop
>
>https://www.postgresql.org/message-id/1419326161.24895.13.camel%40jeff-desktop
>
>https://www.postgresql.org/message-id/87be3bd5-6b13-d76e-5618-6db0a4db584d%40iki.fi
>
>A lot was discussed, which I will try to summarize and address here.
>
>Digression: Skewed Groups:
>
>Imagine the input tuples have the following grouping keys:
>
> 0, 1, 0, 2, 0, 3, 0, 4, ..., 0, N-1, 0, N
>
>Group 0 is a skew group because it consists of 50% of all tuples in
>the table, whereas every other group has a single tuple. If the
>algorithm is able to keep group 0 in memory the whole time until
>finalized, that means that it doesn't have to spill any group-0
>tuples. In this example, that would amount to a 50% savings, and is a
>major advantage of Hash Aggregation versus Sort+Group.
>

Right. I agree efficiently handling skew is important and may be crucial
for achieving good performance.

>High-level approaches:
>
>1. When the in-memory hash table fills, keep existing entries in the
>hash table, and spill the raw tuples for all new groups in a
>partitioned fashion. When all input tuples are read, finalize groups
>in memory and emit. Now that the in-memory hash table is cleared (and
>memory context reset), process a spill file the same as the original
>input, but this time with a fraction of the group cardinality.
>
>2. When the in-memory hash table fills, partition the hash space, and
>evict the groups from all partitions except one by writing out their
>partial aggregate states to disk. Any input tuples belonging to an
>evicted partition get spilled to disk. When the input is read
>entirely, finalize the groups remaining in memory and emit. Now that
>the in-memory hash table is cleared, process the next partition by
>loading its partial states into the hash table, and then processing
>its spilled tuples.
>
>3. Use some kind of hybrid[1][2] of hashing and sorting.
>

Unfortunately the second link does not work :-(

>Evaluation of approaches:
>
>Approach 1 is a nice incremental improvement on today's code. The
>final patch may be around 1KLOC. It's a single kind of on-disk data
>(spilled tuples), and a single algorithm (hashing). It also handles
>skewed groups well because the skewed groups are likely to be
>encountered before the hash table fills up the first time, and
>therefore will stay in memory.
>

I'm not going to block Approach 1, althought I'd really like to see
something that helps with array_agg.

>Approach 2 is nice because it resembles the approach of Hash Join, and
>it can determine whether a tuple should be spilled without a hash
>lookup. Unfortunately, those upsides are fairly mild, and it has
>significant downsides:
>
>* It doesn't handle skew values well because it's likely to evict
> them.
>
>* If we leave part of the hash table in memory, it's difficult to
> ensure that we will be able to actually use the space freed by
> eviction, because the freed memory may be fragmented. That could
> force us to evict the entire in-memory hash table as soon as we
> partition, reducing a lot of the benefit of hashing.
>

Yeah, and it may not work well with the memory accounting if we only track
the size of allocated blocks, not chunks (because pfree likely won't free
the blocks).

>* It requires eviction for the algorithm to work. That may be
> necessary for handling cases like ARRAY_AGG (see below) anyway, but
> this approach constrains the specifics of eviction.
>
>Approach 3 is interesting because it unifies the two approaches and
>can get some of the benfits of both. It's only a single path, so it
>avoids planner mistakes. I really like this idea and it's possible we
>will end up with approach 3. However:
>
>* It requires that all data types support sorting, or that we punt
> somehow.
>
>* Right now we are in a weird state because hash aggregation cheats,
> so it's difficult to evaluate whether Approach 3 is moving us in the
> right direction because we have no other correct implementation to
> compare against. Even if Approach 3 is where we end up, it seems
> like we should fix hash aggregation as a stepping stone first.
>

Aren't all three approaches a way to "fix" hash aggregate? In any case,
it's certainly reasonable to make incremental changes. The question is
whether "approach 1" is sensible step towards some form of "approach 3"

>* It means we have a hash table and sort running concurrently, each
> using memory. Andres said this might not be a problem[3], but I'm
> not convinced that the problem is zero. If you use small work_mem
> for the write phase of sorting, you'll end up with a lot of runs to
> merge later and that has some kind of cost.
>

Why would we need to do both concurrently? I thought we'd empty the hash
table before doing the sort, no?

>* The simplicity might start to evaporate when we consider grouping
> sets and eviction strategy.
>

Hmm, yeah :-/

>Main topics to consider:
>
>ARRAY_AGG:
>
>Some aggregates, like ARRAY_AGG, have a transition state that grows
>proportionally with the group size. In other words, it is not a
>summary like COUNT or AVG, it contains all of the input data in a new
>form.
>

Strictly speaking the state may grow even for count/avg aggregates, e.g.
for numeric types, but it's far less serious than array_agg etc.

>These aggregates are not a good candidate for hash aggregation. Hash
>aggregation is about keeping many transition states running in
>parallel, which is just a bad fit for large transition states. Sorting
>is better because it advances one transition state at a time. We could:
>
>* Let ARRAY_AGG continue to exceed work_mem like today.
>
>* Block or pessimize use of hash aggregation for such aggregates.
>
>* Evict groups from the hash table when it becomes too large. This
> requires the ability to serialize and deserialize transition states,
> and some approaches here might also need combine_func
> specified. These requirements seem reasonable, but we still need
> some answer of what to do for aggregates that grow like ARRAY_AGG
> but don't have the required serialfunc, deserialfunc, or
> combine_func.
>

Do we actually need to handle that case? How many such aggregates are
there? I think it's OK to just ignore that case (and keep doing what we do
now), and require serial/deserial functions for anything better.

>GROUPING SETS:
>
>With grouping sets, there are multiple hash tables and each hash table
>has it's own hash function, so that makes partitioning more
>complex. In Approach 1, that means we need to either (a) not partition
>the spilled tuples; or (b) have a different set of partitions for each
>hash table and spill the same tuple multiple times. In Approach 2, we
>would be required to partition each hash table separately and spill
>tuples multiple times. In Approach 3 (depending on the exact approach
>but taking a guess here) we would need to add a set of phases (one
>extra phase for each hash table) for spilled tuples.
>

No thoughts about this yet.

>MEMORY TRACKING:
>
>I have a patch to track the total allocated memory by
>incrementing/decrementing it when blocks are malloc'd/free'd. This
>doesn't do bookkeeping for each chunk, only each block. Previously,
>Robert Haas raised some concerns[4] about performance, which were
>mitigated[5] but perhaps not entirely eliminated (but did become
>elusive).
>
>The only alternative is estimation, which is ugly and seems like a bad
>idea. Memory usage isn't just driven by inputs, it's also driven by
>patterns of use. Misestimates in the planner are fine (within reason)
>because we don't have any other choice, and a small-factor misestimate
>might not change the plan anyway. But in the executor, a small-factor
>misestimate seems like it's just not doing the job. If a user found
>that hash aggregation was using 3X work_mem, and my only explanation
>is "well, it's just an estimate", I would be pretty embarrassed and
>the user would likely lose confidence in the feature. I don't mean
>that we must track memory perfectly everywhere, but using an estimate
>seems like a mediocre improvement of the current state.

I agree estimates are not the right tool here.

>
>We should proceed with memory context tracking and try to eliminate or
>mitigate performance concerns. I would not like to make any hurculean
>effort as a part of the hash aggregation work though; I think it's
>basically just something a memory manager in a database system should
>have supported all along. I think we will find other uses for it as
>time goes on. We have more and more things happening in the executor
>and having a cheap way to check "how much memory is this thing using?"
>seems very likely to be useful.
>

IMO we should just use the cheapest memory accounting (tracking the amount
of memory allocated for blocks). I agree it's a feature we need, I don't
think we can devise anything cheaper than this.

>Other points:
>
>* Someone brought up the idea of using logtapes.c instead of writing
> separate files for each partition. That seems reasonable, but it's
> using logtapes.c slightly outside of its intended purpose. Also,
> it's awkward to need to specify the number of tapes up-front. Worth
> experimenting with to see if it's a win.
>
>* Tomas did some experiments regarding the number of batches to choose
> and how to choose them. It seems like there's room for improvement
> over ths simple calculation I'm doing now.
>

Me? I don't recall such benchmarks, but maybe I did. But I think we'll
need to repeat those with the new patches etc. I think the question is
whether we see this as an emergency solution - in that case I wouldn't
obsess about getting the best possible parameters.

>* A lot of discussion about a smart eviction strategy. I don't see
> strong evidence that it's worth the complexity at this time. The
> smarter we try to be, the more bookkeeping and memory fragmentation
> problems we will have. If we evict something, we should probably
> evict the whole hash table or some large part of it.
>

Maybe. For each "smart" eviction strategy there is a (trivial) example
of data on which it performs poorly.

I think it's the same thing as with the number of partitions - if we
consider this to be an emergency solution, it's OK if the performance is
not entirely perfect when it kicks in.

regards

--
Tomas Vondra http://www.2ndQuadrant.com
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services