Horton

Re: Memory-Bounded Hash Aggregation

Taylor Vesely <tvesely@pivotal.io>

View thread View on postgr.es
From: Taylor Vesely <tvesely@pivotal.io>
To: Tomas Vondra <tomas.vondra@2ndquadrant.com>
Cc: Jeff Davis <pgsql@j-davis.com>, Adam Lee <ali@pivotal.io>, Melanie Plageman <mplageman@pivotal.io>, pgsql-hackers@postgresql.org
Date: 2019-08-28T19:52:13Z
Lists: pgsql-hackers

Attachments

I started to review this patch yesterday with Melanie Plageman, so we
rebased this patch over the current master. The main conflicts were
due to a simplehash patch that has been committed separately[1]. I've
attached the rebased patch.

I was playing with the code, and if one of the table's most common
values isn't placed into the initial hash table it spills a whole lot
of tuples to disk that might have been avoided if we had some way to
'seed' the hash table with MCVs from the statistics. Seems to me that
you would need some way of dealing with values that are in the MCV
list, but ultimately don't show up in the scan. I imagine that this
kind of optimization would most useful for aggregates on a full table
scan.

Some questions:

Right now the patch always initializes 32 spill partitions. Have you given
any thought into how to intelligently pick an optimal number of
partitions yet?

> That can be done as an add-on to approach #1 by evicting the entire
> Hash table (writing out the partial states), then resetting the memory
> Context.

By add-on approach, do you mean to say that you have something in mind
to combine the two strategies? Or do you mean that it could be implemented
as a separate strategy?

> I think it's clear there's no perfect eviction strategy - for every
> algorithm we came up with we can construct a data set on which it
> performs terribly (I'm sure we could do that for the approach used by
> Greenplum, for example).
>
> So I think it makes sense to do what Jeff proposed, and then maybe try
> improving that in the future with a switch to different eviction
> strategy based on some heuristics.

I agree. It definitely feels like both spilling strategies have their
own use case.

That said, I think it's worth mentioning that with parallel aggregates
it might actually be more useful to spill the trans values instead,
and have them combined in a Gather or Finalize stage.

[1]
https://www.postgresql.org/message-id/flat/48abe675e1330f0c264ab2fe0d4ff23eb244f9ef.camel%40j-davis.com

Commits

  1. Fix costing for disk-based hash aggregation.

  2. Fixes for Disk-based Hash Aggregation.

  3. Disk-based Hash Aggregation.

  4. Extend ExecBuildAggTrans() to support a NULL pointer check.

  5. Save calculated transitionSpace in Agg node.

  6. Minor refactor of nodeAgg.c.

  7. Logical Tape Set: lazily allocate read buffer.

  8. Introduce TupleHashTableHash() and LookupTupleHashEntryHash().

  9. Logical Tape Set: use min heap for freelist.

  10. Fix comments in execGrouping.c

  11. Avoid integer overflow while sifting-up a heap in tuplesort.c.

  12. Make the overflow guards in ExecChooseHashTableSize be more protective.

  13. Improve performance of our private version of qsort. Per recent testing,