Skip to content

Commit 50d6e4a

Browse files
adriangbclaude
andcommitted
perf: merge the two UNKNOWN joins of a residual IN into one
The fallback for an `IN` whose join keeps a residual filter built three mark joins. The first says whether the value matched. The other two, both without a join predicate, say whether the subquery gives a NULL and whether it gives any row at all, and the caller combined them as `has_null OR (value IS NULL AND non_empty)`. One join answers both. Its filter keeps a subquery row when the subquery value is NULL, or when the outer value is NULL and the row is in scope at all. For a value that is not NULL the mark reads `has_null`. For a value that is NULL it reads `non_empty`, which is the weaker fact that case needs and which `has_null` implies. `IS NULL` is two-valued on both sides, so neither test adds an UNKNOWN of its own. `build_join` gains the extra predicate, and `mark_join_with_alias` lets the caller own the alias so that it can name the aliased subquery column. No result changes: only `EXPLAIN` expectations move, and the `CASE` loses its disjunction. A differential fuzz of 560 correlated `IN` and `NOT IN` queries against DuckDB 1.5.2 finds no mismatch, and the same fuzz finds 98 on the merge base. Co-Authored-By: Claude Opus 5 <[email protected]>
1 parent bb043f1 commit 50d6e4a

3 files changed

Lines changed: 109 additions & 91 deletions

File tree

‎datafusion/optimizer/src/decorrelate_predicate_subquery.rs‎

Lines changed: 72 additions & 42 deletions
Original file line numberDiff line numberDiff line change
@@ -285,28 +285,38 @@ fn in_subquery_value_mark_join(
285285
)));
286286
}
287287

288-
// SQL IN needs three facts per outer row to distinguish FALSE from UNKNOWN.
289-
let null_subquery = LogicalPlanBuilder::from(subquery.clone())
290-
.filter(output_expr.is_null())?
291-
.build()?;
292-
let Some(MarkJoin {
293-
plan: null_plan,
294-
mark: subquery_has_null,
295-
..
296-
}) = mark_join(&matched_plan, &null_subquery, None, false, alias)?
297-
else {
298-
return Ok(None);
299-
};
288+
// The value is not matched here, so the answer is UNKNOWN when the
289+
// subquery gives a NULL, and also when the value is NULL and the subquery
290+
// gives any row at all. One mark join answers both: it keeps a subquery row
291+
// in the scope of the outer row when the subquery value is NULL, or when
292+
// the outer value is NULL and the row is in scope at all.
293+
//
294+
// For an outer value that is not NULL the mark reads "the subquery gives a
295+
// NULL". For an outer value that is NULL it reads "the subquery gives a
296+
// row", which is the weaker fact that this case needs, and which the first
297+
// reading implies. `IS NULL` is two-valued on both sides, so neither test
298+
// adds an UNKNOWN of its own.
299+
let unknown_alias = alias.next("__correlated_sq");
300+
let subquery_value = Expr::Column(create_col_from_scalar_expr(
301+
&output_expr,
302+
unknown_alias.clone(),
303+
)?);
300304
let Some(MarkJoin {
301305
plan: final_plan,
302-
mark: subquery_non_empty,
306+
mark: unknown,
303307
..
304-
}) = mark_join(&null_plan, subquery, None, false, alias)?
308+
}) = mark_join_with_alias(
309+
&matched_plan,
310+
subquery,
311+
None,
312+
Some(subquery_value.is_null().or(expr.is_null())),
313+
false,
314+
&unknown_alias,
315+
)?
305316
else {
306317
return Ok(None);
307318
};
308319

