Repository navigation
perf(arrow-row): only encode referenced dictionary values - #11904
Open
princejain756 wants to merge 3 commits into
Open
princejain756 wants to merge 3 commits into
princejain756 wants to merge 3 commits into
Conversation
RowConverter encoded every value in a dictionary's values array for each batch, so a 1M-value dictionary cost ~10ms to convert 4096 rows even when the rows referenced only a small subset of keys. When the values outnumber the rows, gather just the referenced values with MutableArrayData and remap each row's key onto the compacted encoding. 4096 rows keyed into 1M strings: 9.9ms -> 0.15ms (~65x). Closes apache#11901.
github-actions
Bot
added
arrow-row
princejain756
added a commit
to princejain756/princejain756
that referenced
this pull request
Oct 25, 2026
Contributor
|
run benchmark row_format |
|
🤖 Benchmark starting (GKE) | trigger Target: row_format Sharding factor: 1 (1 workers). Comparing row-dictionary-compact (5a1bb36) to 9a95c6d (merge-base) diff Run configurationrun benchmark row_format
shards: 1
Results will be posted when all workers finish. File an issue against this benchmark runner |
Rich-T-kid
self-requested a review
October 25, 2026 21:36
|
🤖 Benchmark completed (GKE) | trigger Target: row_format Comparing row-dictionary-compact (5a1bb36) to 9a95c6d (merge-base) diff Run configurationrun benchmark row_format
shards: 1
DetailsPer-runner informationrow_format — shard 1/1Node: gk3-benchmark-cluster-nap-1shwrix6-6292f611-qz7v Instance: c4a-highmem-16 (12 vCPU / 65 GiB) uname: BENCH_COMMAND: cargo bench --features=arrow,async,test_common,experimental,object_store --bench row_formatCPU Details (lscpu)Resource Usagebase (merge-base)
branch
File an issue against this benchmark runner |
Checking remap.as_ref() inside the per-row map closure in row_lengths added a branch on every row even when remap was None, showing up on the un-compacted string_dictionary_low_cardinality benchmark in GKE. Match on remap.as_deref() once per column in row_lengths (matching encode_column) and zip remap in encode_dictionary_remapped.
Contributor
Author
|
In 5132371 I hoisted |
Rich-T-kid
reviewed
Oct 27, 2026
Rich-T-kid
left a comment
Rich-T-kid
left a comment
Contributor
There was a problem hiding this comment.
this is causing regressions.
convert_columns_prepared 4096 string_dictionary(10, 0) 1.00 48.4±0.05µs ? ?/sec 1.11 53.6±4.03µs ? ?/sec
convert_columns_prepared 4096 string_dictionary(100, 0) 1.00 73.5±0.31µs ? ?/sec 1.06 77.6±4.25µs ? ?/sec
convert_columns_prepared 4096 string_dictionary(100, 0.5) 1.00 54.4±0.19µs ? ?/sec 1.02 55.3±3.83µs ? ?/sec
convert_columns_prepared 4096 string_dictionary(30, 0) 1.00 54.5±1.25µs ? ?/sec 1.11 60.2±4.95µs ? ?/sec
convert_columns_prepared 4096 string_dictionary_low_cardinality(10, 0) 1.00 21.5±0.03µs ? ?/sec 1.24 26.7±3.90µs ? ?/sec
convert_columns_prepared 4096 string_dictionary_low_cardinality(100, 0) 1.00 32.2±0.03µs ? ?/sec 1.17 37.7±3.97µs ? ?/sec
convert_columns_prepared 4096 string_dictionary_low_cardinality(30, 0) 1.00 24.0±0.02µs ? ?/sec 1.22 29.2±3.93µs ? ?/sec
convert_columns_prepared 4096 string_dictionary_sparse_keys(1M values) 1.00 132.8±3.27µs ? ?/sec
is that expected?
Contributor
Author
|
@Rich-T-kid That GKE benchmark ran against In In |
Contributor
|
going to merge into main so we have the correct baseline |
Contributor
|
run benchmark row_format |
|
🤖 Benchmark starting (GKE) | trigger Target: row_format Sharding factor: 1 (1 workers). Comparing row-dictionary-compact (1c9492a) to 68cd02d (merge-base) diff Run configurationrun benchmark row_format
shards: 1
Results will be posted when all workers finish. File an issue against this benchmark runner |
Contributor
|
run benchmark row_format |
|
🤖 Benchmark starting (GKE) | trigger Target: row_format Sharding factor: 1 (1 workers). Comparing row-dictionary-compact (1c9492a) to 68cd02d (merge-base) diff Run configurationrun benchmark row_format
shards: 1
Results will be posted when all workers finish. File an issue against this benchmark runner |
|
🤖 Benchmark completed (GKE) | trigger Target: row_format Comparing row-dictionary-compact (1c9492a) to 68cd02d (merge-base) diff Run configurationrun benchmark row_format
shards: 1
DetailsPer-runner informationrow_format — shard 1/1Node: gk3-benchmark-cluster-nap-ptunuejs-f3ae936a-fl47 Instance: c4a-highmem-16 (12 vCPU / 65 GiB) uname: BENCH_COMMAND: cargo bench --features=arrow,async,test_common,experimental,object_store --bench row_formatCPU Details (lscpu)Resource Usagebase (merge-base)
branch
File an issue against this benchmark runner |
|
🤖 Benchmark completed (GKE) | trigger Target: row_format Comparing row-dictionary-compact (1c9492a) to 68cd02d (merge-base) diff Run configurationrun benchmark row_format
shards: 1
DetailsPer-runner informationrow_format — shard 1/1Node: gk3-benchmark-cluster-nap-hn5nhboo-e5ad4dcb-kgp2 Instance: c4a-highmem-16 (12 vCPU / 65 GiB) uname: BENCH_COMMAND: cargo bench --features=arrow,async,test_common,experimental,object_store --bench row_formatCPU Details (lscpu)Resource Usagebase (merge-base)
branch
File an issue against this benchmark runner |
Rich-T-kid
reviewed
Oct 27, 2026
Rich-T-kid
left a comment
Rich-T-kid
left a comment
Contributor
There was a problem hiding this comment.
I haven't taken too close of a look but the issue & pr discussion make sense. I think we should add benchmarks to get a better guide to when we would want to incure the overhead cost of remapping.
also I think @jayzhan211 would be interested in this as he proposed something similar upstream in datafusion
| // Encoding a dictionary costs time proportional to its values, | ||
| // so when they outnumber the rows, gather only the referenced | ||
| // values and remap each row's key onto them. | ||
| let (values, remap) = match values.len() > dictionary.len() { |
Contributor
There was a problem hiding this comment.
There’s some fixed cost to re-hashing the values to create new mappings. Can we benchmark to find out what a decent cutoff would be?
Record batches are typically 8192 rows, so we wouldn’t want to incur this cost when there are only 10k unique values. Or maybe we would 🤔. I think we should have some numbers to back up this decision.
This branch has not been deployed
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Add this suggestion to a batch that can be applied as a single commit.This suggestion is invalid because no changes were made to the code.Suggestions cannot be applied while the pull request is closed.Suggestions cannot be applied while viewing a subset of changes.Only one suggestion per line can be applied in a batch.Add this suggestion to a batch that can be applied as a single commit.Applying suggestions on deleted lines is not supported.You must change the existing code in this line in order to create a valid suggestion.Outdated suggestions cannot be applied.This suggestion has been applied or marked resolved.Suggestions cannot be applied from pending reviews.Suggestions cannot be applied on multi-line comments.Suggestions cannot be applied while the pull request is queued to merge.Suggestion cannot be applied right now. Please check back later.
Which issue does this PR close?
Rationale for this change
RowConverterencodes every value in a dictionary's values array for each batch, so encoding cost grows with dictionary size rather than row count. The issue reports a 1M-value dictionary costing ~7ms to convert 8192 rows versus ~50us for the equivalent Utf8 array. The same dictionary-retention problem is tracked downstream in apache/datafusion#26696, where hash aggregate output slices keep the whole dictionary.What changes are included in this PR?
Codec::encodergathers only the referenced values viaMutableArrayData(no new dependencies) and stores a per-row remap inEncoder::Dictionary.row_lengthsand the encode path translate each key through the remap when present.encode_dictionary_valueskeeps its signature and handles the un-compacted path as before.4096 string_dictionary_sparse_keys(1M values): 4096 rows keyed into 1024 of 1M strings.Are these changes tested?
New unit tests cover byte equality against an equivalent small dictionary, null keys, round-trip decoding, and sliced arrays. Benchmark results for the new case, this branch vs main:
convert_columns: 9.86ms -> 0.152ms (~65x)convert_columns_prepared: 9.77ms -> 0.155ms (~63x)append_rows: 9.61ms -> 0.150ms (~64x)convert_rows: 51.0us -> 61.3us (decode path is unchanged)Are there any significant user-facing changes?
No. Row encodings are unchanged; this only avoids encoding dictionary values that no row references.