You are viewing a plain text version of this content. The canonical link for it is here.
Posted to github@datafusion.apache.org by "neilconway (via GitHub)" <gi...@apache.org> on 2026/03/04 14:19:19 UTC
[PR] perf: Optimize array set ops on sliced arrays [datafusion]
neilconway opened a new pull request, #20693:
URL: https://github.com/apache/datafusion/pull/20693
## Which issue does this PR close?
N/A
## Rationale for this change
Several array set operations (`array_union`, `array_intersect`, `array_distinct`, `array_except`) operate on all values in the underlying values buffer of a `ListArray` when doing batched row conversion. For sliced ListArrays, `values()` returns the full underlying buffer, which means we end up doing row conversion for rows that aren't in the visible slice. This was not a correctness issue but it is inefficient.
## What changes are included in this PR?
- Change array set ops to do row conversion on the visible slice, not the full values buffer
- Add unit tests for array set ops on sliced ListArrays. These tests pass with or without this PR, but it seems wise to have more test coverage for sliced ListArrays
- Add benchmarks for array set ops on sliced ListArrays.
## Are these changes tested?
Yes.
## Are there any user-facing changes?
No.
## AI usage
Multiple AI tools were used to iterate on this PR. I have reviewed and understand the resulting 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@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] perf: Optimize array set ops on sliced arrays [datafusion]
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on PR #20693:
URL: https://github.com/apache/datafusion/pull/20693#issuecomment-4057696171
This PR looks like it has some conflicts that need to be resolved. Any chance you have time to do so @neilconway ?
--
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@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] perf: Optimize array set ops on sliced arrays [datafusion]
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb merged PR #20693:
URL: https://github.com/apache/datafusion/pull/20693
--
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@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] perf: Optimize array set ops on sliced arrays [datafusion]
Posted by "neilconway (via GitHub)" <gi...@apache.org>.
neilconway commented on PR #20693:
URL: https://github.com/apache/datafusion/pull/20693#issuecomment-3997850923
#20677 is similar, but in that case operating on the full values array leads to a bug.
--
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@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] perf: Optimize array set ops on sliced arrays [datafusion]
Posted by "neilconway (via GitHub)" <gi...@apache.org>.
neilconway commented on PR #20693:
URL: https://github.com/apache/datafusion/pull/20693#issuecomment-4058098094
@alamb Done!
--
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@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] perf: Optimize array set ops on sliced arrays [datafusion]
Posted by "neilconway (via GitHub)" <gi...@apache.org>.
neilconway commented on PR #20693:
URL: https://github.com/apache/datafusion/pull/20693#issuecomment-4059091411
Updated benchmark numbers:
```
⏺ ┌────────────────────────────┬─────────────┬───────────┬─────────┐
│ Benchmark │ Unoptimized │ Optimized │ Speedup │
├────────────────────────────┼─────────────┼───────────┼─────────┤
│ array_union_sliced/10 │ 440 µs │ 206 µs │ 2.1x │
├────────────────────────────┼─────────────┼───────────┼─────────┤
│ array_union_sliced/50 │ 2.14 ms │ 999 µs │ 2.1x │
├────────────────────────────┼─────────────┼───────────┼─────────┤
│ array_union_sliced/100 │ 4.20 ms │ 1.98 ms │ 2.1x │
├────────────────────────────┼─────────────┼───────────┼─────────┤
│ array_intersect_sliced/10 │ 439 µs │ 208 µs │ 2.1x │
├────────────────────────────┼─────────────┼───────────┼─────────┤
│ array_intersect_sliced/50 │ 2.33 ms │ 1.16 ms │ 2.0x │
├────────────────────────────┼─────────────┼───────────┼─────────┤
│ array_intersect_sliced/100 │ 4.53 ms │ 2.31 ms │ 2.0x │
├────────────────────────────┼─────────────┼───────────┼─────────┤
│ array_distinct_sliced/10 │ 184 µs │ 79 µs │ 2.3x │
├────────────────────────────┼─────────────┼───────────┼─────────┤
│ array_distinct_sliced/50 │ 900 µs │ 385 µs │ 2.3x │
├────────────────────────────┼─────────────┼───────────┼─────────┤
│ array_distinct_sliced/100 │ 1.73 ms │ 706 µs │ 2.4x │
├────────────────────────────┼─────────────┼───────────┼─────────┤
│ array_except_sliced/10 │ 420 µs │ 208 µs │ 2.0x │
├────────────────────────────┼─────────────┼───────────┼─────────┤
│ array_except_sliced/50 │ 2.02 ms │ 979 µs │ 2.1x │
├────────────────────────────┼─────────────┼───────────┼─────────┤
│ array_except_sliced/100 │ 4.07 ms │ 1.93 ms │ 2.1x │
└────────────────────────────┴─────────────┴───────────┴─────────┘
```
--
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@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] perf: Optimize array set ops on sliced arrays [datafusion]
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on PR #20693:
URL: https://github.com/apache/datafusion/pull/20693#issuecomment-4062744006
Thanks again @neilconway and @Jefffrey
--
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@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] perf: Optimize array set ops on sliced arrays [datafusion]
Posted by "neilconway (via GitHub)" <gi...@apache.org>.
neilconway commented on PR #20693:
URL: https://github.com/apache/datafusion/pull/20693#issuecomment-3997875840
Benchmarks:
```
group base target
----- ---- ------
array_distinct_sliced/10 1.72 588.8±8.31µs ? ?/sec 1.00 342.8±8.83µs ? ?/sec
array_distinct_sliced/100 1.92 5.6±0.09ms ? ?/sec 1.00 2.9±0.10ms ? ?/sec
array_distinct_sliced/50 1.93 2.8±0.06ms ? ?/sec 1.00 1469.1±44.20µs ? ?/sec
array_except_sliced/10 1.75 1110.5±10.75µs ? ?/sec 1.00 634.5±8.48µs ? ?/sec
array_except_sliced/100 4.06 23.2±0.29ms ? ?/sec 1.00 5.7±0.13ms ? ?/sec
array_except_sliced/50 1.95 5.6±0.09ms ? ?/sec 1.00 2.9±0.03ms ? ?/sec
array_intersect_sliced/10 1.80 1122.6±10.06µs ? ?/sec 1.00 623.3±18.21µs ? ?/sec
array_intersect_sliced/100 3.93 24.1±0.23ms ? ?/sec 1.00 6.1±0.12ms ? ?/sec
array_intersect_sliced/50 1.93 5.9±0.06ms ? ?/sec 1.00 3.1±0.05ms ? ?/sec
array_union_sliced/10 1.65 1175.6±11.55µs ? ?/sec 1.00 710.9±18.95µs ? ?/sec
array_union_sliced/100 3.65 24.9±0.29ms ? ?/sec 1.00 6.8±0.15ms ? ?/sec
array_union_sliced/50 3.60 12.2±0.38ms ? ?/sec 1.00 3.4±0.11ms ? ?/sec
```
These benchmarks use a ratio of 10:1 hidden:visible rows. The reason the benchmark results don't show a ~10x speedup is that previously, we did row conversion on the hidden rows but only applied the set operation to the visible rows, so the latter part was not inefficient.
--
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@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org