neilconway opened a new pull request, #26453:
URL: https://github.com/apache/datafusion/pull/26453
## Which issue does this PR close?
- N/A
## Rationale for this change
This PR optimizes `array_sort` on arrays of primitive values, where at least
one element in the batch contains is NULL.
Previously, `array_sort` started by counting the NULL elements in the row
and then compacting the non-NULL elements to place NULLs either first or last
(depending on the specified sort order). Doing the compaction already requires
looking at every element's validity bit, so we can make this more efficient by
doing the compaction first and deriving the null count as we go. When `NULLS
FIRST`, we then need to move the non-NULL values after the NULLs. Empirically,
the cost of the move is outweighed by the savings from avoiding a separate null
count.
Two alternatives were considered:
1. Using `SetBitCounter` from #25754; results were faster on some inputs and
slower on some inputs.
2. Compacting values at the end of the buffer for `NULLS FIRST`, walking
elements backwards but avoiding the post-compaction move; this was faster for
small rows and slower for large rows.
Along the way, improve the `array_sort` benchmarks:
1. Add coverage for `NULLS LAST`
2. Cycle through several input arrays and make the distribution of NULLs and
array lengths more unpredictable, to avoid the branch predictor being able to
memorize the benchmark input.
Benchmarks: (x86, AMD EPYC-Milan)
int32_null_elements/5 -15.4%
int32_null_elements/20 -4.6%
int32_null_elements/100 -5.6%
int32_null_elements/1000 +1.0%
int32_null_elements_desc/5 -16.5%
int32_null_elements_desc/20 -6.8%
int32_null_elements_desc/100 -3.5%
int32_null_elements_desc/1000 -0.2%
int32_null_elements_nulls_last/5 -20.7%
int32_null_elements_nulls_last/20 -7.7%
int32_null_elements_nulls_last/100 -6.7%
int32_null_elements_nulls_last/1000 -2.0%
## What changes are included in this PR?
See above.
## 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]
