Skip to content

Commit 8733e2e

Browse files
raghavyadav01claudealamb
authored
fix: simplify IN lists containing NULL literals in EliminateFilter (apache#26548)
## Which issue does this PR close? - Closes apache#26542. ## Rationale for this change Under filter semantics only rows for which the predicate is `TRUE` are kept, so `NULL` rejects a row exactly like `FALSE`. That makes two rewrites sound for `IN` lists that hold `NULL` literals: - `x IN (a, NULL)` is `TRUE` exactly when `x` matches `a`. A `NULL` member can only turn `FALSE` into `NULL`, and both reject. The `NULL` members can be dropped, and a list of nothing but `NULL`s rejects every row. - `x NOT IN (a, NULL)` is `FALSE` when `x` matches `a` and `NULL` otherwise, so it is never `TRUE` and rejects every row. Leaving the `NULL`s in place keeps a filter that `PruningPredicate` does not handle well, which is the pruning degradation described in the issue. apache#24711 fixed this only for the compact path (lists over 20 members) and apache#25187 made short lists on several types reach the same path. ## What changes are included in this PR? An `Expr::InList` arm in `simplify_filter_predicate`, plus a `simplify_filter_in_list` helper and an `is_null_literal` predicate, in `datafusion/optimizer/src/eliminate_filter.rs`. The rewrite stays in `EliminateFilter` deliberately. It is **not** sound in `ExprSimplifier`: in a general expression context `SELECT 3 IN (1, NULL)` must remain `NULL`, and dropping the `NULL` would make it `FALSE`. The negated case keeps the original `InList` inside `FilterPredicate::RejectsAll` rather than substituting a literal, so nothing is discarded that the `AND`/`OR` reconstruction may still need. ## Are these changes tested? Yes — five tests in `eliminate_filter.rs`: | test | asserts | |---|---| | `filter_in_list_with_null_drops_null` | `a IN (1, 2, NULL)` → `a IN (1, 2)` | | `filter_in_list_of_only_nulls_rejects_all` | `a IN (NULL)` → `EmptyRelation` | | `filter_not_in_list_with_null_rejects_all` | `a NOT IN (1, NULL)` → `EmptyRelation` | | `filter_in_list_without_null_is_untouched` | no `NULL` → unchanged | | `filter_not_in_list_without_null_is_untouched` | no `NULL` → unchanged | I wrote the tests first and confirmed the three `NULL` cases **fail on `main`** before the change and pass after, while the two control tests pass in both states. Also run: the full `datafusion-optimizer` suite (948 + 29 + 5 passing), `cargo fmt --all -- --check`, and `cargo clippy -p datafusion-optimizer --all-targets -- -D warnings`, all clean. `in_list.slt` and the `null_aware_*` slt files pass. `expr`, `predicates`, `scalar` and `aggregate` slt files each fail identically with and without this change on my machine (a local test-data issue), so they are unaffected. ## Are there any user-facing changes? Explain output for filters whose `IN` list contains `NULL` literals: the `NULL` members no longer appear, and a filter that can never be `TRUE` becomes an empty relation. Query results are unchanged. --------- Signed-off-by: Raghvendra Yadav <[email protected]> Co-authored-by: Claude Opus 5 (1M context) <[email protected]> Co-authored-by: Andrew Lamb <[email protected]>
1 parent 56eca4a commit 8733e2e

5 files changed

Lines changed: 145 additions & 5 deletions

File tree

‎datafusion/optimizer/src/eliminate_filter.rs‎

Lines changed: 52 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -6,6 +6,7 @@
66
77
use datafusion_common::tree_node::Transformed;
88
use datafusion_common::{Result, ScalarValue};
9+
use datafusion_expr::expr::InList;
910
use datafusion_expr::{EmptyRelation, Expr, Filter, LogicalPlan, Operator};
1011
use std::sync::Arc;
1112

@@ -86,6 +87,10 @@ struct SimplifiedFilterPredicate {
8687
/// throughout an `AND` / `OR` tree because both operators are monotonic with
8788
/// respect to whether their result can be `TRUE`. It is not safe through `NOT`
8889
/// or arbitrary expressions, so those are deliberately treated as leaves.
90+
///
91+
/// The same equivalence lets `IN` lists drop their `NULL` members, and makes
92+
/// `NOT IN` lists that contain one reject every row. See
93+
/// [`simplify_filter_in_list`].
8994
fn simplify_filter_predicate(expr: Expr) -> SimplifiedFilterPredicate {
9095
match expr {
9196
Expr::Literal(ScalarValue::Boolean(Some(true)), _) => {
@@ -100,10 +105,57 @@ fn simplify_filter_predicate(expr: Expr) -> SimplifiedFilterPredicate {
100105
Expr::BinaryExpr(binary) if binary.op == Operator::Or => {
101106
simplify_filter_or(*binary.left, *binary.right)
102107
}
108+
Expr::InList(in_list) => simplify_filter_in_list(in_list),
103109
expr => simplified(FilterPredicate::Expression(expr), false),
104110
}
105111
}
106112

113+
fn is_null_literal(expr: &Expr) -> bool {
114+
matches!(expr, Expr::Literal(scalar, _) if scalar.is_null())
115+
}
116+
117+
/// Simplifies an `IN` list under filter semantics by dropping `NULL` members.
118+
///
119+
/// `x NOT IN (a, NULL)` is `FALSE` when `x` matches `a` and `NULL` otherwise, so
120+
/// it is never `TRUE` and rejects every row.
121+
///
122+
/// This is only sound under filter semantics; the same rewrite in a general
123+
/// expression context would change `SELECT 3 IN (1, NULL)` from `NULL` to `FALSE`.
124+
fn simplify_filter_in_list(in_list: InList) -> SimplifiedFilterPredicate {
125+
let InList {
126+
expr,
127+
mut list,
128+
negated,
129+
} = in_list;
130+
131+
// `retain` drops the `NULL`s in place. Most lists have none, and that case
132+
// then costs one pass and no allocation.
133+
let len_before = list.len();
134+
list.retain(|e| !is_null_literal(e));
135+
136+
if list.len() == len_before {
137+
// No `NULL` members, so there is nothing to simplify.
138+
return simplified(
139+
FilterPredicate::Expression(Expr::InList(InList::new(expr, list, negated))),
140+
false,
141+
);
142+
}
143+
144+
if negated || list.is_empty() {
145+
// `NOT IN` with a `NULL` member, and `IN` over nothing but `NULL`s, are
146+
// both `NULL` for every row that they do not reject outright.
147+
return simplified(
148+
FilterPredicate::RejectsAll(Expr::Literal(ScalarValue::Boolean(None), None)),
149+
true,
150+
);
151+
}
152+
153+
simplified(
154+
FilterPredicate::Expression(Expr::InList(InList::new(expr, list, negated))),
155+
true,
156+
)
157+
}
158+
107159
fn simplify_filter_and(left: Expr, right: Expr) -> SimplifiedFilterPredicate {
108160
let left = simplify_filter_predicate(left);
109161
let right = simplify_filter_predicate(right);

‎datafusion/sqllogictest/test_files/eliminate_outer_join.slt‎

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -84,9 +84,9 @@ explain select * from t1 left join t2 on t1.a = t2.x where t2.x in (1, 2, null);
8484
----
8585
logical_plan
8686
01)Inner Join: t1.a = t2.x
87-
02)--Filter: t1.a IN ([Int32(1), Int32(2), Int32(NULL)])
87+
02)--Filter: t1.a IN ([Int32(1), Int32(2)])
8888
03)----TableScan: t1 projection=[a, b, c]
89-
04)--Filter: t2.x IN ([Int32(1), Int32(2), Int32(NULL)])
89+
04)--Filter: t2.x IN ([Int32(1), Int32(2)])
9090
05)----TableScan: t2 projection=[x, y, z]
9191

