JingsongLi commented on code in PR #1145:
URL: https://github.com/apache/paimon-rust/pull/1145#discussion_r4479058520


##########
crates/paimon/src/table/global_index_scanner/evaluator.rs:
##########
@@ -349,7 +394,14 @@ impl GlobalIndexScanner {
                         match result {
                             Some(child_result) => {
                                 fully_evaluated &= 
child_result.fully_evaluated;
+                                if child_result.fully_evaluated {
+                                    exact_ranges.extend(exclude_row_ranges(

Review Comment:
   [P1] Keep OR range subtraction linear for fragmented bitmap hits
   
   For a nullable floating Bitmap index, `f < 0` returns every non-null row as 
a candidate. With alternating `1.0` and NULL, both range lists passed here 
consist of the same K disjoint singleton intervals. `exclude_row_ranges` 
restarts its scan of the cuts for each base interval, so this one OR arm 
performs K(K+1)/2 comparisons. The final subtraction can repeat the cost. A 
million-row input with this distribution reaches about 125 billion comparisons 
for one subtraction.
   
   I reproduced the scaling through public write, Bitmap index build and scan 
planning with `f < 0 OR f = 1`. On my macOS debug build, planning took 
approximately 16 ms, 187 ms and 791 ms for 2,048, 8,192 and 16,384 disjoint 
intervals respectively. The exact-only control planned the same ranges in 2 to 
4 ms. This is on the normal scalar index path and is also shared by vector and 
full-text search.
   
   Please use a two-pointer difference over sorted, merged ranges. Empty or 
identical inputs can also avoid the subtraction.
   



##########
crates/paimon/src/arrow/residual.rs:
##########
@@ -258,6 +250,63 @@ pub(crate) fn evaluate_predicate_mask(
 
 /// Two [`DataField`]s refer to the same logical column when their IDs match, 
or
 /// (for schemas without stable IDs) their names match.
+/// Evaluates `NOT predicate`. The `NOT` is pushed down to the leaves with
+/// De Morgan first: a leaf masks NULL as false, so negating a combined mask
+/// would turn UNKNOWN into true.
+fn evaluate_negated_mask(
+    batch: &RecordBatch,
+    predicate: &Predicate,
+    file_fields: &[DataField],
+    scan_fields: &[DataField],
+) -> crate::Result<Option<BooleanArray>> {
+    match predicate {
+        // NOT(a AND b) = NOT a OR NOT b, evaluated like the `Or` arm.
+        Predicate::And(children) => {
+            let mut combined = BooleanArray::from(vec![false; 
batch.num_rows()]);
+            for child in children {
+                let Some(mask) = evaluate_negated_mask(batch, child, 
file_fields, scan_fields)?
+                else {
+                    return Ok(None);
+                };
+                combined = combine_filter_masks(&combined, &mask, true);
+            }
+            Ok(Some(combined))
+        }
+        // NOT(a OR b) = NOT a AND NOT b, evaluated like the `And` arm.
+        Predicate::Or(children) => {
+            let mut combined = None;
+            for child in children {
+                let Some(mask) = evaluate_negated_mask(batch, child, 
file_fields, scan_fields)?
+                else {
+                    continue;
+                };
+                combined = Some(match combined {
+                    Some(existing) => combine_filter_masks(&existing, &mask, 
false),
+                    None => mask,
+                });
+            }
+            Ok(combined)
+        }
+        Predicate::Not(inner) => evaluate_predicate_mask(batch, inner, 
file_fields, scan_fields),
+        _ => {
+            let Some(mask) = evaluate_predicate_mask(batch, predicate, 
file_fields, scan_fields)?
+            else {
+                return Ok(None);
+            };
+            let negated =
+                boolean_mask_from_predicate(mask.len(), |row_index| 
!mask.value(row_index));
+            if let Some(guard) = predicate.not_null_guard() {

Review Comment:
   [P2] Preserve NULL semantics when a Mosaic file physically omits the field
   
   The new guard excludes a stored NULL for `NOT starts_with(name, 'a')`. A 
same-schema Mosaic file may omit that logical field physically. Mosaic remaps 
against the columns actually stored, and `remap_predicate` in 
`arrow/filtering.rs` folds the missing positive leaf to `AlwaysFalse` and then 
flips the retained `Not` to `AlwaysTrue`. The guard never sees it.
   
   I reproduced this with the existing sparse Mosaic fixture, a nullable 
logical `new_name` column absent from the file, and 
`Predicate::negate(starts_with("new_name", "a"))`. The reader returned all six 
fixture IDs `[1, 2, 10, 11, 20, 21]`. Since the omitted field is NULL for all 
rows, the expected result is empty.
   
   Please apply the NULL-aware negation rule before missing fields are folded 
into constants, and add a sparse-file regression for a leaf retained under 
`Not`.
   



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: [email protected]

For queries about this service, please contact Infrastructure at:
[email protected]

Reply via email to