apache / apache/datafusion

Speed up hash join build phase [experiment]

Open
#18,376 0 comments 0 reactions 1 assignee Claimed by @Dandandan View on GitHub
enhancement performance
Dominant language
Rust
Stars
9.3k
Forks
2.4k
Avg merge
3d 7h
Merged PRs (30d)
344

Description

### Is your feature request related to a problem or challenge?

If the build side of the join is large, a significant bottleneck can be building the hash table.
We can explore some opportunities to improve the performance of building this map.

### Describe the solution you'd like

**Core Idea**

The slowest part of building the hash map is finding and then inserting the items (hash + offset) into the map for each element.

We should be able to test the following:

* Sort the items by hash (and offset) to be able to deduplicate hashes (this introduces some overhead but the hope is this pays off during inserting to the table)
* We can use insert_unique (https://docs.rs/hashbrown/latest/hashbrown/struct.HashTable.html#method.insert_unique) rather than https://docs.rs/hashbrown/latest/hashbrown/struct.HashTable.html#method.entry for the first entry, which should be quite a bit faster by not having to search for existing items
* Keep on using the previous entry for duplicated elements (saving calls to `entry` for each duplicate)

If this doesn't involve any regressions, there are some other opportunities for further improving the performance and simplify the join algorithm by using the sorted property for improving the "chain" datastructure as well (I'll do some experiments on this later).

### Describe alternatives you've considered

_No response_

### Additional context

_No response_

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.