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]
