Skip to content

Commit 2b59b51

Browse files
viiryaOmega359
authored andcommitted
feat: support multi-column NOT IN subqueries with null-aware joins (apache#19857)
## Which issue does this PR close? - Closes apache#25737. Follow-up to apache#10583, which made single-column `NOT IN` a null-aware anti join. ## Rationale for this change Multi-column `IN` / `NOT IN` subqueries fail to plan: ```sql SELECT * FROM t1 WHERE (a, b) NOT IN (SELECT x, y FROM t2); SELECT * FROM t1 WHERE (c2, c3) NOT IN ( SELECT c2, c3 FROM t2 WHERE t1.c1 = t2.c1 ); ``` Supporting them requires SQL three-valued logic over the whole tuple. A NULL in one element does not make every comparison UNKNOWN the way a scalar NULL does: `(NULL, 8) = (1, 2)` is `UNKNOWN AND FALSE`, which is FALSE, so the outer row is kept. `(NULL, 2) = (1, 2)` is UNKNOWN, so it is dropped. ## What changes are included in this PR? A null-aware join already reads its equi-join keys by position: `on[0]` is the `NOT IN` value key and `on[1..]` are the correlation scope keys of a correlated subquery. A tuple needs several value keys, so both the logical `Join` and `HashJoinExec` now record how many leading keys are value keys (`null_aware_value_keys`). The layout becomes `on[..V]` for the tuple elements and `on[V..]` for the correlation keys. - **SQL planning / analyzer**: `(a, b) IN (SELECT x, y ...)` is accepted when the tuple and subquery column counts match. Type coercion and placeholder inference work element by element. A tuple compared with a single struct-typed column (`(a, b) IN (SELECT s ...)`) is still a scalar struct comparison. - **Decorrelation**: emits one equality per tuple element, ahead of the correlation predicates, so the elements become the leading keys in order. Constant elements are projected as outer columns, the same way the scalar constant case already is. A tuple `IN` / `NOT IN` inside a projection or an `OR` goes through a null-aware mark join. - **`HashJoinExec`**: `V > 1` uses the existing per-build-row path of correlated null-aware joins. A row counts as NULL-valued when any value key is NULL. Candidate pairs are then kept only when their value tuples have no definite mismatch, i.e. every element pair is equal or involves a NULL. This works for both `LeftAnti` and `LeftMark`, with or without scope keys and join filters. - **Dynamic filter pushdown**: probe rows with a NULL in any value key are kept. - **Protobuf**: `JoinNode` and `HashJoinExecNode` carry `null_aware_value_keys`. A missing field (`0`) decodes as `1`. ## What is the testing strategy for this PR? - `null_aware_anti_join.slt` covers: - 2- and 3-column `NOT IN` with NULLs on either side, an empty subquery, and correlated equality and non-equality correlations - constant tuple elements - `NOT IN` as a nullable projected value and under `OR` - per-element type coercion, column count errors, a single struct column, and placeholders - `subquery.slt` covers multi-column `IN`. - `hash_join/exec.rs` unit tests run `LeftAnti` and `LeftMark` with probe-side and build-side NULLs, three columns, an empty probe side, and correlated scope keys, across batch sizes. Further unit tests cover value-key validation and the protobuf round trip. `shared_bounds.rs` tests the dynamic filter NULL escape over every value key. - `roundtrip_logical_plan.rs` round-trips a correlated multi-column `NOT IN` plan. ## Are there any user-facing changes? Multi-column `IN` / `NOT IN` subqueries are now supported. API change: `Join` and `HashJoinExec` have a new public `null_aware_value_keys` field, and the generated protobuf `JoinNode` and `HashJoinExecNode` have a new field. Code that builds these with struct literals must set it (`1` keeps the previous behavior). The 56.0.0 upgrade guide describes the change.
1 parent 5854713 commit 2b59b51

34 files changed

Lines changed: 2280 additions & 340 deletions

File tree

Lines changed: 33 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,33 @@
1+
name Q10
2+
group null_aware_join
3+
4+
load sql_benchmarks/null_aware_join/init/load.sql
5+
6+
# Correctness canary: the NOT IN result must match a reference count that does
7+
# not use NOT IN. It holds for every NAJ_ROWS. No key holds a NULL, so a row is
8+
# kept exactly when no subquery row equals its whole tuple.
9+
assert I
10+
SELECT count(*) = (
11+
SELECT count(*)
12+
FROM small_outer o
13+
WHERE NOT EXISTS (
14+
SELECT 1 FROM small_inner i WHERE i.id_n0 = o.id_n0 AND i.z = o.z
15+
)
16+
)
17+
FROM small_outer o
18+
WHERE (o.id_n0, o.z) NOT IN (SELECT i.id_n0, i.z FROM small_inner i);
19+
----
20+
true
21+
22+
expect_plan HashJoinExec
23+
24+
run
25+
-- Q10: uncorrelated multi-column NOT IN over nullable keys that hold no NULL.
26+
-- A tuple NOT IN always decides UNKNOWN per build row (the outer side), but
27+
-- without NULLs there is no candidate pair to check, so this is the floor for
28+
-- the multi-column shape.
29+
SELECT count(*)
30+
FROM small_outer o
31+
WHERE (o.id_n0, o.z) NOT IN (SELECT i.id_n0, i.z FROM small_inner i);
32+
33+
cleanup sql_benchmarks/null_aware_join/init/cleanup.sql
Lines changed: 35 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,35 @@
1+
name Q11
2+
group null_aware_join
3+
4+
load sql_benchmarks/null_aware_join/init/load.sql
5+
6+
# Correctness canary: the NOT IN result must match a reference count that does
7+
# not use NOT IN. It holds for every NAJ_ROWS. The outer tuple holds no NULL, so
8+
# a subquery row makes it UNKNOWN or TRUE exactly when `z` matches and `id_n1`
9+
# is NULL or equal; the row is kept only when no such subquery row exists.
10+
assert I
11+
SELECT count(*) = (
12+
SELECT count(*)
13+
FROM small_outer o
14+
WHERE NOT EXISTS (
15+
SELECT 1 FROM small_inner i
16+
WHERE i.z = o.z AND (i.id_n1 IS NULL OR i.id_n1 = o.id_n0)
17+
)
18+
)
19+
FROM small_outer o
20+
WHERE (o.id_n0, o.z) NOT IN (SELECT i.id_n1, i.z FROM small_inner i);
21+
----
22+
true
23+
24+
expect_plan HashJoinExec
25+
26+
run
27+
-- Q11: uncorrelated multi-column NOT IN with 1% NULL in one subquery element.
28+
-- Each NULL-valued subquery row is paired with every outer row and the pair is
29+
-- kept as UNKNOWN only when the other element matches, so the cost grows with
30+
-- (outer rows) x (NULL-valued subquery rows). Compare with Q10 and Q12.
31+
SELECT count(*)
32+
FROM small_outer o
33+
WHERE (o.id_n0, o.z) NOT IN (SELECT i.id_n1, i.z FROM small_inner i);
34+
35+
cleanup sql_benchmarks/null_aware_join/init/cleanup.sql
Lines changed: 37 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,37 @@
1+
name Q12
2+
group null_aware_join
3+
4+
load sql_benchmarks/null_aware_join/init/load.sql
5+
6+
# Correctness canary: the NOT IN result must match a reference count that does
7+
# not use NOT IN. It holds for every NAJ_ROWS. The subquery holds no NULL, so a
8+
# subquery row makes an outer tuple UNKNOWN or TRUE exactly when `z` matches and
9+
# the outer `id_n1` is NULL or equal; the row is kept only when no such
10+
# subquery row exists.
11+
assert I
12+
SELECT count(*) = (
13+
SELECT count(*)
14+
FROM small_outer o
15+
WHERE NOT EXISTS (
16+
SELECT 1 FROM small_inner i
17+
WHERE i.z = o.z AND (o.id_n1 IS NULL OR i.id_n0 = o.id_n1)
18+
)
19+
)
20+
FROM small_outer o
21+
WHERE (o.id_n1, o.z) NOT IN (SELECT i.id_n0, i.z FROM small_inner i);
22+
----
23+
true
24+
25+
expect_plan HashJoinExec
26+
27+
run
28+
-- Q12: uncorrelated multi-column NOT IN with 1% NULL in one outer element,
29+
-- the mirror of Q11. The outer side is the build side, so each NULL-valued
30+
-- build row is paired with every subquery row and kept as UNKNOWN only when
31+
-- the other element matches: the cost grows with (NULL-valued outer rows) x
32+
-- (subquery rows). Compare with Q10 and Q11.
33+
SELECT count(*)
34+
FROM small_outer o
35+
WHERE (o.id_n1, o.z) NOT IN (SELECT i.id_n0, i.z FROM small_inner i);
36+
37+
cleanup sql_benchmarks/null_aware_join/init/cleanup.sql

‎benchmarks/sql_benchmarks/null_aware_join/init/load.sql‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -14,7 +14,7 @@
1414
-- `id` is only ~half covered by the subquery side, so the anti join returns rows
1515
-- rather than degenerating to an empty or full result.
1616

17-
-- Small tables: used by the correlated queries (Q04-Q08), whose cost grows with
17+
-- Small tables: used by the correlated and multi-column queries (Q04-Q12), whose cost grows with
1818
-- the product of the two table sizes.
1919
CREATE TABLE small_outer AS
2020
SELECT

‎benchmarks/sql_benchmarks/null_aware_join/null_aware_join.suite‎

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -1,4 +1,4 @@
1-
description = "Null-aware (NOT IN) hash join benchmarks: uncorrelated, non-equality-correlated, and equality-correlated NOT IN across NULL fractions, plus the positive IN shape that must not be null-aware"
1+
description = "Null-aware (NOT IN) hash join benchmarks: uncorrelated, non-equality-correlated, and equality-correlated NOT IN across NULL fractions, plus the positive IN shape that must not be null-aware, and multi-column (tuple) NOT IN with and without NULLs"
22

33
query_pattern = "q{QUERY_ID_PADDED}.benchmark"
44

@@ -8,7 +8,7 @@ short = "r"
88
env = "NAJ_ROWS"
99
default = "10000"
1010
values = ["10000", "..."]
11-
help = "Rows per table for the correlated queries (Q04-Q09). These evaluate the join filter over candidate build x probe pairs, so their cost grows with the square of this value."
11+
help = "Rows per table for the correlated and multi-column queries (Q04-Q12). These evaluate the join filter over candidate build x probe pairs, so their cost grows with the square of this value."
1212

1313
[[options]]
1414
name = "large-rows"

‎datafusion/core/src/physical_planner.rs‎

Lines changed: 16 additions & 12 deletions
Original file line numberDiff line numberDiff line change
@@ -41,7 +41,7 @@ use crate::physical_plan::explain::ExplainExec;
4141
use crate::physical_plan::filter::FilterExecBuilder;
4242
use crate::physical_plan::joins::utils as join_utils;
4343
use crate::physical_plan::joins::{
44-
AsOfJoinExec, AsOfMatchExpr, CrossJoinExec, HashJoinExec, NestedLoopJoinExec,
44+
AsOfJoinExec, AsOfMatchExpr, CrossJoinExec, HashJoinExecBuilder, NestedLoopJoinExec,
4545
PartitionMode, SortMergeJoinExec,
4646
};
4747
use crate::physical_plan::limit::{GlobalLimitExec, LocalLimitExec};
@@ -1358,6 +1358,7 @@ impl DefaultPhysicalPlanner {
13581358
join_type,
13591359
null_equality,
13601360
null_aware,
1361+
null_aware_value_keys,
13611362
schema: join_schema,
13621363
..
13631364
}) => {
@@ -1790,17 +1791,20 @@ impl DefaultPhysicalPlanner {
17901791
PartitionMode::CollectLeft
17911792
};
17921793

1793-
Arc::new(HashJoinExec::try_new(
1794-
physical_left,
1795-
physical_right,
1796-
join_on,
1797-
join_filter,
1798-
join_type,
1799-
None,
1800-
partition_mode,
1801-
*null_equality,
1802-
*null_aware,
1803-
)?)
1794+
Arc::new(
1795+
HashJoinExecBuilder::new(
1796+
physical_left,
1797+
physical_right,
1798+
join_on,
1799+
*join_type,
1800+
)
1801+
.with_filter(join_filter)
1802+
.with_partition_mode(partition_mode)
1803+
.with_null_equality(*null_equality)
1804+
.with_null_aware(*null_aware)
1805+
.with_null_aware_value_keys(*null_aware_value_keys)
1806+
.build()?,
1807+
)
18041808
};
18051809

