rok opened a new pull request, #55293: URL: https://github.com/apache/arrow/pull/55293
### Rationale for this change Since #46859, `is_in` predicates with more than 50 values are not simplified against Parquet row group statistics at all, so such filters read every row group. See #55292 for the background. The same problem was reported in G-Research/gr-oss#1440 and fixed in Polars in pola-rs/polars#29923. ### What changes are included in this PR? - The `is_in` kernel state keeps a sorted, null-free copy of the value set when it has more than 50 values. An already sorted set is reused as is after a single O(N) check; otherwise it is sorted lazily on first use, so plain kernel calls don't pay for it. Primitive sets are sorted with `std::sort` on a copy, which is about 13x faster than `sort_indices` + `take` for 10M shuffled values. - `SimplifyWithGuarantee` applies all inequality guarantees on a field to a large `is_in` call at once by binary searching the sorted set. If no value can match, the call becomes `false`, otherwise it is left alone (no rebinding). Using both row group bounds together is what lets us skip row groups that lie inside the hull of the value set but hold none of its values. - Bounds are brought into the field type exactly and then put through the same casts as the argument. Strict bounds through non-injective (floating point) casts are weakened to inclusive ones. - `Comparison::StripOrderPreservingCasts` no longer strips unsigned to signed casts that may wrap. This also fixes the existing comparison simplifier. - Sets of up to 50 values keep using the existing filter and rebind path. ### Are these changes tested? New `Expression.SimplifyIsInLargeValueSet` and `Expression.SimplifyLargeIsInThenExecute` tests, plus a Parquet dataset test that prunes row groups inside the hull of the value set. Scan timings on a 49M row file with 47 row groups (release build, file in page cache): filters with 100 to 100K ids go from ~100 ms (the whole file) to 4 to 8 ms, 1M ids from ~300 ms to 26 to 42 ms, 10M ids from ~450 ms to ~260 ms. A value set that touches every row group costs the same as before. ### Are there any user-facing changes? No API changes. `is_in` filters with more than 50 values prune Parquet row groups again. ### Was AI used for this PR? **PR code and description written by:** - [ ] Human - [x] AI **Reviewed before submission by:** - [x] Human - [ ] AI - [ ] Not reviewed The code was drafted with an AI assistant; I reviewed, tested and benchmarked it and iterated on the design. * GitHub Issue: #55292 -- 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]