9292
query IITIIT rowsort

‎datafusion/sqllogictest/test_files/in_list.slt‎

Lines changed: 88 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1059,3 +1059,91 @@ ORDER BY n
10591059
# Cleanup
10601060
statement ok
10611061
DROP TABLE in_list_case_items;
1062+
1063+
1064+
##########
1065+
# IN lists containing NULL literals, under filter semantics
1066+
#
1067+
# A NULL member can only turn FALSE into NULL, and a filter keeps only the rows
1068+
# for which its predicate is TRUE, so NULL rejects a row just like FALSE:
1069+
# x IN (a, NULL) keeps exactly the rows that x IN (a) keeps
1070+
# x IN (NULL) keeps nothing
1071+
# x NOT IN (a, NULL) keeps nothing: it is FALSE on a match and NULL otherwise
1072+
#
1073+
# This holds only inside a filter. In a general expression context
1074+
# SELECT 3 IN (1, NULL) must still be NULL, which is checked at the end.
1075+
##########
1076+
1077+
statement ok
1078+
CREATE TABLE in_list_nulls (label VARCHAR, n INT) AS VALUES
1079+
('one', 1),
1080+
('eleven', 11),
1081+
('other', 42);
1082+
1083+
statement ok
1084+
set datafusion.explain.logical_plan_only = true;
1085+
1086+
# The NULL member is dropped from the list. The list is kept over
1087+
# THRESHOLD_INLINE_INLIST members so that it stays an IN list instead of being
1088+
# rewritten into a chain of ORs.
1089+
query TT
1090+
explain select label from in_list_nulls where n in (1, 11, 42, 7, NULL);
1091+
----
1092+
logical_plan
1093+
01)Projection: in_list_nulls.label
1094+
02)--Filter: in_list_nulls.n IN ([Int32(1), Int32(11), Int32(42), Int32(7)])
1095+
03)----TableScan: in_list_nulls projection=[label, n]
1096+
1097+
# A list of nothing but NULLs rejects every row.
1098+
query TT
1099+
explain select label from in_list_nulls where n in (NULL);
1100+
----
1101+
logical_plan EmptyRelation: rows=0
1102+
1103+
# NOT IN with a NULL member is never TRUE, so it rejects every row.
1104+
query TT
1105+
explain select label from in_list_nulls where n not in (1, 11, NULL);
1106+
----
1107+
logical_plan EmptyRelation: rows=0
1108+
1109+
# Lists without a NULL member are left alone.
1110+
query TT
1111+
explain select label from in_list_nulls where n in (1, 11, 42, 7);
1112+
----
1113+
logical_plan
1114+
01)Projection: in_list_nulls.label
1115+
02)--Filter: in_list_nulls.n IN ([Int32(1), Int32(11), Int32(42), Int32(7)])
1116+
03)----TableScan: in_list_nulls projection=[label, n]
1117+
1118+
statement ok
1119+
set datafusion.explain.logical_plan_only = false;
1120+
1121+
# The rewritten filters return the same rows as the originals.
1122+
query T rowsort
1123+
select label from in_list_nulls where n in (1, 11, 42, 7, NULL);
1124+
----
1125+
eleven
1126+
one
1127+
other
1128+
1129+
query T
1130+
select label from in_list_nulls where n in (NULL);
1131+
----
1132+
1133+
query T
1134+
select label from in_list_nulls where n not in (1, 11, 42, 7, NULL);
1135+
----
1136+
1137+
# Outside a filter the NULL must still make the result NULL, not FALSE.
1138+
query B
1139+
select 3 in (1, NULL);
1140+
----
1141+
NULL
1142+
1143+
query B
1144+
select 1 in (1, NULL);
1145+
----
1146+
true
1147+
1148+
statement ok
1149+
DROP TABLE in_list_nulls;

‎datafusion/sqllogictest/test_files/simplify_expr.slt‎

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -296,10 +296,10 @@ explain select price from decimal_prices where cast(price as decimal(38,15)) in
296296
);
297297
----
298298
logical_plan
299-
01)Filter: CAST(decimal_prices.price AS Decimal128(38, 15)) IN ([Decimal128(4.000000000000000,38,15), Decimal128(4.000000000000001,38,15), Decimal128(NULL,38,15)])
299+
01)Filter: CAST(decimal_prices.price AS Decimal128(38, 15)) IN ([Decimal128(4.000000000000000,38,15), Decimal128(4.000000000000001,38,15)])
300300
02)--TableScan: decimal_prices projection=[price]
301301
physical_plan
302-
01)FilterExec: CAST(price@0 AS Decimal128(38, 15)) IN (SET) ([4.000000000000000, 4.000000000000001, NULL])
302+
01)FilterExec: CAST(price@0 AS Decimal128(38, 15)) IN (SET) ([4.000000000000000, 4.000000000000001])
303303
02)--DataSourceExec: partitions=1, partition_sizes=[1]
304304

305305
query TT

0 commit comments

Comments
 (0)