Skip to content

Commit 6e9d54e

Browse files
committed
[core] Push NOT down to the leaves before evaluating it
A leaf yields false for NULL, so negating a compound result turned NOT(NOT(v = 1) AND id >= 0) true for a NULL v.
1 parent 1d42473 commit 6e9d54e

4 files changed

Lines changed: 109 additions & 31 deletions

File tree

‎crates/paimon/src/arrow/residual.rs‎

Lines changed: 58 additions & 16 deletions
Original file line numberDiff line numberDiff line change
@@ -161,22 +161,7 @@ pub(crate) fn evaluate_predicate_mask(
161161
}
162162
Ok(Some(combined))
163163
}
164-
Predicate::Not(inner) => {
165-
let Some(mask) = evaluate_predicate_mask(batch, inner, file_fields, scan_fields)?
166-
else {
167-
return Ok(None);
168-
};
169-
let negated =
170-
boolean_mask_from_predicate(mask.len(), |row_index| !mask.value(row_index));
171-
if let Some(guard) = inner.not_null_guard() {
172-
let Some(guard) = evaluate_predicate_mask(batch, &guard, file_fields, scan_fields)?
173-
else {
174-
return Ok(None);
175-
};
176-
return Ok(Some(combine_filter_masks(&negated, &guard, false)));
177-
}
178-
Ok(Some(negated))
179-
}
164+
Predicate::Not(inner) => evaluate_negated_mask(batch, inner, file_fields, scan_fields),
180165
Predicate::Leaf {
181166
column,
182167
index,
@@ -265,6 +250,63 @@ pub(crate) fn evaluate_predicate_mask(
265250

266251
/// Two [`DataField`]s refer to the same logical column when their IDs match, or
267252
/// (for schemas without stable IDs) their names match.
253+
/// Evaluates `NOT predicate`. The `NOT` is pushed down to the leaves with
254+
/// De Morgan first: a leaf masks NULL as false, so negating a combined mask
255+
/// would turn UNKNOWN into true.
256+
fn evaluate_negated_mask(
257+
batch: &RecordBatch,
258+
predicate: &Predicate,
259+
file_fields: &[DataField],
260+
scan_fields: &[DataField],
261+
) -> crate::Result<Option<BooleanArray>> {
262+
match predicate {
263+
// NOT(a AND b) = NOT a OR NOT b, evaluated like the `Or` arm.
264+
Predicate::And(children) => {
265+
let mut combined = BooleanArray::from(vec![false; batch.num_rows()]);
266+
for child in children {
267+
let Some(mask) = evaluate_negated_mask(batch, child, file_fields, scan_fields)?
268+
else {
269+
return Ok(None);
270+
};
271+
combined = combine_filter_masks(&combined, &mask, true);
272+
}
273+
Ok(Some(combined))
274+
}
275+
// NOT(a OR b) = NOT a AND NOT b, evaluated like the `And` arm.
276+
Predicate::Or(children) => {
277+
let mut combined = None;
278+
for child in children {
279+
let Some(mask) = evaluate_negated_mask(batch, child, file_fields, scan_fields)?
280+
else {
281+
continue;
282+
};
283+
combined = Some(match combined {
284+
Some(existing) => combine_filter_masks(&existing, &mask, false),
285+
None => mask,
286+
});
287+
}
288+
Ok(combined)
289+
}
290+
Predicate::Not(inner) => evaluate_predicate_mask(batch, inner, file_fields, scan_fields),
291+
_ => {
292+
let Some(mask) = evaluate_predicate_mask(batch, predicate, file_fields, scan_fields)?
293+
else {
294+
return Ok(None);
295+
};
296+
let negated =
297+
boolean_mask_from_predicate(mask.len(), |row_index| !mask.value(row_index));
298+
if let Some(guard) = predicate.not_null_guard() {
299+
let Some(guard) = evaluate_predicate_mask(batch, &guard, file_fields, scan_fields)?
300+
else {
301+
return Ok(None);
302+
};
303+
return Ok(Some(combine_filter_masks(&negated, &guard, false)));
304+
}
305+
Ok(Some(negated))
306+
}
307+
}
308+
}
309+
268310
pub(crate) fn same_data_field(left: &DataField, right: &DataField) -> bool {
269311
left.id() == right.id() || left.name() == right.name()
270312
}

‎crates/paimon/src/spec/predicate.rs‎

Lines changed: 30 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -586,8 +586,6 @@ impl Predicate {
586586
/// [`negate`]: Predicate::negate
587587
pub(crate) fn not_null_guard(&self) -> Option<Predicate> {
588588
match self {
589-
// NOT(NOT(x)) is x, so it is unknown wherever x is.
590-
Predicate::Not(inner) => inner.not_null_guard(),
591589
Predicate::Leaf {
592590
column,
593591
index,
@@ -2550,10 +2548,7 @@ pub(crate) fn eval_row(predicate: &Predicate, row: &BinaryRow) -> Result<bool> {
25502548
}
25512549
Ok(false)
25522550
}
2553-
Predicate::Not(inner) => match inner.not_null_guard() {
2554-
Some(guard) => Ok(eval_row(&guard, row)? && !eval_row(inner, row)?),
2555-
None => Ok(!eval_row(inner, row)?),
2556-
},
2551+
Predicate::Not(inner) => eval_row_negated(inner, row),
25572552
Predicate::Leaf {
25582553
index,
25592554
data_type,
@@ -2567,6 +2562,35 @@ pub(crate) fn eval_row(predicate: &Predicate, row: &BinaryRow) -> Result<bool> {
25672562
}
25682563
}
25692564

2565+
/// Evaluates `NOT predicate`. The `NOT` is pushed down to the leaves with
2566+
/// De Morgan first: a leaf yields false for NULL, so negating a compound
2567+
/// result would turn UNKNOWN into true.
2568+
fn eval_row_negated(predicate: &Predicate, row: &BinaryRow) -> Result<bool> {
2569+
match predicate {
2570+
Predicate::And(children) => {
2571+
for child in children {
2572+
if eval_row_negated(child, row)? {
2573+
return Ok(true);
2574+
}
2575+
}
2576+
Ok(false)
2577+
}
2578+
Predicate::Or(children) => {
2579+
for child in children {
2580+
if !eval_row_negated(child, row)? {
2581+
return Ok(false);
2582+
}
2583+
}
2584+
Ok(true)
2585+
}
2586+
Predicate::Not(inner) => eval_row(inner, row),
2587+
_ => match predicate.not_null_guard() {
2588+
Some(guard) => Ok(eval_row(&guard, row)? && !eval_row(predicate, row)?),
2589+
None => Ok(!eval_row(predicate, row)?),
2590+
},
2591+
}
2592+
}
2593+
25702594
/// Evaluate a single leaf predicate.
25712595
///
25722596
/// This function is infallible: all type decoding happens in `extract_datum`

‎crates/paimon/src/table/de_vector_scan/tests.rs‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1015,7 +1015,7 @@ async fn top1_after_bitmap_then_btree(
10151015
first_f: Vec<Option<f64>>,
10161016
filter: fn(&crate::spec::PredicateBuilder) -> crate::spec::Predicate,
10171017
) -> Vec<i32> {
1018-
use crate::spec::{ArrayType, DataType, Datum, DoubleType, FloatType, IntType};
1018+
use crate::spec::{ArrayType, DataType, DoubleType, FloatType, IntType};
10191019
use arrow_array::types::Float32Type;
10201020
use arrow_array::{Float64Array, ListArray};
10211021

‎crates/paimon/tests/table_predicate_delete_test.rs‎

Lines changed: 20 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -716,9 +716,10 @@ async fn negated_data_predicate_keeps_null_rows() {
716716

717717
#[tokio::test]
718718
async fn raw_double_negation_keeps_null_rows_out() {
719-
// NOT(NOT(v = 10)) is v = 10, so the NULL row stays out. Widening `v`
720-
// makes the read go through the Arrow residual filter.
721-
for widened in [false, true] {
719+
// NOT(NOT(v = 10)) is v = 10, so the NULL row stays out, also when the
720+
// inner NOT sits under AND. Widening `v` makes the read go through the
721+
// Arrow residual filter.
722+
for (widened, nested) in [(false, false), (true, false), (false, true), (true, true)] {
722723
let table = table(&[]).await;
723724
write_batch(
724725
&table,
@@ -753,22 +754,33 @@ async fn raw_double_negation_keeps_null_rows_out() {
753754
} else {
754755
Datum::Int(10)
755756
};
756-
let predicate = Predicate::Not(Box::new(Predicate::Not(Box::new(
757-
pb.equal("v", value).unwrap(),
758-
))));
757+
let not_v = Predicate::Not(Box::new(pb.equal("v", value).unwrap()));
758+
let inner = if nested {
759+
Predicate::And(vec![
760+
not_v,
761+
pb.greater_or_equal("id", Datum::Int(0)).unwrap(),
762+
])
763+
} else {
764+
not_v
765+
};
766+
let predicate = Predicate::Not(Box::new(inner));
759767

760768
assert_eq!(
761769
read_ids(&table, predicate.clone()).await,
762770
vec![1],
763-
"widened={widened}"
771+
"widened={widened} nested={nested}"
764772
);
765773
let update = table.new_write_builder().new_update().unwrap();
766774
commit(
767775
&table,
768776
update.delete_by_predicate(Some(predicate)).await.unwrap(),
769777
)
770778
.await;
771-
assert_eq!(ids(&table).await, vec![0, 2], "widened={widened}");
779+
assert_eq!(
780+
ids(&table).await,
781+
vec![0, 2],
782+
"widened={widened} nested={nested}"
783+
);
772784
}
773785
}
774786

0 commit comments

Comments
 (0)