You are viewing a plain text version of this content. The canonical link for it is here.
Posted to issues-all@impala.apache.org by "Riza Suminto (Jira)" <ji...@apache.org> on 2020/03/19 19:35:00 UTC
[jira] [Assigned] (IMPALA-9434) Implement / Evaluate Robin Hood
Hashing for exec/hash-table.h
[ https://issues.apache.org/jira/browse/IMPALA-9434?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Riza Suminto reassigned IMPALA-9434:
------------------------------------
Assignee: Riza Suminto
> 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: issues-all-unsubscribe@impala.apache.org
For additional commands, e-mail: issues-all-help@impala.apache.org