mzabaluev opened a new pull request, #11872: URL: https://github.com/apache/arrow-rs/pull/11872
# Which issue does this PR close? - Part of #11839 # Rationale for this change `filter` on `List` and `LargeList` arrays falls back to `MutableArrayData`, which calls `try_extend` once per selected row range. Each call goes through the validity `set_bits` and the boxed extend closure of every descendant array. This is the arrow-rs half of the problem in apache/datafusion#26581, where filtering a struct with a list-of-structs field dominates the cost of `CASE` evaluation. # What changes are included in this PR? - **New `filter_list` kernel for `List` / `LargeList`.** In one pass over the selected rows, it builds the new offsets and a child `FilterPredicate` that selects the value ranges of those rows, then recurses through `filter_array`. Nested structs, strings, primitives and inner lists use their native kernels. The child predicate uses materialized `Slices`, merged across adjacent rows, because child selections are runs of values. A child mask is also built, starting from a zeroed allocation with only the selected ranges set, because `filter_run_end_array` reads the mask bits. - **`filter_bits` heuristic.** It now also uses the strategy path for a materialized `Slices` predicate with fewer slices than mask words, the same way it already handles sparse `Indices`. Without this, filtering the validity of child columns compressed the whole child mask even when only a few ranges were selected. Top-level predicates only take this path when their slices are this few, and the `filter_bits` benchmarks show no change. # Are these changes tested? New tests compare `filter`, with and without `optimize()`, against `take` and run `validate_full` on the result. They cover: - `List` and `LargeList`, with null slots, empty lists, and a null slot with a non-empty range - sliced arrays and `List<List<_>>` - `List<RunEndEncoded>`, which exercises the child mask - predicates that hit every iteration strategy, including all-true, all-false and shorter-than-array ones - a fuzz test over `Struct<Int32, List<Struct<Int32, Utf8>>>` with random slicing and selectivity Benchmarks from #11841, compared against `main` (Apple M4 Pro): | case | kept 1/2 | kept 1023/1024 | kept 1/1024 | |---|---|---|---| | list\<i32\> w NULLs | −35% | −24% | +2% (noise, 3.0 µs) | | context list\<i32\> w NULLs | −31% | −17% | −37% | | list\<struct\<i64, utf8\>\> w NULLs | −44% | −58% | −33% | | context list\<struct\<i64, utf8\>\> w NULLs | −43% | −54% | −51% | | struct\<8 x i64, list\<struct\<i64, utf8\>\>\> w NULLs | −37% | −60% | −38% | | context struct\<8 x i64, list\<struct\<i64, utf8\>\>\> w NULLs | −37% | −60% | −41% | # Are there any significant user-facing changes? No. The public API and the output of `filter` are unchanged. 🤖 Generated with [Claude Code](https://claude.com/claude-code) -- 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]
