Partition file filtering logic is incorrect for logical `not()` function

[Nathan-Fenner]

Apache Iceberg Rust version

0.4.0 (latest version)

Describe the bug

Consider the following example table partition file:

id	count
"a"	3
"b"	2
"c"	5
"d"	7
"e"	5

This partition file will have statistics:

statistic	column	value
lower_bound	count	2
upper_bound	count	7

If I perform a query with predicate count >= 5, this partition must be included.

If I perform a query with predicate not(count >= 5), this partition must still be included.

The logic in manifest_evaluator.rs is currently 2-values, with options ROWS_MIGHT_MATCH and ROWS_CANNOT_MATCH. But then the only correct behavior for not would be

    fn not(&mut self, inner: bool) -> crate::Result<bool> {
      ROWS_MIGHT_MATCH
    }

The tests need to be expanded in order to catch this logical error, and a 3-value logic with (MUST_MATCH, MIGHT_MATCH, CANNOT_MATCH) values probably needs to be adopted to correctly handle all of these cases.

To Reproduce

No response

Expected behavior

No response

Willingness to contribute

I cannot contribute a fix for this bug at this time

[ZENOTME]

Thanks @Nathan-Fenner!

The problem is that not(ROWS_MIGHT_MATCH) can be ROWS_MIGHT_MATCH or CANNOT_MATCH. E.g. following above:

• 2<= count <= 7 is ROWS_MIGHT_MATCH and not(2<= count <= 7) is CANNOT_MATCH
• 2<= count is ROWS_MIGHT_MATCH and not(2<= count) is ROWS_MIGHT_MATCH

We need to separate these two kind of case. But I think 2<= count <= 7 is also not means MUTS_MATCH🤔 It's more like "ROW_COVER". But I think the more easier way to solve this maybe use the rewrite_not to avoid not before evaluate. cc @liurenjie1024

[ZENOTME]

I find that we already have rewrite_not for partition filter:

iceberg-rust/crates/iceberg/src/scan/cache.rs

Line 85 in b84e0d2

.rewrite_not()

Maybe we can transfer this invariant to ManifestEvaluator::New to make it clearer.

One problem I find is that although we have rewrite_not logic, it can't process nested not like not(not(not(bar > 10))). And I fixed it in #1431.

[Nathan-Fenner]

I haven't verified, but it does sound plausible to me that rewrite_not is always called before running ManifestEvaluator::New.

If that were the case, I would be inclined to change the implementation for the manifest_evaluator.rs to return ROWS_MIGHT_MATCH with an explanatory comment that:

1. This is necessary for correctness, because of the not(x < 3) case for data x = [1, 2, 4, 5]
2. But it doesn't cause over-scanning because in practice the not() predicates are always removed by the rewrite_not transformation

This keeps the implementation of ManifestEvaluator::New independently correct in case it's ever (accidentally?) used with a predicate that has a not() in it, but also explains why it doesn't need to be made more complex to accommodate them.

[ZENOTME]

I haven't verified, but it does sound plausible to me that rewrite_not is always called before running ManifestEvaluator::New.

If that were the case, I would be inclined to change the implementation for the manifest_evaluator.rs to return ROWS_MIGHT_MATCH with an explanatory comment that:

1. This is necessary for correctness, because of the not(x < 3) case for data x = [1, 2, 4, 5]
2. But it doesn't cause over-scanning because in practice the not() predicates are always removed by the rewrite_not transformation

This keeps the implementation of ManifestEvaluator::New independently correct in case it's ever (accidentally?) used with a predicate that has a not() in it, but also explains why it doesn't need to be made more complex to accommodate them.

I think directly refuse to process the not may make the semantics clearer🤔

1. call rewrite_not in ManifestEvaluator::New to gurantee that there is not possible not in expression
2. return Error in not visitor

[liurenjie1024]

I agree with @ZENOTME that we should return Error in not visitor.

call rewrite_not in ManifestEvaluator::New to gurantee that there is not possible not in expression

I think we could make this an optional behavior.

ManifestEvaluator is typically not public api and not used by first time user.