Skip to content

Commit e5d3cc8

Browse files
robert3005claude
andcommitted
Prove comparisons true for every row from statistics
Stats rewrites could only falsify a predicate. A scan can also skip a predicate that statistics prove true for every row, for example a hash join bound that covers the whole range of a column in a file. - Binary comparisons, AND, OR and BETWEEN get `satisfy` rules. A comparison is proven when the bounds of its operands order every pair of values and neither operand holds a null or a NaN. - `VortexFile::is_satisfied` proves a filter from the file statistics. - `VortexFile::is_satisfied_by_non_null_rows` proves it for the rows in which no column is null. This holds when a filter would only remove rows with nulls. Co-Authored-By: Claude Opus 5.5 <[email protected]> Signed-off-by: Robert Kruszewski <[email protected]>
1 parent 1dba73c commit e5d3cc8

4 files changed

Lines changed: 204 additions & 1 deletion

File tree

‎vortex-expr/src/stats/rewrite/builtins.rs‎

Lines changed: 74 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -52,6 +52,7 @@ use vortex_session::VortexSession;
5252
use crate::stats::bound::stat;
5353
use crate::stats::rewrite::StatsRewriteRule;
5454
use crate::stats::rewrite::falsify;
55+
use crate::stats::rewrite::satisfy;
5556
use crate::stats::rewrite::like_variant::LikeVariant;
5657
use crate::stats::session::StatsSession;
5758

@@ -128,6 +129,14 @@ impl StatsRewriteRule for BinaryNanCountStatsRewrite {
128129
) -> VortexResult<Option<BoundExpression>> {
129130
binary_falsify::<NanCountProof>(expr, session)
130131
}
132+
133+
fn satisfy(
134+
&self,
135+
expr: &BoundExpression,
136+
session: &VortexSession,
137+
) -> VortexResult<Option<BoundExpression>> {
138+
binary_satisfy(expr, session)
139+
}
131140
}
132141

133142
#[derive(Debug)]
@@ -221,6 +230,56 @@ fn binary_falsify<P: NonNanProof>(
221230
})
222231
}
223232

233+
/// Proves a comparison true for every row: the bounds of the operands order every pair of
234+
/// values, and neither operand holds a null or a NaN, for which a comparison is not true.
235+
fn binary_satisfy(
236+
expr: &BoundExpression,
237+
session: &VortexSession,
238+
) -> VortexResult<Option<BoundExpression>> {
239+
let operator = expr.as_::<Binary>();
240+
let lhs = expr.child(0);
241+
let rhs = expr.child(1);
242+
243+
let value_predicate = match operator {
244+
Operator::Gt => min(lhs).zip(max(rhs)).map(|(a, b)| gt(a, b)),
245+
Operator::Gte => min(lhs).zip(max(rhs)).map(|(a, b)| gt_eq(a, b)),
246+
Operator::Lt => max(lhs).zip(min(rhs)).map(|(a, b)| lt(a, b)),
247+
Operator::Lte => max(lhs).zip(min(rhs)).map(|(a, b)| lt_eq(a, b)),
248+
Operator::And => {
249+
return Ok(match (satisfy(lhs, session)?, satisfy(rhs, session)?) {
250+
(Some(lhs), Some(rhs)) => Some(and(lhs, rhs)),
251+
_ => None,
252+
});
253+
}
254+
Operator::Or => {
255+
return Ok(or_collect(
256+
satisfy(lhs, session)?
257+
.into_iter()
258+
.chain(satisfy(rhs, session)?),
259+
));
260+
}
261+
Operator::Eq
262+
| Operator::NotEq
263+
| Operator::Add
264+
| Operator::Sub
265+
| Operator::Mul
266+
| Operator::Div => None,
267+
};
268+
let Some(value_predicate) = value_predicate else {
269+
return Ok(None);
270+
};
271+
let Some(null_checks) = [lhs, rhs]
272+
.into_iter()
273+
.map(|operand| null_count(operand).map(|count| eq(count, lit(0u64))))
274+
.collect::<Option<Vec<_>>>()
275+
else {
276+
return Ok(None);
277+
};
278+
let guarded = and_collect(null_checks.into_iter().chain([value_predicate]))
279+
.vortex_expect("at least one predicate");
280+
with_non_nan_guards::<NanCountProof>([lhs, rhs], guarded)
281+
}
282+
224283
#[derive(Debug)]
225284
struct BetweenStatsRewrite;
226285

