Skip to content

Commit b20f1f8

Browse files
committed
Address review: slt tests, unconditional rewrite, doc comments
- Replace the unit tests with end-to-end tests in in_list.slt, covering the rewritten plans, the rows they return, and that SELECT 3 IN (1, NULL) is still NULL outside a filter. - Attempt the rewrite for every InList instead of guarding the match arm on is_null_literal; simplify_filter_in_list now reports whether it changed anything by comparing the list length. - Explain the new simplification in the simplify_filter_predicate doc comment. The slt lists are kept above THRESHOLD_INLINE_INLIST so they stay IN lists rather than being rewritten into OR chains.
1 parent 1e9f250 commit b20f1f8

2 files changed

Lines changed: 114 additions & 97 deletions

File tree

‎datafusion/optimizer/src/eliminate_filter.rs‎

Lines changed: 26 additions & 97 deletions
Original file line numberDiff line numberDiff line change
@@ -100,6 +100,10 @@ struct SimplifiedFilterPredicate {
100100
/// throughout an `AND` / `OR` tree because both operators are monotonic with
101101
/// respect to whether their result can be `TRUE`. It is not safe through `NOT`
102102
/// or arbitrary expressions, so those are deliberately treated as leaves.
103+
///
104+
/// The same equivalence lets `IN` lists drop their `NULL` members, and makes
105+
/// `NOT IN` lists that contain one reject every row. See
106+
/// [`simplify_filter_in_list`].
103107
fn simplify_filter_predicate(expr: Expr) -> SimplifiedFilterPredicate {
104108
match expr {
105109
Expr::Literal(ScalarValue::Boolean(Some(true)), _) => {
@@ -114,9 +118,7 @@ fn simplify_filter_predicate(expr: Expr) -> SimplifiedFilterPredicate {
114118
Expr::BinaryExpr(binary) if binary.op == Operator::Or => {
115119
simplify_filter_or(*binary.left, *binary.right)
116120
}
117-
Expr::InList(in_list) if in_list.list.iter().any(is_null_literal) => {
118-
simplify_filter_in_list(in_list)
119-
}
121+
Expr::InList(in_list) => simplify_filter_in_list(in_list),
120122
expr => simplified(FilterPredicate::Expression(expr), false),
121123
}
122124
}
@@ -125,7 +127,7 @@ fn is_null_literal(expr: &Expr) -> bool {
125127
matches!(expr, Expr::Literal(scalar, _) if scalar.is_null())
126128
}
127129

128-
/// Simplifies an `IN` list that contains `NULL` literals under filter semantics.
130+
/// Simplifies an `IN` list under filter semantics by dropping `NULL` members.
129131
///
130132
/// `x IN (a, NULL)` is `TRUE` exactly when `x` matches `a`: a `NULL` member can
131133
/// only turn `FALSE` into `NULL`, and `NULL` rejects a row just like `FALSE`.
@@ -138,28 +140,36 @@ fn is_null_literal(expr: &Expr) -> bool {
138140
/// This is only sound under filter semantics; the same rewrite in a general
139141
/// expression context would change `SELECT 3 IN (1, NULL)` from `NULL` to `FALSE`.
140142
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-
145143
let InList {
146144
expr,
147145
list,
148146
negated,
149147
} = in_list;
148+
149+
let len_before = list.len();
150150
let list: Vec<Expr> = list.into_iter().filter(|e| !is_null_literal(e)).collect();
151151

152-
if list.is_empty() {
153-
simplified(
154-
FilterPredicate::RejectsAll(Expr::Literal(ScalarValue::Boolean(None), None)),
155-
true,
156-
)
157-
} else {
158-
simplified(
152+
if list.len() == len_before {
153+
// No `NULL` members, so there is nothing to simplify.
154+
return simplified(
159155
FilterPredicate::Expression(Expr::InList(InList::new(expr, list, negated))),
156+
false,
157+
);
158+
}
159+
160+
if negated || list.is_empty() {
161+
// `NOT IN` with a `NULL` member, and `IN` over nothing but `NULL`s, are
162+
// both `NULL` for every row that they do not reject outright.
163+
return simplified(
164+
FilterPredicate::RejectsAll(Expr::Literal(ScalarValue::Boolean(None), None)),
160165
true,
161-
)
166+
);
162167
}
168+
169+
simplified(
170+
FilterPredicate::Expression(Expr::InList(InList::new(expr, list, negated))),
171+
true,
172+
)
163173
}
164174

165175
fn simplify_filter_and(left: Expr, right: Expr) -> SimplifiedFilterPredicate {
@@ -540,85 +550,4 @@ mod tests {
540550
EmptyRelation: rows=0
541551
")
542552
}
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-
}
624553
}

‎datafusion/sqllogictest/test_files/in_list.slt‎

Lines changed: 88 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -858,3 +858,91 @@ ORDER BY n
858858
# Cleanup
859859
statement ok
860860
DROP TABLE in_list_case_items;
861+
862+
863+
##########
864+
# IN lists containing NULL literals, under filter semantics
865+
#
866+
# A NULL member can only turn FALSE into NULL, and a filter keeps only the rows
867+
# for which its predicate is TRUE, so NULL rejects a row just like FALSE:
868+
# x IN (a, NULL) keeps exactly the rows that x IN (a) keeps
869+
# x IN (NULL) keeps nothing
870+
# x NOT IN (a, NULL) keeps nothing: it is FALSE on a match and NULL otherwise
871+
#
872+
# This holds only inside a filter. In a general expression context
873+
# SELECT 3 IN (1, NULL) must still be NULL, which is checked at the end.
874+
##########
875+
876+
statement ok
877+
CREATE TABLE in_list_nulls (label VARCHAR, n INT) AS VALUES
878+
('one', 1),
879+
('eleven', 11),
880+
('other', 42);
881+
882+
statement ok
883+
set datafusion.explain.logical_plan_only = true;
884+
885+
# The NULL member is dropped from the list. The list is kept over
886+
# THRESHOLD_INLINE_INLIST members so that it stays an IN list instead of being
887+
# rewritten into a chain of ORs.
888+
query TT
889+
explain select label from in_list_nulls where n in (1, 11, 42, 7, NULL);
890+
----
891+
logical_plan
892+
01)Projection: in_list_nulls.label
893+
02)--Filter: in_list_nulls.n IN ([Int32(1), Int32(11), Int32(42), Int32(7)])
894+
03)----TableScan: in_list_nulls projection=[label, n]
895+
896+
# A list of nothing but NULLs rejects every row.
897+
query TT
898+
explain select label from in_list_nulls where n in (NULL);
899+
----
900+
logical_plan EmptyRelation: rows=0
901+
902+
# NOT IN with a NULL member is never TRUE, so it rejects every row.
903+
query TT
904+
explain select label from in_list_nulls where n not in (1, 11, NULL);
905+
----
906+
logical_plan EmptyRelation: rows=0
907+
908+
# Lists without a NULL member are left alone.
909+
query TT
910+
explain select label from in_list_nulls where n in (1, 11, 42, 7);
911+
----
912+
logical_plan
913+
01)Projection: in_list_nulls.label
914+
02)--Filter: in_list_nulls.n IN ([Int32(1), Int32(11), Int32(42), Int32(7)])
915+
03)----TableScan: in_list_nulls projection=[label, n]
916+
917+
statement ok
918+
set datafusion.explain.logical_plan_only = false;
919+
920+
# The rewritten filters return the same rows as the originals.
921+
query T rowsort
922+
select label from in_list_nulls where n in (1, 11, 42, 7, NULL);
923+
----
924+
eleven
925+
one
926+
other
927+
928+
query T
929+
select label from in_list_nulls where n in (NULL);
930+
----
931+
932+
query T
933+
select label from in_list_nulls where n not in (1, 11, 42, 7, NULL);
934+
----
935+
936+
# Outside a filter the NULL must still make the result NULL, not FALSE.
937+
query B
938+
select 3 in (1, NULL);
939+
----
940+
NULL
941+
942+
query B
943+
select 1 in (1, NULL);
944+
----
945+
true
946+
947+
statement ok
948+
DROP TABLE in_list_nulls;

0 commit comments

Comments
 (0)