drill-issues mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "ASF GitHub Bot (JIRA)" <j...@apache.org>
Subject [jira] [Commented] (DRILL-4237) Skew in hash distribution
Date Tue, 15 Mar 2016 18:52:33 GMT

    [ https://issues.apache.org/jira/browse/DRILL-4237?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=15195956#comment-15195956

ASF GitHub Bot commented on DRILL-4237:

GitHub user chunhui-shi opened a pull request:


    DRILL-4237 DRILL-4478 fully implement hash to use murmur3 and corresp…

    Since we have to have our own implementations of hash functions, UNIT tests should guarantee
the correctness of implementation. Due to hash function is critical to distributed SQL engine's
performance, make changes to allow future adding/testing new hash function to be smooth.
    1, Implement Murmur3 to work on DrillBuf and long(double), both avoid object or extra
buffer creation.
    2, fix xxHash
    3, Point hash functions in hash32, hash64, hash32AsDouble and hash64AsDouble to HashHelper.hash32|64
    4, Test Correctness of the hash functions by comparing with original c implementation's
generated hash results. 
    Testing vectors are generated from https://github.com/chunhui-shi/smhasher by running
these commands after build:
    gethash Murmur3F --json=MurmurHash3
    gethash xxHash64 --json=XXHash
    5, Adding tests to cover Hash**WithSeed.
    6, Fix DRILL-4478 which prevent binar_string function working correctly.

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:


To close this pull request, make a commit to your master/trunk branch
with (at least) the following in the commit message:

    This closes #430
commit 2210279618dee857df32f28c647ee8ec8409a44a
Author: chunhui-shi <cshi@maprtech.com>
Date:   2016-03-15T17:36:54Z

    DRILL-4237 DRILL-4478 fully implement hash to use murmur3 and correspondent unit tests


> 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
> +-----------------------------------+--------------+
> |              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
> 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

View raw message