Re: tweaking NTUP_PER_BUCKET

On 8 Červenec 2014, 16:16, Robert Haas wrote:
> On Tue, Jul 8, 2014 at 9:35 AM, Tomas Vondra <tv@fuzzy.cz> wrote:
>> Maybe. I'm not against setting NTUP_PER_BUCKET=1, but with large outer
>> relations it may be way cheaper to use higher NTUP_PER_BUCKET values
>> instead of increasing the number of batches (resulting in repeated scans
>> of the outer table). I think it's important (but difficult) to keep
>> these
>> things somehow balanced.
>
> Right, I think that's clear.  I'm just pointing out that you get to
> decide: you can either start with a larger NTUP_PER_BUCKET and then
> reduce it if you enough memory left, or you can start with a smaller
> NTUP_PER_BUCKET and then increase it if you run short of memory.

I don't think those two approaches are equal.

With the approach I took, I can use a compromise value (NTUP=4) initially,
and only resize the hash table once at the end (while keeping the amount
of memory under work_mem all the time).

With the "NTUP=1 and increase in case of memory pressure" you have to
shrink the table immediately (to fit into work_mem), and if the hash table
gets split into multiple batches you're suddenly in a situation with lower
memory pressure and you may need to increase it again.

>>> Yet another idea is to stick with your scheme, but do the dynamic
>>> bucket splits lazily.  Set a flag on each bucket indicating whether or
>>> not it needs a lazy split.  When someone actually probes the hash
>>> table, if the flag is set for a particular bucket, move any tuples
>>> that don't belong as we scan the bucket.  If we reach the end of the
>>> bucket chain, clear the flag.
>>
>> I don't think a lazy scheme makes much sense here. There are two clearly
>> separated phases - loading the table and search.
>>
>> Also, it seems to me it can't work as described. Say we build a table
>> and
>> then find out we need a table 4x the size. If I understand your proposal
>> correctly, you'd just resize buckets array, copy the existing buckets
>> (first 1/4 buckets) and set 'needs_split' flags. Correct?
>>
>> Well, the problem is that while scanning a bucket you already need to
>> know
>> which tuples belong there. But with the lazy approach, the tuples might
>> still be in the old (not yet split) buckets. So you'd have to search the
>> current bucket and all buckets that were not split yet. Or did I miss
>> something?
>
> If you have, say, bucket 0..63 and you decide to change it to buckets
> 0..255, then any tuple that isn't in bucket N has to be in bucket N %
> 64.  More generally, any time you expand or contract by a power of two
> it's pretty easy to figure out where tuples have to go.

OK.

> But even if you do something that's not a power of two, like say a 10x
> compaction of the buckets, there's still only two buckets that can
> contain any particular hash value.  If the hash value is H, the old
> number of buckets is O, and the new number of buckets is N, then the
> tuple has got to be in bucket H % O or bucket H % N.  If bucket H % O
> doesn't have the needs-split flag set, then it must be in H % N (if it
> exists at all).

I wonder if this is really worth the effort - my guess is it's efficient
only if large portion of buckets is not visited (and thus does not need to
be split) at all. Not sure how common that is (our workloads certainly are
not like that).

regards
Tomas