dshogan-amzn opened a new pull request, #19015:
URL: https://github.com/apache/iceberg/pull/19015

   Closes #19014
   
   `InclusiveMetricsEvaluator`, `InclusiveStatsEvaluator`, `ManifestEvaluator` 
and `ParquetMetricsRowGroupFilter` compare an `IN` predicate's literals against 
lower and upper bounds with a linear scan, and skip the check entirely above 
200 literals (#1588). Above the limit, every file, manifest or row group is 
kept, even when none of its bounds contain a literal.
   
   ## Change
   
   - New `SortedInLiterals` in `org.apache.iceberg.expressions`. Each evaluator 
creates one instance, which sorts each `IN` literal set once by the term's 
comparator (the same comparator the bounds checks already use) and caches it by 
the identity of the bound predicate's literal set. `anyInRange(sorted, 
comparator, lower, upper)` finds the first literal not below `lower` with 
`Collections.binarySearch` and checks it against `upper`.
   - `InclusiveEvalVisitor.in()`, `ManifestEvaluator.in()` and 
`ParquetMetricsRowGroupFilter.in()` use it and no longer have a literal limit. 
Every other check in those methods (nulls, NaN, unreliable bounds, nested and 
variant columns) is unchanged and still runs before the range check.
   - Sorting happens on first use, at the point where the comparator was 
already requested, so types without a comparator behave exactly as before.
   - The cache is a synchronized identity map, so an evaluator stays safe to 
share across threads.
   
   `SortedInLiterals` is public only so `ParquetMetricsRowGroupFilter` can use 
it from another package. I'm happy to move it, mark it internal, or duplicate 
the few lines in Parquet if reviewers prefer.
   
   Results are unchanged: a file, manifest or row group is pruned only when no 
literal is within its bounds, which is the same test as before. The only 
behavioral change is that lists over 200 values are now evaluated.
   
   ## Validation
   
   - `./gradlew --no-daemon :iceberg-api:test --tests 
org.apache.iceberg.expressions.TestInclusiveMetricsEvaluator --tests 
org.apache.iceberg.expressions.TestInclusiveManifestEvaluator`
   - `./gradlew --no-daemon :iceberg-core:test --tests 
'org.apache.iceberg.expressions.TestInclusiveMetricsEvaluator*' --tests 
'org.apache.iceberg.TestInclusiveStatsEvaluator*'`
   - `./gradlew --no-daemon :iceberg-parquet:test --tests 
org.apache.iceberg.parquet.TestParquetMetricsRowGroupFilter :iceberg-data:test 
--tests 'org.apache.iceberg.data.TestMetricsRowGroupFilter*'`
   - `./gradlew --no-daemon :iceberg-api:revapi :iceberg-parquet:revapi 
:iceberg-api:javadoc` plus checkstyle and Spotless for `api`, `core`, `parquet` 
and `data`
   
   Three existing assertions expected a 400-literal `IN` below the file's lower 
bound to be read because of the limit; they now expect the file to be skipped. 
New cases cover large lists that contain the lower bound, contain the upper 
bound, or fall on both sides of the bounds, for the metrics, stats, manifest 
and Parquet row-group evaluators.
   
   With the 200-literal limit restored inside `anyInRange`, every new and 
updated large-list assertion fails.
   
   ## Planning cost
   
   A local JMH benchmark, not included in this PR: one manifest of 10,000 files 
in an unpartitioned table, each file covering a disjoint range of 10 keys, with 
`IN` values spread across the whole key range. JDK 17, one fork, 3 warmup and 5 
measurement iterations. Baseline is `main` at 2517ec2; both were run back to 
back on the same host.
   
   | Keys | Baseline files | Patched files | Baseline ms/op | Patched ms/op | 
Baseline MB/op | Patched MB/op |
   |---:|---:|---:|---:|---:|---:|---:|
   | 50 | 50 | 50 | 21.58 ± 3.91 | 14.82 ± 6.82 | 11.53 | 11.37 |
   | 200 | 200 | 200 | 33.90 ± 1.87 | 15.42 ± 7.03 | 11.70 | 11.54 |
   | 201 | 10,000 | 201 | 16.91 ± 6.60 | 15.18 ± 6.75 | 19.43 | 11.53 |
   | 1,000 | 10,000 | 1,000 | 16.88 ± 7.80 | 16.17 ± 8.87 | 19.59 | 12.41 |
   | 5,000 | 10,000 | 5,000 | 17.43 ± 7.20 | 18.47 ± 10.29 | 20.32 | 16.74 |
   
   At or below 200 values, the binary search replaces the linear scan; at 200 
values manifest filtering takes less than half the time. Above 200 values, the 
baseline skips the check and keeps all 10,000 files, while this change keeps 
only the files that can match, in about the same time.
   
   ## Related
   
   #18933 narrows `IN` literals to a file's bucket before the bounds check. The 
two changes are independent, but both edit `InclusiveEvalVisitor.in()`, so 
whichever merges second needs a small rebase. Combined, each bucket's narrowed 
literals would be sorted once.
   
   ## AI use
   
   I used an AI coding assistant during investigation and implementation. I 
reviewed the code, tests, and benchmark results before submission.
   


-- 
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]


---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]

Reply via email to