[
https://issues.apache.org/jira/browse/DRILL-4237?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=15246797#comment-15246797
]
ASF GitHub Bot commented on DRILL-4237:
---------------------------------------
GitHub user chunhui-shi opened a pull request:
https://github.com/apache/drill/pull/485
DRILL-4237: Implement murmur3 for HashHelper
Unit Test was removed from this commit. Test codes and the the test vector
generator program will be included in functional tests in a separate checkin.
While implementing hash function instead of inventing a hash function, one
thing need to emphasize is, in these well tested and widely accepted
algorithms, all parameters and steps to shuffle are carefully designed and
tested by the inventors and the community(e.g. smhasher). It is not just
generating 'random' result from 'random' input. So each implementations of the
algorithm should prove their complete correctness by testing with the same
standard as I am doing here: cover all code paths(in murmurhash and xxhash
cases, it is all possible input lengths that may go through different code
paths, and sign/unsign cases).
You can merge this pull request into a Git repository by running:
$ git pull https://github.com/chunhui-shi/drill hash
Alternatively you can review and apply these changes as the patch at:
https://github.com/apache/drill/pull/485.patch
To close this pull request, make a commit to your master/trunk branch
with (at least) the following in the commit message:
This closes #485
----
commit 0eb01aab364137058d8ec5e62d7aa53278d0f842
Author: chunhui-shi <c...@maprtech.com>
Date: 2016-03-15T17:36:54Z
DRILL-4237 DRILL-4478 fully implement hash to use murmur3 and correspondent
unit tests
Change hash to direct call. Address other code style comment.
Clean up tests. Add or correct comments.
Move correctness test routines out of this commit
DRILL-4237 DRILL-4478 fully implement hash to use murmur3 and correspondent
unit tests
Change hash to direct call. Address other code style comment.
Clean up tests. Add or correct comments.
Move correctness test routines out of this commit
----
> Skew in hash distribution
> -------------------------
>
> Key: DRILL-4237
> URL: https://issues.apache.org/jira/browse/DRILL-4237
> Project: Apache Drill
> Issue Type: Bug
> Components: Functions - Drill
> Affects Versions: 1.4.0
> Reporter: Aman Sinha
> Assignee: Chunhui Shi
>
> Apparently, the fix in DRILL-4119 did not fully resolve the data skew issue.
> It worked fine on the smaller sample of the data set but on another sample of
> the same data set, it still produces skewed values - see below the hash
> values which are all odd numbers.
> {noformat}
> 0: jdbc:drill:zk=local> select columns[0], hash32(columns[0]) from `test.csv`
> limit 10;
> +-----------------------------------+--------------+
> | EXPR$0 | EXPR$1 |
> +-----------------------------------+--------------+
> | f71aaddec3316ae18d43cb1467e88a41 | 1506011089 |
> | 3f3a13bb45618542b5ac9d9536704d3a | 1105719049 |
> | 6935afd0c693c67bba482cedb7a2919b | -18137557 |
> | ca2a938d6d7e57bda40501578f98c2a8 | -1372666789 |
> | fab7f08402c8836563b0a5c94dbf0aec | -1930778239 |
> | 9eb4620dcb68a84d17209da279236431 | -970026001 |
> | 16eed4a4e801b98550b4ff504242961e | 356133757 |
> | a46f7935fea578ce61d8dd45bfbc2b3d | -94010449 |
> | 7fdf5344536080c15deb2b5a2975a2b7 | -141361507 |
> | b82560a06e2e51b461c9fe134a8211bd | -375376717 |
> +-----------------------------------+--------------+
> {noformat}
> This indicates an underlying issue with the XXHash64 java implementation,
> which is Drill's implementation of the C version. One of the key difference
> as pointed out by [~jnadeau] was the use of unsigned int64 in the C version
> compared to the Java version which uses (signed) long. I created an XXHash
> version using com.google.common.primitives.UnsignedLong. However,
> UnsignedLong does not have bit-wise operations that are needed for XXHash
> such as rotateLeft(), XOR etc. One could write wrappers for these but at
> this point, the question is: should we think of an alternative hash function
> ?
> The alternative approach could be the murmur hash for numeric data types that
> we were using earlier and the Mahout version of hash function for string
> types
> (https://github.com/apache/drill/blob/master/exec/java-exec/src/main/java/org/apache/drill/exec/expr/fn/impl/HashHelper.java#L28).
> As a test, I reverted to this function and was getting good hash
> distribution for the test data.
> I could not find any performance comparisons of our perf tests (TPC-H or DS)
> with the original and newer (XXHash) hash functions. If performance is
> comparable, should we revert to the original function ?
> As an aside, I would like to remove the hash64 versions of the functions
> since these are not used anywhere.
--
This message was sent by Atlassian JIRA
(v6.3.4#6332)