309-
let unknown = subquery_has_null.or(expr.is_null().and(subquery_non_empty));
310320
let result = when(matched, lit(true))
311321
.when(unknown, lit(ScalarValue::Boolean(None)))
312322
.otherwise(lit(false))?;
@@ -421,6 +431,7 @@ fn build_join_top(
421431
left,
422432
subquery,
423433
in_predicate_opt.as_ref(),
434+
None,
424435
join_type,
425436
&subquery_alias,
426437
)?
@@ -450,19 +461,35 @@ fn mark_join(
450461
alias_generator: &Arc<AliasGenerator>,
451462
) -> Result<Option<MarkJoin>> {
452463
let alias = alias_generator.next("__correlated_sq");
464+
mark_join_with_alias(left, subquery, in_predicate_opt, None, negated, &alias)
465+
}
453466

454-
let exists_col = Expr::Column(Column::new(Some(alias.clone()), "mark"));
467+
/// Same as [`mark_join`], but the caller owns the alias, so it can give an
468+
/// `extra_predicate` that names a column of the aliased subquery.
469+
fn mark_join_with_alias(
470+
left: &LogicalPlan,
471+
subquery: &LogicalPlan,
472+
in_predicate_opt: Option<&Expr>,
473+
extra_predicate: Option<Expr>,
474+
negated: bool,
475+
alias: &str,
476+
) -> Result<Option<MarkJoin>> {
477+
let exists_col = Expr::Column(Column::new(Some(alias.to_string()), "mark"));
455478
let exists_expr = if negated { !exists_col } else { exists_col };
456479

457-
Ok(
458-
build_join(left, subquery, in_predicate_opt, JoinType::LeftMark, &alias)?.map(
459-
|join| MarkJoin {
460-
plan: join.plan,
461-
mark: exists_expr,
462-
three_valued_exact: join.mark_is_three_valued_exact,
463-
},
464-
),
465-
)
480+
Ok(build_join(
481+
left,
482+
subquery,
483+
in_predicate_opt,
484+
extra_predicate,
485+
JoinType::LeftMark,
486+
alias,
487+
)?
488+
.map(|join| MarkJoin {
489+
plan: join.plan,
490+
mark: exists_expr,
491+
three_valued_exact: join.mark_is_three_valued_exact,
492+
}))
466493
}
467494

