mzabaluev opened a new issue, #11839:
URL: https://github.com/apache/arrow-rs/issues/11839
### Is your feature request related to a problem or challenge?
`filter` (and so `filter_record_batch` and `FilterPredicate::filter`) has
native kernels for many data types, but `List`, `LargeList`, `FixedSizeList`
and `Map` don't currently have one. They fall back to `MutableArrayData`, which
calls `try_extend` once per selected row range. Each `try_extend` call updates
the validity bitmap with `set_bits` and runs the boxed `extend` closure of
every descendant array. With a fragmented selection, the cost depends on the
number of ranges times the depth and width of the nested type, not on the
number of bytes copied. The native `Struct` kernel doesn't help here: as soon
as a struct contains a list, everything below the list goes through
`MutableArrayData` again.
This shows up in DataFusion in apache/datafusion#26581. `CASE WHEN` filters
its input once per branch, and a column of type `Struct<a..h: Int64, items:
List<Struct<x: Int64, y: Utf8>>>` makes the query 46× slower at 128 items per
row than the same query over extracted scalar fields (1.07 s vs 0.024 s on 4M
rows).
### Describe the solution you'd like
Native filter kernels for these types, following the existing
`filter_list_view` and `filter_struct` kernels:
- **`List` / `LargeList` / `Map`:** in one pass over the selection, rebuild
the offsets and build a `BooleanBuffer` mask over the child values that covers
the value range of each selected row. Then filter the child recursively with
`filter_array`, using a predicate whose count is already known
(`FilterBuilder::with_count`). Nested structs and leaf arrays then go through
the existing bulk kernels. Validity goes through
`FilterPredicate::filter_nulls`.
- **`FixedSizeList`:** the child mask is the row selection scaled by the
list size. No offsets are needed.
None of this changes the public API or the output of `filter`.
I plan to do this in small, separate PRs:
- [ ] Benchmarks for filtering nested list types
(`arrow/benches/filter_kernels.rs`)
- [ ] `List` / `LargeList`
- [ ] `FixedSizeList`
- [ ] `Map` (reuses the offsets/mask helper from the `List` PR)
### Describe alternatives you've considered
- **Make `MutableArrayData::extend` cheaper.** That helps every caller, but
the
per-range dynamic dispatch through the closures of every descendant is
built
into its design. It also wouldn't let the child struct use the filter
strategy
and selectivity heuristics in `filter.rs`.
- **Fix it only in DataFusion**, by projecting field accesses before `CASE`
filtering (proposed in apache/datafusion#26581). That's worth doing too,
but
every other user that filters nested data, like `filter_record_batch` on
scans and joins, would still be affected by this issue.
--
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]
