From: Tomas Vondra <tomas.vondra@2ndquadrant.com>
To: Jeff Davis <pgsql@j-davis.com>
Cc: Adam Lee <ali@pivotal.io>
Cc: Melanie Plageman <mplageman@pivotal.io>
Cc: pgsql-hackers@postgresql.org
Subject: Re: Memory-Bounded Hash Aggregation
Date: Fri, 2 Aug 2019 17:21:23 +0200
Message-ID: <20190802152123.ichmacgx3y3x7dc3@development> (raw)
In-Reply-To: <617fea8258ba3df7bc8b21cd7f3afc219f2383d9.camel@j-davis.com>
References: <507ac540ec7c20136364b5272acbcd4574aa76ef.camel@j-davis.com>
<20190703001753.s5e5cme3ucjgeu6c@development>
<e13b52d4d8f9c10f7b58f39270213b868c99b685.camel@j-davis.com>
<20190711155520.zqipi23o3yybx7ym@development>
<9be86fc1adc315f69b8af4b379087ab451008d8a.camel@j-davis.com>
<20190802064405.GA94036@mars.local>
<617fea8258ba3df7bc8b21cd7f3afc219f2383d9.camel@j-davis.com>
On Fri, Aug 02, 2019 at 08:11:19AM -0700, Jeff Davis wrote:
>On Fri, 2019-08-02 at 14:44 +0800, Adam Lee wrote:
>> I'm late to the party.
>
>You are welcome to join any time!
>
>> 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.
>
>Let's say the worst case is that we encounter 10 million groups of size
>one first; just enough to fill up memory. Then, we encounter a single
>additional group of size 20 million, and need to write out all of those
>20 million raw tuples. That's still not worse than Sort+GroupAgg which
>would need to write out all 30 million raw tuples (in practice Sort is
>pretty fast so may still win in some cases, but not by any huge
>amount).
>
>> 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?
>
>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.
>
>It does add to the complexity though, and would only work for the
>aggregates that support serializing and combining partial states. It
>also might be a net loss to do the extra work of initializing and
>evicting a partial state if we don't have large enough groups to
>benefit.
>
>Given that the worst case isn't worse than Sort+GroupAgg, I think it
>should be left as a future optimization. That would give us time to
>tune the process to work well in a variety of cases.
>
+1 to leaving that as a future optimization
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.
regards
--
Tomas Vondra http://www.2ndQuadrant.com
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Reply to all the recipients using the --to and --cc options:
reply via email
To: pgsql-hackers@postgresql.org
Cc: tomas.vondra@2ndquadrant.com, pgsql@j-davis.com, ali@pivotal.io, mplageman@pivotal.io
Subject: Re: Memory-Bounded Hash Aggregation
In-Reply-To: <20190802152123.ichmacgx3y3x7dc3@development>
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
This inbox is served by DDX for PostgreSQL; see mirroring instructions
for how to clone and mirror all data and code used for this inbox