@@ -243,6 +302,21 @@ impl StatsRewriteRule for BetweenStatsRewrite {
243302
let rhs = binary(options.upper_strict.to_operator(), arr, upper);
244303
falsify(&and(lhs, rhs), session)
245304
}
305+
306+
fn satisfy(
307+
&self,
308+
expr: &BoundExpression,
309+
session: &VortexSession,
310+
) -> VortexResult<Option<BoundExpression>> {
311+
let options = expr.as_::<Between>();
312+
let arr = expr.child(0).clone();
313+
let lower = expr.child(1).clone();
314+
let upper = expr.child(2).clone();
315+
316+
let lhs = binary(options.lower_strict.to_operator(), lower, arr.clone());
317+
let rhs = binary(options.upper_strict.to_operator(), arr, upper);
318+
satisfy(&and(lhs, rhs), session)
319+
}
246320
}
247321

248322
#[derive(Debug)]

‎vortex-file/src/file.rs‎

Lines changed: 32 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -32,6 +32,8 @@ use vortex_utils::aliases::hash_map::HashMap;
3232
use crate::FileStatistics;
3333
use crate::footer::Footer;
3434
use crate::pruning::can_prune_file_stats;
35+
use crate::pruning::is_satisfied_by_file_stats;
36+
use crate::pruning::is_satisfied_by_non_null_file_stats;
3537
use crate::v2::FileStatsLayoutReader;
3638

3739
/// Represents a Vortex file, providing access to its metadata and content.
@@ -292,6 +294,36 @@ impl VortexFile {
292294
)
293295
}
294296

297+
/// Returns `true` if file-level statistics prove the expression is true for every row in
298+
/// this file, so that a filter on it would keep every row.
299+
pub fn is_satisfied(&self, filter: &Expression) -> VortexResult<bool> {
300+
let Some(stats) = self.footer.statistics() else {
301+
return Ok(false);
302+
};
303+
304+
is_satisfied_by_file_stats(
305+
&filter.bind(self.footer.dtype())?,
306+
self.footer.row_count(),
307+
stats,
308+
&self.session,
309+
)
310+
}
311+
312+
/// Returns `true` if file-level statistics prove the expression is true for every row of this
313+
/// file in which no column is null, so that a filter on it would only remove rows with nulls.
314+
pub fn is_satisfied_by_non_null_rows(&self, filter: &Expression) -> VortexResult<bool> {
315+
let Some(stats) = self.footer.statistics() else {
316+
return Ok(false);
317+
};
318+
319+
is_satisfied_by_non_null_file_stats(
320+
&filter.bind(self.footer.dtype())?,
321+
self.footer.row_count(),
322+
stats,
323+
&self.session,
324+
)
325+
}
326+
295327
/// Return the file's natural row splits as root-coordinate ranges.
296328
///
297329
/// These are the ranges that the default [`SplitBy`] would use for an all-fields scan.

‎vortex-file/src/pruning.rs‎

Lines changed: 52 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -11,6 +11,8 @@ use vortex_array::dtype::DType;
1111
use vortex_array::dtype::FieldPath;
1212
use vortex_array::expr::BoundExpression;
1313
use vortex_array::expr::bound::lit;
14+
use vortex_array::expr::stats::Stat;
15+
use vortex_array::scalar::Scalar;
1416
use vortex_array::scalar_fn::fns::cast::Cast;
1517
use vortex_array::scalar_fn::fns::get_item::GetItem;
1618
use vortex_array::scalar_fn::fns::literal::Literal;
@@ -32,8 +34,51 @@ pub(crate) fn can_prune_file_stats(
3234
let Some(pruning_expr) = expr.falsify(session)? else {
3335
return Ok(false);
3436
};
37+
evaluate_file_stats_proof(pruning_expr, row_count, file_stats, false, session)
38+
}
3539

