[
https://issues.apache.org/jira/browse/IMPALA-9434?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=17062933#comment-17062933
]
Joe McDonnell commented on IMPALA-9434:
---------------------------------------
[~rizaon] Glad to hear it!
Here are some resources that describe Robin Hood hashing in greater detail:
[https://andre.arko.net/2017/08/24/robin-hood-hashing/] - links to lots of good
posts
[https://www.sebastiansylvan.com/post/robin-hood-hashing-should-be-your-default-hash-table-implementation/]
[https://www.lewuathe.com/robin-hood-hashing-experiment.html] - This has a good
example of insertion behavior
When I was looking at code, insert was going to need to change fundamentally,
and it can't use Probe() to find the right index like it does now (
[https://github.com/apache/impala/blob/master/be/src/exec/hash-table.inline.h#L100]
).
> Implement / Evaluate Robin Hood Hashing for exec/hash-table.h
> -------------------------------------------------------------
>
> Key: IMPALA-9434
> URL: https://issues.apache.org/jira/browse/IMPALA-9434
> Project: IMPALA
> Issue Type: Improvement
> Components: Backend
> Affects Versions: Impala 3.4.0
> Reporter: Joe McDonnell
> Assignee: Riza Suminto
> Priority: Minor
> Labels: ramp-up
>
> exec/hash-table.h's HashTable currently implements an open addressing hash
> table with linear and quadratic probing. Since there are few guarantees about
> the probe length, we limit the load factor to 0.75 to avoid high probe
> lengths. In general, probe lengths increase severely as the load factor goes
> higher than that.
> Robin Hood Hashing reduces the variances of probe lengths by continually
> rebalancing elements. It steals from the "rich" elements that have a very
> short probe length and gives to the "poor" elements with a long probe length.
> This tighter guarantee about the probe length allows for a higher load factor
> (0.9).
> We should evaluate Robin Hood Hashing to see if it improves our hash table
> performance. Since this hash table does not support deletes, that reduces the
> complexity. The Bucket already has some unused bytes in case we need them.
--
This message was sent by Atlassian Jira
(v8.3.4#803005)
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
