neilconway opened a new pull request, #25754:
URL: https://github.com/apache/datafusion/pull/25754
## Which issue does this PR close?
- N/A
## Rationale for this change
After applying the predicate to the input list, `array_filter` has to
compute two things: the row offsets for the result list, and the "keep" bitmap
to pass to Arrow's `filter` kernel to copy the result values.
When the predicate returned one or more NULLs, the previous implementation
computed row offsets with a bit-by-bit loop over the result of applying the
predicate, which is relatively slow. We can do better by first converting the
predicate result bitmap into the "keep" bitmap (normalizing NULLs to cleared
bits), and then using the keep bitmap to compute row offsets. This last step
can be done with Arrow's `count_set_bits_offset`, which uses popcount to do
outperform a simple bit-by-bit loop.
Along the way, avoid creating two transient copies of the input row offset
buffer. The previous code built a vector of adjusted row offsets to account for
slicing of the input list; we can instead account for slicing without an
additional data structure but instead by subtracting the first offset value
from each row offset. This matches how sliced inputs are typically handled
elsewhere.
Benchmarks: (M4 Max)
- int32/keep10/no_nulls, 3.383 → 2.505 µs, −26.0%
- int32/keep50/no_nulls, 4.236 → 3.393 µs, −19.9%
- int32/keep90/no_nulls, 4.669 → 3.830 µs, −18.0%
- int32/keep50/null_elements25, 8.406 → 4.430 µs, −47.3%
- int32/keep_null_elements, 4.104 → 3.263 µs, −20.5%
- int32/keep50/null_rows50, 5.427 → 3.458 µs, −36.3%
- int32/keep50/null_rows99, 1.140 → 1.132 µs, −0.7%
- utf8/keep10/no_nulls, 11.246 → 10.390 µs, −7.6%
- utf8/keep50/no_nulls, 19.738 → 18.736 µs, −5.1%
- utf8/keep90/no_nulls, 14.289 → 13.456 µs, −5.8%
- utf8/keep50/null_elements25, 24.502 → 20.354 µs, −16.9%
- utf8/keep_null_elements, 6.838 → 6.032 µs, −11.8%
- utf8/keep50/null_rows50, 13.233 → 11.068 µs, −16.4%
- utf8/keep50/null_rows99, 1.252 → 1.237 µs, −1.2%
- utf8_view/keep10/no_nulls, 6.323 → 6.063 µs, −4.1%
- utf8_view/keep50/no_nulls, 7.173 → 6.990 µs, −2.5%
- utf8_view/keep90/no_nulls, 7.843 → 7.522 µs, −4.1%
- utf8_view/keep50/null_elements25, 11.256 → 7.872 µs, −30.1%
- utf8_view/keep_null_elements, 4.083 → 3.339 µs, −18.2%
- utf8_view/keep50/null_rows50, 6.865 → 5.169 µs, −24.7%
- utf8_view/keep50/null_rows99, 1.239 → 1.224 µs, −1.2%
- utf8/wide_128, 18.384 → 18.013 µs, −2.0%
- utf8/variable_0_to_32, 19.724 → 18.733 µs, −5.0%
- int32/large_1m/null_elements25, 3474.170 → 1067.504 µs, −69.3%
- scalar/true, 0.562 → 0.474 µs, −15.7%*
- scalar/false, 0.704 → 0.630 µs, −10.6%
- scalar/null, 0.727 → 0.653 µs, −10.2%
- int32/keep_all, 4.370 → 2.473 µs, −43.4%
- int32/keep_none, 3.416 → 2.588 µs, −24.2%
- int32/captured_column, 5.917 → 5.229 µs, −11.6%
- int32/keep50/null_rows50/hidden_storage, 6.760 → 4.735 µs, −30.0%
- utf8/sliced, 24.296 → 20.197 µs, −16.9%
- utf8/large_list, 24.351 → 20.462 µs, −16.0%
## What changes are included in this PR?
* Optimize computing row offsets for result, when predicate returns NULLs
* Avoid needless copy/allocation for adjusted input row offsets
* Add fast-paths for when the predicate selects all elements or no elements
* Refactor `List` and `LargeList` into a single implementation,
parameterized on offset type
* Add benchmark for `array_filter`
## What is the testing strategy for this PR?
Existing tests pass, test coverage expanded.
## Are there any user-facing changes?
No.
--
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]
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
