Re: PATCH: postpone building buckets to the end of Hash (in HashJoin)

Hi,

attached is v2 of the patch, with a bugfix and two significant improvements:

1) bugfix: forgotten memset() in ExecHashIncreaseNumBatches()

    Caused segfaults whenever we started with a single batch and then
    had to increase the number of batches.

2) 0002: postpone the batching (not just build of buckets)

    When ExecChooseHashTableSize finds out we'll probably need batching,
    we start with nbatch=1 anyway, and only switch to batching (with the
    estimated number of batches) after filling work_mem.

    This helps in two basic cases - firstly, when we do over-estimates
    we may end up doing batching even when we could do with a single
    batch (i.e. without writing to temp files at all). That's really
    expensive, and this helps with that - not entirely, because we can
    only distinguish "no batching vs. batching" case and not the number
    of batches, but that's the more interesting case anyway (the
    difference between batching with 16 or 32 batches is not large, at
    least in my experience).

    The other use case is the patch adding bloom filters, because it
    allows with properly sizing the bloom filter, which needs the number
    of distinct values. So while the filter might be sized using the
    estimated number of tuples passed to the Hash, it's likely to be
    larger than needed and thus more expensive. So sizing the bloom
    filter is crucial, and this change allows first accumulating enough
    data to estimate the size of bloom filter first. More discussion in
    the other patch.

3) 0003: eliminate the MaxAlloc limit

    Currently the size of buckets is limited my MaxAlloc, which means it
    can't exceed 512MB (assuming I've done my math correctly), which
    means ~67M buckets. This removes the MaxAlloc limit and just keeps
    the (INT_MAX/2) limit, so ~2B rows. I don't think it's worth
    extending further at this point.

    There was a discussion about this, quoting the f2fc98fb message:

       Limit the size of the hashtable pointer array to not more than
       MaxAllocSize, per reports from Kouhei Kaigai and others of
       "invalid memory alloc request size" failures.  There was
       discussion of allowing the array to get larger than that by using
       the "huge" palloc API, but so far no proof that that is actually
       a good idea, and at this point in the 9.5 cycle major changes
       from old behavior don't seem like the way to go.

    I believe the objections were correct, because it'd really waste a
    lot of memory in case of over-estimates. I do however think that
    doing (1) and (2) fixes this issue, because with those changes we
    never allocate the buckets based on the initial estimate. We pretty
    much get the exact number of buckets necessary.

I haven't done any performance testing yet (well, I did, but not
reliable enough for sharing here). I'll post more data early January,
once the machine completes other tests it's running right now.

I've also been thinking about what other optimizations might be
possible, and the one thing I'm wondering about is adding HyperLogLog
counter. The thing is that we do size buckets based on number of rows,
but that may be nonsense - to size the hash table, we actually need
number of distinct values. So when the Hash contains duplicate rows (say
10 rows for each value), we end up with only ~10% of buckets containing
any data (about 10 tuples in a list).

If we knew the number of distinct values, we could make the buckets
smaller and thus reduce the memory requirements significantly.

I mention this because the patch with bloom filters actually uses HLL to
size the bloom filters, so this would not be really introducing any new
code.


regards

--
Tomas Vondra                  http://www.2ndQuadrant.com
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services