Problem
evaluate_set_membership_predicate in arrow/residual.rs (shared by the parquet row filter and the exact residual backstop) evaluates an In/NotIn literal set by running one whole-column comparison kernel per literal and OR-combining the masks. Cost is O(rows × literals).
This is fine for hand-written filters with a few literals, but an engine that pushes a batch of point-lookup keys down as an In predicate (hundreds of literals against a table read) makes every probe quadratic — e.g. 500 keys × 500K rows = 250M comparisons per pushed batch.
Proposal
Build a hash set of the literal values once and answer membership with a single pass over the column, for the common column shapes (Binary/LargeBinary/BinaryView, Utf8/LargeUtf8/Utf8View, Int8–Int64). Everything else keeps the per-literal loop, preserving its exact semantics including its error behavior for unconvertible literals.
Measured in StreamFusion (github.com/datafusion-contrib/StreamFusion), which pushes each streaming batch's state keys down as In: without the fix, per-batch probes were quadratic; with it, the probe is one hash-set pass at parquet decode.
Problem
evaluate_set_membership_predicateinarrow/residual.rs(shared by the parquet row filter and the exact residual backstop) evaluates anIn/NotInliteral set by running one whole-column comparison kernel per literal and OR-combining the masks. Cost is O(rows × literals).This is fine for hand-written filters with a few literals, but an engine that pushes a batch of point-lookup keys down as an
Inpredicate (hundreds of literals against a table read) makes every probe quadratic — e.g. 500 keys × 500K rows = 250M comparisons per pushed batch.Proposal
Build a hash set of the literal values once and answer membership with a single pass over the column, for the common column shapes (Binary/LargeBinary/BinaryView, Utf8/LargeUtf8/Utf8View, Int8–Int64). Everything else keeps the per-literal loop, preserving its exact semantics including its error behavior for unconvertible literals.
Measured in StreamFusion (github.com/datafusion-contrib/StreamFusion), which pushes each streaming batch's state keys down as
In: without the fix, per-batch probes were quadratic; with it, the probe is one hash-set pass at parquet decode.