Rich-T-kid opened a new issue, #12195:
URL: https://github.com/apache/arrow-rs/issues/12195
### Problem
`DictionaryBuffer` preserves Parquet dictionary encoding while a batch uses
one dictionary page. If the batch crosses into a different column chunk or a
plain-encoded page, `spill_values` expands every key into its byte value.
`into_array` later hashes those values, deduplicates them, and rebuilds a
dictionary.
In other words, a transition currently does this:
```text
dictionary keys + unique values
|
| expand every key
v
flat byte values
|
| hash and deduplicate
v
new dictionary keys + values
```
For low-cardinality columns, a small set of strings can be copied and hashed
millions of times.
For example, suppose a batch starts with:
```text
dictionary A
values = ["mobile", "desktop"]
keys = [0, 1, 0, 0, 1, ...] // 1,000,000 keys
```
and then encounters:
```text
dictionary B
values = ["mobile", "tablet"]
keys = [0, 1, 1, ...]
```
The current fallback materializes the first million strings before
rebuilding a dictionary.
[`DictionaryBuffer::spill_values`](https://github.com/apache/arrow-rs/blob/main/parquet/src/arrow/buffer/dictionary_buffer.rs)
already describes spilling as a degenerate path.
### Proposed direction
Merge the unique dictionaries and remap their keys instead of materializing
row values:
```text
A values = ["mobile", "desktop"]
B values = ["mobile", "tablet"]
|
| merge unique values
v
merged = ["mobile", "desktop", "tablet"]
A remap = [0, 1]
B remap = [0, 2]
A keys [0, 1, 0] -> [0, 1, 0]
B keys [0, 1, 1] -> [0, 2, 2]
```
This keeps work proportional to the unique dictionary bytes plus the keys,
rather than the bytes produced by expanding every row.
A possible representation is a third buffer state:
```rust
enum DictionaryBuffer<K, V> {
// Zero-copy fast path for one Parquet dictionary page.
Dict { /* keys and shared values */ },
// Multiple dictionaries, or dictionary data followed by plain values.
Merged { /* keys, unique values, and lookup state */ },
// Plain values that have not been dictionary encoded.
Values { /* offset buffer */ },
}
```
The first `Dict -> Merged` transition would seed the merged dictionary with
the existing unique values. Existing keys remain valid because those values
keep their order. Later dictionaries get a small source-key-to-merged-key map.
Plain values still need to be interned individually, but previously decoded
dictionary rows no longer need to be expanded.
```text
empty
|
+-- dictionary page ----------> Dict
| |
| | different dictionary
| | or plain fallback
| v
+-- plain page ---------------> Merged
|
v
final DictionaryArray
```
The existing `Dict` path should remain unchanged when a batch uses one
dictionary page.
### Expected complexity
Let:
- `N` be the row count
- `U` be the number of unique values
- `B` be the total bytes after expanding all rows
- `D` be the bytes in the unique dictionaries
The spill path copies and hashes `O(B)` bytes and allocates `O(N)` offsets.
Dictionary merging should hash `O(D)` bytes, build `O(U)` remapping state, and
translate `O(N)` keys.
For one million rows, 100 unique 20-byte strings means processing roughly 20
MB of repeated string data today versus roughly 2 KB of unique string data when
merging dictionaries.
### Tasks
- Implement a merged dictionary state that preserves keys across dictionary
and plain-page transitions.
- Recognize equal dictionaries backed by different allocations and keep the
zero-copy path.
- Evaluate ending batches at dictionary boundaries as a simpler way to avoid
spilling.
### Requirements
- Preserve nulls and dictionary-key validation.
- Do not regress the one-dictionary-page fast path.
- Cover dictionary-to-dictionary, dictionary-to-plain, and
multi-column-chunk transitions.
- Benchmark low and medium cardinality with both aligned and crossing batch
boundaries.
- Measure allocation volume and bytes hashed in addition to elapsed time.
- Include end-to-end results that expose any cost from smaller or irregular
batches.
- Keep requested dictionary value-type conversion and UTF-8 validation
operating on unique values.
--
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]
