Skip to content

Commit 56bf8b4

Browse files
committed
apacheGH-36283: [C++] Fix predicate pushdown for nullable columns with range statistics
Prior to this change, predicate pushdown was broken for nullable columns with range statistics (min != max). Parquet generates guarantees of the form: or_(and_(field >= min, field <= max), is_null(field)) However, Inequality::ExtractOne() only handled single comparisons inside or_(..., is_null), not and_(...) expressions. This meant no inequalities were extracted and SimplifyWithGuarantee() could not simplify predicates. This affected ALL predicates on nullable columns: - Comparisons: equal, less, greater, less_equal, greater_equal - Set membership: is_in The fix adds ExpandNullableRangeGuarantees() which transforms: or_(and_(A, B), is_null(x)) into: [or_(A, is_null(x)), or_(B, is_null(x))] This expansion is valid because (A AND B) OR C ≡ (A OR C) AND (B OR C). Each expanded guarantee can then be processed by existing simplification logic. Added tests for both comparison operators and is_in with nullable range guarantees.
1 parent a9f0a4a commit 56bf8b4

2 files changed

Lines changed: 195 additions & 0 deletions

File tree

‎cpp/src/arrow/compute/expression.cc‎

Lines changed: 68 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -918,6 +918,69 @@ std::vector<Expression> GuaranteeConjunctionMembers(
918918
return FlattenedAssociativeChain(guaranteed_true_predicate).fringe;
919919
}
920920