36-
let binder = FileStatsBinder { file_stats };
40+
/// Returns `true` if file-level statistics prove `expr` is true for every row of the file.
41+
pub(crate) fn is_satisfied_by_file_stats(
42+
expr: &BoundExpression,
43+
row_count: u64,
44+
file_stats: &FileStatistics,
45+
session: &VortexSession,
46+
) -> VortexResult<bool> {
47+
let Some(proof) = expr.satisfy(session)? else {
48+
return Ok(false);
49+
};
50+
evaluate_file_stats_proof(proof, row_count, file_stats, false, session)
51+
}
52+
53+
/// Returns `true` if file-level statistics prove `expr` is true for every row of the file in which
54+
/// no column is null.
55+
///
56+
/// The proof binds every null count to zero. The min and max statistics ignore nulls, so a proof
57+
/// over them holds for the rows without nulls.
58+
pub(crate) fn is_satisfied_by_non_null_file_stats(
59+
expr: &BoundExpression,
60+
row_count: u64,
61+
file_stats: &FileStatistics,
62+
session: &VortexSession,
63+
) -> VortexResult<bool> {
64+
let Some(proof) = expr.satisfy(session)? else {
65+
return Ok(false);
66+
};
67+
evaluate_file_stats_proof(proof, row_count, file_stats, true, session)
68+
}
69+
70+
/// Evaluates a stats proof against the file statistics; only a definite `true` proves it.
71+
fn evaluate_file_stats_proof(
72+
pruning_expr: BoundExpression,
73+
row_count: u64,
74+
file_stats: &FileStatistics,
75+
no_nulls: bool,
76+
session: &VortexSession,
77+
) -> VortexResult<bool> {
78+
let binder = FileStatsBinder {
79+
file_stats,
80+
no_nulls,
81+
};
3782
let pruning_expr = bind_stats(pruning_expr, &binder)?;
3883

3984
if let Some(result) = pruning_expr.as_opt::<Literal>() {
@@ -56,6 +101,8 @@ pub(crate) fn can_prune_file_stats(
56101

57102
struct FileStatsBinder<'a> {
58103
file_stats: &'a FileStatistics,
104+
/// Whether to bind every null count to zero, restricting a proof to the rows without nulls.
105+
no_nulls: bool,
59106
}
60107

61108
impl StatBinder for FileStatsBinder<'_> {
@@ -81,6 +128,10 @@ impl FileStatsBinder<'_> {
81128
aggregate_fn: &AggregateFnRef,
82129
stat_dtype: &DType,
83130
) -> Option<BoundExpression> {
131+
if self.no_nulls && Stat::from_aggregate_fn(aggregate_fn) == Some(Stat::NullCount) {
132+
return Some(lit(Scalar::try_new(stat_dtype.clone(), Some(0u64.into())).ok()?));
133+
}
134+
84135
let (aggregates, _) = self.file_stats.get_by_path(field_path)?;
85136
let value = aggregates.get(aggregate_fn).into_inner()?;
86137
let value = if value.dtype() == stat_dtype {

‎vortex-file/src/tests.rs‎

Lines changed: 46 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -3141,6 +3141,52 @@ async fn test_can_prune_composite_predicates() -> VortexResult<()> {
31413141
Ok(())
31423142
}
31433143

3144+
#[tokio::test]
3145+
#[cfg_attr(miri, ignore)]
3146+
async fn test_is_satisfied_by_file_stats() -> VortexResult<()> {
3147+
let st = StructArray::from_fields(&[
3148+
("age", buffer![15i32, 18, 22, 25].into_array()),
3149+
("price", buffer![120i32, 130, 140, 150].into_array()),
3150+
])?;
3151+
let mut buf = ByteBufferMut::empty();
3152+
SESSION
3153+
.write_options()
3154+
.write(&mut buf, st.into_array().to_array_stream())
3155+
.await?;
3156+
let file = SESSION.open_options().open_buffer(buf)?;
3157+
3158+
assert!(file.is_satisfied(&gt(col("age"), lit(10)))?);
3159+
assert!(file.is_satisfied(&and(gt(col("age"), lit(10)), lt(col("price"), lit(200))))?);
3160+
3161+
// Some rows fail these, so they must not be proven.
3162+
assert!(!file.is_satisfied(&gt(col("age"), lit(20)))?);
3163+
assert!(!file.is_satisfied(&lt(col("price"), lit(140)))?);
3164+
3165+
Ok(())
3166+
}
3167+
3168+
#[tokio::test]
3169+
#[cfg_attr(miri, ignore)]
3170+
async fn test_is_satisfied_by_non_null_rows() -> VortexResult<()> {
3171+
let st = StructArray::from_fields(&[(
3172+
"age",
3173+
PrimitiveArray::from_option_iter([Some(15i32), None, Some(22), Some(25)]).into_array(),
3174+
)])?;
3175+
let mut buf = ByteBufferMut::empty();
3176+
SESSION
3177+
.write_options()
3178+
.write(&mut buf, st.into_array().to_array_stream())
3179+
.await?;
3180+
let file = SESSION.open_options().open_buffer(buf)?;
3181+
3182+
// The null row fails the comparison, so it only holds for the rows without nulls.
3183+
let bound = and(gt_eq(col("age"), lit(10)), lt_eq(col("age"), lit(30)));
3184+
assert!(!file.is_satisfied(&bound)?);
3185+
assert!(file.is_satisfied_by_non_null_rows(&bound)?);
3186+
assert!(!file.is_satisfied_by_non_null_rows(&gt(col("age"), lit(20)))?);
3187+
Ok(())
3188+
}
3189+
31443190
#[tokio::test]
31453191
#[cfg_attr(miri, ignore)]
31463192
async fn test_can_prune_nested_struct_field() -> VortexResult<()> {

0 commit comments

Comments
 (0)