rok opened a new issue, #55292:
URL: https://github.com/apache/arrow/issues/55292
### Describe the enhancement requested
Since #46859 (the fix for #46777) `SimplifyWithGuarantee` skips `is_in`
calls whose value set has more than 50 elements. The old approach filtered the
value set and rebound the call for every row group guarantee, which was far too
slow for large sets. The side effect is that a filter like
`pc.field("id").isin(ids)` with a few hundred ids or more now reads every row
group of a Parquet file, even when the ids only touch a handful of them. This
came up again in G-Research/gr-oss#1440, and Polars recently fixed the same
problem on their side (pola-rs/polars#29923).
We can do better without going back to the slow path. Keep a sorted copy of
the value set in the `is_in` kernel state and binary search it for the range
admitted by a row group's min/max. That is O(log N) per row group, exact for
any number of values (it also prunes row groups that lie inside the hull of the
value set but contain none of its values, which a min/max check of the set
alone can't do), and it never rebinds the call. The sorted copy only has to be
computed once per bound expression, and only when it is actually used for
simplification, so plain `is_in` kernel calls don't pay for it.
#43256 tried something similar a while ago and stalled. The review there
asked not to add a sortedness flag to `SetLookupOptions` and to keep any
memoized data in the kernel state. This proposal follows that.
### Component(s)
C++
--
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]
