Repository navigation
Commit bfe5668
refactor join-key equality filtering (apache#23843)
### Summary
- related to apache#23237
Simplified and sped up candidate-pair equality filtering by eliminating
per-row type dispatch and by using a pre-built comparator that respects
`NullEquality` semantics.
Added targeted hash-join microbenchmarks to exercise high-fanout and
single hot bucket join cases with long string keys and multi column
keys.
### Description
**Before this change**, hash join probing produced candidate build/probe
row-index pairs and then equal_rows_arr validated those pairs by
materializing temporary key arrays, comparing those arrays, building a
boolean mask, and filtering the candidate indices.
**After this change**, `equal_rows_arr` validates candidate pairs by
comparing the original key arrays directly by row index using
`JoinKeyComparator`, then appending only matching candidate indices to
the output arrays. It also now checks that the input shapes are valid
before doing that work.
**Where This Happens in Hash Join**
During hash join probing, DataFusion first asks the join hash map for
candidate build/probe index pairs. Those pairs are still “candidate”
matches because the hash table is based on hash values, so DataFusion
must confirm that the actual join-key values are equal.
**Before**
```
For each batch of candidate pairs:
build_indices + probe_indices
1. allocate taken build key arrays
2. allocate taken probe key arrays
3. allocate equality boolean arrays
4. allocate/combine boolean masks
5. filter index arrays
```
**After**
```
For each batch of candidate pairs:
build_indices + probe_indices
1. compare build/probe rows directly
2. append matching indices
```
This should particularly help workloads where:
* many candidate pairs are produced
* most candidate pairs are real matches
* join keys are multi-column
### Benchmark Performance
In apache#23980, we added new Q24 and
Q25 benchmarksto make this behavior visible:
* Q24 stresses a single hot long string key where every matching probe
row fans out to the whole build side.
* Q25 stresses a skewed composite join key with a long string component,
so multi-column equality filtering is exercised.
These benchmarks are meant to show whether future changes improve this
exact candidate-pair validation path which replicate the hot partition
case, not just generic hash join performance.
Query | main | branch | Change
-- | -- | -- | --
Q24: single hot bucket, high fanout | 725.4 ms | 298.3 ms | 2.43× faster
Q25: skewed multi-column string key | 299.7 ms | 139.8 ms | 2.14× faster
Q3: 100K×60M dense | 56.5 ms | 51.9 ms | 1.09× faster
Q14, Q16 | - | - | ~1.06–1.10× faster
Q1: 25×1.5M | 1.52 ms | 1.76 ms | 1.16× "slower" (0.24 ms; mostly noise)
Q4: 100K×60M, 10% hit | 141.9 ms | 153.3 ms | 1.08× slower (11 ms)
Q2, Q5–Q13, Q15, Q17–Q23 (18 queries) | - | - | no change
### Testing
- ran unit tests for the joins utilities in the physical-plan crate with
`cargo test` and the new tests
`test_equal_rows_arr_filters_candidate_pairs` and
`test_equal_rows_arr_respects_null_equality` passed.
---------
Co-authored-by: kosiew <[email protected]>1 parent fd88495 commit bfe5668
1 file changed
Lines changed: 405 additions & 64 deletions
0 commit comments