[C++][Dataset] Prune Parquet row groups for is_in predicates with large value sets #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. 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++