You are viewing a plain text version of this content. The canonical link for it is here.
Posted to github@arrow.apache.org by "asubiotto (via GitHub)" <gi...@apache.org> on 2025/12/10 12:35:08 UTC
[PR] arrow-select: improve dictionary interleave fallback performance [arrow-rs]
asubiotto opened a new pull request, #8978:
URL: https://github.com/apache/arrow-rs/pull/8978
The naive interleave_fallback would use MutableArray and extend it with the full values slice each time the target array changed in the indices slice.
This commit introduces a new approach where dictionary values are concatenated once and then new offsets are computed over these taking the indices into account. This results in 50-75% performance improvement in microbenchmarks and will also improve memory usage during interleaves (used heavily in sorts).
Note that this path is only taken when should_merge_dictionary_values returns false.
```
$ cargo bench --bench interleave_kernels -- 'dict' --baseline main
interleave dict(20, 0.0) 100 [0..100, 100..230, 450..1000]
time: [627.14 ns 634.76 ns 644.13 ns]
change: [−65.614% −65.345% −65.002%] (p = 0.00 < 0.05)
Performance has improved.
Found 9 outliers among 100 measurements (9.00%)
2 (2.00%) low mild
6 (6.00%) high mild
1 (1.00%) high severe
interleave dict(20, 0.0) 400 [0..100, 100..230, 450..1000]
time: [934.35 ns 937.51 ns 940.60 ns]
change: [−71.488% −71.340% −71.208%] (p = 0.00 < 0.05)
Performance has improved.
Found 3 outliers among 100 measurements (3.00%)
3 (3.00%) high mild
interleave dict(20, 0.0) 1024 [0..100, 100..230, 450..1000]
time: [1.6485 µs 1.6528 µs 1.6566 µs]
change: [−74.307% −74.190% −74.088%] (p = 0.00 < 0.05)
Performance has improved.
interleave dict(20, 0.0) 1024 [0..100, 100..230, 450..1000, 0..1000]
time: [1.6723 µs 1.6782 µs 1.6842 µs]
change: [−74.664% −74.544% −74.438%] (p = 0.00 < 0.05)
Performance has improved.
Found 2 outliers among 100 measurements (2.00%)
1 (1.00%) low mild
1 (1.00%) high severe
interleave dict_sparse(20, 0.0) 100 [0..100, 100..230, 450..1000]
time: [1.5985 µs 1.6064 µs 1.6148 µs]
change: [−12.510% −12.116% −11.715%] (p = 0.00 < 0.05)
Performance has improved.
Found 19 outliers among 100 measurements (19.00%)
10 (10.00%) low mild
6 (6.00%) high mild
3 (3.00%) high severe
interleave dict_sparse(20, 0.0) 400 [0..100, 100..230, 450..1000]
time: [1.9310 µs 1.9466 µs 1.9680 µs]
change: [−41.488% −41.091% −40.628%] (p = 0.00 < 0.05)
Performance has improved.
Found 15 outliers among 100 measurements (15.00%)
3 (3.00%) low mild
6 (6.00%) high mild
6 (6.00%) high severe
interleave dict_sparse(20, 0.0) 1024 [0..100, 100..230, 450..1000]
time: [2.7812 µs 2.8516 µs 2.9401 µs]
change: [−56.097% −55.276% −54.274%] (p = 0.00 < 0.05)
Performance has improved.
Found 15 outliers among 100 measurements (15.00%)
8 (8.00%) high mild
7 (7.00%) high severe
interleave dict_sparse(20, 0.0) 1024 [0..100, 100..230, 450..1000, 0..1000]
time: [3.4926 µs 3.6558 µs 3.8427 µs]
change: [−48.423% −46.405% −44.379%] (p = 0.00 < 0.05)
Performance has improved.
interleave dict_distinct 100
time: [2.0013 µs 2.0106 µs 2.0205 µs]
change: [−1.6162% −1.0465% −0.4647%] (p = 0.00 < 0.05)
Change within noise threshold.
Found 4 outliers among 100 measurements (4.00%)
4 (4.00%) high mild
interleave dict_distinct 1024
time: [1.9784 µs 1.9855 µs 1.9924 µs]
change: [−2.4655% −1.8461% −1.2265%] (p = 0.00 < 0.05)
Performance has improved.
interleave dict_distinct 2048
time: [1.9832 µs 1.9959 µs 2.0087 µs]
change: [−2.9917% −2.3003% −1.6062%] (p = 0.00 < 0.05)
Performance has improved.
```
# Which issue does this PR close?
Specific performance improvement, I believe issue is redundant.
# Rationale for this change
See commit message/PR description.
# What changes are included in this PR?
Ditto.
# Are these changes tested?
This PR adds an additional test for interleave_fallback dictionaries with nulls in addition to the existing tests.
# 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: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] arrow-select: improve dictionary interleave fallback performance [arrow-rs]
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on PR #8978:
URL: https://github.com/apache/arrow-rs/pull/8978#issuecomment-3641882616
run benchmark interleave_kernels
--
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@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] arrow-select: improve dictionary interleave fallback performance [arrow-rs]
Posted by "Dandandan (via GitHub)" <gi...@apache.org>.
Dandandan commented on code in PR #8978:
URL: https://github.com/apache/arrow-rs/pull/8978#discussion_r2607719714
##########
arrow-select/src/interleave.rs:
##########
@@ -346,6 +347,57 @@ fn interleave_fallback(
Ok(make_array(array_data.freeze()))
}
+/// interleave_fallback_dictionary is a fallback implementation for interleaving
+/// dictionaries when it was determined that the dictionary values should not
+/// be merged. This implementation concatenates the value slices and recomputes
+/// the resulting dictionary keys.
+fn interleave_fallback_dictionary<K: ArrowDictionaryKeyType>(
+ dictionaries: &[&DictionaryArray<K>],
+ indices: &[(usize, usize)],
+) -> Result<ArrayRef, ArrowError> {
+ let relative_offsets: Vec<usize> = dictionaries
+ .iter()
+ .scan(0usize, |offset, dict| {
+ let current = *offset;
+ *offset += dict.values().len();
+ Some(current)
+ })
+ .collect();
+ let all_values: Vec<&dyn Array> = dictionaries.iter().map(|d| d.values().as_ref()).collect();
+ let concatenated_values = concat(&all_values)?;
+
+ let mut has_nulls = false;
+ let new_keys: Vec<K::Native> = indices
+ .iter()
+ .map(|(a, b)| {
+ let dict = dictionaries[*a];
+ let old_keys = dict.keys();
+ if old_keys.is_valid(*b) {
Review Comment:
In the case `old_keys` has no nulls, we don't need to check this?
For that case, it might make sense to add a code path without checking?
```
let new_keys = indices
.iter()
.map(|(a, b)| {
let dict = dictionaries[*a];
let old_keys = dict.keys();
let old_key = old_keys.values()[*b].as_usize();
K::Native::from_usize(relative_offsets[*a] + old_key).unwrap()
}).collect()
```
--
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@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] arrow-select: improve dictionary interleave fallback performance [arrow-rs]
Posted by "alamb-ghbot (via GitHub)" <gi...@apache.org>.
alamb-ghbot commented on PR #8978:
URL: https://github.com/apache/arrow-rs/pull/8978#issuecomment-3637309270
🤖 Hi @alamb, thanks for the request (https://github.com/apache/arrow-rs/pull/8978#issuecomment-3637308157).
[`scrape_comments.py`](https://github.com/alamb/datafusion-benchmarking/blob/main/scripts/scrape_comments.py) only supports whitelisted benchmarks.
- Standard: (none)
- Criterion: arrow_reader, arrow_reader_clickbench, arrow_reader_row_filter, arrow_statistics, arrow_writer, coalesce_kernels, concatenate_kernels, filter_kernels, interleave_kernels, take_kernels, union_array, variant_builder, variant_kernels, variant_validation
Please choose one or more of these with `run benchmark <name>` or `run benchmark <name1> <name2>...`
--
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@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] arrow-select: improve dictionary interleave fallback performance [arrow-rs]
Posted by "alamb-ghbot (via GitHub)" <gi...@apache.org>.
alamb-ghbot commented on PR #8978:
URL: https://github.com/apache/arrow-rs/pull/8978#issuecomment-3637382331
🤖: Benchmark completed
<details><summary>Details</summary>
<p>
```
group asubiotto_interleavedict main
----- ------------------------ ----
interleave dict(20, 0.0) 100 [0..100, 100..230, 450..1000] 1.00 840.7±11.01ns ? ?/sec 4.12 3.5±0.03µs ? ?/sec
interleave dict(20, 0.0) 1024 [0..100, 100..230, 450..1000, 0..1000] 1.00 2.8±0.04µs ? ?/sec 6.12 16.9±0.09µs ? ?/sec
interleave dict(20, 0.0) 1024 [0..100, 100..230, 450..1000] 1.00 2.7±0.03µs ? ?/sec 6.38 17.1±0.35µs ? ?/sec
interleave dict(20, 0.0) 400 [0..100, 100..230, 450..1000] 1.00 1457.0±12.46ns ? ?/sec 5.61 8.2±0.12µs ? ?/sec
interleave dict_distinct 100 1.00 2.9±0.07µs ? ?/sec 1.02 3.0±0.02µs ? ?/sec
interleave dict_distinct 1024 1.00 2.9±0.04µs ? ?/sec 1.02 3.0±0.02µs ? ?/sec
interleave dict_distinct 2048 1.00 2.9±0.11µs ? ?/sec 1.02 3.0±0.02µs ? ?/sec
interleave dict_sparse(20, 0.0) 100 [0..100, 100..230, 450..1000] 1.00 2.9±0.31µs ? ?/sec 1.20 3.5±0.08µs ? ?/sec
interleave dict_sparse(20, 0.0) 1024 [0..100, 100..230, 450..1000, 0..1000] 1.00 5.2±0.33µs ? ?/sec 3.26 17.1±0.23µs ? ?/sec
interleave dict_sparse(20, 0.0) 1024 [0..100, 100..230, 450..1000] 1.00 4.6±0.32µs ? ?/sec 3.69 17.1±0.35µs ? ?/sec
interleave dict_sparse(20, 0.0) 400 [0..100, 100..230, 450..1000] 1.00 3.6±0.28µs ? ?/sec 2.27 8.1±0.12µs ? ?/sec
interleave i32(0.0) 100 [0..100, 100..230, 450..1000] 1.03 315.8±5.85ns ? ?/sec 1.00 307.8±2.71ns ? ?/sec
interleave i32(0.0) 1024 [0..100, 100..230, 450..1000, 0..1000] 1.00 1861.3±29.98ns ? ?/sec 1.00 1855.9±60.53ns ? ?/sec
interleave i32(0.0) 1024 [0..100, 100..230, 450..1000] 1.00 1833.7±20.52ns ? ?/sec 1.00 1836.6±23.45ns ? ?/sec
interleave i32(0.0) 400 [0..100, 100..230, 450..1000] 1.00 910.4±4.28ns ? ?/sec 1.01 917.9±37.61ns ? ?/sec
interleave i32(0.5) 100 [0..100, 100..230, 450..1000] 1.03 616.4±9.50ns ? ?/sec 1.00 600.6±8.44ns ? ?/sec
interleave i32(0.5) 1024 [0..100, 100..230, 450..1000, 0..1000] 1.00 4.3±0.07µs ? ?/sec 1.00 4.3±0.05µs ? ?/sec
interleave i32(0.5) 1024 [0..100, 100..230, 450..1000] 1.00 4.3±0.02µs ? ?/sec 1.00 4.3±0.09µs ? ?/sec
interleave i32(0.5) 400 [0..100, 100..230, 450..1000] 1.00 1839.5±17.46ns ? ?/sec 1.00 1843.6±52.88ns ? ?/sec
interleave str(20, 0.0) 100 [0..100, 100..230, 450..1000] 1.03 818.5±13.18ns ? ?/sec 1.00 792.6±5.35ns ? ?/sec
interleave str(20, 0.0) 1024 [0..100, 100..230, 450..1000, 0..1000] 1.00 6.1±0.04µs ? ?/sec 1.01 6.2±0.06µs ? ?/sec
interleave str(20, 0.0) 1024 [0..100, 100..230, 450..1000] 1.00 6.1±0.04µs ? ?/sec 1.00 6.1±0.11µs ? ?/sec
interleave str(20, 0.0) 400 [0..100, 100..230, 450..1000] 1.00 2.5±0.02µs ? ?/sec 1.05 2.7±0.02µs ? ?/sec
interleave str(20, 0.5) 100 [0..100, 100..230, 450..1000] 1.00 1056.1±3.69ns ? ?/sec 1.01 1065.4±3.88ns ? ?/sec
interleave str(20, 0.5) 1024 [0..100, 100..230, 450..1000, 0..1000] 1.00 10.1±0.09µs ? ?/sec 1.01 10.2±0.09µs ? ?/sec
interleave str(20, 0.5) 1024 [0..100, 100..230, 450..1000] 1.00 10.1±0.09µs ? ?/sec 1.01 10.1±0.22µs ? ?/sec
interleave str(20, 0.5) 400 [0..100, 100..230, 450..1000] 1.01 3.6±0.04µs ? ?/sec 1.00 3.6±0.03µs ? ?/sec
interleave str_view(0.0) 100 [0..100, 100..230, 450..1000] 1.00 809.4±19.59ns ? ?/sec 1.06 857.0±7.21ns ? ?/sec
interleave str_view(0.0) 1024 [0..100, 100..230, 450..1000, 0..1000] 1.00 5.0±0.05µs ? ?/sec 1.02 5.1±0.06µs ? ?/sec
interleave str_view(0.0) 1024 [0..100, 100..230, 450..1000] 1.00 5.0±0.02µs ? ?/sec 1.02 5.1±0.11µs ? ?/sec
interleave str_view(0.0) 400 [0..100, 100..230, 450..1000] 1.05 2.2±0.08µs ? ?/sec 1.00 2.1±0.01µs ? ?/sec
interleave struct(i32(0.0), i32(0.0) 100 [0..100, 100..230, 450..1000] 1.00 837.5±7.10ns ? ?/sec 1.00 836.2±9.60ns ? ?/sec
interleave struct(i32(0.0), i32(0.0) 1024 [0..100, 100..230, 450..1000, 0..1000] 1.01 4.0±0.09µs ? ?/sec 1.00 4.0±0.02µs ? ?/sec
interleave struct(i32(0.0), i32(0.0) 1024 [0..100, 100..230, 450..1000] 1.00 4.0±0.03µs ? ?/sec 1.01 4.0±0.02µs ? ?/sec
interleave struct(i32(0.0), i32(0.0) 400 [0..100, 100..230, 450..1000] 1.00 1903.0±33.03ns ? ?/sec 1.00 1893.6±4.04ns ? ?/sec
interleave struct(i32(0.0), str(20, 0.0) 100 [0..100, 100..230, 450..1000] 1.00 1388.5±15.44ns ? ?/sec 1.02 1411.3±33.83ns ? ?/sec
interleave struct(i32(0.0), str(20, 0.0) 1024 [0..100, 100..230, 450..1000, 0..1000] 1.00 8.3±0.04µs ? ?/sec 1.01 8.4±0.09µs ? ?/sec
interleave struct(i32(0.0), str(20, 0.0) 1024 [0..100, 100..230, 450..1000] 1.00 8.3±0.15µs ? ?/sec 1.01 8.4±0.30µs ? ?/sec
interleave struct(i32(0.0), str(20, 0.0) 400 [0..100, 100..230, 450..1000] 1.00 3.6±0.03µs ? ?/sec 1.04 3.7±0.10µs ? ?/sec
interleave struct(str(20, 0.0), str(20, 0.0)) 100 [0..100, 100..230, 450..1000] 1.00 1842.4±12.57ns ? ?/sec 1.06 1959.4±15.50ns ? ?/sec
interleave struct(str(20, 0.0), str(20, 0.0)) 1024 [0..100, 100..230, 450..1000, 0..1000] 1.00 12.6±0.10µs ? ?/sec 1.00 12.7±0.12µs ? ?/sec
interleave struct(str(20, 0.0), str(20, 0.0)) 1024 [0..100, 100..230, 450..1000] 1.00 12.7±0.43µs ? ?/sec 1.00 12.6±0.11µs ? ?/sec
interleave struct(str(20, 0.0), str(20, 0.0)) 400 [0..100, 100..230, 450..1000] 1.00 5.4±0.11µs ? ?/sec 1.02 5.5±0.16µs ? ?/sec
```
</p>
</details>
--
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@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] arrow-select: improve dictionary interleave fallback performance [arrow-rs]
Posted by "alamb-ghbot (via GitHub)" <gi...@apache.org>.
alamb-ghbot commented on PR #8978:
URL: https://github.com/apache/arrow-rs/pull/8978#issuecomment-3637310921
🤖 `./gh_compare_arrow.sh` [gh_compare_arrow.sh](https://github.com/alamb/datafusion-benchmarking/blob/main/scripts/gh_compare_arrow.sh) Running
Linux aal-dev 6.14.0-1018-gcp #19~24.04.1-Ubuntu SMP Wed Sep 24 23:23:09 UTC 2025 x86_64 x86_64 x86_64 GNU/Linux
Comparing asubiotto/interleavedict (f1136f4a2981b07ec63090545a1bedf278047dec) to dff6402457910389af785d768e0f9e274d9526a7 [diff](https://github.com/apache/arrow-rs/compare/dff6402457910389af785d768e0f9e274d9526a7..f1136f4a2981b07ec63090545a1bedf278047dec)
BENCH_NAME=interleave_kernels
BENCH_COMMAND=cargo bench --features=arrow,async,test_common,experimental --bench interleave_kernels
BENCH_FILTER=
BENCH_BRANCH_NAME=asubiotto_interleavedict
Results will be posted here when complete
--
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@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] arrow-select: improve dictionary interleave fallback performance [arrow-rs]
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb merged PR #8978:
URL: https://github.com/apache/arrow-rs/pull/8978
--
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@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] arrow-select: improve dictionary interleave fallback performance [arrow-rs]
Posted by "asubiotto (via GitHub)" <gi...@apache.org>.
asubiotto commented on code in PR #8978:
URL: https://github.com/apache/arrow-rs/pull/8978#discussion_r2606532180
##########
arrow-select/src/interleave.rs:
##########
@@ -346,6 +347,57 @@ fn interleave_fallback(
Ok(make_array(array_data.freeze()))
}
+/// interleave_fallback_dictionary is a fallback implementation for interleaving
+/// dictionaries when it was determined that the dictionary values should not
+/// be merged. This implementation concatenates the value slices and recomputes
+/// the resulting dictionary keys.
+fn interleave_fallback_dictionary<K: ArrowDictionaryKeyType>(
+ dictionaries: &[&DictionaryArray<K>],
+ indices: &[(usize, usize)],
+) -> Result<ArrayRef, ArrowError> {
+ // Compute offsets for each dictionary's keys in the merged values array
+ let mut offsets = Vec::with_capacity(dictionaries.len());
+ let mut current_offset = 0usize;
+ for dict in dictionaries.iter() {
Review Comment:
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@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] arrow-select: improve dictionary interleave fallback performance [arrow-rs]
Posted by "Dandandan (via GitHub)" <gi...@apache.org>.
Dandandan commented on PR #8978:
URL: https://github.com/apache/arrow-rs/pull/8978#issuecomment-3641329402
> If keys are nullable from the input but no nulls were found, we now return a null buffer that is fully valid. We were using a None null buffer before. Are these two semantically equivalent
Yes you can use `None` null buffer, this is more efficient than a all-valid null buffer.
--
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@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] arrow-select: improve dictionary interleave fallback performance [arrow-rs]
Posted by "alamb-ghbot (via GitHub)" <gi...@apache.org>.
alamb-ghbot commented on PR #8978:
URL: https://github.com/apache/arrow-rs/pull/8978#issuecomment-3641958689
🤖: Benchmark completed
<details><summary>Details</summary>
<p>
```
group asubiotto_interleavedict main
----- ------------------------ ----
interleave dict(20, 0.0) 100 [0..100, 100..230, 450..1000] 1.00 816.5±11.19ns ? ?/sec 4.18 3.4±0.03µs ? ?/sec
interleave dict(20, 0.0) 1024 [0..100, 100..230, 450..1000, 0..1000] 1.00 2.3±0.03µs ? ?/sec 7.32 16.8±0.08µs ? ?/sec
interleave dict(20, 0.0) 1024 [0..100, 100..230, 450..1000] 1.00 2.2±0.02µs ? ?/sec 7.60 17.1±0.10µs ? ?/sec
interleave dict(20, 0.0) 400 [0..100, 100..230, 450..1000] 1.00 1275.6±23.88ns ? ?/sec 6.24 8.0±0.11µs ? ?/sec
interleave dict_distinct 100 1.05 3.0±0.02µs ? ?/sec 1.00 2.9±0.02µs ? ?/sec
interleave dict_distinct 1024 1.00 2.9±0.09µs ? ?/sec 1.00 2.9±0.08µs ? ?/sec
interleave dict_distinct 2048 1.04 3.0±0.02µs ? ?/sec 1.00 2.9±0.07µs ? ?/sec
interleave dict_sparse(20, 0.0) 100 [0..100, 100..230, 450..1000] 1.00 2.8±0.18µs ? ?/sec 1.23 3.4±0.06µs ? ?/sec
interleave dict_sparse(20, 0.0) 1024 [0..100, 100..230, 450..1000, 0..1000] 1.00 5.0±0.34µs ? ?/sec 3.40 17.0±0.16µs ? ?/sec
interleave dict_sparse(20, 0.0) 1024 [0..100, 100..230, 450..1000] 1.00 4.2±0.21µs ? ?/sec 4.10 17.0±0.17µs ? ?/sec
interleave dict_sparse(20, 0.0) 400 [0..100, 100..230, 450..1000] 1.00 3.2±0.21µs ? ?/sec 2.51 8.0±0.04µs ? ?/sec
interleave i32(0.0) 100 [0..100, 100..230, 450..1000] 1.00 307.9±8.11ns ? ?/sec 1.00 309.3±1.88ns ? ?/sec
interleave i32(0.0) 1024 [0..100, 100..230, 450..1000, 0..1000] 1.00 1848.5±19.41ns ? ?/sec 1.00 1851.3±6.03ns ? ?/sec
interleave i32(0.0) 1024 [0..100, 100..230, 450..1000] 1.04 1905.0±12.19ns ? ?/sec 1.00 1828.4±6.50ns ? ?/sec
interleave i32(0.0) 400 [0..100, 100..230, 450..1000] 1.00 913.8±3.21ns ? ?/sec 1.00 915.0±7.38ns ? ?/sec
interleave i32(0.5) 100 [0..100, 100..230, 450..1000] 1.01 609.7±5.27ns ? ?/sec 1.00 601.7±4.32ns ? ?/sec
interleave i32(0.5) 1024 [0..100, 100..230, 450..1000, 0..1000] 1.00 4.3±0.07µs ? ?/sec 1.00 4.3±0.05µs ? ?/sec
interleave i32(0.5) 1024 [0..100, 100..230, 450..1000] 1.02 4.4±0.18µs ? ?/sec 1.00 4.3±0.02µs ? ?/sec
interleave i32(0.5) 400 [0..100, 100..230, 450..1000] 1.05 1927.1±34.75ns ? ?/sec 1.00 1838.5±9.15ns ? ?/sec
interleave str(20, 0.0) 100 [0..100, 100..230, 450..1000] 1.00 796.1±19.40ns ? ?/sec 1.00 795.4±12.73ns ? ?/sec
interleave str(20, 0.0) 1024 [0..100, 100..230, 450..1000, 0..1000] 1.00 6.2±0.02µs ? ?/sec 1.01 6.2±0.09µs ? ?/sec
interleave str(20, 0.0) 1024 [0..100, 100..230, 450..1000] 1.00 6.1±0.04µs ? ?/sec 1.00 6.2±0.07µs ? ?/sec
interleave str(20, 0.0) 400 [0..100, 100..230, 450..1000] 1.00 2.6±0.01µs ? ?/sec 1.02 2.6±0.05µs ? ?/sec
interleave str(20, 0.5) 100 [0..100, 100..230, 450..1000] 1.00 1065.7±16.28ns ? ?/sec 1.00 1067.7±4.08ns ? ?/sec
interleave str(20, 0.5) 1024 [0..100, 100..230, 450..1000, 0..1000] 1.00 10.1±0.13µs ? ?/sec 1.00 10.1±0.15µs ? ?/sec
interleave str(20, 0.5) 1024 [0..100, 100..230, 450..1000] 1.00 10.1±0.17µs ? ?/sec 1.00 10.1±0.11µs ? ?/sec
interleave str(20, 0.5) 400 [0..100, 100..230, 450..1000] 1.01 3.6±0.02µs ? ?/sec 1.00 3.6±0.04µs ? ?/sec
interleave str_view(0.0) 100 [0..100, 100..230, 450..1000] 1.00 862.0±22.30ns ? ?/sec 1.00 861.5±11.77ns ? ?/sec
interleave str_view(0.0) 1024 [0..100, 100..230, 450..1000, 0..1000] 1.00 4.9±0.11µs ? ?/sec 1.01 5.0±0.34µs ? ?/sec
interleave str_view(0.0) 1024 [0..100, 100..230, 450..1000] 1.03 5.0±0.02µs ? ?/sec 1.00 4.9±0.02µs ? ?/sec
interleave str_view(0.0) 400 [0..100, 100..230, 450..1000] 1.04 2.2±0.06µs ? ?/sec 1.00 2.1±0.02µs ? ?/sec
interleave struct(i32(0.0), i32(0.0) 100 [0..100, 100..230, 450..1000] 1.00 827.3±4.74ns ? ?/sec 1.01 837.3±4.63ns ? ?/sec
interleave struct(i32(0.0), i32(0.0) 1024 [0..100, 100..230, 450..1000, 0..1000] 1.01 4.0±0.02µs ? ?/sec 1.00 4.0±0.01µs ? ?/sec
interleave struct(i32(0.0), i32(0.0) 1024 [0..100, 100..230, 450..1000] 1.02 4.0±0.05µs ? ?/sec 1.00 3.9±0.02µs ? ?/sec
interleave struct(i32(0.0), i32(0.0) 400 [0..100, 100..230, 450..1000] 1.00 1850.7±9.06ns ? ?/sec 1.02 1896.0±8.73ns ? ?/sec
interleave struct(i32(0.0), str(20, 0.0) 100 [0..100, 100..230, 450..1000] 1.00 1331.1±19.63ns ? ?/sec 1.02 1357.5±23.65ns ? ?/sec
interleave struct(i32(0.0), str(20, 0.0) 1024 [0..100, 100..230, 450..1000, 0..1000] 1.00 8.4±0.27µs ? ?/sec 1.01 8.5±0.26µs ? ?/sec
interleave struct(i32(0.0), str(20, 0.0) 1024 [0..100, 100..230, 450..1000] 1.00 8.3±0.04µs ? ?/sec 1.00 8.3±0.09µs ? ?/sec
interleave struct(i32(0.0), str(20, 0.0) 400 [0..100, 100..230, 450..1000] 1.00 3.6±0.02µs ? ?/sec 1.01 3.6±0.03µs ? ?/sec
interleave struct(str(20, 0.0), str(20, 0.0)) 100 [0..100, 100..230, 450..1000] 1.00 1816.7±9.09ns ? ?/sec 1.04 1894.4±196.92ns ? ?/sec
interleave struct(str(20, 0.0), str(20, 0.0)) 1024 [0..100, 100..230, 450..1000, 0..1000] 1.01 12.8±1.42µs ? ?/sec 1.00 12.8±0.46µs ? ?/sec
interleave struct(str(20, 0.0), str(20, 0.0)) 1024 [0..100, 100..230, 450..1000] 1.01 12.7±0.13µs ? ?/sec 1.00 12.6±0.07µs ? ?/sec
interleave struct(str(20, 0.0), str(20, 0.0)) 400 [0..100, 100..230, 450..1000] 1.00 5.4±0.35µs ? ?/sec 1.00 5.4±0.31µs ? ?/sec
```
</p>
</details>
--
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@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] arrow-select: improve dictionary interleave fallback performance [arrow-rs]
Posted by "asubiotto (via GitHub)" <gi...@apache.org>.
asubiotto commented on PR #8978:
URL: https://github.com/apache/arrow-rs/pull/8978#issuecomment-3641440567
Hmm I'm not sure the archery test failure is related to this PR
--
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@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] arrow-select: improve dictionary interleave fallback performance [arrow-rs]
Posted by "alamb-ghbot (via GitHub)" <gi...@apache.org>.
alamb-ghbot commented on PR #8978:
URL: https://github.com/apache/arrow-rs/pull/8978#issuecomment-3641883100
🤖 `./gh_compare_arrow.sh` [gh_compare_arrow.sh](https://github.com/alamb/datafusion-benchmarking/blob/main/scripts/gh_compare_arrow.sh) Running
Linux aal-dev 6.14.0-1018-gcp #19~24.04.1-Ubuntu SMP Wed Sep 24 23:23:09 UTC 2025 x86_64 x86_64 x86_64 GNU/Linux
Comparing asubiotto/interleavedict (ca2ece4fdbf1bfc33a0dcf41fcceef3474db6e45) to dff6402457910389af785d768e0f9e274d9526a7 [diff](https://github.com/apache/arrow-rs/compare/dff6402457910389af785d768e0f9e274d9526a7..ca2ece4fdbf1bfc33a0dcf41fcceef3474db6e45)
BENCH_NAME=interleave_kernels
BENCH_COMMAND=cargo bench --features=arrow,async,test_common,experimental --bench interleave_kernels
BENCH_FILTER=
BENCH_BRANCH_NAME=asubiotto_interleavedict
Results will be posted here when complete
--
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@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] arrow-select: improve dictionary interleave fallback performance [arrow-rs]
Posted by "asubiotto (via GitHub)" <gi...@apache.org>.
asubiotto commented on code in PR #8978:
URL: https://github.com/apache/arrow-rs/pull/8978#discussion_r2608038050
##########
arrow-select/src/interleave.rs:
##########
@@ -346,6 +347,57 @@ fn interleave_fallback(
Ok(make_array(array_data.freeze()))
}
+/// interleave_fallback_dictionary is a fallback implementation for interleaving
+/// dictionaries when it was determined that the dictionary values should not
+/// be merged. This implementation concatenates the value slices and recomputes
+/// the resulting dictionary keys.
+fn interleave_fallback_dictionary<K: ArrowDictionaryKeyType>(
+ dictionaries: &[&DictionaryArray<K>],
+ indices: &[(usize, usize)],
+) -> Result<ArrayRef, ArrowError> {
+ let relative_offsets: Vec<usize> = dictionaries
+ .iter()
+ .scan(0usize, |offset, dict| {
+ let current = *offset;
+ *offset += dict.values().len();
+ Some(current)
+ })
+ .collect();
+ let all_values: Vec<&dyn Array> = dictionaries.iter().map(|d| d.values().as_ref()).collect();
+ let concatenated_values = concat(&all_values)?;
+
+ let mut has_nulls = false;
+ let new_keys: Vec<K::Native> = indices
+ .iter()
+ .map(|(a, b)| {
+ let dict = dictionaries[*a];
+ let old_keys = dict.keys();
+ if old_keys.is_valid(*b) {
Review Comment:
Yes, I considered even computing offsets in one pass and nulls in another. Will play around with this.
--
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@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] arrow-select: improve dictionary interleave fallback performance [arrow-rs]
Posted by "asubiotto (via GitHub)" <gi...@apache.org>.
asubiotto commented on PR #8978:
URL: https://github.com/apache/arrow-rs/pull/8978#issuecomment-3636897061
cc @alamb / @tustvold
--
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@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] arrow-select: improve dictionary interleave fallback performance [arrow-rs]
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on PR #8978:
URL: https://github.com/apache/arrow-rs/pull/8978#issuecomment-3643449826
Thanks @asubiotto and @Dandandan
--
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@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] arrow-select: improve dictionary interleave fallback performance [arrow-rs]
Posted by "alamb-ghbot (via GitHub)" <gi...@apache.org>.
alamb-ghbot commented on PR #8978:
URL: https://github.com/apache/arrow-rs/pull/8978#issuecomment-3637308365
🤖 Hi @alamb, thanks for the request (https://github.com/apache/arrow-rs/pull/8978#issuecomment-3637308157).
[`scrape_comments.py`](https://github.com/alamb/datafusion-benchmarking/blob/main/scripts/scrape_comments.py) only supports whitelisted benchmarks.
- Standard: (none)
- Criterion: arrow_reader, arrow_reader_clickbench, arrow_reader_row_filter, arrow_statistics, arrow_writer, coalesce_kernels, concatenate_kernels, filter_kernels, interleave_kernels, take_kernels, union_array, variant_builder, variant_kernels, variant_validation
Please choose one or more of these with `run benchmark <name>` or `run benchmark <name1> <name2>...`
Unsupported benchmarks: interleave_kernel.
--
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@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] arrow-select: improve dictionary interleave fallback performance [arrow-rs]
Posted by "asubiotto (via GitHub)" <gi...@apache.org>.
asubiotto commented on PR #8978:
URL: https://github.com/apache/arrow-rs/pull/8978#issuecomment-3641352726
> > If keys are nullable from the input but no nulls were found, we now return a null buffer that is fully valid. We were using a None null buffer before. Are these two semantically equivalent
>
> Yes you can use `None` null buffer, this is more efficient than a all-valid null buffer.
Ok, changed it back.
--
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@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] arrow-select: improve dictionary interleave fallback performance [arrow-rs]
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on PR #8978:
URL: https://github.com/apache/arrow-rs/pull/8978#issuecomment-3641872642
> Hmm I'm not sure the archery test failure is related to this PR
I don't think si -- I restarted the tests
--
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@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] arrow-select: improve dictionary interleave fallback performance [arrow-rs]
Posted by "Dandandan (via GitHub)" <gi...@apache.org>.
Dandandan commented on code in PR #8978:
URL: https://github.com/apache/arrow-rs/pull/8978#discussion_r2606505926
##########
arrow-select/src/interleave.rs:
##########
@@ -346,6 +347,57 @@ fn interleave_fallback(
Ok(make_array(array_data.freeze()))
}
+/// interleave_fallback_dictionary is a fallback implementation for interleaving
+/// dictionaries when it was determined that the dictionary values should not
+/// be merged. This implementation concatenates the value slices and recomputes
+/// the resulting dictionary keys.
+fn interleave_fallback_dictionary<K: ArrowDictionaryKeyType>(
+ dictionaries: &[&DictionaryArray<K>],
+ indices: &[(usize, usize)],
+) -> Result<ArrayRef, ArrowError> {
+ // Compute offsets for each dictionary's keys in the merged values array
+ let mut offsets = Vec::with_capacity(dictionaries.len());
+ let mut current_offset = 0usize;
+ for dict in dictionaries.iter() {
Review Comment:
This can use collect to vec in one go (which is faster than preallocating and push).
--
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@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] arrow-select: improve dictionary interleave fallback performance [arrow-rs]
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on PR #8978:
URL: https://github.com/apache/arrow-rs/pull/8978#issuecomment-3637308157
run benchmarks interleave_kernel
--
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@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] arrow-select: improve dictionary interleave fallback performance [arrow-rs]
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on PR #8978:
URL: https://github.com/apache/arrow-rs/pull/8978#issuecomment-3637435584
```
interleave dict(20, 0.0) 100 [0..100, 100..230, 450..1000] 1.00 840.7±11.01ns ? ?/sec 4.12 3.5±0.03µs ? ?/sec
interleave dict(20, 0.0) 1024 [0..100, 100..230, 450..1000, 0..1000] 1.00 2.8±0.04µs ? ?/sec 6.12 16.9±0.09µs ? ?/sec
interleave dict(20, 0.0) 1024 [0..100, 100..230, 450..1000] 1.00 2.7±0.03µs ? ?/sec 6.38 17.1±0.35µs ? ?/sec
interleave dict(20, 0.0) 400 [0..100, 100..230, 450..1000] 1.00 1457.0±12.46ns ? ?/sec 5.61 8.2±0.12µs ? ?/sec
interleave dict_distinct 100 1.00 2.9±0.07µs ? ?/sec 1.02 3.0±0.02µs ? ?/sec
interleave dict_distinct 1024 1.00 2.9±0.04µs ? ?/sec 1.02 3.0±0.02µs ? ?/sec
interleave dict_distinct 2048 1.00 2.9±0.11µs ? ?/sec 1.02 3.0±0.02µs ? ?/sec
interleave dict_sparse(20, 0.0) 100 [0..100, 100..230, 450..1000] 1.00 2.9±0.31µs ? ?/sec 1.20 3.5±0.08µs ? ?/sec
interleave dict_sparse(20, 0.0) 1024 [0..100, 100..230, 450..1000, 0..1000] 1.00 5.2±0.33µs ? ?/sec 3.26 17.1±0.23µs ? ?/sec
interleave dict_sparse(20, 0.0) 1024 [0..100, 100..230, 450..1000] 1.00 4.6±0.32µs ? ?/sec 3.69 17.1±0.35µs ? ?/sec
interleave dict_sparse(20, 0.0) 400 [0..100, 100..230, 450..1000] 1.00 3.6±0.28µs ? ?/sec 2.27 8.1±0.12µs ? ?/sec
```
That looks very nice results
--
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@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] arrow-select: improve dictionary interleave fallback performance [arrow-rs]
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on PR #8978:
URL: https://github.com/apache/arrow-rs/pull/8978#issuecomment-3643433235
> interleave dict(20, 0.0) 100 [0..100, 100..230, 450..1000] 1.00 816.5±11.19ns ? ?/sec 4.18 3.4±0.03µs ? ?/sec
interleave dict(20, 0.0) 1024 [0..100, 100..230, 450..1000, 0..1000] 1.00 2.3±0.03µs ? ?/sec 7.32 16.8±0.08µs ? ?/sec
interleave dict(20, 0.0) 1024 [0..100, 100..230, 450..1000] 1.00 2.2±0.02µs ? ?/sec 7.60 17.1±0.10µs ? ?/sec
interleave dict(20, 0.0) 400 [0..100, 100..230, 450..1000] 1.00 1275.6±23.88ns ? ?/sec 6.24 8.0±0.11µs ? ?/sec
🚀
--
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@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] arrow-select: improve dictionary interleave fallback performance [arrow-rs]
Posted by "asubiotto (via GitHub)" <gi...@apache.org>.
asubiotto commented on PR #8978:
URL: https://github.com/apache/arrow-rs/pull/8978#issuecomment-3641173761
Updated with the optimized non-nullable code path. I also updated this PR with two correctness fixes:
1) If keys are nullable from the input but no nulls were found, we now return a null buffer that is fully valid. We were using a `None` null buffer before. Are these two semantically equivalent?
2) In the case that the dictionaries to interleave share an underlying values slice and there is overflow, the fallback path would panic. I now changed `should_merge_dictionary_values` to also return whether key overflow is detected and use the general `interleave_fallback` path in that case. Added a test for this.
--
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@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org