apache / apache/datafusion

Optimize rehash/null branching in hash util functions

Open
#20,152 1 comment 1 reaction 1 assignee Claimed by @notashes View on GitHub
enhancement
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?

https://github.com/apache/datafusion/blob/b80bf2ca8ef74900fee96a1cc169bdedf53b36fc/datafusion/common/src/hash_utils.rs#L398-L444

- Dictionary doesn't consider if there are 0 null keys + has rehash check inside the hotloop

https://github.com/apache/datafusion/blob/b80bf2ca8ef74900fee96a1cc169bdedf53b36fc/datafusion/common/src/hash_utils.rs#L455-L468

- Struct collects the valid indices even if there are no nulls

https://github.com/apache/datafusion/blob/b80bf2ca8ef74900fee96a1cc169bdedf53b36fc/datafusion/common/src/hash_utils.rs#L487-L489

https://github.com/apache/datafusion/blob/b80bf2ca8ef74900fee96a1cc169bdedf53b36fc/datafusion/common/src/hash_utils.rs#L574-L576

https://github.com/apache/datafusion/blob/b80bf2ca8ef74900fee96a1cc169bdedf53b36fc/datafusion/common/src/hash_utils.rs#L643-L645

- Map/ListView/FixedSizeList checks for existence of null buffer only, not for if there are nulls (null_count)

https://github.com/apache/datafusion/blob/b80bf2ca8ef74900fee96a1cc169bdedf53b36fc/datafusion/common/src/hash_utils.rs#L713-L715

- Run array has rehash check inside hotloop

### Describe the solution you'd like

- Always check for null path based on null_count; for dictionary + struct we should have separate paths for when there are nulls vs when there are no nulls (to be consistent with how the other functions handle this)
- This may be a pedantic case (how often would we have an array with a null buffer but no nulls in it?), but can consider cases like having an array with nulls, but then slicing into a section of it that contains no null values
- Pull rehash outside the hotloop

### Describe alternatives you've considered

If there aren't noticeable performance improvements then might not be worth considering. Maybe branch prediction is good enough for having rehash check inside the hotloop since that wouldn't change per iteration 🤔

### Additional context

Can take inspiration from

- https://github.com/apache/datafusion/pull/19374

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.