Joe McDonnell created IMPALA-15718:
--------------------------------------
Summary: Investigate pushing the hash into the tagged ptr for
PHJ's hash table
Key: IMPALA-15718
URL: https://issues.apache.org/jira/browse/IMPALA-15718
Project: IMPALA
Issue Type: Improvement
Components: Backend
Affects Versions: Impala 5.0.0
Reporter: Joe McDonnell
The hash table has two arrays: one for the buckets and one for the hashes. The
buckets are tagged pointers with 8 bytes per bucket. The hashes are 4 bytes.
This is 12 bytes per bucket. Each access compares the lookup hash with the hash
for that bucket index, then if that matches, it accesses the tagged ptr for an
equality check on the tuple.
For the hash join, we know the number of rows up front and size the hash table
to handle it. There are no resizes. For this case, 4 bytes for the hash is
excessive. We've already used parts of the hash to pick the partition and get
to the bucket, so they don't hold additional entropy. There are also
diminishing returns to storing more hash bits. Storing one byte of hash
eliminates 99.96% of collisions (255/256). Going to 2 bytes is only going from
99.61% to 99.998% and doubles the memory. 4 bytes is pointless.
The tagger pointer implementation assumes that we could run on a system with 57
bit addresses (5-level page tables). This typically does not happen. (Risk
area: If this does start to happen, this code would need to detect that and
avoid this implementation.) Machines use 4-level page tables with 48-bit
addresses. This means that there are 16 bits available in the tagged ptr. We
use a couple of them today, but there are about 14 bits available to store a
hash.
If we fold several hash bits into the tagged ptr, we can avoid the separate
array of hashes. That reduces the memory footprint from 12 bytes to 8 bytes. It
also avoids an extra cache line access for the hashes array.
There are other approaches for speeding up the hash table (and we should do
more testing with those other methods), but this is a fairly simple win for
hash joins. This doesn't apply to the grouping agg, because it does resizes and
would benefit from having the whole hash available.
--
This message was sent by Atlassian Jira
(v10.3.26#10030026)
