Dictionary values are not merged for view types, and the merge interner can overflow the key type on its own
- Dominant language
- Rust
- Stars
- 3.6k
- Forks
- 1.3k
- Avg merge
- 2d 18h
- Merged PRs (30d)
- 169
Description
### Describe the bug
Combining `DictionaryArray`s whose dictionaries were built independently requires
merging their values. `merge_dictionary_values` deduplicates, so the merged
dictionary holds only the distinct referenced values; the `MutableArrayData`
fallback concatenates them and can exceed what the key type addresses even when
the distinct values fit comfortably.
Since #10675 this surfaces as a `DictionaryKeyOverflowError` rather than a panic,
which is the right behaviour for a genuine overflow. But in the two cases below
the distinct values *do* fit, and the error is avoidable.
**1. View-typed dictionary values are never merged.**
`should_merge_dictionary_values` matches primitives and offset-based byte arrays.
`Utf8View`/`BinaryView` are neither, so it returns early with
`should_merge = false` and such dictionaries always take the non-deduplicating
path. Were it to reach the merge, `get_masked_values` would hit
`unimplemented!()` — it has no arm for the view layouts either.
The two are indistinguishable to a caller: identical data merges as `Utf8` and
fails as `Utf8View`.
**2. The interner alone can overflow the key type.**
`Interner` is best-effort by design — a hash collision evicts the previous
occupant, so one value may be handed several keys. In practice this leaves ~42%
duplicates, enough to overflow a `UInt16` key at realistic cardinalities. This
affects `Utf8` dictionaries too; it is simply less visible there.
### To Reproduce
```rust
// (1) identical data, only the value layout differs
let utf8 = || {
let v: StringArray = (0..200).map(|i| Some(format!("v{i}"))).collect();
DictionaryArray::::new(UInt8Array::from_iter_values(0..200), Arc::new(v))
};
let view = || {
let v: StringViewArray = (0..200).map(|i| Some(format!("v{i}"))).collect();
DictionaryArray::::new(UInt8Array::from_iter_values(0..200), Arc::new(v))
};
concat(&[&utf8(), &utf8()]); // Ok(400)
concat(&[&view(), &view()]); // Err("Dictionary key bigger than the key type")
```
```rust
// (2) 4 dictionaries over the same distinct values, UInt16 keys, Utf8 values
// (so the merge path is actually taken)
4 x 20000 distinct -> Ok, merged dict = 28445 (+42%)
4 x 40000 distinct -> Ok, merged dict = 57433 (+43%)
4 x 60000 distinct -> Err(DictionaryKeyOverflowError)
```
### Expected behavior
Both should succeed with a merged dictionary holding one key per distinct value:
200 in the first case, 60000 in the second. `DictionaryKeyOverflowError` should
be reserved for a genuine overflow — more distinct values than the key type can
address.
### Additional context
Encountered in a column store that declares dictionary-encoded columns as
`Dictionary(UInt16, Utf8View)`. Every data source builds its own dictionary, so
any query combining batches hits this: a sort-preserving merge, a hash join's
build side, or plain `CoalesceBatchesExec` — the last of which means it
reproduces with a single partition.
Follow-up to #10674 / #10675, which made this an error instead of a panic.
I have a fix and can open a PR.
Contributor guide
Research direction
Start by locating should_merge_dictionary_values, get_masked_values, Interner, and the concat path, then run the two reproductions from the issue. Done means view-typed dictionaries merge successfully and the interner does not create a key-type overflow when distinct values fit; genuine overflows should still return DictionaryKeyOverflowError.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- rust
- Domain
- data
- Issue type
- Bug
- Difficulty
- 4/5
- Estimated time
- 3-5 days
- Activity status
- Active
- Clarity
- Mostly clear
- Newbie friendliness
- 55/100