You are viewing a plain text version of this content. The canonical link for it is here.
Posted to github@datafusion.apache.org by "saadtajwar (via GitHub)" <gi...@apache.org> on 2026/07/29 00:12:33 UTC
[PR] feat: null aware RightAnti hash join execution [datafusion]
saadtajwar opened a new pull request, #23957:
URL: https://github.com/apache/datafusion/pull/23957
## Which issue does this PR close?
- Part of #23931 (not closes yet)
## Rationale for this change (copied from issue):
DataFusion plans NOT IN (subquery) as a null-aware anti join, but HashJoinExec only supports null_aware = true for LeftAnti with a single join key (validated in datafusion-physical-plan/src/joins/hash_join/exec.rs). Since HashJoinExec always builds on the left input, the build side of a null-aware anti join is the outer table, not the subquery.
This has two costs:
Memory scales with the wrong side. For SELECT ... FROM big_fact WHERE key NOT IN (SELECT k FROM small_dim), the hash table is built over the entire fact table. Memory is O(outer) when it could be O(subquery).
The operator cannot be distributed. The null-aware logic coordinates three pieces of global state across probe partitions through in-process shared memory: probe_side_has_null: AtomicBool, probe_side_non_empty: AtomicBool, and the visited-build-row bitmap, with the last probe partition to finish emitting the unmatched build rows (hash_join/stream.rs). This is correct and cheap in one process, but engines that split probe partitions across processes get independent copies of all three and produce duplicated or incorrect rows. Ballista hit exactly this (https://github.com/apache/datafusion-ballista/issues/2187) and currently has to force the join into a single task (https://github.com/apache/datafusion-ballista/pull/2188), losing all parallelism.
## What changes are included in this PR?
This PR is the first of two - when a path IS built as `RightAnti` + null aware + `CollectLeft` partition mode, the join executes as expected. The second PR that will be created after this will support the planner changes to emit null-aware `RightAnti` & the `JoinSelection` swap logic!
This PR specifically adds the `build_side_has_null` field and assigns at build-time, and correctly satisfies the invariant of no rows being output if true + build state with null keys not being output + empty build side outputting all probe rows
## Are these changes tested?
Yes
## Are there any user-facing changes?
No
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] feat: null aware RightAnti hash join execution + planning support [datafusion]
Posted by "kumarUjjawal (via GitHub)" <gi...@apache.org>.
kumarUjjawal commented on code in PR #23957:
URL: https://github.com/apache/datafusion/pull/23957#discussion_r3742604536
##########
datafusion/physical-plan/src/joins/hash_join/exec.rs:
##########
@@ -2360,6 +2368,9 @@ async fn collect_left_input(
bounds = None;
}
+ let build_has_null =
Review Comment:
`logical_null_count()` now runs for every hash join, but build_side_has_null is only used by null-aware RightAnti. For dictionary/run-end keys this can add an unnecessary O(build rows) pass to unrelated joins. Can we compute it only for null-aware RightAnti?
##########
datafusion/physical-plan/src/joins/hash_join/exec.rs:
##########
Review Comment:
The optimizer no longer swaps filtered joins, which fixes the SQL planner path. However, public HashJoinExec::try_new and protobuf decoding still accept filtered null-aware RightAnti, where the build-NULL check runs before the filter. I suggest rejecting that combination?
##########
datafusion/physical-plan/src/joins/hash_join/stream.rs:
##########
@@ -742,40 +742,58 @@ impl HashJoinStream {
let timer = self.join_metrics.join_time.timer();
// Null-aware anti join semantics:
+
// For LeftAnti: output LEFT (build) rows where LEFT.key NOT IN RIGHT.key
// 1. If RIGHT (probe) contains NULL in any batch, no LEFT rows should be output
// 2. LEFT rows with NULL keys should not be output (handled in final stage)
+
+ // For RightAnti: output RIGHT (probe) rows where RIGHT.key NOT IN LEFT.key
+ // 1. If LEFT (build) contains NULL, no RIGHT rows should be output
+ // 2. RIGHT rows with NULL keys should not be output
+ // 3. If LEFT (build) is empty, all RIGHT rows should be output
if self.null_aware {
- // Mark that we've seen a probe batch with actual rows (probe side is non-empty)
- // Only set this if batch has rows - empty batches don't count
- // Use shared atomic state so all partitions can see this global information
- if state.batch.num_rows() > 0 {
- build_side
- .left_data
- .probe_side_non_empty
- .store(true, Ordering::Relaxed);
- }
+ match self.join_type {
+ JoinType::RightAnti => {
+ if build_side.left_data.build_side_has_null {
+ timer.done();
+ self.state = HashJoinStreamState::FetchProbeBatch;
+ return Ok(StatefulStreamResult::Continue);
+ }
+ }
+ JoinType::LeftAnti => {
+ // Mark that we've seen a probe batch with actual rows (probe side is non-empty)
+ // Only set this if batch has rows - empty batches don't count
+ // Use shared atomic state so all partitions can see this global information
+ if state.batch.num_rows() > 0 {
+ build_side
+ .left_data
+ .probe_side_non_empty
+ .store(true, Ordering::Relaxed);
+ }
- // Check if probe side (RIGHT) contains NULL
- // Since null_aware validation ensures single column join, we only check the first column
- let probe_key_column = &state.values[0];
- if probe_key_column.null_count() > 0 {
- // Found NULL in probe side - set shared flag to prevent any output
- build_side
- .left_data
- .probe_side_has_null
- .store(true, Ordering::Relaxed);
- }
+ // Check if probe side (RIGHT) contains NULL
+ // Since null_aware validation ensures single column join, we only check the first column
+ let probe_key_column = &state.values[0];
+ if probe_key_column.logical_null_count() > 0 {
Review Comment:
This changes filtered LeftAnti results. A dictionary/run-end logical NULL is recorded globally before the JoinFilterm runs. For example, outer (1, A), subquery (NULL, B), with outer.group = inner.group: the NULL row is rejected, so theouter row should survive, but this suppresses it. Please revert this LeftAnti change for this PR, limit it to unfiltered joins, or make NULL handling filter-aware.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] feat: null aware RightAnti hash join execution + planning support [datafusion]
Posted by "kumarUjjawal (via GitHub)" <gi...@apache.org>.
kumarUjjawal commented on code in PR #23957:
URL: https://github.com/apache/datafusion/pull/23957#discussion_r3735838661
##########
datafusion/physical-plan/src/joins/hash_join/stream.rs:
##########
@@ -894,14 +912,26 @@ impl HashJoinStream {
last_joined_right_idx.map_or(0, |v| v + 1)
};
- let (left_indices, right_indices) = adjust_indices_by_join_type(
+ let (left_indices, mut right_indices) = adjust_indices_by_join_type(
left_indices,
right_indices,
index_alignment_range_start..index_alignment_range_end,
self.join_type,
self.right_side_ordered,
)?;
+ // If null-aware RightAnti join, we don't want to emit NULL probe keys
Review Comment:
always allocates a Vec and copies every unmatched index, even when the probe batch has no NULLs. This affects low-hit NOT IN queries that return many rows—the important target workload. Reuse the logical validity mask and skip the copy when it contains no NULLs.
##########
datafusion/physical-plan/src/joins/hash_join/stream.rs:
##########
@@ -742,40 +742,58 @@ impl HashJoinStream {
let timer = self.join_metrics.join_time.timer();
// Null-aware anti join semantics:
+
// For LeftAnti: output LEFT (build) rows where LEFT.key NOT IN RIGHT.key
// 1. If RIGHT (probe) contains NULL in any batch, no LEFT rows should be output
// 2. LEFT rows with NULL keys should not be output (handled in final stage)
+
+ // For RightAnti: output RIGHT (probe) rows where RIGHT.key NOT IN LEFT.key
+ // 1. If LEFT (build) contains NULL, no RIGHT rows should be output
+ // 2. RIGHT rows with NULL keys should not be output
+ // 3. If LEFT (build) is empty, all RIGHT rows should be output
if self.null_aware {
- // Mark that we've seen a probe batch with actual rows (probe side is non-empty)
- // Only set this if batch has rows - empty batches don't count
- // Use shared atomic state so all partitions can see this global information
- if state.batch.num_rows() > 0 {
- build_side
- .left_data
- .probe_side_non_empty
- .store(true, Ordering::Relaxed);
- }
+ match self.join_type {
+ JoinType::RightAnti => {
Review Comment:
filtered null-aware joins should not beswapped or filtered null-aware RightAnti should be rejected.
##########
datafusion/physical-plan/src/joins/hash_join/exec.rs:
##########
@@ -2330,6 +2338,8 @@ async fn collect_left_input(
bounds = None;
}
+ let build_has_null = !left_values.is_empty() && left_values[0].null_count() > 0;
Review Comment:
This can:
- Miss a NULL in the subquery and incorrectly return outer rows.
- Return a logically NULL outer key when the subquery is non-empty.
we should use logical NULL masks on both sides.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] feat: null aware RightAnti hash join execution [datafusion]
Posted by "saadtajwar (via GitHub)" <gi...@apache.org>.
saadtajwar commented on PR #23957:
URL: https://github.com/apache/datafusion/pull/23957#issuecomment-5111657965
cc @andygrove - looking forward to your feedback! I'll have the second PR with the planner support up shortly :)
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] feat: null aware RightAnti hash join execution + planning support [datafusion]
Posted by "saadtajwar (via GitHub)" <gi...@apache.org>.
saadtajwar commented on PR #23957:
URL: https://github.com/apache/datafusion/pull/23957#issuecomment-5232750401
@kumarUjjawal thank you again for taking the time to review here! Addressed your comments in [the latest commit](https://github.com/apache/datafusion/pull/23957/changes/fff036aedd0238484c85798d7417d289612d5b00) - please let me know what you think!
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] feat: null aware RightAnti hash join execution [datafusion]
Posted by "codecov-commenter (via GitHub)" <gi...@apache.org>.
codecov-commenter commented on PR #23957:
URL: https://github.com/apache/datafusion/pull/23957#issuecomment-5111385599
## [Codecov](https://app.codecov.io/gh/apache/datafusion/pull/23957?dropdown=coverage&src=pr&el=h1&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) Report
:x: Patch coverage is `94.80519%` with `4 lines` in your changes missing coverage. Please review.
:white_check_mark: Project coverage is 80.70%. Comparing base ([`551c592`](https://app.codecov.io/gh/apache/datafusion/commit/551c592ca6b6e50ff41b62ca8bff282a28be01e4?dropdown=coverage&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache)) to head ([`eb3ba98`](https://app.codecov.io/gh/apache/datafusion/commit/eb3ba98f4a462628c5a0a934cd29034cde4fbf5a?dropdown=coverage&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache)).
:warning: Report is 27 commits behind head on main.
| [Files with missing lines](https://app.codecov.io/gh/apache/datafusion/pull/23957?dropdown=coverage&src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) | Patch % | Lines |
|---|---|---|
| [...fusion/physical-plan/src/joins/hash\_join/stream.rs](https://app.codecov.io/gh/apache/datafusion/pull/23957?src=pr&el=tree&filepath=datafusion%2Fphysical-plan%2Fsrc%2Fjoins%2Fhash_join%2Fstream.rs&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache#diff-ZGF0YWZ1c2lvbi9waHlzaWNhbC1wbGFuL3NyYy9qb2lucy9oYXNoX2pvaW4vc3RyZWFtLnJz) | 95.00% | [1 Missing and 1 partial :warning: ](https://app.codecov.io/gh/apache/datafusion/pull/23957?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) |
| [...tafusion/physical-plan/src/joins/hash\_join/exec.rs](https://app.codecov.io/gh/apache/datafusion/pull/23957?src=pr&el=tree&filepath=datafusion%2Fphysical-plan%2Fsrc%2Fjoins%2Fhash_join%2Fexec.rs&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache#diff-ZGF0YWZ1c2lvbi9waHlzaWNhbC1wbGFuL3NyYy9qb2lucy9oYXNoX2pvaW4vZXhlYy5ycw==) | 96.66% | [0 Missing and 1 partial :warning: ](https://app.codecov.io/gh/apache/datafusion/pull/23957?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) |
| [datafusion/physical-plan/src/joins/mod.rs](https://app.codecov.io/gh/apache/datafusion/pull/23957?src=pr&el=tree&filepath=datafusion%2Fphysical-plan%2Fsrc%2Fjoins%2Fmod.rs&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache#diff-ZGF0YWZ1c2lvbi9waHlzaWNhbC1wbGFuL3NyYy9qb2lucy9tb2QucnM=) | 85.71% | [1 Missing :warning: ](https://app.codecov.io/gh/apache/datafusion/pull/23957?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) |
<details><summary>Additional details and impacted files</summary>
```diff
@@ Coverage Diff @@
## main #23957 +/- ##
==========================================
+ Coverage 80.65% 80.70% +0.04%
==========================================
Files 1093 1095 +2
Lines 371629 372600 +971
Branches 371629 372600 +971
==========================================
+ Hits 299725 300690 +965
+ Misses 54012 53938 -74
- Partials 17892 17972 +80
```
</details>
[:umbrella: View full report in Codecov by Harness](https://app.codecov.io/gh/apache/datafusion/pull/23957?dropdown=coverage&src=pr&el=continue&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache).
:loudspeaker: Have feedback on the report? [Share it here](https://about.codecov.io/codecov-pr-comment-feedback/?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache).
<details><summary> :rocket: New features to boost your workflow: </summary>
- :snowflake: [Test Analytics](https://docs.codecov.com/docs/test-analytics): Detect flaky tests, report on failures, and find test suite problems.
- :package: [JS Bundle Analysis](https://docs.codecov.com/docs/javascript-bundle-analysis): Save yourself from yourself by tracking and limiting bundle sizes in JS merges.
</details>
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] feat: null aware RightAnti hash join execution + planning support [datafusion]
Posted by "saadtajwar (via GitHub)" <gi...@apache.org>.
saadtajwar commented on code in PR #23957:
URL: https://github.com/apache/datafusion/pull/23957#discussion_r3670307488
##########
datafusion/physical-plan/src/joins/hash_join/exec.rs:
##########
@@ -422,9 +425,14 @@ impl HashJoinExecBuilder {
// Validate null_aware flag
if exec.null_aware {
let join_type = exec.join_type();
- if !matches!(join_type, JoinType::LeftAnti) {
+ let partition_mode = exec.partition_mode();
+ if !matches!(
+ (join_type, partition_mode),
+ (JoinType::LeftAnti, _)
+ | (JoinType::RightAnti, PartitionMode::CollectLeft) // `PartitionMode::CollectLeft` is safe because `RightAnti` is probe-driven
Review Comment:
Do we need the `partition_mode` check for `CollectLeft` here? Or should we just count on it being enforced/never chosen as anything but `CollectLeft` beforehand? I suppose it's possible to explicitly create a plan with a different partition mode if you bypass the SQL -> plan frontend and create directly? Or do we make the assumption that users will only create logical plans and not physical? 👀
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] feat: null aware RightAnti hash join execution + planning support [datafusion]
Posted by "saadtajwar (via GitHub)" <gi...@apache.org>.
saadtajwar commented on code in PR #23957:
URL: https://github.com/apache/datafusion/pull/23957#discussion_r3744596424
##########
datafusion/physical-plan/src/joins/hash_join/stream.rs:
##########
@@ -742,40 +742,58 @@ impl HashJoinStream {
let timer = self.join_metrics.join_time.timer();
// Null-aware anti join semantics:
+
// For LeftAnti: output LEFT (build) rows where LEFT.key NOT IN RIGHT.key
// 1. If RIGHT (probe) contains NULL in any batch, no LEFT rows should be output
// 2. LEFT rows with NULL keys should not be output (handled in final stage)
+
+ // For RightAnti: output RIGHT (probe) rows where RIGHT.key NOT IN LEFT.key
+ // 1. If LEFT (build) contains NULL, no RIGHT rows should be output
+ // 2. RIGHT rows with NULL keys should not be output
+ // 3. If LEFT (build) is empty, all RIGHT rows should be output
if self.null_aware {
- // Mark that we've seen a probe batch with actual rows (probe side is non-empty)
- // Only set this if batch has rows - empty batches don't count
- // Use shared atomic state so all partitions can see this global information
- if state.batch.num_rows() > 0 {
- build_side
- .left_data
- .probe_side_non_empty
- .store(true, Ordering::Relaxed);
- }
+ match self.join_type {
+ JoinType::RightAnti => {
+ if build_side.left_data.build_side_has_null {
+ timer.done();
+ self.state = HashJoinStreamState::FetchProbeBatch;
+ return Ok(StatefulStreamResult::Continue);
+ }
+ }
+ JoinType::LeftAnti => {
+ // Mark that we've seen a probe batch with actual rows (probe side is non-empty)
+ // Only set this if batch has rows - empty batches don't count
+ // Use shared atomic state so all partitions can see this global information
+ if state.batch.num_rows() > 0 {
+ build_side
+ .left_data
+ .probe_side_non_empty
+ .store(true, Ordering::Relaxed);
+ }
- // Check if probe side (RIGHT) contains NULL
- // Since null_aware validation ensures single column join, we only check the first column
- let probe_key_column = &state.values[0];
- if probe_key_column.null_count() > 0 {
- // Found NULL in probe side - set shared flag to prevent any output
- build_side
- .left_data
- .probe_side_has_null
- .store(true, Ordering::Relaxed);
- }
+ // Check if probe side (RIGHT) contains NULL
+ // Since null_aware validation ensures single column join, we only check the first column
+ let probe_key_column = &state.values[0];
+ if probe_key_column.logical_null_count() > 0 {
Review Comment:
Ah I see - limited to unfiltered, thank you for the catch
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] feat: null aware RightAnti hash join execution + planning support [datafusion]
Posted by "saadtajwar (via GitHub)" <gi...@apache.org>.
saadtajwar commented on code in PR #23957:
URL: https://github.com/apache/datafusion/pull/23957#discussion_r3744599717
##########
datafusion/physical-plan/src/joins/hash_join/exec.rs:
##########
Review Comment:
Ah thank you, done
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] feat: null aware RightAnti hash join execution + planning support [datafusion]
Posted by "saadtajwar (via GitHub)" <gi...@apache.org>.
saadtajwar commented on code in PR #23957:
URL: https://github.com/apache/datafusion/pull/23957#discussion_r3744596946
##########
datafusion/physical-plan/src/joins/hash_join/exec.rs:
##########
@@ -2360,6 +2368,9 @@ async fn collect_left_input(
bounds = None;
}
+ let build_has_null =
Review Comment:
Yes! Sounds good, done
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] feat: null aware RightAnti hash join execution + planning support [datafusion]
Posted by "kumarUjjawal (via GitHub)" <gi...@apache.org>.
kumarUjjawal merged PR #23957:
URL: https://github.com/apache/datafusion/pull/23957
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] feat: null aware RightAnti hash join execution + planning support [datafusion]
Posted by "saadtajwar (via GitHub)" <gi...@apache.org>.
saadtajwar commented on PR #23957:
URL: https://github.com/apache/datafusion/pull/23957#issuecomment-5227308527
@kumarUjjawal thanks for the PR comments! Pushed some commits to address those, please let me know your thoughts!
I couldn't find any existing benchmarks that exercises this path, so I just ran the below on my local machine! Please let me know your thoughts - thanks again for taking the time to review!
```sql
-- large outer (nullable key)
CREATE TABLE big_outer AS
SELECT
CASE WHEN value % 17 = 0 THEN CAST(NULL AS BIGINT) ELSE value END AS k,
value AS payload
FROM range(5000000);
-- small subquery side (nullable key)
CREATE TABLE small_dim AS
SELECT
CASE WHEN value % 19 = 0 THEN CAST(NULL AS BIGINT) ELSE value END AS k
FROM range(20000);
SET datafusion.optimizer.join_reordering = true;
SET datafusion.optimizer.prefer_hash_join = true;
EXPLAIN
SELECT count(*)
FROM big_outer o
WHERE o.k NOT IN (SELECT k FROM small_dim);
```
Query under test:
```sql
SELECT count(*)
FROM big_outer o
WHERE o.k NOT IN (SELECT k FROM small_dim);
```
Runner flags (same on both sides):
```bash
--iterations 3 --partitions 2 --batch-size 4096 --memory-limit 2G
```
#### Plans
| Branch | Hash join |
|---|---|
| `main` | `LeftAnti`, `null_aware` (build on **outer** / 5M rows) |
| this PR | `RightAnti`, `CollectLeft`, `null_aware` (build on **subquery** / 20K rows) |
#### Results
| | iter 0 | iter 1 | iter 2 | Peak pool reserved |
|---|---:|---:|---:|---:|
| **main** | 58.8 ms | 57.6 ms | 51.9 ms | **77.5 MB** |
| **this PR** | 36.2 ms | 31.6 ms | 31.3 ms | **314.9 KB** |
So for this shape the PR cuts peak join memory by ~250x (build moves from the outer table to the subquery) and is ~1.7x faster wall-clock on this machine
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] feat: null aware RightAnti hash join execution [datafusion]
Posted by "saadtajwar (via GitHub)" <gi...@apache.org>.
saadtajwar commented on code in PR #23957:
URL: https://github.com/apache/datafusion/pull/23957#discussion_r3670307488
##########
datafusion/physical-plan/src/joins/hash_join/exec.rs:
##########
@@ -422,9 +425,14 @@ impl HashJoinExecBuilder {
// Validate null_aware flag
if exec.null_aware {
let join_type = exec.join_type();
- if !matches!(join_type, JoinType::LeftAnti) {
+ let partition_mode = exec.partition_mode();
+ if !matches!(
+ (join_type, partition_mode),
+ (JoinType::LeftAnti, _)
+ | (JoinType::RightAnti, PartitionMode::CollectLeft) // `PartitionMode::CollectLeft` is safe because `RightAnti` is probe-driven
Review Comment:
Do we need the `partition_mode` check for `CollectLeft` here? Or should we just count on it being enforced/never chosen as anything but `CollectLeft` beforehand?
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] feat: null aware RightAnti hash join execution + planning support [datafusion]
Posted by "saadtajwar (via GitHub)" <gi...@apache.org>.
saadtajwar commented on PR #23957:
URL: https://github.com/apache/datafusion/pull/23957#issuecomment-5329850363
Hey @kumarUjjawal - just wanted to check in here and see if this is good to go! Thanks!
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] feat: null aware RightAnti hash join execution + planning support [datafusion]
Posted by "saadtajwar (via GitHub)" <gi...@apache.org>.
saadtajwar commented on PR #23957:
URL: https://github.com/apache/datafusion/pull/23957#issuecomment-5282759066
> I'm leaving this open for 1-2 days if no one has any objections I will merge.
Sounds good! Thanks @kumarUjjawal !
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] feat: null aware RightAnti hash join execution [datafusion]
Posted by "saadtajwar (via GitHub)" <gi...@apache.org>.
saadtajwar commented on code in PR #23957:
URL: https://github.com/apache/datafusion/pull/23957#discussion_r3670307488
##########
datafusion/physical-plan/src/joins/hash_join/exec.rs:
##########
@@ -422,9 +425,14 @@ impl HashJoinExecBuilder {
// Validate null_aware flag
if exec.null_aware {
let join_type = exec.join_type();
- if !matches!(join_type, JoinType::LeftAnti) {
+ let partition_mode = exec.partition_mode();
+ if !matches!(
+ (join_type, partition_mode),
+ (JoinType::LeftAnti, _)
+ | (JoinType::RightAnti, PartitionMode::CollectLeft) // `PartitionMode::CollectLeft` is safe because `RightAnti` is probe-driven
Review Comment:
Do we need the `partition_mode` check for `CollectLeft` here? Or should we just count on it being enforced/never chosen as anything but `CollectLeft` beforehand? I suppose it's possible to explicitly create a plan with a different partition mode if you bypass the SQL -> plan frontend and create directly?
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] feat: null aware RightAnti hash join execution + planning support [datafusion]
Posted by "saadtajwar (via GitHub)" <gi...@apache.org>.
saadtajwar commented on code in PR #23957:
URL: https://github.com/apache/datafusion/pull/23957#discussion_r3739622020
##########
datafusion/physical-plan/src/joins/hash_join/stream.rs:
##########
@@ -742,40 +742,58 @@ impl HashJoinStream {
let timer = self.join_metrics.join_time.timer();
// Null-aware anti join semantics:
+
// For LeftAnti: output LEFT (build) rows where LEFT.key NOT IN RIGHT.key
// 1. If RIGHT (probe) contains NULL in any batch, no LEFT rows should be output
// 2. LEFT rows with NULL keys should not be output (handled in final stage)
+
+ // For RightAnti: output RIGHT (probe) rows where RIGHT.key NOT IN LEFT.key
+ // 1. If LEFT (build) contains NULL, no RIGHT rows should be output
+ // 2. RIGHT rows with NULL keys should not be output
+ // 3. If LEFT (build) is empty, all RIGHT rows should be output
if self.null_aware {
- // Mark that we've seen a probe batch with actual rows (probe side is non-empty)
- // Only set this if batch has rows - empty batches don't count
- // Use shared atomic state so all partitions can see this global information
- if state.batch.num_rows() > 0 {
- build_side
- .left_data
- .probe_side_non_empty
- .store(true, Ordering::Relaxed);
- }
+ match self.join_type {
+ JoinType::RightAnti => {
Review Comment:
Thanks, done! Added that condition to `can_swap_hash_join`
##########
datafusion/physical-plan/src/joins/hash_join/exec.rs:
##########
@@ -2330,6 +2338,8 @@ async fn collect_left_input(
bounds = None;
}
+ let build_has_null = !left_values.is_empty() && left_values[0].null_count() > 0;
Review Comment:
Ah good catch - fixed to use those logical null masks!
##########
datafusion/physical-plan/src/joins/hash_join/stream.rs:
##########
@@ -894,14 +912,26 @@ impl HashJoinStream {
last_joined_right_idx.map_or(0, |v| v + 1)
};
- let (left_indices, right_indices) = adjust_indices_by_join_type(
+ let (left_indices, mut right_indices) = adjust_indices_by_join_type(
left_indices,
right_indices,
index_alignment_range_start..index_alignment_range_end,
self.join_type,
self.right_side_ordered,
)?;
+ // If null-aware RightAnti join, we don't want to emit NULL probe keys
Review Comment:
Ah I see, that makes sense, thanks! Pushed a change to address, please let me know your thoughts!
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] feat: null aware RightAnti hash join execution + planning support [datafusion]
Posted by "saadtajwar (via GitHub)" <gi...@apache.org>.
saadtajwar commented on PR #23957:
URL: https://github.com/apache/datafusion/pull/23957#issuecomment-5247186338
> @saadtajwar can you please look at the failing ci
Apologies - this should be fixed now. Really appreciate you reviewing as always!
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] feat: null aware RightAnti hash join execution + planning support [datafusion]
Posted by "kumarUjjawal (via GitHub)" <gi...@apache.org>.
kumarUjjawal commented on PR #23957:
URL: https://github.com/apache/datafusion/pull/23957#issuecomment-5235601972
@saadtajwar can you please look at the failing ci
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] feat: null aware RightAnti hash join execution + planning support [datafusion]
Posted by "kumarUjjawal (via GitHub)" <gi...@apache.org>.
kumarUjjawal commented on PR #23957:
URL: https://github.com/apache/datafusion/pull/23957#issuecomment-5282342996
I'm leaving this open for 1-2 days if no one has any objections I will merge.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] feat: null aware RightAnti hash join execution + planning support [datafusion]
Posted by "saadtajwar (via GitHub)" <gi...@apache.org>.
saadtajwar commented on PR #23957:
URL: https://github.com/apache/datafusion/pull/23957#issuecomment-5137228963
cc @andygrove - just to update, this PR should now fully close out #23931 ! Just this one PR now with all changes instead of two :)
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] feat: null aware RightAnti hash join execution + planning support [datafusion]
Posted by "kumarUjjawal (via GitHub)" <gi...@apache.org>.
kumarUjjawal commented on PR #23957:
URL: https://github.com/apache/datafusion/pull/23957#issuecomment-5330017082
Thank you @saadtajwar
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org