Skip to content

Commit bfe5668

Browse files
shehab-alikosiew
andcommitted
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

File tree

  • datafusion/physical-plan/src/joins

0 commit comments

Comments
 (0)