[
https://issues.apache.org/jira/browse/HIVE-20624?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=16624893#comment-16624893
]
Gopal V commented on HIVE-20624:
--------------------------------
There is one slightly complicated way to do this without reallocating the
original hash probe arrays - but by doing bucketing in a slightly strange way.
Beyond 4M entries in a single hash table, it is better to bucket the actual
probe array out, though it is not memory efficient to pre-bucket them into
n-hashtables (like what the hybrid grace did).
So instead of rehashing the entire hashtable, you can "add a bucket" and only
move the entries which fall out of a bucket, but make that movement minimal
during rehashing (i.e the entries which are removed are swapped out with the
new bucket).
To be very specific, the approach is only necessary when the hashtable is
oversized and not when it has less than 4M items, so after 4M items have been
added, the next step is to add another smaller probe array & move everything
from bucket 0 -> bucket 1 that swapped places (there's no data in bucket 1 to
move backwards).
The next rehash is more complicated, because it needs to potentially swap items
from bucket 0 to 1 and back, after moving new items to bucket 2 from both,
which needs to make sure that enough data moves into the new bucket when
rebucketing.
Because we have sequential bucketing here, there is a neat google algorithm to
fall back up on (here's the code in Golang for JumpHash).
{code}
func Hash(key uint64, numBuckets int) int32 {
var b int64 = -1
var j int64
for j < int64(numBuckets) {
b = j
key = key*2862933555777941757 + 1
j = int64(float64(b+1) *
(float64(int64(1)<<31) / float64((key>>33)+1)))
}
return int32(b)
}
{code}
> Vectorization: Fast Hash table should not double after certain size, instead
> should grow
> ----------------------------------------------------------------------------------------
>
> Key: HIVE-20624
> URL: https://issues.apache.org/jira/browse/HIVE-20624
> Project: Hive
> Issue Type: Bug
> Components: Vectorization
> Reporter: Gopal V
> Priority: Major
>
> The reason to use Power of two is to simplify the inner loop for the hash
> function, but this is a significant memory issue when dealing with somewhat
> larger hashtables like the customer or customer_address hashtables in TPC-DS.
> This doubling is pretty bad when the hashtable load-factor is 0.75 and the
> expected key count is 65M (for customer/customer_address)
> {code}
> long worstCaseNeededSlots = 1L << DoubleMath.log2(numRows /
> hashTableLoadFactor, RoundingMode.UP);
> {code}
> That estimate is actually matching the actual impl, but after acquiring 65M
> items in a single array, the rehashing will require a temporary growth to
> 65+128 while the rehash is in progress, all to fit exactly 65 back into it.
> Fixing the estimate to match the implementation produced a number of
> regressions in query runtimes, though the part that needs fixing is the
> doubling implementation.
> The obvious solution is to add 4M more everytime and use a modulo function or
> the Lemire's multiply + shift operation[1], but more on that in comments.
--
This message was sent by Atlassian JIRA
(v7.6.3#76005)