468495
/// A [`JoinType::LeftMark`] join that replaces a subquery predicate.
@@ -642,6 +669,7 @@ fn build_join(
642669
left: &LogicalPlan,
643670
subquery: &LogicalPlan,
644671
in_predicate_opt: Option<&Expr>,
672+
extra_predicate: Option<Expr>,
645673
join_type: JoinType,
646674
alias: &str,
647675
) -> Result<Option<BuiltJoin>> {
@@ -754,6 +782,14 @@ fn build_join(
754782
(None, None) => lit(true),
755783
};
756784

785+
// `lit(true)` is the filter of a join that has no predicate of its own, and
786+
// `true AND p` is only noise in the plan.
787+
let join_filter = match extra_predicate {
788+
Some(extra) if join_filter == lit(true) => extra,
789+
Some(extra) => join_filter.and(extra),
790+
None => join_filter,
791+
};
792+
757793
// The keys of the join that replaces an `IN` or `NOT IN` predicate. An
758794
// `EXISTS` has no value to compare, so its join never needs null-aware
759795
// semantics.
@@ -1638,23 +1674,17 @@ mod tests {
16381674

16391675
assert_optimized_plan_equal!(
16401676
plan,
1641-
@r"
1642-
Projection: CASE WHEN __correlated_sq_1.mark THEN Boolean(true) WHEN __correlated_sq_2.mark OR test.c IS NULL AND __correlated_sq_3.mark THEN Boolean(NULL) ELSE Boolean(false) END AS is_present [is_present:Boolean;N]
1643-
LeftMark Join: Filter: test.a > __correlated_sq_3.a [a:UInt32, b:UInt32, c:UInt32, mark:Boolean;N, mark:Boolean;N, mark:Boolean;N]
1644-
LeftMark Join: Filter: test.a > __correlated_sq_2.a [a:UInt32, b:UInt32, c:UInt32, mark:Boolean;N, mark:Boolean;N]
1645-
LeftMark Join: Filter: test.c = __correlated_sq_1.c AND test.a > __correlated_sq_1.a [a:UInt32, b:UInt32, c:UInt32, mark:Boolean;N]
1646-
TableScan: test [a:UInt32, b:UInt32, c:UInt32]
1647-
Projection: __correlated_sq_1.c, __correlated_sq_1.a [c:UInt32, a:UInt32]
1648-
SubqueryAlias: __correlated_sq_1 [c:UInt32, a:UInt32]
1649-
Projection: sq.c, sq.a [c:UInt32, a:UInt32]
1650-
TableScan: sq [a:UInt32, b:UInt32, c:UInt32]
1651-
Projection: __correlated_sq_2.a [a:UInt32]
1652-
SubqueryAlias: __correlated_sq_2 [c:UInt32, a:UInt32]
1653-
Filter: sq.c IS NULL [c:UInt32, a:UInt32]
1654-
Projection: sq.c, sq.a [c:UInt32, a:UInt32]
1655-
TableScan: sq [a:UInt32, b:UInt32, c:UInt32]
1656-
Projection: __correlated_sq_3.a [a:UInt32]
1657-
SubqueryAlias: __correlated_sq_3 [c:UInt32, a:UInt32]
1677+
@"
1678+
Projection: CASE WHEN __correlated_sq_1.mark THEN Boolean(true) WHEN __correlated_sq_2.mark THEN Boolean(NULL) ELSE Boolean(false) END AS is_present [is_present:Boolean;N]
1679+
LeftMark Join: Filter: test.a > __correlated_sq_2.a AND (__correlated_sq_2.c IS NULL OR test.c IS NULL) [a:UInt32, b:UInt32, c:UInt32, mark:Boolean;N, mark:Boolean;N]
1680+
LeftMark Join: Filter: test.c = __correlated_sq_1.c AND test.a > __correlated_sq_1.a [a:UInt32, b:UInt32, c:UInt32, mark:Boolean;N]
1681+
TableScan: test [a:UInt32, b:UInt32, c:UInt32]
1682+
Projection: __correlated_sq_1.c, __correlated_sq_1.a [c:UInt32, a:UInt32]
1683+
SubqueryAlias: __correlated_sq_1 [c:UInt32, a:UInt32]
1684+
Projection: sq.c, sq.a [c:UInt32, a:UInt32]
1685+
TableScan: sq [a:UInt32, b:UInt32, c:UInt32]
1686+
Projection: __correlated_sq_2.c, __correlated_sq_2.a [c:UInt32, a:UInt32]
1687+
SubqueryAlias: __correlated_sq_2 [c:UInt32, a:UInt32]
16581688
Projection: sq.c, sq.a [c:UInt32, a:UInt32]
16591689
TableScan: sq [a:UInt32, b:UInt32, c:UInt32]
16601690
"

‎datafusion/sqllogictest/test_files/joins.slt‎

Lines changed: 6 additions & 10 deletions
Original file line numberDiff line numberDiff line change
@@ -1989,21 +1989,17 @@ where join_t1.t1_id + 12 not in
19891989
----
19901990
logical_plan
19911991
01)Projection: join_t1.t1_id, join_t1.t1_name, join_t1.t1_int
1992-
02)--Filter: NOT CASE WHEN __correlated_sq_2.mark THEN Boolean(true) WHEN __correlated_sq_3.mark OR CAST(join_t1.t1_id AS Int64) + Int64(12) IS NULL AND __correlated_sq_4.mark THEN Boolean(NULL) ELSE Boolean(false) END
1993-
03)----LeftMark Join: Filter: join_t1.t1_int > UInt32(0)
1994-
04)------LeftMark Join: Filter: join_t1.t1_int > UInt32(0)
1992+
02)--Filter: __correlated_sq_3.mark IS DISTINCT FROM Boolean(true) OR __correlated_sq_2.mark IS NOT DISTINCT FROM Boolean(true)
1993+
03)----LeftMark Join: Filter: join_t1.t1_int > UInt32(0) AND (__correlated_sq_3.join_t2.t2_id + Int64(1) IS NULL OR CAST(join_t1.t1_id AS Int64) + Int64(12) IS NULL)
1994+
04)------Filter: __correlated_sq_2.mark IS DISTINCT FROM Boolean(true)
19951995
05)--------LeftMark Join: CAST(join_t1.t1_id AS Int64) + Int64(12) = __correlated_sq_2.join_t2.t2_id + Int64(1) Filter: join_t1.t1_int > UInt32(0)
19961996
06)----------TableScan: join_t1 projection=[t1_id, t1_name, t1_int]
19971997
07)----------SubqueryAlias: __correlated_sq_2
19981998
08)------------Projection: CAST(join_t2.t2_id AS Int64) + Int64(1)
19991999
09)--------------TableScan: join_t2 projection=[t2_id]
2000-
10)--------SubqueryAlias: __correlated_sq_3
2001-
11)----------Projection: CAST(join_t2.t2_id AS Int64) + Int64(1)
2002-
12)------------Filter: CAST(join_t2.t2_id AS Int64) + Int64(1) IS NULL
2003-
13)--------------TableScan: join_t2 projection=[t2_id]
2004-
14)------SubqueryAlias: __correlated_sq_4
2005-
15)--------Projection: CAST(join_t2.t2_id AS Int64) + Int64(1)
2006-
16)----------TableScan: join_t2 projection=[t2_id]
2000+
10)------SubqueryAlias: __correlated_sq_3
2001+
11)--------Projection: CAST(join_t2.t2_id AS Int64) + Int64(1)
2002+
12)----------TableScan: join_t2 projection=[t2_id]
20072003

