You are viewing a plain text version of this content. The canonical link for it is here.
Posted to github@datafusion.apache.org by "jayzhan211 (via GitHub)" <gi...@apache.org> on 2026/09/20 14:45:10 UTC
[I] Support null-aware (`NOT IN`) anti / mark joins in `SortMergeJoinExec` [datafusion]
jayzhan211 opened a new issue, #25546:
URL: https://github.com/apache/datafusion/issues/25546
### Is your feature request related to a problem or challenge?
`x NOT IN (subquery)` is planned as a _null-aware_ join: three-valued logic makes the result depend on facts about the whole subquery side, not on any single key comparison. For the uncorrelated `LeftAnti` form:
| subquery side | result |
| ------------------- | --------------------------------------------------- |
| empty | every outer row, including rows whose `x` is NULL |
| contains a NULL key | no rows |
| otherwise | outer rows with a non-NULL `x` that matches nothing |
Only `HashJoinExec` implements this (the `null_aware` flag, pinned to `PartitionMode::CollectLeft`). `SortMergeJoinExec` does not, so the planner always routes these joins to a hash join, even with `prefer_hash_join = false` (#22810 fixed the wrong results that came from not doing so).
The consequence is that a null-aware join is the one join shape with **no memory-bounded execution path**. It is pinned to `CollectLeft`, `prefer_hash_join = false` does not apply to it, and the sort-merge fallback proposed in #24768 / #25217 has to exclude it because there is no sort-merge join to fall back to. A large `NOT IN` fails with `Resources exhausted` and no setting changes that.
**Reproducer** — `datafusion-cli -m 100M --mem-pool-type fair -f repro.sql`:
```sql
set datafusion.execution.target_partitions = 4;
set datafusion.optimizer.prefer_hash_join = false; -- the documented workaround for joins that do not fit
create view big as select v as x from (select unnest(generate_series(1, 20000000)) as v);
create view small as select v as y from (select unnest(generate_series(1, 1000)) as v);
-- null-aware: fails
select count(*) from big where x not in (select y from small);
-- control: same data, same anti join, without NOT IN semantics: completes through SortMergeJoinExec
select count(*) from big where not exists (select 1 from small where small.y = big.x);
```
```text
Resources exhausted: Additional allocation failed for HashJoinInput ...
Error: Failed to allocate additional 152.6 MB for HashJoinInput with 0.0 B already allocated for this reservation - 100.0 MB remain available for the total memory pool: fair(pool_size: 100.0 MB)
+----------+
| count(*) |
+----------+
| 19999000 |
+----------+
```
The plans show why (`prefer_hash_join = false` in both):
```text
-- x NOT IN (select y from t2)
HashJoinExec: mode=CollectLeft, join_type=LeftAnti, on=[(x@0, y@0)], null_aware
-- NOT EXISTS (select 1 from t2 where t2.y = t1.x)
SortMergeJoinExec: join_type=LeftAnti, on=[(x@0, y@0)]
SortExec: expr=[x@0 ASC], preserve_partitioning=[false]
SortExec: expr=[y@0 ASC], preserve_partitioning=[false]
```
### Describe the solution you'd like
Teach `SortMergeJoinExec` the null-aware semantics, then relax the `!null_aware` guard in the physical planner. A first step could be limited to the uncorrelated, single-key `LeftAnti` case.
One observation that may make this cheaper than it looks: both global facts are visible at the _head_ of a sorted input. With nulls first on the subquery side, a partition knows after reading its first subquery row whether it holds any row and whether it holds a NULL key. So the cross-partition part could be a one-time barrier at stream start (each partition reports `(saw_row, saw_null)`), rather than deferring all output to the end as the hash join's probe-completion tracking has to. A simpler variant is to require a single partition for a null-aware sort-merge join. (An idea only, not prototyped.)
The correlated `LeftMark` form (value key `on[0]` plus scope keys `on[1..]`, see the `null_aware` docs on `HashJoinExec`) needs the same facts _per scope group_ and can follow separately.
### Describe alternatives you've considered
- Keep the status quo: null-aware joins stay hash-only and keep failing under a memory limit.
- Spill inside the hash join instead (the hybrid design in #24768, CollectLeft phase). That fixes it without a sort-merge join, but is much further out.
### Additional context
- #24768 — spilling hash join EPIC; this ticket was suggested there (https://github.com/apache/datafusion/issues/24768#issuecomment-5590357419)
- #25217 — sort-merge fallback for hash joins, which excludes null-aware joins for this reason
- #22810 — wrong results when a null-aware join reached `SortMergeJoinExec`; the guard this ticket would relax
- `NestedLoopJoinExec` has no null-aware path either (noted in `decorrelate_predicate_subquery.rs`)
- An implementation should run `null_aware_anti_join.slt` / `null_aware_mark_join.slt` with `prefer_hash_join = false`: a mistake here is silently wrong rows, not an error.
--
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.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: [I] Support null-aware (`NOT IN`) anti / mark joins in `SortMergeJoinExec` [datafusion]
Posted by "TinyMurky (via GitHub)" <gi...@apache.org>.
TinyMurky commented on issue #25546:
URL: https://github.com/apache/datafusion/issues/25546#issuecomment-5800193542
take
--
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: [I] Support null-aware (`NOT IN`) anti / mark joins in `SortMergeJoinExec` [datafusion]
Posted by "TinyMurky (via GitHub)" <gi...@apache.org>.
TinyMurky commented on issue #25546:
URL: https://github.com/apache/datafusion/issues/25546#issuecomment-6394252626
Hello @jayzhan211!
Sorry for the late, I have finished the first version PR, could you review this PR?
In this PR I introduced an API change, which I added `null_aware` to `SortMergeJoinExec`
https://github.com/apache/datafusion/blob/7798c94d6f506e237ef233f641a1c1a74ece9bc7/datafusion/proto-models/proto/datafusion.proto#L1829-L1839
The reason behind it is that I was trying to add `null_aware` to `SortMergeJoinExec::try_new`，which imitating the interface of `HashJoinExec::try_new`.
https://github.com/apache/datafusion/blob/7798c94d6f506e237ef233f641a1c1a74ece9bc7/datafusion/physical-plan/src/joins/sort_merge_join/exec.rs#L211-L227
However, the api change mention above trigger the following warning from [cargo-semver-checks](https://github.com/obi1kenobi/cargo-semver-checks), the full warning message can be found in [here](https://github.com/apache/datafusion/pull/26090#issuecomment-6393008954)
```
Thank you for opening this pull request!
Reviewer note: cargo-semver-checks reported the current version number is not SemVer-compatible with the changes in this pull request (compared against the base branch).
```
How should I address this warning?
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: [I] Support null-aware (`NOT IN`) anti / mark joins in `SortMergeJoinExec` [datafusion]
Posted by "jayzhan211 (via GitHub) via github" <gi...@datafusion.apache.org>.
jayzhan211 closed issue #25546: Support null-aware (`NOT IN`) anti / mark joins in `SortMergeJoinExec`
URL: https://github.com/apache/datafusion/issues/25546
--
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