18061810
// If plan was mutated previously then need to create the ExecutionPlan

‎datafusion/core/tests/fuzz_cases/mod.rs‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -21,6 +21,7 @@ mod distinct_count_string_fuzz;
2121
#[expect(clippy::needless_pass_by_value)]
2222
mod join_fuzz;
2323
mod merge_fuzz;
24+
mod null_aware_join_fuzz;
2425
#[expect(clippy::needless_pass_by_value)]
2526
mod sort_fuzz;
2627
#[expect(clippy::needless_pass_by_value)]
Lines changed: 182 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,182 @@
1+
// Licensed to the Apache Software Foundation (ASF) under one
2+
// or more contributor license agreements. See the NOTICE file
3+
// distributed with this work for additional information
4+
// regarding copyright ownership. The ASF licenses this file
5+
// to you under the Apache License, Version 2.0 (the
6+
// "License"); you may not use this file except in compliance
7+
// with the License. You may obtain a copy of the License at
8+
//
9+
// http://www.apache.org/licenses/LICENSE-2.0
10+
//
11+
// Unless required by applicable law or agreed to in writing,
12+
// software distributed under the License is distributed on an
13+
// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
14+
// KIND, either express or implied. See the License for the
15+
// specific language governing permissions and limitations
16+
// under the License.
17+
18+
//! Fuzz test for null-aware (`NOT IN`) joins.
19+
//!
20+
//! Scalar and multi-column `NOT IN` / `IN` subqueries, which plan as
21+
//! null-aware hash joins, are compared with `NOT EXISTS` / `EXISTS`
22+
//! formulations of the same three-valued logic, which do not. Random tables
23+
//! with NULLs on both sides are swept across batch sizes and partition counts.
24+
25+
use std::sync::Arc;
26+
27+
use arrow::array::{Int32Array, RecordBatch};
28+
use arrow::datatypes::{DataType, Field, Schema};
29+
use arrow::util::pretty::pretty_format_batches;
30+
use datafusion::datasource::MemTable;
31+
use datafusion::prelude::{SessionConfig, SessionContext};
32+
use rand::rngs::StdRng;
33+
use rand::{Rng, SeedableRng};
34+
35+
#[tokio::test(flavor = "multi_thread")]
36+
async fn null_aware_join_matches_reference() {
37+
for seed in 0..20 {
38+
let mut rng = StdRng::seed_from_u64(seed);
39+
let outer = random_table(&mut rng, &["id", "k", "a", "b", "c"]);
40+
let inner = random_table(&mut rng, &["k", "x", "y", "z"]);
41+
for target_partitions in [1, 4] {
42+
for batch_size in [1, 3, 8192] {
43+
let config = SessionConfig::new()
44+
.with_target_partitions(target_partitions)
45+
.with_batch_size(batch_size)
46+
// Keep multi-partition runs from collapsing to a single
47+
// partition on these small inputs.
48+
.set_usize(
49+
"datafusion.optimizer.hash_join_single_partition_threshold",
50+
0,
51+
)
52+
.set_usize(
53+
"datafusion.optimizer.hash_join_single_partition_threshold_rows",
54+
0,
55+
);
56+
let ctx = SessionContext::new_with_config(config);
57+
ctx.register_table("o", Arc::clone(&outer) as _).unwrap();
58+
ctx.register_table("i", Arc::clone(&inner) as _).unwrap();
59+
for (query, reference) in cases() {
60+
let actual = run(&ctx, &query).await;
61+
let expected = run(&ctx, &reference).await;
62+
assert_eq!(
63+
actual, expected,
64+
"seed={seed} target_partitions={target_partitions} \
65+
batch_size={batch_size}\nquery: {query}\nreference: {reference}"
66+
);
67+
}
68+
}
69+
}
70+
}
71+
}
72+
73+
/// Pairs of (query, reference) that must return the same rows.
74+
fn cases() -> Vec<(String, String)> {
75+
let mut cases = vec![];
76+
// (correlation inside the subquery, the same correlation in the reference)
77+
for (correlation, reference_correlation) in [
78+
("", ""),
79+
(" WHERE i.k = o.k", " AND i.k = o.k"),
80+
(" WHERE i.k < o.k", " AND i.k < o.k"),
81+
(
82+
" WHERE i.k = o.k AND i.z < o.c",
83+
" AND i.k = o.k AND i.z < o.c",
84+
),
85+
] {
86+
// (outer value, subquery output, element-wise equality)
87+
for (value, output, equal) in [
88+
("o.a", "i.x", "o.a = i.x"),
89+
("(o.a, o.b)", "i.x, i.y", "o.a = i.x AND o.b = i.y"),
90+
(
91+
"(o.a, o.b, o.c)",
92+
"i.x, i.y, i.z",
93+
"o.a = i.x AND o.b = i.y AND o.c = i.z",
94+
),
95+
("(o.a, 1)", "i.x, i.y", "o.a = i.x AND 1 = i.y"),
96+
] {
97+
let subquery = format!("SELECT {output} FROM i{correlation}");
98+
let matched = format!(
99+
"EXISTS (SELECT 1 FROM i WHERE ({equal}){reference_correlation})"
100+
);
101+
let unknown = format!(
102+
"EXISTS (SELECT 1 FROM i WHERE ({equal}) IS NULL{reference_correlation})"
103+
);
104+
let not_in = format!(
105+
"NOT EXISTS (SELECT 1 FROM i WHERE ({equal}) IS NOT FALSE{reference_correlation})"
106+
);
107+
cases.push((
108+
format!("SELECT o.id FROM o WHERE {value} NOT IN ({subquery})"),
109+
format!("SELECT o.id FROM o WHERE {not_in}"),
110+
));
111+
cases.push((
112+
format!("SELECT o.id FROM o WHERE {value} IN ({subquery})"),
113+
format!("SELECT o.id FROM o WHERE {matched}"),
114+
));
115+
cases.push((
116+
format!(
117+
"SELECT o.id FROM o WHERE {value} NOT IN ({subquery}) OR o.id % 3 = 0"
118+
),
119+
format!("SELECT o.id FROM o WHERE {not_in} OR o.id % 3 = 0"),
120+
));
121+
cases.push((
122+
format!("SELECT o.id, {value} NOT IN ({subquery}) AS r FROM o"),
123+
format!(
124+
"SELECT o.id, CASE WHEN {matched} THEN false \
125+
WHEN {unknown} THEN NULL ELSE true END AS r FROM o"
126+
),
127+
));
128+
}
129+
}
130+
cases
131+
}
132+
133+
/// A table of nullable `Int32` columns with values in `0..3`, split into up
134+
/// to three partitions. A column named `id` holds unique row ids instead.
135+
fn random_table(rng: &mut StdRng, columns: &[&str]) -> Arc<MemTable> {
136+
let schema = Arc::new(Schema::new(
137+
columns
138+
.iter()
139+
.map(|name| Field::new(*name, DataType::Int32, true))
140+
.collect::<Vec<_>>(),
141+
));
142+
let null_fraction = [0.0, 0.1, 0.3][rng.random_range(0..3)];
143+
let mut next_id = 0;
144+
let partitions = (0..rng.random_range(1..4))
145+
.map(|_| {
146+
let rows = rng.random_range(0..6);
147+
let arrays = columns
148+
.iter()
149+
.map(|name| {
150+
let values: Int32Array = if *name == "id" {
151+
(next_id..next_id + rows).map(Some).collect()
152+
} else {
153+
(0..rows)
154+
.map(|_| {
155+
(!rng.random_bool(null_fraction))
156+
.then(|| rng.random_range(0..3))
157+
})
158+
.collect()
159+
};
160+
Arc::new(values) as _
161+
})
162+
.collect();
163+
next_id += rows;
164+
vec![RecordBatch::try_new(Arc::clone(&schema), arrays).unwrap()]
165+
})
166+
.collect();
167+
Arc::new(MemTable::try_new(schema, partitions).unwrap())
168+
}
169+
170+
/// The rows of `sql`, sorted.
171+
async fn run(ctx: &SessionContext, sql: &str) -> Vec<String> {
172+
let batches = ctx.sql(sql).await.unwrap().collect().await.unwrap();
173+
let formatted = pretty_format_batches(&batches).unwrap().to_string();
174+
let mut rows: Vec<String> = formatted
175+
.lines()
176+
.filter(|line| line.starts_with('|'))
177+
.skip(1)
178+
.map(String::from)
179+
.collect();
180+
rows.sort();
181+
rows
182+
}

0 commit comments

Comments
 (0)