Horton

Re: Memory-Bounded Hash Aggregation

Adam Lee <ali@pivotal.io>

View thread View on postgr.es
From: Adam Lee <ali@pivotal.io>
To: Jeff Davis <pgsql@j-davis.com>
Cc: Melanie Plageman <mplageman@pivotal.io>, pgsql-hackers@postgresql.org
Date: 2019-08-02T06:44:05Z
Lists: pgsql-hackers 
> 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.

I'm late to the party.

These two approaches both spill the input tuples, what if the skewed
groups are not encountered before the hash table fills up? The spill
files' size and disk I/O could be downsides.

Greenplum spills all the groups by writing the partial aggregate states,
reset the memory context, process incoming tuples and build in-memory
hash table, then reload and combine the spilled partial states at last,
how does this sound?

-- 
Adam Lee

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,