Implement Radix Hash Join

[Dandandan]

Is your feature request related to a problem or challenge?

Hash Joins with large build side & lots of hash-duplicates are relatively slow in DataFusion.

The cost seems largely associated with traversing the chain of duplicates (chain_traverse) (1) + which is known to be very cache-inefficient, as the access pattern is mostly random.

Currently, we implement hash joins partitioned by hash, but we can implement a more efficient algorithm (radix hash join) that splits build data into smaller tables that individually mostly fits in CPU caches and allow more efficient access patterns.

[TODO: collect some issues / examples]

(1) #17494

Describe the solution you'd like

Implement a version of Radix Hash Joins:

https://15721.courses.cs.cmu.edu/spring2016/papers/balkesen-icde2013.pdf

Describe alternatives you've considered

No response

Additional context

No response

[Omega359]

This paper is well worth a read here https://db.in.tum.de/~bandle/papers/bandle-partitionVsNonPartition.pdf

"So unless the radix join is beneficial for other
reasons, e.g., larger than main-memory working sets, we express
reservations that implementing the radix join in a general-purpose
production system justifies the added complexity."

[Dandandan]

Thank you!

[Omega359]

For anyone curious how radix joins work I present to you Andy Pavlo (who else): https://youtu.be/pqRV7Mss1Fg?si=WPlilqTfHIC-7UMf&t=1813

[Dandandan]

Another data point is that DuckDB and other engines implement radix hash join and seem to have good results doing so, maybe there are newer resources showing this improvement better?

TPC-H joins are relatively easy: most joins are on some integer key column without many duplicate values when the build side is the "correct" one. The results from this paper are from TPC-H only (on which we perform already reasonably good for most queries).