Skip to content

Commit c2bdac8

Browse files
fzlzjerryfzlzjerry
committed
fix: preserve null semantics without regressing filters
1 parent 5d9051e commit c2bdac8

8 files changed

Lines changed: 257 additions & 117 deletions

File tree

‎datafusion/functions-nested/src/array_has.rs‎

Lines changed: 5 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -179,9 +179,11 @@ impl ScalarUDFImpl for ArrayHas {
179179
let mut has_unsafe_nullable_element = false;
180180
for arg in args.iter() {
181181
// `needle IN (needle)` preserves NULL semantics. A different
182-
// nullable element does not: array_has([NULL], value) is
183-
// false, while value IN (NULL) is NULL.
184-
if info.nullable(arg)? && arg != &*needle {
182+
// nullable element does not: array_has([NULL], value) is false,
183+
// while value IN (NULL) is NULL. Volatile expressions are
184+
// evaluated separately, so syntactic equality is insufficient.
185+
let safe_same_expr = arg == &*needle && !arg.is_volatile();
186+
if info.nullable(arg)? && !safe_same_expr {
185187
has_unsafe_nullable_element = true;
186188
break;
187189
}

‎datafusion/optimizer/src/eliminate_filter.rs‎

Lines changed: 205 additions & 20 deletions
Original file line numberDiff line numberDiff line change
@@ -15,18 +15,18 @@
1515
// specific language governing permissions and limitations
1616
// under the License.
1717

18-
//! [`EliminateFilter`] replaces `where false` or `where null` with an empty relation.
18+
//! [`EliminateFilter`] removes filters that accept all or no input rows.
1919
2020
use datafusion_common::tree_node::Transformed;
2121
use datafusion_common::{Result, ScalarValue};
22-
use datafusion_expr::{EmptyRelation, Expr, Filter, LogicalPlan};
22+
use datafusion_expr::{EmptyRelation, Expr, Filter, LogicalPlan, Operator};
2323
use std::sync::Arc;
2424

2525
use crate::optimizer::ApplyOrder;
2626
use crate::{OptimizerConfig, OptimizerRule};
2727

28-
/// Optimization rule that eliminate the scalar value (true/false/null) filter
29-
/// with an [LogicalPlan::EmptyRelation]
28+
/// Optimization rule that eliminates filters whose predicates always accept or
29+
/// reject their input rows.
3030
///
3131
/// This saves time in planning and executing the query.
3232
/// Note that this rule should be applied after simplify expressions optimizer rule.
@@ -58,35 +58,132 @@ impl OptimizerRule for EliminateFilter {
5858
plan: LogicalPlan,
5959
_config: &dyn OptimizerConfig,
6060
) -> Result<Transformed<LogicalPlan>> {
61-
match plan {
62-
LogicalPlan::Filter(Filter {
63-
predicate: Expr::Literal(ScalarValue::Boolean(v), _),
64-
input,
65-
..
66-
}) => match v {
67-
Some(true) => Ok(Transformed::yes(Arc::unwrap_or_clone(input))),
68-
Some(false) | None => Ok(Transformed::yes(LogicalPlan::EmptyRelation(
69-
EmptyRelation {
70-
produce_one_row: false,
71-
schema: Arc::clone(input.schema()),
72-
},
73-
))),
74-
},
75-
_ => Ok(Transformed::no(plan)),
61+
let LogicalPlan::Filter(Filter {
62+
predicate, input, ..
63+
}) = plan
64+
else {
65+
return Ok(Transformed::no(plan));
66+
};
67+
68+
let simplified = simplify_filter_predicate(predicate);
69+
match simplified.predicate {
70+
FilterPredicate::AcceptsAll => {
71+
Ok(Transformed::yes(Arc::unwrap_or_clone(input)))
72+
}
73+
FilterPredicate::RejectsAll => Ok(Transformed::yes(
74+
LogicalPlan::EmptyRelation(EmptyRelation {
75+
produce_one_row: false,
76+
schema: Arc::clone(input.schema()),
77+
}),
78+
)),
79+
FilterPredicate::Expression(predicate) => Ok(Transformed::new_transformed(
80+
LogicalPlan::Filter(Filter::new(predicate, input)),
81+
simplified.transformed,
82+
)),
7683
}
7784
}
7885
}
7986

87+
/// The outcome of a predicate when only rows for which it evaluates to `TRUE`
88+
/// are retained.
89+
enum FilterPredicate {
90+
AcceptsAll,
91+
RejectsAll,
92+
Expression(Expr),
93+
}
94+
95+
struct SimplifiedFilterPredicate {
96+
predicate: FilterPredicate,
97+
transformed: bool,
98+
}
99+
100+
/// Simplifies positive `AND` / `OR` trees according to filter semantics.
101+
///
102+
/// A `NULL` predicate rejects a row just like `FALSE`. This equivalence is safe
103+
/// throughout an `AND` / `OR` tree because both operators are monotonic with
104+
/// respect to whether their result can be `TRUE`. It is not safe through `NOT`
105+
/// or arbitrary expressions, so those are deliberately treated as leaves.
106+
fn simplify_filter_predicate(expr: Expr) -> SimplifiedFilterPredicate {
107+
match expr {
108+
Expr::Literal(ScalarValue::Boolean(Some(true)), _) => {
109+
simplified(FilterPredicate::AcceptsAll, false)
110+
}
111+
Expr::Literal(ScalarValue::Boolean(Some(false) | None), _) => {
112+
simplified(FilterPredicate::RejectsAll, false)
113+
}
114+
Expr::BinaryExpr(binary) if binary.op == Operator::And => {
115+
simplify_filter_and(*binary.left, *binary.right)
116+
}
117+
Expr::BinaryExpr(binary) if binary.op == Operator::Or => {
118+
simplify_filter_or(*binary.left, *binary.right)
119+
}
120+
expr => simplified(FilterPredicate::Expression(expr), false),
121+
}
122+
}
123+
124+
fn simplify_filter_and(left: Expr, right: Expr) -> SimplifiedFilterPredicate {
125+
let left = simplify_filter_predicate(left);
126+
let right = simplify_filter_predicate(right);
127+
let children_transformed = left.transformed || right.transformed;
128+
129+
match (left.predicate, right.predicate) {
130+
(FilterPredicate::RejectsAll, _) | (_, FilterPredicate::RejectsAll) => {
131+
simplified(FilterPredicate::RejectsAll, true)
132+
}
133+
(FilterPredicate::AcceptsAll, predicate)
134+
| (predicate, FilterPredicate::AcceptsAll) => simplified(predicate, true),
135+
(FilterPredicate::Expression(left), FilterPredicate::Expression(right)) => {
136+
simplified(
137+
FilterPredicate::Expression(left.and(right)),
138+
children_transformed,
139+
)
140+
}
141+
}
142+
}
143+
144+
fn simplify_filter_or(left: Expr, right: Expr) -> SimplifiedFilterPredicate {
145+
let left = simplify_filter_predicate(left);
146+
let right = simplify_filter_predicate(right);
147+
let children_transformed = left.transformed || right.transformed;
148+
149+
match (left.predicate, right.predicate) {
150+
(FilterPredicate::AcceptsAll, _) | (_, FilterPredicate::AcceptsAll) => {
151+
simplified(FilterPredicate::AcceptsAll, true)
152+
}
153+
(FilterPredicate::RejectsAll, predicate)
154+
| (predicate, FilterPredicate::RejectsAll) => simplified(predicate, true),
155+
(FilterPredicate::Expression(left), FilterPredicate::Expression(right)) => {
156+
simplified(
157+
FilterPredicate::Expression(left.or(right)),
158+
children_transformed,
159+
)
160+
}
161+
}
162+
}
163+
164+
fn simplified(
165+
predicate: FilterPredicate,
166+
transformed: bool,
167+
) -> SimplifiedFilterPredicate {
168+
SimplifiedFilterPredicate {
169+
predicate,
170+
transformed,
171+
}
172+
}
173+
80174
#[cfg(test)]
81175
mod tests {
176+
use std::ops::Not;
82177
use std::sync::Arc;
83178

84179
use crate::OptimizerContext;
85180
use crate::assert_optimized_plan_eq_snapshot;
86181
use datafusion_common::{Result, ScalarValue};
87182
use datafusion_expr::{Expr, col, lit, logical_plan::builder::LogicalPlanBuilder};
88183

89-
use crate::eliminate_filter::EliminateFilter;
184+
use crate::eliminate_filter::{
185+
EliminateFilter, FilterPredicate, simplify_filter_predicate,
186+
};
90187
use crate::test::*;
91188
use datafusion_expr::test::function_stub::sum;
92189

@@ -134,6 +231,94 @@ mod tests {
134231
assert_optimized_plan_equal!(plan, @"EmptyRelation: rows=0")
135232
}
136233

234+
#[test]
235+
fn filter_and_null() -> Result<()> {
236+
let null = Expr::Literal(ScalarValue::Boolean(None), None);
237+
238+
let plan = LogicalPlanBuilder::from(test_table_scan()?)
239+
.filter(col("b").and(null.clone()))?
240+
.build()?;
241+
assert_optimized_plan_equal!(plan, @"EmptyRelation: rows=0")?;
242+
243+
let plan = LogicalPlanBuilder::from(test_table_scan()?)
244+
.filter(null.and(col("b")))?
245+
.build()?;
246+
assert_optimized_plan_equal!(plan, @"EmptyRelation: rows=0")?;
247+
248+
Ok(())
249+
}
250+
251+
#[test]
252+
fn filter_or_null() -> Result<()> {
253+
let null = Expr::Literal(ScalarValue::Boolean(None), None);
254+
255+
let plan = LogicalPlanBuilder::from(test_table_scan()?)
256+
.filter(col("b").or(null.clone()))?
257+
.build()?;
258+
assert_optimized_plan_equal!(
259+
plan,
260+
@r"
261+
Filter: test.b
262+
TableScan: test
263+
"
264+
)?;
265+
266+
let plan = LogicalPlanBuilder::from(test_table_scan()?)
267+
.filter(null.or(col("b")))?
268+
.build()?;
269+
assert_optimized_plan_equal!(
270+
plan,
271+
@r"
272+
Filter: test.b
273+
TableScan: test
274+
"
275+
)?;
276+
277+
Ok(())
278+
}
279+
280+
#[test]
281+
fn filter_nested_null_predicates() -> Result<()> {
282+
let null = Expr::Literal(ScalarValue::Boolean(None), None);
283+
284+
let plan = LogicalPlanBuilder::from(test_table_scan()?)
285+
.filter(col("b").and(col("b").or(null.clone())))?
286+
.build()?;
287+
assert_optimized_plan_equal!(
288+
plan,
289+
@r"
290+
Filter: test.b AND test.b
291+
TableScan: test
292+
"
293+
)?;
294+
295+
let plan = LogicalPlanBuilder::from(test_table_scan()?)
296+
.filter(col("b").or(col("c").and(null)))?
297+
.build()?;
298+
assert_optimized_plan_equal!(
299+
plan,
300+
@r"
301+
Filter: test.b
302+
TableScan: test
303+
"
304+
)?;
305+
306+
Ok(())
307+
}
308+
309+
#[test]
310+
fn filter_null_simplification_does_not_cross_not() {
311+
let null = Expr::Literal(ScalarValue::Boolean(None), None);
312+
let predicate = col("b").or(null).not();
313+
let result = simplify_filter_predicate(predicate.clone());
314+
315+
assert!(!result.transformed);
316+
let FilterPredicate::Expression(actual) = result.predicate else {
317+
panic!("expected the predicate to remain an expression")
318+
};
319+
assert_eq!(actual, predicate);
320+
}
321+
137322
#[test]
138323
fn filter_false_nested() -> Result<()> {
139324
let filter_expr = lit(false);

0 commit comments

Comments
 (0)