20082004
# In subquery to join with outer filter
20092005

‎datafusion/sqllogictest/test_files/subquery_projection.slt‎

Lines changed: 31 additions & 39 deletions
Original file line numberDiff line numberDiff line change
@@ -141,30 +141,22 @@ query TT
141141
EXPLAIN SELECT id, id IN (SELECT n2.id FROM n2 WHERE n2.z < n1.z) AS m FROM n1;
142142
----
143143
logical_plan
144-
01)Projection: n1.id, CASE WHEN __correlated_sq_1.mark THEN Boolean(true) WHEN __correlated_sq_2.mark OR n1.id IS NULL AND __correlated_sq_3.mark THEN Boolean(NULL) ELSE Boolean(false) END AS m
145-
02)--LeftMark Join: Filter: __correlated_sq_3.z < n1.z
146-
03)----LeftMark Join: Filter: __correlated_sq_2.z < n1.z
147-
04)------LeftMark Join: n1.id = __correlated_sq_1.id Filter: __correlated_sq_1.z < n1.z
148-
05)--------TableScan: n1 projection=[id, z]
149-
06)--------SubqueryAlias: __correlated_sq_1
150-
07)----------TableScan: n2 projection=[id, z]
151-
08)------SubqueryAlias: __correlated_sq_2
152-
09)--------Projection: n2.z
153-
10)----------Filter: n2.id IS NULL
154-
11)------------TableScan: n2 projection=[id, z]
155-
12)----SubqueryAlias: __correlated_sq_3
156-
13)------TableScan: n2 projection=[z]
144+
01)Projection: n1.id, __correlated_sq_1.mark IS NOT DISTINCT FROM Boolean(true) OR __correlated_sq_2.mark IS NOT DISTINCT FROM Boolean(true) AND __correlated_sq_1.mark IS DISTINCT FROM Boolean(true) AND Boolean(NULL) AS m
145+
02)--LeftMark Join: Filter: __correlated_sq_2.z < n1.z AND (__correlated_sq_2.id IS NULL OR n1.id IS NULL)
146+
03)----LeftMark Join: n1.id = __correlated_sq_1.id Filter: __correlated_sq_1.z < n1.z
147+
04)------TableScan: n1 projection=[id, z]
148+
05)------SubqueryAlias: __correlated_sq_1
149+
06)--------TableScan: n2 projection=[id, z]
150+
07)----SubqueryAlias: __correlated_sq_2
151+
08)------TableScan: n2 projection=[id, z]
157152
physical_plan
158-
01)ProjectionExec: expr=[id@0 as id, CASE WHEN mark@1 THEN true WHEN mark@2 OR id@0 IS NULL AND mark@3 THEN NULL ELSE false END as m]
159-
02)--NestedLoopJoinExec: join_type=RightMark, filter=z@1 < z@0, projection=[id@0, mark@2, mark@3, mark@4]
153+
01)ProjectionExec: expr=[id@0 as id, mark@1 IS NOT DISTINCT FROM true OR mark@2 IS NOT DISTINCT FROM true AND mark@1 IS DISTINCT FROM true AND NULL as m]
154+
02)--NestedLoopJoinExec: join_type=RightMark, filter=z@3 < z@1 AND (id@2 IS NULL OR id@0 IS NULL), projection=[id@0, mark@2, mark@3]
160155
03)----DataSourceExec: partitions=1, partition_sizes=[1]
161-
04)----NestedLoopJoinExec: join_type=RightMark, filter=z@1 < z@0
162-
05)------FilterExec: id@0 IS NULL, projection=[z@1]
156+
04)----RepartitionExec: partitioning=RoundRobinBatch(4), input_partitions=1
157+
05)------HashJoinExec: mode=CollectLeft, join_type=LeftMark, on=[(id@0, id@0)], filter=z@1 < z@0
163158
06)--------DataSourceExec: partitions=1, partition_sizes=[1]
164-
07)------RepartitionExec: partitioning=RoundRobinBatch(4), input_partitions=1
165-
08)--------HashJoinExec: mode=CollectLeft, join_type=LeftMark, on=[(id@0, id@0)], filter=z@1 < z@0
166-
09)----------DataSourceExec: partitions=1, partition_sizes=[1]
167-
10)----------DataSourceExec: partitions=1, partition_sizes=[1]
159+
07)--------DataSourceExec: partitions=1, partition_sizes=[1]
168160

