apache / apache/arrow

[C++] AsofJoinNode 128-bit hashing

Open
#32,894 1 comment 0 reactions 0 assignees View on GitHub
Component: C++ Type: enhancement
Dominant language
C++
Stars
17.1k
Forks
4.3k
Avg merge
3d 18h
Merged PRs (30d)
91

Description

A recent version of `AsofJoinNode` uses 64-bit hashing for by-key values. This [leads to a non-negligible probability of collisions](https://github.com/apache/arrow/pull/13880) that are not arbitrated. Using 128-bit hashing, the probability will become negligible.

**Reporter**: [Yaron Gvili](https://issues.apache.org/jira/browse/ARROW-17653) / @rtpsw

**Note**: *This issue was originally created as [ARROW-17653](https://issues.apache.org/jira/browse/ARROW-17653). Please see the [migration documentation](https://github.com/apache/arrow/issues/14542) for further details.*

Contributor guide

Open the contributing guide

Research direction

Start by locating AsofJoinNode and tracing how it hashes by-key values during as-of joins. Compare the current hashing path with the collision concern described in the issue; done means the node uses 128-bit hashing for these values and the relevant behavior is covered by the project’s existing validation or tests.

Written by the indexing model from the issue text.

Assessment

Tech stack
cpp
Domain
data-engineering
Issue type
Bug
Difficulty
4/5
Estimated time
3-5 days
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
38/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.