Skip to content

Commit 9d6acf9

Browse files
committed
fix: simplify IN lists containing NULL literals in EliminateFilter
`x IN (a, NULL)` is TRUE exactly when x matches a: a NULL member can only turn FALSE into NULL, and NULL rejects a row just like FALSE. The NULL members can therefore be dropped, and a list of nothing but NULLs rejects every row. `x NOT IN (a, NULL)` is FALSE when x matches a and NULL otherwise, so it is never TRUE and also rejects every row. Leaving the NULLs in place kept filters that PruningPredicate does not handle well, which is the degradation described in apache#26542. Extend simplify_filter_predicate with an Expr::InList arm. This is sound only under filter semantics, where just the TRUE rows are kept; the same rewrite in ExprSimplifier would change SELECT 3 IN (1, NULL) from NULL to FALSE, so it stays in EliminateFilter. Closes apache#26542
1 parent 44a105b commit 9d6acf9

1 file changed

Lines changed: 126 additions & 0 deletions

File tree

‎datafusion/optimizer/src/eliminate_filter.rs‎

Lines changed: 126 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -19,6 +19,7 @@
1919
2020
use datafusion_common::tree_node::Transformed;
2121
use datafusion_common::{Result, ScalarValue};
22+
use datafusion_expr::expr::InList;
2223
use datafusion_expr::{EmptyRelation, Expr, Filter, LogicalPlan, Operator};
2324
use std::sync::Arc;
2425

@@ -113,10 +114,54 @@ fn simplify_filter_predicate(expr: Expr) -> SimplifiedFilterPredicate {
113114
Expr::BinaryExpr(binary) if binary.op == Operator::Or => {
114115
simplify_filter_or(*binary.left, *binary.right)
115116
}
117+
Expr::InList(in_list) if in_list.list.iter().any(is_null_literal) => {
118+
simplify_filter_in_list(in_list)
119+
}
116120
expr => simplified(FilterPredicate::Expression(expr), false),
117121
}
118122
}
119123

124+
fn is_null_literal(expr: &Expr) -> bool {
125+
matches!(expr, Expr::Literal(scalar, _) if scalar.is_null())
126+
}
127+
128+
/// Simplifies an `IN` list that contains `NULL` literals under filter semantics.
129+
///
130+
/// `x IN (a, NULL)` is `TRUE` exactly when `x` matches `a`: a `NULL` member can
131+
/// only turn `FALSE` into `NULL`, and `NULL` rejects a row just like `FALSE`.
132+
/// The `NULL` members can therefore be dropped, and a list of nothing but
133+
/// `NULL`s rejects every row.
134+
///
135+
/// `x NOT IN (a, NULL)` is `FALSE` when `x` matches `a` and `NULL` otherwise, so
136+
/// it is never `TRUE` and rejects every row.
137+
///
138+
/// This is only sound under filter semantics; the same rewrite in a general
139+
/// expression context would change `SELECT 3 IN (1, NULL)` from `NULL` to `FALSE`.
140+
fn simplify_filter_in_list(in_list: InList) -> SimplifiedFilterPredicate {
141+
if in_list.negated {
142+
return simplified(FilterPredicate::RejectsAll(Expr::InList(in_list)), true);
143+
}
144+
145+
let InList {
146+
expr,
147+
list,
148+
negated,
149+
} = in_list;
150+
let list: Vec<Expr> = list.into_iter().filter(|e| !is_null_literal(e)).collect();
151+
152+
if list.is_empty() {
153+
simplified(
154+
FilterPredicate::RejectsAll(Expr::Literal(ScalarValue::Boolean(None), None)),
155+
true,
156+
)
157+
} else {
158+
simplified(
159+
FilterPredicate::Expression(Expr::InList(InList::new(expr, list, negated))),
160+
true,
161+
)
162+
}
163+
}
164+
120165
fn simplify_filter_and(left: Expr, right: Expr) -> SimplifiedFilterPredicate {
121166
let left = simplify_filter_predicate(left);
122167
let right = simplify_filter_predicate(right);
@@ -495,4 +540,85 @@ mod tests {
495540
EmptyRelation: rows=0
496541
")
497542
}
543+
544+
#[test]
545+
fn filter_in_list_with_null_drops_null() -> Result<()> {
546+
// SELECT a FROM test WHERE a IN (1, 2, NULL)
547+
// A NULL member can only turn FALSE into NULL, and NULL rejects a row
548+
// just like FALSE, so the filter keeps exactly the rows that a IN (1, 2) keeps.
549+
let filter_expr = col("a").in_list(
550+
vec![
551+
lit(1u32),
552+
lit(2u32),
553+
Expr::Literal(ScalarValue::UInt32(None), None),
554+
],
555+
false,
556+
);
557+
558+
let plan = LogicalPlanBuilder::from(test_table_scan()?)
559+
.filter(filter_expr)?
560+
.build()?;
561+
562+
assert_optimized_plan_equal!(plan, @r"
563+
Filter: test.a IN ([UInt32(1), UInt32(2)])
564+
TableScan: test
565+
")
566+
}
567+
568+
#[test]
569+
fn filter_in_list_of_only_nulls_rejects_all() -> Result<()> {
570+
// SELECT a FROM test WHERE a IN (NULL) is NULL for every row.
571+
let filter_expr =
572+
col("a").in_list(vec![Expr::Literal(ScalarValue::UInt32(None), None)], false);
573+
574+
let plan = LogicalPlanBuilder::from(test_table_scan()?)
575+
.filter(filter_expr)?
576+
.build()?;
577+
578+
assert_optimized_plan_equal!(plan, @"EmptyRelation: rows=0")
579+
}
580+
581+
#[test]
582+
fn filter_not_in_list_with_null_rejects_all() -> Result<()> {
583+
// SELECT a FROM test WHERE a NOT IN (1, NULL) is FALSE when a = 1 and
584+
// NULL otherwise, so it is never TRUE.
585+
let filter_expr = col("a").in_list(
586+
vec![lit(1u32), Expr::Literal(ScalarValue::UInt32(None), None)],
587+
true,
588+
);
589+
590+
let plan = LogicalPlanBuilder::from(test_table_scan()?)
591+
.filter(filter_expr)?
592+
.build()?;
593+
594+
assert_optimized_plan_equal!(plan, @"EmptyRelation: rows=0")
595+
}
596+
597+
#[test]
598+
fn filter_in_list_without_null_is_untouched() -> Result<()> {
599+
let filter_expr = col("a").in_list(vec![lit(1u32), lit(2u32)], false);
600+
601+
let plan = LogicalPlanBuilder::from(test_table_scan()?)
602+
.filter(filter_expr)?
603+
.build()?;
604+
605+
assert_optimized_plan_equal!(plan, @r"
606+
Filter: test.a IN ([UInt32(1), UInt32(2)])
607+
TableScan: test
608+
")
609+
}
610+
611+
#[test]
612+
fn filter_not_in_list_without_null_is_untouched() -> Result<()> {
613+
let filter_expr = col("a").in_list(vec![lit(1u32), lit(2u32)], true);
614+
615+
let plan = LogicalPlanBuilder::from(test_table_scan()?)
616+
.filter(filter_expr)?
617+
.build()?;
618+
619+
assert_optimized_plan_equal!(plan, @r"
620+
Filter: test.a NOT IN ([UInt32(1), UInt32(2)])
621+
TableScan: test
622+
")
623+
}
498624
}

0 commit comments

Comments
 (0)