Re: Spilling hashed SetOps and aggregates to disk

On Mon, Jun 11, 2018 at 1:50 PM, Jeff Davis <pgsql(at)j-davis(dot)com> wrote:
> I think average group size is the wrong way to look at it, because
> averages are only useful for a normal distribution. The two most
> interesting cases are:
>
> 1. Fairly uniform group size (e.g. normal dist)
> 2. Skew values, power law distribution, etc., where some groups are
> very large and most are tiny by comparison. I am calling the very large
> groups "skewed groups".

I wasn't using the term "average" in a mathematical sense. I suppose
I really meant "typical". I agree that thinking about cases where the
group size is nonuniform is a good idea, but I don't think I agree
that all uniform distributions are created equal. Uniform
distributions with 1 row per group are very different than uniform
distributions with 1000 rows per group.

> If we get the skewed groups into the hash table, and avoid OOM, I think
> that is a success. My patch did that, except it didn't account for two
> cases:
>
> (a) clustered input, where skewed groups may not appear until the
> hash table is already full; and
> (b) variable-sized transition values that grow with the group size

I think that many of the algorithms under consideration could be
implemented without worrying about variable-sized transition values,
and then the approach could be extended later. However, whether or
not a given algorithm can handle clustered input seems like a fairly
basic property of the algorithm. I don't think we should set the bar
too high because no algorithm is going to be perfect in every case; at
the same time, clustered input is pretty common in real-world
scenarios, and an algorithm that handles such cases better has a
significant leg up over one that can't, all other things being equal.
I'm not sure I remember precisely what your proposal was any more.

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company