neilconway opened a new pull request, #25607:
URL: https://github.com/apache/datafusion/pull/25607
## Which issue does this PR close?
- N/A
## Rationale for this change
`array_compact` did the following for every non-null row:
1. Count the # of logical nulls to determine the new (post-compact) row
offset
2. Walk the row's elements to identify spans of valid (non-null) elements to
copy
3. Copying those elements with `MutableArrayData::try_extend`
This PR adopts several improvements:
1. There is no reason to stop at row boundaries when copying elements
2. For primitive types, it is more efficient to copy output values as part
of the same loop that scans for non-null values
3. For `Utf8` and `LargeUtf8`, we walk the input once to build a bitmap of
elements to keep and the offsets of each row in the result value. We then do a
second pass, copying contiguous spans of strings and avoiding re-validating
UTF-8.
4. For all other types, we walk the input to build a "keep" bitmap and
identify row offsets, and then use Arrow's `filter` kernel to produce the
retained values.
5. The previous approach also computed logical nulls for the entire values
buffer, which can be expensive; we now only do so for the visible span
Benchmarks: (#25566)
- primitive/mixed_nulls/2048, 8.153 → 1.442, −82.3%
- primitive/mixed_nulls/1048576, 8.252 → 1.498, −81.9%
- primitive/hidden_nulls/2048, 0.069 → 0.056, −19.2%
- primitive/hidden_nulls/1048576, 5.450 → 0.087, −98.4%
- dictionary/mixed_nulls/2048, 7.186 → 3.145, −56.2%
- dictionary/mixed_nulls/1048576, 543.524 → 3.287, −99.4%
- dictionary/hidden_nulls/2048, 1.002 → 0.994, −0.8%
- dictionary/hidden_nulls/1048576, 1409.995 → 1.040, −99.9%
- random/primitive/random_sparse, 6.030 → 1.756, −70.9%
- random/primitive/random, 8.956 → 2.040, −77.2%
- random/primitive/random_half, 9.081 → 2.224, −75.5%
- random/primitive/random_dense, 4.362 → 1.176, −73.0%
- random/utf8/random_sparse, 9.499 → 3.041, −68.0%
- random/utf8/random, 11.660 → 4.400, −62.3%
- random/utf8/random_half, 11.779 → 4.865, −58.7%
- random/utf8/random_dense, 4.896 → 1.970, −59.8%
- random/utf8_view/random_sparse, 6.639 → 2.037, −69.3%
- random/utf8_view/random, 8.846 → 3.630, −59.0%
- random/utf8_view/random_half, 9.099 → 2.839, −68.8%
- random/utf8_view/random_dense, 4.431 → 1.553, −64.9%
- types/utf8/mixed, 11.060 → 4.750, −57.1%
- nulls/clustered, 5.160 → 1.662, −67.8%
- nulls/utf8/clustered, 7.688 → 2.791, −63.7%
- types/boolean/mixed, 9.097 → 3.934, −56.8%
- types/decimal128/mixed, 8.879 → 1.725, −80.6%
- types/nested/sparse, 10.887 → 4.716, −56.7%
- types/struct_nested/sparse, 13.854 → 5.012, −63.8%
- types/fixed_nested/sparse, 18.550 → 8.904, −52.0%
- types/map/sparse, 15.843 → 10.117, −36.1%
- types/run/mixed, 271.347 → 6.285, −97.7%
- shape/variable/utf8, 18.560 → 7.661, −58.7%
- shape/near_uniform/utf8, 19.018 → 7.510, −60.5%
- shape/variable/utf8_sparse, 13.989 → 4.779, −65.8%
- shape/near_uniform/utf8_sparse, 13.878 → 4.613, −66.8%
- strings/utf8_short, 10.601 → 4.920, −53.6%
- strings/utf8_long, 21.283 → 8.636, −59.4%
- shape/width_128, 6.873 → 1.280, −81.4%
- shape/utf8/width_128, 5.658 → 2.025, −64.2%
- shape/8192_rows, 252.878 → 42.117, −83.3%
- parent_nulls/primitive/mostly, 3.464 → 1.044, −69.9%
- parent_nulls/utf8/some, 208.496 → 78.724, −62.2%
- parent_nulls/utf8/mostly, 4.195 → 2.979, −29.0%
- parent_nulls/nested/mostly, 6.322 → 7.098, +12.3%
- empty/zero_rows, 0.080 → 0.053, −34.1%
- empty/empty_lists, 0.072 → 0.054, −25.2%
- empty/null_lists, 0.741 → 0.054, −92.8%
- nulls/all, 3.055 → 0.253, −91.7%
- all_null/utf8, 3.175 → 0.262, −91.7%
- large_list/utf8, 10.986 → 4.767, −56.6%
- child_slice/utf8, 13.512 → 4.736, −65.0%
## What changes are included in this PR?
* Optimize `array_compact` as described above
* Refactor some shared code with `array_filter` into a shared helper
* Improve unit test coverage
## What is the testing strategy for this PR?
Existing tests pass. New tests added.
## 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]
