apache / apache/arrow-rs

Dictionary values are not merged for view types, and the merge interner can overflow the key type on its own

Open
#10,925 0 comments 0 reactions 0 assignees View on GitHub
bug
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

Open the contributing 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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.