You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@datafusion.apache.org by gi...@apache.org on 2026/09/17 14:32:41 UTC
(datafusion) branch gh-readonly-queue/main/pr-25386-a2b809331f70bb5468709c5f318cf0882f63e1e4 created (now ba414ce783)
This is an automated email from the ASF dual-hosted git repository.
github-merge-queue[bot] pushed a change to branch gh-readonly-queue/main/pr-25386-a2b809331f70bb5468709c5f318cf0882f63e1e4
in repository https://gitbox.apache.org/repos/asf/datafusion.git
at ba414ce783 bench: SQL benchmark suite for null-aware (NOT IN) joins (#25386)
This branch includes the following new commits:
new ba414ce783 bench: SQL benchmark suite for null-aware (NOT IN) joins (#25386)
The 1 revisions listed above as "new" are entirely new to this
repository and will be described in separate emails. The revisions
listed as "add" were already present in the repository and have only
been added to this reference.
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datafusion.apache.org
For additional commands, e-mail: commits-help@datafusion.apache.org
(datafusion) 01/01: bench: SQL benchmark suite for null-aware (NOT IN) joins (#25386)
Posted by gi...@apache.org.
This is an automated email from the ASF dual-hosted git repository.
github-merge-queue[bot] pushed a commit to branch gh-readonly-queue/main/pr-25386-a2b809331f70bb5468709c5f318cf0882f63e1e4
in repository https://gitbox.apache.org/repos/asf/datafusion.git
commit ba414ce783d5239bc0012f396ddfb68fa778a1a0
Author: Adrian Garcia Badaracco <17...@users.noreply.github.com>
AuthorDate: Thu Sep 17 14:32:16 2026 +0000
bench: SQL benchmark suite for null-aware (NOT IN) joins (#25386)
## Which issue does this PR close?
- N/A. This PR adds benchmarks only. It is split out of #25339 so that
the suite is on `main` first, and that PR can then be measured against
it.
## Rationale for this change
A `NOT IN` subquery becomes a null-aware join. An outer row that finds
no match is TRUE only when neither side has a NULL in scope. If a NULL
is in scope, the result is UNKNOWN.
This decision is cheap for an uncorrelated `NOT IN`. For a correlated
`NOT IN`, the correlation predicate stays behind as a join filter. The
join must then evaluate that filter for each candidate (build row x
probe row) pair, to find which rows the NULLs reach. A non-equality
correlation gives no equality key, so there is no scope key to reduce
the number of pairs. The cost then grows with the NULL count multiplied
by the size of the opposite table.
No benchmark measured this shape, so there was no way to see the cost,
or to tell a change from noise. Review on #25339 asked for this
benchmark.
These are the measured results for #25339. Each number is the median of
60 iterations, taken as 6 interleaved rounds of 10 iterations on an
Apple M4 Pro in release mode. The two sides are the base commit of
#25339 and its head commit, each with this suite applied, so the
comparison isolates the change in that PR.
| Query | Shape | base | #25339 | |
|---|---|---|---|---|
| Q01 | uncorrelated, non-nullable keys | 17.9 ms | 17.7 ms | 0.99x |
| Q02 | uncorrelated, 1% NULL subquery side | 14.9 ms | 14.9 ms | 1.00x
|
| Q03 | uncorrelated, 50% NULL outer side | 14.6 ms | 14.6 ms | 1.00x |
| Q04 | correlated, nullable keys, no NULL present | 0.9 ms | 0.9 ms |
0.96x |
| Q05 | correlated, 1% NULL outer side | 0.9 ms | 2.9 ms | 3.1x |
| Q06 | correlated, 50% NULL outer side | 0.9 ms | 96.2 ms | 109x |
| Q07 | correlated, 50% NULL subquery side | 0.8 ms | 94.4 ms | 112x |
| Q08 | as Q06, with an equality correlation | 1.1 ms | 15.1 ms | 14x |
Q01 to Q04 are the comparable rows, and they show no change. The base
gives wrong results for Q05 to Q08, which is the bug that #25339
corrects. Thus the base numbers for those four rows are the time to
calculate an incorrect result. They show the cost of correct results,
not a regression. These are the results at the default sizes. DuckDB
agrees with the "correct" column.
| Query | correct (#25339) | base |
|---|---|---|
| Q05 | 7460 | 7450 |
| Q06 | 5010 | 5000 |
| Q07 | 10 | 0 |
| Q08 | 5530 | 10000 |
Q06 and Q07 are the rows that the review of #25339 asked about. They
also give the baseline to measure any later optimization of that path
against. Q08 has the same NULL fraction as Q06 and is 6 times cheaper,
which is the value of the equality correlation.
## What changes are included in this PR?
A `null_aware_join` SQL benchmark suite. There are no Rust changes. The
runner finds suites in `benchmarks/sql_benchmarks/`, and the load SQL
makes each table from `range()`, so there is no data generation step.
- Q01 to Q03 are uncorrelated `NOT IN` at different NULL fractions.
Their cost is linear with the table size. They are the regression guard
for the plain null-aware path.
- Q04 is the correlated shape with nullable keys that hold no NULL. It
separates the baseline cost of the shape from the per-pair filter work.
- Q05 to Q07 are the same correlation at 1% and 50% NULL on each side.
This is where that work becomes visible.
- Q08 has the same NULL fraction as Q06, but adds an equality
correlation. The candidate pairs then come from a hash lookup. The
difference between Q06 and Q08 shows the value of the scope key.
Both table sizes are knobs. `NAJ_ROWS` (default 10000) sets the size for
the correlated queries, whose cost grows with its square.
`NAJ_LARGE_ROWS` (default 1000000) sets the size for the uncorrelated
queries.
```bash
./bench.sh run null_aware_join
# One query, with more rows for the correlated shape
NAJ_ROWS=20000 ./bench.sh run null_aware_join 6
```
This PR also adds the suite to `bench.sh` (including `all`) and
documents it in `benchmarks/README.md` and
`benchmarks/sql_benchmarks/README.md`.
There is one Rust change: the `Debug` output of `HashJoinExec` now
includes `null_aware`. The suite's `expect_plan` directive matches that
output, so Q02 to Q07 can require `null_aware: true`. Before this
change, `expect_plan HashJoinExec` also passed for a plain anti join.
## What is the testing strategy for this PR?
This PR adds benchmarks, so it adds no new tests. The existing
`checked_in_suites_cover_benchmark_directories` test in
`benchmarks/src/sql_benchmark_suite.rs` covers suite discovery, and it
passes with the new directory.
Each query has these checks:
- `expect_plan HashJoinExec`. Q02 to Q07 also require `expect_plan
null_aware: true`. Q01 has non-nullable keys, so it is not null-aware.
Q08 plans as a plain mark join on `main`, so #25339 adds its
`null_aware: true` check.
- Q01 to Q04 have an `assert` correctness canary. The assert compares
the `NOT IN` count with a reference count that does not use `NOT IN`, so
it is correct for all values of `NAJ_ROWS` and `NAJ_LARGE_ROWS`. I
checked each reference against the `NOT IN` result in DuckDB at six
pairs of sizes. The same asserts for Q05 to Q08 fail on `main`, so
#25339 adds them together with the fix. I ran them on this branch merged
with #25339, and all eight queries pass at the default sizes and at `-r
3000 -l 1001`.
I ran all eight queries on this branch at the default sizes and at `-r
1500 -l 101`. As a counterfactual check on `main`, the Q05 to Q08
asserts fail, and `null_aware: true` fails on Q01 and Q08.
Each query also runs on `main` as written. Q08 uses the mark join form
on purpose. The plain `WHERE ... NOT IN` form with an equality
correlation does not plan on `main`, and a query that runs on only one
branch cannot compare two branches.
## Are there any user-facing changes?
No. This PR changes benchmarks and documentation only. It does not
change library code.
🤖 Generated with [Claude Code](https://claude.com/claude-code)
---------
Co-authored-by: Claude <no...@anthropic.com>
---
benchmarks/README.md | 30 ++++++++++++
benchmarks/bench.sh | 32 +++++++++++++
benchmarks/sql_benchmarks/README.md | 1 +
.../null_aware_join/benchmarks/q01.benchmark | 26 ++++++++++
.../null_aware_join/benchmarks/q02.benchmark | 27 +++++++++++
.../null_aware_join/benchmarks/q03.benchmark | 26 ++++++++++
.../null_aware_join/benchmarks/q04.benchmark | 34 +++++++++++++
.../null_aware_join/benchmarks/q05.benchmark | 19 ++++++++
.../null_aware_join/benchmarks/q06.benchmark | 20 ++++++++
.../null_aware_join/benchmarks/q07.benchmark | 18 +++++++
.../null_aware_join/benchmarks/q08.benchmark | 26 ++++++++++
.../null_aware_join/init/cleanup.sql | 4 ++
.../sql_benchmarks/null_aware_join/init/load.sql | 55 ++++++++++++++++++++++
.../null_aware_join/null_aware_join.suite | 31 ++++++++++++
.../physical-plan/src/joins/hash_join/exec.rs | 1 +
15 files changed, 350 insertions(+)
diff --git a/benchmarks/README.md b/benchmarks/README.md
index df96b1aeeb..5a555e15ab 100644
--- a/benchmarks/README.md
+++ b/benchmarks/README.md
@@ -966,6 +966,36 @@ Several queries are included to test hash joins under various workloads.
./bench.sh run hj
```
+## Null-Aware Join
+
+This benchmark focuses on `NOT IN` subqueries, which plan as null-aware joins: an
+outer row that finds no match is TRUE only if neither side has a NULL in scope,
+and UNKNOWN otherwise.
+
+Deciding which outer rows are UNKNOWN is cheap when the `NOT IN` is uncorrelated
+(Q01-Q03) and is linear in the table sizes. When the subquery is correlated, the
+correlation predicate stays behind as a join filter, and the join has to evaluate
+that filter per candidate (build row x probe row) pair to decide which rows the
+NULLs actually reach. A non-equality correlation leaves no equality key to narrow
+those pairs, so Q04-Q07 measure how that cost grows with the NULL fraction, while
+Q08 adds an equality correlation that turns the candidate pairs into a hash
+lookup.
+
+Both table sizes are knobs: `NAJ_ROWS` (default `10000`) sizes the correlated
+queries, whose cost grows with its square, and `NAJ_LARGE_ROWS` (default
+`1000000`) sizes the uncorrelated ones.
+
+### Example Run
+
+```bash
+# No need to generate data: this benchmark uses table function `range()` as the data source
+
+./bench.sh run null_aware_join
+
+# Or, with more rows for the correlated queries (~4x the per-pair filter work)
+NAJ_ROWS=20000 ./bench.sh run null_aware_join
+```
+
## Sort Merge Join
This benchmark focuses on the performance of queries with sort merge joins, minimizing other overheads such as scanning data sources or evaluating predicates.
diff --git a/benchmarks/bench.sh b/benchmarks/bench.sh
index 7cd0141b4b..05ede43178 100755
--- a/benchmarks/bench.sh
+++ b/benchmarks/bench.sh
@@ -112,6 +112,9 @@ parquet_row_filter_skip: Per-RG fully-matched RowFilter skip on Parquet (apache/
range filter + pushdown, so most row groups are fully matched and the per-row RowFilter is skipped on them
(subgroups via BENCH_SUBGROUP: skip = clustered key so the skip fires, control = scrambled key so it never fires)
(data generated inline by the suite's load SQL; knobs: PRED_ROWS, RG_SIZE)
+null_aware_join: Null-aware (NOT IN) hash join micro-benchmarks: uncorrelated, non-equality-correlated and equality-correlated
+ NOT IN across NULL fractions, to measure the per-pair join-filter work the correlated cases do
+ (data generated inline by the suite's load SQL from range(); knobs: NAJ_ROWS, NAJ_LARGE_ROWS)
# ClickBench Benchmarks
clickbench_1: ClickBench queries against a single parquet file
@@ -272,6 +275,10 @@ main() {
# Data is generated inline by the suite's load SQL (COPY).
echo "parquet_row_filter_skip: no external data to generate"
;;
+ null_aware_join)
+ # Data is generated inline by the suite's load SQL from range().
+ echo "null_aware_join: no external data to generate"
+ ;;
asof_join)
data_asof_join
;;
@@ -491,6 +498,7 @@ main() {
run_tpcds
run_smj
run_dict
+ run_null_aware_join
;;
tpch)
run_tpch "1" "parquet"
@@ -519,6 +527,9 @@ main() {
parquet_row_filter_skip)
run_parquet_row_filter_skip
;;
+ null_aware_join)
+ run_null_aware_join
+ ;;
asof_join)
run_asof_join
;;
@@ -937,6 +948,27 @@ run_parquet_row_filter_skip() {
bash -c "$SQL_CARGO_COMMAND"
}
+# Runs the null_aware_join suite: NOT IN (null-aware) hash joins. The load SQL
+# builds every table inline from range(), so there is no data step.
+#
+# Q01-Q03 are uncorrelated NOT IN and are linear in the table size; they are the
+# regression guard for the plain null-aware path. Q04-Q08 are correlated, where
+# the correlation predicate stays behind as a join filter that the join applies
+# per candidate (build row x probe row) pair while deciding which rows are
+# UNKNOWN; with no equality correlation there are no scope keys to narrow those
+# pairs, so Q05-Q07 scale with the NULL count times the opposite table's size.
+#
+# NAJ_ROWS rows per table for the correlated queries (default 10_000)
+# NAJ_LARGE_ROWS rows per table for the uncorrelated queries (default 1_000_000)
+run_null_aware_join() {
+ echo "Running null_aware_join benchmark (rows=${NAJ_ROWS:-10000}, large_rows=${NAJ_LARGE_ROWS:-1000000})..."
+ debug_run env BENCH_NAME=null_aware_join \
+ NAJ_ROWS="${NAJ_ROWS:-10000}" \
+ NAJ_LARGE_ROWS="${NAJ_LARGE_ROWS:-1000000}" \
+ ${QUERY:+BENCH_QUERY="${QUERY}"} \
+ bash -c "$SQL_CARGO_COMMAND"
+}
+
# Runs the tpch in memory (needs tpch parquet data)
run_tpch_mem() {
SCALE_FACTOR=$1
diff --git a/benchmarks/sql_benchmarks/README.md b/benchmarks/sql_benchmarks/README.md
index c5a4136e8e..fb09c95daa 100644
--- a/benchmarks/sql_benchmarks/README.md
+++ b/benchmarks/sql_benchmarks/README.md
@@ -37,6 +37,7 @@ in the community:
| `hj` | Hash join benchmark |
| `imdb` | IMDb benchmark |
| `nlj` | Nested‑loop join benchmark |
+| `null_aware_join` | Null-aware (`NOT IN`) hash join micro-benchmarks. Q01-Q03 are uncorrelated `NOT IN` across NULL fractions and are linear in the table size (`NAJ_LARGE_ROWS`, default `1000000`). Q04-Q08 are correlated, so the correlation predicate stays behind as a join filter that the join applies per candidate (build row Ă— probe row) pair while deciding which outer rows are UNKNOWN; without an equality correlation there are no scope keys to narrow those pairs, so their cost gr [...]
| `push_down_topk` | `ORDER BY ... LIMIT` over outer joins (TPC-H data); exercises pushing a TopK through a join |
| `smj` | Sort‑merge join benchmark |
| `sort tpch` | Sorting benchmarks against the TPC-H lineitem table |
diff --git a/benchmarks/sql_benchmarks/null_aware_join/benchmarks/q01.benchmark b/benchmarks/sql_benchmarks/null_aware_join/benchmarks/q01.benchmark
new file mode 100644
index 0000000000..b2f9e0ab49
--- /dev/null
+++ b/benchmarks/sql_benchmarks/null_aware_join/benchmarks/q01.benchmark
@@ -0,0 +1,26 @@
+name Q01
+group null_aware_join
+
+load sql_benchmarks/null_aware_join/init/load.sql
+
+# Correctness canary: the NOT IN result must match a reference count
+# that does not use NOT IN. It holds for every NAJ_ROWS / NAJ_LARGE_ROWS.
+# Odd ids are never in the subquery, which holds only even ids.
+assert I
+SELECT count(*) = (SELECT count(*) FROM large_outer WHERE id % 2 = 1)
+FROM large_outer o
+WHERE o.id NOT IN (SELECT i.id FROM large_inner i);
+----
+true
+
+expect_plan HashJoinExec
+
+run
+-- Q1: uncorrelated NOT IN, non-nullable key on both sides.
+-- No null-aware handling is needed at all, so this is the floor for the shape
+-- and a guard against the anti-join path getting slower for everyone else.
+SELECT count(*)
+FROM large_outer o
+WHERE o.id NOT IN (SELECT i.id FROM large_inner i);
+
+cleanup sql_benchmarks/null_aware_join/init/cleanup.sql
diff --git a/benchmarks/sql_benchmarks/null_aware_join/benchmarks/q02.benchmark b/benchmarks/sql_benchmarks/null_aware_join/benchmarks/q02.benchmark
new file mode 100644
index 0000000000..ba8554b1cb
--- /dev/null
+++ b/benchmarks/sql_benchmarks/null_aware_join/benchmarks/q02.benchmark
@@ -0,0 +1,27 @@
+name Q02
+group null_aware_join
+
+load sql_benchmarks/null_aware_join/init/load.sql
+
+# Correctness canary: the NOT IN result must match a reference count
+# that does not use NOT IN. It holds for every NAJ_ROWS / NAJ_LARGE_ROWS.
+# The subquery always holds a NULL, so no outer row is TRUE.
+assert I
+SELECT count(*) = 0
+FROM large_outer o
+WHERE o.id NOT IN (SELECT i.id_n1 FROM large_inner i);
+----
+true
+
+expect_plan HashJoinExec
+expect_plan null_aware: true
+
+run
+-- Q2: uncorrelated NOT IN, 1% NULL on the subquery side.
+-- A single NULL anywhere in the subquery makes every unmatched outer row
+-- UNKNOWN, which is the cheap bulk path. Linear in the table sizes.
+SELECT count(*)
+FROM large_outer o
+WHERE o.id NOT IN (SELECT i.id_n1 FROM large_inner i);
+
+cleanup sql_benchmarks/null_aware_join/init/cleanup.sql
diff --git a/benchmarks/sql_benchmarks/null_aware_join/benchmarks/q03.benchmark b/benchmarks/sql_benchmarks/null_aware_join/benchmarks/q03.benchmark
new file mode 100644
index 0000000000..28f1ed3410
--- /dev/null
+++ b/benchmarks/sql_benchmarks/null_aware_join/benchmarks/q03.benchmark
@@ -0,0 +1,26 @@
+name Q03
+group null_aware_join
+
+load sql_benchmarks/null_aware_join/init/load.sql
+
+# Correctness canary: the NOT IN result must match a reference count
+# that does not use NOT IN. It holds for every NAJ_ROWS / NAJ_LARGE_ROWS.
+# The non-NULL outer ids are odd, and the subquery holds only even ids.
+assert I
+SELECT count(*) = (SELECT count(*) FROM large_outer WHERE id % 2 = 1)
+FROM large_outer o
+WHERE o.id_n50 NOT IN (SELECT i.id FROM large_inner i);
+----
+true
+
+expect_plan HashJoinExec
+expect_plan null_aware: true
+
+run
+-- Q3: uncorrelated NOT IN, 50% NULL on the outer side.
+-- Every NULL outer row is UNKNOWN on its own. Linear in the table sizes.
+SELECT count(*)
+FROM large_outer o
+WHERE o.id_n50 NOT IN (SELECT i.id FROM large_inner i);
+
+cleanup sql_benchmarks/null_aware_join/init/cleanup.sql
diff --git a/benchmarks/sql_benchmarks/null_aware_join/benchmarks/q04.benchmark b/benchmarks/sql_benchmarks/null_aware_join/benchmarks/q04.benchmark
new file mode 100644
index 0000000000..c72b5bceed
--- /dev/null
+++ b/benchmarks/sql_benchmarks/null_aware_join/benchmarks/q04.benchmark
@@ -0,0 +1,34 @@
+name Q04
+group null_aware_join
+
+load sql_benchmarks/null_aware_join/init/load.sql
+
+# Correctness canary: the NOT IN result must match a reference count
+# that does not use NOT IN. It holds for every NAJ_ROWS / NAJ_LARGE_ROWS.
+# A row is TRUE when the subquery is empty, or when its key is not NULL and
+# not in the subquery. `id` = 2 * v is in the subquery when v % 1000 < o.z.
+assert I
+SELECT count(*) = (
+ SELECT count(*) FROM small_outer o
+ WHERE o.z <= (SELECT min(z) FROM small_inner)
+ OR (o.id_n0 IS NOT NULL AND NOT (o.id % 2 = 0 AND (o.id / 2) % 1000 < o.z))
+)
+FROM small_outer o
+WHERE o.id_n0 NOT IN (SELECT i.id_n0 FROM small_inner i WHERE i.z < o.z);
+----
+true
+
+expect_plan HashJoinExec
+expect_plan null_aware: true
+
+run
+-- Q4: non-equality-correlated NOT IN, nullable keys that hold no NULL.
+-- The correlation `i.z < o.z` has no equality, so it stays behind as a join
+-- filter and the join has no correlation scope keys. With no NULL on either
+-- side there is nothing to mark, so this is the zero-NULL baseline: it shows
+-- what the correlated NOT IN shape costs before any per-pair filter work.
+SELECT count(*)
+FROM small_outer o
+WHERE o.id_n0 NOT IN (SELECT i.id_n0 FROM small_inner i WHERE i.z < o.z);
+
+cleanup sql_benchmarks/null_aware_join/init/cleanup.sql
diff --git a/benchmarks/sql_benchmarks/null_aware_join/benchmarks/q05.benchmark b/benchmarks/sql_benchmarks/null_aware_join/benchmarks/q05.benchmark
new file mode 100644
index 0000000000..2d0a04077d
--- /dev/null
+++ b/benchmarks/sql_benchmarks/null_aware_join/benchmarks/q05.benchmark
@@ -0,0 +1,19 @@
+name Q05
+group null_aware_join
+
+load sql_benchmarks/null_aware_join/init/load.sql
+
+expect_plan HashJoinExec
+expect_plan null_aware: true
+
+run
+-- Q5: non-equality-correlated NOT IN, 1% NULL on the outer side.
+-- With no correlation scope keys the join filter is evaluated over every
+-- (NULL outer row x probe row) pair, so the work scales with the NULL count
+-- times the subquery size. At 1% NULL that product is still small; Q06 is the
+-- same query at 50%.
+SELECT count(*)
+FROM small_outer o
+WHERE o.id_n1 NOT IN (SELECT i.id_n0 FROM small_inner i WHERE i.z < o.z);
+
+cleanup sql_benchmarks/null_aware_join/init/cleanup.sql
diff --git a/benchmarks/sql_benchmarks/null_aware_join/benchmarks/q06.benchmark b/benchmarks/sql_benchmarks/null_aware_join/benchmarks/q06.benchmark
new file mode 100644
index 0000000000..668476ded9
--- /dev/null
+++ b/benchmarks/sql_benchmarks/null_aware_join/benchmarks/q06.benchmark
@@ -0,0 +1,20 @@
+name Q06
+group null_aware_join
+
+load sql_benchmarks/null_aware_join/init/load.sql
+
+expect_plan HashJoinExec
+expect_plan null_aware: true
+
+run
+-- Q6: non-equality-correlated NOT IN, 50% NULL on the outer side.
+-- Worst case for the pairing that has no correlation scope keys: half the
+-- outer rows are NULL, and the join filter is evaluated for each of them
+-- against every subquery row, including for outer rows already known to be
+-- UNKNOWN. Compare against Q05 (same query, 1% NULL) to see how the cost
+-- tracks the NULL fraction.
+SELECT count(*)
+FROM small_outer o
+WHERE o.id_n50 NOT IN (SELECT i.id_n0 FROM small_inner i WHERE i.z < o.z);
+
+cleanup sql_benchmarks/null_aware_join/init/cleanup.sql
diff --git a/benchmarks/sql_benchmarks/null_aware_join/benchmarks/q07.benchmark b/benchmarks/sql_benchmarks/null_aware_join/benchmarks/q07.benchmark
new file mode 100644
index 0000000000..38bf7e9048
--- /dev/null
+++ b/benchmarks/sql_benchmarks/null_aware_join/benchmarks/q07.benchmark
@@ -0,0 +1,18 @@
+name Q07
+group null_aware_join
+
+load sql_benchmarks/null_aware_join/init/load.sql
+
+expect_plan HashJoinExec
+expect_plan null_aware: true
+
+run
+-- Q7: non-equality-correlated NOT IN, 50% NULL on the subquery side.
+-- The mirror of Q06: a NULL subquery row makes every outer row in its
+-- correlation scope UNKNOWN, so the filter is evaluated over every
+-- (outer row x NULL probe row) pair.
+SELECT count(*)
+FROM small_outer o
+WHERE o.id_n0 NOT IN (SELECT i.id_n50 FROM small_inner i WHERE i.z < o.z);
+
+cleanup sql_benchmarks/null_aware_join/init/cleanup.sql
diff --git a/benchmarks/sql_benchmarks/null_aware_join/benchmarks/q08.benchmark b/benchmarks/sql_benchmarks/null_aware_join/benchmarks/q08.benchmark
new file mode 100644
index 0000000000..39d4fbd4ce
--- /dev/null
+++ b/benchmarks/sql_benchmarks/null_aware_join/benchmarks/q08.benchmark
@@ -0,0 +1,26 @@
+name Q08
+group null_aware_join
+
+load sql_benchmarks/null_aware_join/init/load.sql
+
+expect_plan HashJoinExec
+
+run
+-- Q8: NOT IN correlated by both an equality and a non-equality, 50% NULL on
+-- the outer side. The equality correlation becomes a correlation scope key, so
+-- the candidate pairs come from a hash lookup on `k` (16 groups here) instead
+-- of the full cross product, and only those pairs reach the join filter. Same
+-- NULL fraction as Q06, so the gap between the two is what the scope key buys.
+--
+-- The `OR` keeps this a mark join: a bare `WHERE ... NOT IN` with an equality
+-- correlation is the shape that does not plan at all before this suite's
+-- motivating fix, and the point here is to measure the scope-key path, not to
+-- pick a shape that only runs on one branch.
+SELECT count(*)
+FROM small_outer o
+WHERE o.z > 900
+ OR o.id_n50 NOT IN (
+ SELECT i.id_n0 FROM small_inner i WHERE i.k = o.k AND i.z < o.z
+ );
+
+cleanup sql_benchmarks/null_aware_join/init/cleanup.sql
diff --git a/benchmarks/sql_benchmarks/null_aware_join/init/cleanup.sql b/benchmarks/sql_benchmarks/null_aware_join/init/cleanup.sql
new file mode 100644
index 0000000000..f92df3fdeb
--- /dev/null
+++ b/benchmarks/sql_benchmarks/null_aware_join/init/cleanup.sql
@@ -0,0 +1,4 @@
+DROP TABLE small_outer;
+DROP TABLE small_inner;
+DROP TABLE large_outer;
+DROP TABLE large_inner;
diff --git a/benchmarks/sql_benchmarks/null_aware_join/init/load.sql b/benchmarks/sql_benchmarks/null_aware_join/init/load.sql
new file mode 100644
index 0000000000..1225c71995
--- /dev/null
+++ b/benchmarks/sql_benchmarks/null_aware_join/init/load.sql
@@ -0,0 +1,55 @@
+-- Synthetic tables for the null-aware (NOT IN) hash join benchmarks. Built from
+-- `range()`, so there is no data generation step.
+--
+-- Columns, on both sides:
+-- id Int64 NOT NULL -- NOT IN over this never needs null-aware handling
+-- id_n0 Int64 NULL, 0% NULL -- nullable, but no NULL is ever present
+-- id_n1 Int64 NULL, 1% NULL
+-- id_n50 Int64 NULL, 50% NULL
+-- z correlation value for a non-equality correlation (`i.z < o.z`)
+-- k correlation key for an equality correlation (`i.k = o.k`), 16 groups
+--
+-- `id_n0` is nullable so the planner still builds a null-aware join, but holds no
+-- NULL, which is what makes it the zero-NULL baseline for the correlated queries.
+-- `id` is only ~half covered by the subquery side, so the anti join returns rows
+-- rather than degenerating to an empty or full result.
+
+-- Small tables: used by the correlated queries (Q04-Q08), whose cost grows with
+-- the product of the two table sizes.
+CREATE TABLE small_outer AS
+SELECT
+ value AS id,
+ CASE WHEN value < 0 THEN NULL ELSE value END AS id_n0,
+ CASE WHEN value % 100 = 0 THEN NULL ELSE value END AS id_n1,
+ CASE WHEN value % 2 = 0 THEN NULL ELSE value END AS id_n50,
+ value % 1000 AS z,
+ value % 16 AS k
+FROM range(0, ${NAJ_ROWS:-10000});
+
+CREATE TABLE small_inner AS
+SELECT
+ value * 2 AS id,
+ CASE WHEN value < 0 THEN NULL ELSE value * 2 END AS id_n0,
+ CASE WHEN value % 100 = 0 THEN NULL ELSE value * 2 END AS id_n1,
+ CASE WHEN value % 2 = 0 THEN NULL ELSE value * 2 END AS id_n50,
+ value % 1000 AS z,
+ value % 16 AS k
+FROM range(0, ${NAJ_ROWS:-10000});
+
+-- Large tables: used by the uncorrelated queries (Q01-Q03), whose cost is linear
+-- in the table size.
+CREATE TABLE large_outer AS
+SELECT
+ value AS id,
+ CASE WHEN value < 0 THEN NULL ELSE value END AS id_n0,
+ CASE WHEN value % 100 = 0 THEN NULL ELSE value END AS id_n1,
+ CASE WHEN value % 2 = 0 THEN NULL ELSE value END AS id_n50
+FROM range(0, ${NAJ_LARGE_ROWS:-1000000});
+
+CREATE TABLE large_inner AS
+SELECT
+ value * 2 AS id,
+ CASE WHEN value < 0 THEN NULL ELSE value * 2 END AS id_n0,
+ CASE WHEN value % 100 = 0 THEN NULL ELSE value * 2 END AS id_n1,
+ CASE WHEN value % 2 = 0 THEN NULL ELSE value * 2 END AS id_n50
+FROM range(0, ${NAJ_LARGE_ROWS:-1000000});
diff --git a/benchmarks/sql_benchmarks/null_aware_join/null_aware_join.suite b/benchmarks/sql_benchmarks/null_aware_join/null_aware_join.suite
new file mode 100644
index 0000000000..559363de06
--- /dev/null
+++ b/benchmarks/sql_benchmarks/null_aware_join/null_aware_join.suite
@@ -0,0 +1,31 @@
+description = "Null-aware (NOT IN) hash join benchmarks: uncorrelated, non-equality-correlated, and equality-correlated NOT IN across NULL fractions"
+
+query_pattern = "q{QUERY_ID_PADDED}.benchmark"
+
+[[options]]
+name = "rows"
+short = "r"
+env = "NAJ_ROWS"
+default = "10000"
+values = ["10000", "..."]
+help = "Rows per table for the correlated NOT IN queries (Q04-Q08). These evaluate the join filter over candidate build x probe pairs, so their cost grows with the square of this value."
+
+[[options]]
+name = "large-rows"
+short = "l"
+env = "NAJ_LARGE_ROWS"
+default = "1000000"
+values = ["1000000", "..."]
+help = "Rows per table for the uncorrelated NOT IN queries (Q01-Q03), whose cost is linear in the table size."
+
+[[examples]]
+command = "cargo run --release --bin benchmark_runner -- null_aware_join"
+description = "Run all null-aware join queries at the default sizes."
+
+[[examples]]
+command = "cargo run --release --bin benchmark_runner -- null_aware_join --query 6"
+description = "Run only Q06, the worst case for filter evaluation over NULL build rows."
+
+[[examples]]
+command = "cargo run --release --bin benchmark_runner -- null_aware_join -r 20000"
+description = "Run with 20,000 rows per table for the correlated queries (~4x the filter work of the default)."
diff --git a/datafusion/physical-plan/src/joins/hash_join/exec.rs b/datafusion/physical-plan/src/joins/hash_join/exec.rs
index 688ce6f866..7b9e701119 100644
--- a/datafusion/physical-plan/src/joins/hash_join/exec.rs
+++ b/datafusion/physical-plan/src/joins/hash_join/exec.rs
@@ -920,6 +920,7 @@ impl fmt::Debug for HashJoinExec {
.field("left_fut", &self.left_fut)
.field("random_state", &self.random_state)
.field("mode", &self.mode)
+ .field("null_aware", &self.null_aware)
.field("metrics", &self.metrics)
.field("projection", &self.projection)
.field("column_indices", &self.column_indices)
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datafusion.apache.org
For additional commands, e-mail: commits-help@datafusion.apache.org