169161
query IB rowsort
170162
SELECT id, id IN (SELECT n2.id FROM n2 WHERE n2.z < n1.z) AS m FROM n1;
@@ -453,30 +445,30 @@ EXPLAIN SELECT k FROM ra WHERE NULLIF(ra.k, 1) NOT IN (SELECT rb.k FROM rb WHERE
453445
----
454446
logical_plan
455447
01)Projection: ra.k
456-
02)--Filter: NOT CASE WHEN __correlated_sq_2.mark THEN Boolean(true) WHEN __correlated_sq_3.mark OR nullif(CAST(ra.k AS Int64), Int64(1)) IS NULL AND __correlated_sq_4.mark THEN Boolean(NULL) ELSE Boolean(false) END
457-
03)----Projection: ra.k, __correlated_sq_2.mark, __correlated_sq_3.mark, __correlated_sq_4.mark
458-
04)------LeftMark Join: Filter: __correlated_sq_4.z > ra.z
459-
05)--------LeftMark Join: Filter: __correlated_sq_3.z > ra.z
448+
02)--Filter: __correlated_sq_3.mark IS DISTINCT FROM Boolean(true) OR __correlated_sq_2.mark IS NOT DISTINCT FROM Boolean(true)
449+
03)----Projection: ra.k, __correlated_sq_2.mark, __correlated_sq_3.mark
450+
04)------LeftMark Join: Filter: __correlated_sq_3.z > ra.z AND nullif(CAST(ra.k AS Int64), Int64(1)) IS NULL
451+
05)--------Filter: __correlated_sq_2.mark IS DISTINCT FROM Boolean(true)
460452
06)----------LeftMark Join: nullif(CAST(ra.k AS Int64), Int64(1)) = __correlated_sq_2.rb.k Filter: __correlated_sq_2.z > ra.z
461453
07)------------TableScan: ra projection=[k, z]
462454
08)------------SubqueryAlias: __correlated_sq_2
463455
09)--------------Projection: CAST(rb.k AS Int64), rb.z
464456
10)----------------TableScan: rb projection=[k, z]
465-
11)----------EmptyRelation: rows=0
466-
12)--------SubqueryAlias: __correlated_sq_4
467-
13)----------TableScan: rb projection=[z]
457+
11)--------SubqueryAlias: __correlated_sq_3
458+
12)----------TableScan: rb projection=[z]
468459
physical_plan
469-
01)FilterExec: NOT CASE WHEN mark@1 THEN true WHEN mark@2 OR nullif(CAST(k@0 AS Int64), 1) IS NULL AND mark@3 THEN NULL ELSE false END, projection=[k@0]
470-
02)--NestedLoopJoinExec: join_type=RightMark, filter=z@1 > z@0, projection=[k@0, mark@2, mark@3, mark@4]
471-
03)----DataSourceExec: partitions=1, partition_sizes=[1]
472-
04)----NestedLoopJoinExec: join_type=RightMark, filter=z@1 > z@0
473-
05)------EmptyExec
474-
06)------RepartitionExec: partitioning=RoundRobinBatch(4), input_partitions=1
475-
07)--------HashJoinExec: mode=CollectLeft, join_type=RightMark, on=[(rb.k@0, nullif(ra.k,Int64(1))@2)], filter=z@1 > z@0, projection=[k@0, z@1, mark@3]
476-
08)----------ProjectionExec: expr=[CAST(k@0 AS Int64) as rb.k, z@1 as z]
477-
09)------------DataSourceExec: partitions=1, partition_sizes=[1]
478-
10)----------ProjectionExec: expr=[k@0 as k, z@1 as z, nullif(CAST(k@0 AS Int64), 1) as nullif(ra.k,Int64(1))]
479-
11)------------DataSourceExec: partitions=1, partition_sizes=[1]
460+
01)FilterExec: mark@2 IS DISTINCT FROM true OR mark@1 IS NOT DISTINCT FROM true, projection=[k@0]
461+
02)--RepartitionExec: partitioning=RoundRobinBatch(4), input_partitions=1
462+
03)----NestedLoopJoinExec: join_type=LeftMark, filter=z@2 > z@1 AND nullif(CAST(k@0 AS Int64), 1) IS NULL, projection=[k@0, mark@2, mark@3]
463+
04)------CoalescePartitionsExec
464+
05)--------FilterExec: mark@2 IS DISTINCT FROM true
465+
06)----------RepartitionExec: partitioning=RoundRobinBatch(4), input_partitions=1
466+
07)------------HashJoinExec: mode=CollectLeft, join_type=RightMark, on=[(rb.k@0, nullif(ra.k,Int64(1))@2)], filter=z@1 > z@0, projection=[k@0, z@1, mark@3]
467+
08)--------------ProjectionExec: expr=[CAST(k@0 AS Int64) as rb.k, z@1 as z]
468+
09)----------------DataSourceExec: partitions=1, partition_sizes=[1]
469+
10)--------------ProjectionExec: expr=[k@0 as k, z@1 as z, nullif(CAST(k@0 AS Int64), 1) as nullif(ra.k,Int64(1))]
470+
11)----------------DataSourceExec: partitions=1, partition_sizes=[1]
471+
12)------DataSourceExec: partitions=1, partition_sizes=[1]
480472

481473
# The correlation names no column of the subquery, so it stays as a residual
482474
# filter and the subquery is either the whole of `ic` or empty. A NULL in

0 commit comments

Comments
 (0)