apache / apache/doris

[Enhancement] XXHASH_128 Implememtation to Prevent Hash Collision

Open
#66,704 1 comment 1 reaction 0 assignees View on GitHub
Dominant language
Java
Stars
15.9k
Forks
3.9k
Avg merge
2d 23h
Merged PRs (30d)
520

Description

### Search before asking

- [x] I had searched in the [issues](https://github.com/apache/doris/issues?q=is%3Aissue) and found no similar issues.

### Description

I'm attempting to do duplicate analysis by hashing several fields and storing the hash. If the hash already exists then the item is determined as a duplicate.

Using XXHash_64 results in a hash collision chance of ~93% with 10 billion items (based on this calculator https://kevingal.com/apps/collision.html).

I could use another hash function such as MD5 or SHA. In the case of MD5 it's much slower and would effect performance. In the case of SHA I would need to store the hash as a string as the largest integer type is 128 bits, which prevents me from using the hash column as a key.

From what I can see implementing a XXHASH_128 function would be the best option, though I might be overlooking something as I've only started using Doris. Any suggestions are welcome, thanks.

### Solution

Implement XXHASH_128.

I'm willing to submit a PR but I'm not sure where to start, any guidance would be appreciated.

### Are you willing to submit PR?

- [x] Yes I am willing to submit a PR!

### Code of Conduct

- [x] I agree to follow this project's [Code of Conduct](https://www.apache.org/foundation/policies/conduct)

Contributor guide

Open the contributing guide

Research direction

Start by locating Doris's existing XXHASH_64 implementation and the code that exposes hash functions and key column types. Check how a 128-bit result can be represented and used as a key; done when XXHASH_128 is available for duplicate analysis without requiring string storage, with tests covering its result and collision-related behavior.

Written by the indexing model from the issue text.

Assessment

Tech stack
java
Domain
databases
Issue type
Feature
Difficulty
4/5
Estimated time
3-5 days
Activity status
Active
Clarity
Mostly clear
Newbie friendliness
48/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.