921+
/// \brief Expand guarantees of the form or_(and_(...), is_null(x)) into multiple
922+
/// guarantees of the form or_(member, is_null(x)).
923+
///
924+
/// Parquet statistics for nullable columns generate guarantees like:
925+
/// or_(and_(field >= min, field <= max), is_null(field))
926+
///
927+
/// By expanding this into:
928+
/// [or_(field >= min, is_null(field)), or_(field <= max, is_null(field))]
929+
///
930+
/// each inequality can be extracted by Inequality::ExtractOne and used for
931+
/// simplification of comparisons, is_in, etc.
932+
///
933+
/// This expansion is logically valid because:
934+
/// (A AND B) OR C ≡ (A OR C) AND (B OR C)
935+
///
936+
/// So treating the expanded forms as separate guarantees (implicitly ANDed)
937+
/// is equivalent to the original.
938+
///
939+
/// Also handles the reversed form: or_(is_null(x), and_(...))
940+
///
941+
/// See: https://github.com/apache/arrow/issues/36283
942+
void ExpandNullableRangeGuarantees(std::vector<Expression>* conjunction_members) {
943+
std::vector<Expression> expanded;
944+
945+
for (const auto& member : *conjunction_members) {
946+
auto call = member.call();
947+
if (!call || call->function_name != "or_kleene" || call->arguments.size() != 2) {
948+
expanded.push_back(member);
949+
continue;
950+
}
951+
952+
const auto& lhs = call->arguments[0];
953+
const auto& rhs = call->arguments[1];
954+
auto lhs_call = lhs.call();
955+
auto rhs_call = rhs.call();
956+
957+
// Detect pattern: or_(and_(...), is_null(x)) or or_(is_null(x), and_(...))
958+
const Expression* and_expr = nullptr;
959+
const Expression* null_expr = nullptr;
960+
961+
if (lhs_call && lhs_call->function_name == "and_kleene" &&
962+
rhs_call && rhs_call->function_name == "is_null") {
963+
and_expr = &lhs;
964+
null_expr = &rhs;
965+
} else if (lhs_call && lhs_call->function_name == "is_null" &&
966+
rhs_call && rhs_call->function_name == "and_kleene") {
967+
and_expr = &rhs;
968+
null_expr = &lhs;
969+
}
970+
971+
if (and_expr && null_expr) {
972+
// Expand: for each member of the and_kleene, create or_(member, is_null(x))
973+
for (const auto& and_member : FlattenedAssociativeChain(*and_expr).fringe) {
974+
expanded.push_back(or_(and_member, *null_expr));
975+
}
976+
} else {
977+
expanded.push_back(member);
978+
}
979+
}
980+
981+
*conjunction_members = std::move(expanded);
982+
}
983+
921984
/// \brief Extract an equality from an expression.
922985
///
923986
/// Recognizes expressions of the form:
@@ -1436,6 +1499,11 @@ Result<Expression> SimplifyWithGuarantee(Expression expr,
14361499

14371500
RETURN_NOT_OK(ExtractKnownFieldValues(&conjunction_members, &known_values));
14381501

1502+
// Expand or_(and_(...), is_null(x)) guarantees into multiple or_(ineq, is_null(x))
1503+
// guarantees. This enables predicate pushdown for nullable columns with range
1504+
// statistics (the common case). See: https://github.com/apache/arrow/issues/36283
1505+
ExpandNullableRangeGuarantees(&conjunction_members);
1506+
14391507
ARROW_ASSIGN_OR_RAISE(expr,
14401508
ReplaceFieldsWithKnownValues(known_values, std::move(expr)));
14411509

‎cpp/src/arrow/compute/expression_test.cc‎

Lines changed: 127 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -2003,6 +2003,133 @@ TEST(Expression, SimplifyIsIn) {
20032003
.ExpectUnchanged();
20042004
}
20052005

2006+
// Test for nullable range guarantees: or_(and_(>= min, <= max), is_null(x))
2007+
// This is the pattern generated by parquet statistics for nullable columns.
2008+
// See: https://github.com/apache/arrow/issues/36283
2009+
TEST(Expression, SimplifyWithNullableRangeGuarantee) {
2010+
// Helper to create the nullable range guarantee pattern that parquet generates
2011+
auto nullable_range = [](Expression field, int min_val, int max_val) {
2012+
return or_(and_(greater_equal(field, literal(min_val)),
2013+
less_equal(field, literal(max_val))),
2014+
is_null(field));
2015+
};
2016+
2017+
// Also test reversed form: or_(is_null(x), and_(...))
2018+
auto nullable_range_reversed = [](Expression field, int min_val, int max_val) {
2019+
return or_(is_null(field),
2020+
and_(greater_equal(field, literal(min_val)),
2021+
less_equal(field, literal(max_val))));
2022+
};
2023+
2024+
// Test equal - value outside range
2025+
// For nullable guarantees, "definitely false" becomes not_(true_unless_null(x))
2026+
// which is equivalent to false for non-null rows and null for null rows
2027+
Simplify{equal(field_ref("i32"), literal(50))}
2028+
.WithGuarantee(nullable_range(field_ref("i32"), 100, 200))
2029+
.Expect(not_(true_unless_null(field_ref("i32"))));
2030+
2031+
// Test equal - value inside range (cannot simplify)
2032+
Simplify{equal(field_ref("i32"), literal(150))}
2033+
.WithGuarantee(nullable_range(field_ref("i32"), 100, 200))
2034+
.ExpectUnchanged();
2035+
2036+
// Test less - max < filter value (all rows satisfy)
2037+
Simplify{less(field_ref("i32"), literal(300))}
2038+
.WithGuarantee(nullable_range(field_ref("i32"), 100, 200))
2039+
.Expect(true_unless_null(field_ref("i32")));
2040+
2041+
// Test less - filter value <= min (no rows satisfy)
2042+
Simplify{less(field_ref("i32"), literal(50))}
2043+
.WithGuarantee(nullable_range(field_ref("i32"), 100, 200))
2044+
.Expect(not_(true_unless_null(field_ref("i32"))));
2045+
2046+
// Test greater - min > filter value (all rows satisfy)
2047+
Simplify{greater(field_ref("i32"), literal(50))}
2048+
.WithGuarantee(nullable_range(field_ref("i32"), 100, 200))
2049+
.Expect(true_unless_null(field_ref("i32")));
2050+
2051+
// Test greater - filter value >= max (no rows satisfy)
2052+
Simplify{greater(field_ref("i32"), literal(250))}
2053+
.WithGuarantee(nullable_range(field_ref("i32"), 100, 200))
2054+
.Expect(not_(true_unless_null(field_ref("i32"))));
2055+
2056+
// Test less_equal - max <= filter value (all rows satisfy)
2057+
Simplify{less_equal(field_ref("i32"), literal(200))}
2058+
.WithGuarantee(nullable_range(field_ref("i32"), 100, 200))
2059+
.Expect(true_unless_null(field_ref("i32")));
2060+
2061+
// Test greater_equal - min >= filter value (all rows satisfy)
2062+
Simplify{greater_equal(field_ref("i32"), literal(100))}
2063+
.WithGuarantee(nullable_range(field_ref("i32"), 100, 200))
2064+
.Expect(true_unless_null(field_ref("i32")));
2065+
2066+
// Test with reversed guarantee form: or_(is_null(x), and_(...))
2067+
Simplify{equal(field_ref("i32"), literal(50))}
2068+
.WithGuarantee(nullable_range_reversed(field_ref("i32"), 100, 200))
2069+
.Expect(not_(true_unless_null(field_ref("i32"))));
2070+
2071+
Simplify{greater(field_ref("i32"), literal(250))}
2072+
.WithGuarantee(nullable_range_reversed(field_ref("i32"), 100, 200))
2073+
.Expect(not_(true_unless_null(field_ref("i32"))));
2074+
}
2075+
2076+
TEST(Expression, SimplifyIsInWithNullableRangeGuarantee) {
2077+
auto is_in_i32 = [](std::string json_array,
2078+
SetLookupOptions::NullMatchingBehavior null_matching) {
2079+
SetLookupOptions options{ArrayFromJSON(int32(), json_array), null_matching};
2080+
return call("is_in", {field_ref("i32")}, options);
2081+
};
2082+
2083+
// Helper to create the nullable range guarantee pattern
2084+
auto nullable_range = [](Expression field, int min_val, int max_val) {
2085+
return or_(and_(greater_equal(field, literal(min_val)),
2086+
less_equal(field, literal(max_val))),
2087+
is_null(field));
2088+
};
2089+
2090+
for (SetLookupOptions::NullMatchingBehavior null_matching : {
2091+
SetLookupOptions::MATCH,
2092+
SetLookupOptions::SKIP,
2093+
}) {
2094+
// All values outside range -> should simplify to false
2095+
Simplify{is_in_i32("[1,2,3]", null_matching)}
2096+
.WithGuarantee(nullable_range(field_ref("i32"), 100, 200))
2097+
.Expect(false);
2098+
2099+
// All values below range
2100+
Simplify{is_in_i32("[10,20,30]", null_matching)}
2101+
.WithGuarantee(nullable_range(field_ref("i32"), 100, 200))
2102+
.Expect(false);
2103+
2104+
// All values above range
2105+
Simplify{is_in_i32("[300,400,500]", null_matching)}
2106+
.WithGuarantee(nullable_range(field_ref("i32"), 100, 200))
2107+
.Expect(false);
2108+
2109+
// Some values inside range, some outside -> keep only values in range
2110+
Simplify{is_in_i32("[50,150,250]", null_matching)}
2111+
.WithGuarantee(nullable_range(field_ref("i32"), 100, 200))
2112+
.Expect(is_in_i32("[150]", null_matching));
2113+
2114+
// Values at boundaries
2115+
Simplify{is_in_i32("[99,100,200,201]", null_matching)}
2116+
.WithGuarantee(nullable_range(field_ref("i32"), 100, 200))
2117+
.Expect(is_in_i32("[100,200]", null_matching));
2118+
2119+
// All values inside range -> unchanged
2120+
Simplify{is_in_i32("[120,150,180]", null_matching)}
2121+
.WithGuarantee(nullable_range(field_ref("i32"), 100, 200))
2122+
.ExpectUnchanged();
2123+
}
2124+
2125+
// Test with reversed guarantee form
2126+
Simplify{is_in_i32("[1,2,3]", SetLookupOptions::MATCH)}
2127+
.WithGuarantee(or_(is_null(field_ref("i32")),
2128+
and_(greater_equal(field_ref("i32"), literal(100)),
2129+
less_equal(field_ref("i32"), literal(200)))))
2130+
.Expect(false);
2131+
}
2132+
20062133
TEST(Expression, SimplifyThenExecute) {
20072134
auto filter =
20082135
or_({equal(field_ref("f32"), literal(0)),

0 commit comments

Comments
 (0)