[PR] perf(arrow-select): native filter kernel for FixedSizeList [arrow-rs]

["mzabaluev-flarion (via GitHub)" <gi...@apache.org>]

mzabaluev-flarion opened a new pull request, #11865:
URL: https://github.com/apache/arrow-rs/pull/11865

   # Which issue does this PR close?
   
   - Part of #11839
   
   **Stacked on #11844.** This branch contains that PR's commit, so only the last commit, "native filter kernel for FixedSizeList", is new here.
   
   # Rationale for this change
   
   `filter` on `FixedSizeList` arrays falls back to `MutableArrayData`, which calls `try_extend` once per selected row range and runs the boxed extend closure of every descendant array.
   
   # What changes are included in this PR?
   
   - **`filter_fixed_size_list`:** scales the selected row ranges by the list size into child slices, then filters the child with `filter_array`, the same way #11844 does for `List`. Validity goes through `FilterPredicate::filter_nulls`. A list size of 0 needs no special case, because empty child slices are skipped.
   - **Shared helpers:** `push_child_slice` (merges adjacent ranges and skips empty ones) and `child_slices_predicate` (builds the child mask and the `Slices` strategy) are moved out of `filter_offsets` from #11844, and the `List` kernel now uses them too.
   
   # Are these changes tested?
   
   New tests compare `filter`, with and without `optimize()`, against `take` and run `validate_full` on the result. They cover:
   - nulls and slicing
   - `List<FixedSizeList>` and `FixedSizeList<List>`
   - `FixedSizeList<Struct<Int32, Utf8>>`
   - `FixedSizeList<RunEndEncoded>`, which exercises the child mask
   - list size 0
   - a fuzz test with random list sizes, slicing and selectivity
   
   The existing `FixedSizeList` tests pass unchanged.
   
   Benchmarks from #11841, compared against `main` (Apple M4 Pro):
   
   | case | kept 1/2 | kept 1023/1024 | kept 1/1024 |
   |---|---|---|---|
   | fixed_size_list\<i32\> w NULLs | −47% | −14% | −2% |
   | context fixed_size_list\<i32\> w NULLs | −41% | −16% | −33% |
   | fixed_size_list\<struct\<i64, utf8\>\> | −25% | **+25%** | −31% |
   | context fixed_size_list\<struct\<i64, utf8\>\> | −28% | **+25%** | −43% |
   
   The 1023/1024 regression for the struct case comes from the `Utf8` child. `filter_bytes` rebuilds the offsets of each selected slice one element at a time, while `MutableArrayData` shifts the whole run of offsets. A follow-up change to `FilterBytes::extend_offsets_slices` fixes this. It makes this case 70% faster than `main` and plain string filtering at 1023/1024 32% faster.
   
   # 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: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org

Re: [PR] perf(arrow-select): native filter kernel for FixedSizeList [arrow-rs]

["mzabaluev-flarion (via GitHub)" <gi...@apache.org>]

mzabaluev-flarion closed pull request #11865: perf(arrow-select): native filter kernel for FixedSizeList
URL: https://github.com/apache/arrow-rs/pull/11865


-- 
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: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org