Re: Memory-Bounded Hash Aggregation

On Wed, 2020-02-12 at 21:51 -0800, Jeff Davis wrote:
> On Mon, 2020-02-10 at 15:57 -0800, Jeff Davis wrote:
> > Attaching latest version (combined logtape changes along with main
> > HashAgg patch).
> 
> I ran a matrix of small performance tests to look for regressions.

I ran some more tests, this time comparing Hash Aggregation to
Sort+Group.

Summary of trends:

  group key complexity : favors Hash
  group key size       : favors Hash
  group size           : favors Hash
  higher work_mem      : favors Sort[1]
  data set size        : favors Sort[1]
  number of aggregates : favors Hash[2]

  [1] I have closed the gap a bit with some post-experiment tuning.
      I have just begun to analyze this case so I think there is
      quite a bit more room for improvement.
  [2] Could use more exploration -- I don't have an explanation.

Data sets:
  t20m_1_int4: ~20 million groups of size ~1 (uniform)
  t1m_20_int4: ~1 million groups of size ~20 (uniform)
  t1k_20k_int4: ~1k groups of size ~20k (uniform)

  also, text versions of each of those with collate "C.UTF-8"

Results:

1. A general test to vary the group size, key type, and work_mem.

Query:
  select i from $TABLE group by i offset 100000000;

work_mem='4MB'

+----------------+----------+-------------+--------------+
|                | sort(ms) | hashagg(ms) | sort/hashagg |
+----------------+----------+-------------+--------------+
| t20m_1_int4    |   11852  |      10640  |         1.11 |
| t1m_20_int4    |   11108  |       8109  |         1.37 |
| t1k_20k_int4   |    8575  |       2732  |         3.14 |
| t20m_1_text    |   80463  |      12902  |         6.24 |
| t1m_20_text
|   58586  |       9252  |         6.33 |
| t1k_20k_text   |   21781  | 
5739  |         3.80 |
+----------------+----------+-------------+----
----------+

work_mem='32MB'

+----------------+----------+-------------+--------------+
|                | sort(ms) | hashagg(ms) | sort/hashagg |
+----------------+----------+-------------+--------------+
| t20m_1_int4    |    9656  |      11702  |         0.83 |
| t1m_20_int4    |    8870  |       9804  |         0.90 |
| t1k_20k_int4   |    6359  |       1852  |         3.43 |
| t20m_1_text    |   74266  |      14434  |         5.15 |
| t1m_20_text    |   56549  |      10180  |         5.55 |
| t1k_20k_text   |   21407  |       3989  |         5.37 |
+----------------+----------+-------------+--------------+

2. Test group key size

data set:
   20m rows, four int4 columns.
   Columns a,b,c are all the constant value 1, forcing each
   comparison to look at all four columns.

Query: select a,b,c,d from wide group by a,b,c,d offset 100000000;

  work_mem='4MB'
  Sort         : 30852ms
  HashAgg      : 12343ms
  Sort/HashAgg : 2.50

In theory, if the first grouping column is highly selective, then Sort
may have a slight advantage because it can look at only the first
column, while HashAgg needs to look at all 4. But HashAgg only needs to
perform this calculation once and it seems hard enough to show this in
practice that I consider it an edge case. In "normal" cases, it appears
that more grouping columns significantly favors Hash Agg.

3. Test number of aggregates

Data Set: same as for test #2 (group key size).

Query: select d, count(a),sum(b),avg(c),min(d)
       from wide group by d offset 100000000;

  work_mem='4MB'
  Sort         : 22373ms
  HashAgg      : 17338ms
  Sort/HashAgg : 1.29

I don't have an explanation of why HashAgg is doing better here. Both
of them are using JIT and essentially doing the same number of
advancements. This could use more exploration, but the effect isn't
major.

4. Test data size

Data 400 million rows of four random int8s. Group size of one.

Query: select a from t400m_1_int8 group by a offset 1000000000;

  work_mem='32MB'
  Sort         : 300675ms
  HashAgg      : 560740ms
  Sort/HashAgg : 0.54

I tried increasing the max number of partitions and brought the HashAgg
runtime down to 481985 (using 1024 partitions), which closes the gap to
0.62. That's not too bad for HashAgg considering this is a group size
of one with a simple group key. A bit more tuning might be able to
close the gap further.

Conclusion:

HashAgg is winning in a lot of cases, and this will be an important
improvement for many workloads. Not only is it faster in a lot of
cases, but it's also less risky. When an input has unknown group size,
it's much easier for the planner to choose HashAgg -- a small downside
and a big upside.

Regards,
    Jeff Davis