Wrong results: EmitTo::First(n) collision-list compaction in GroupValuesColumn can overwrite a not-yet-visited entry's list
- Dominant language
- Rust
- Stars
- 9.3k
- Forks
- 2.4k
- Avg merge
- 3d 7h
- Merged PRs (30d)
- 344
Description
### Describe the bug
In `GroupValuesColumn::::emit(EmitTo::First(n))`, the hash-table `retain` pass compacts the surviving non-inlined collision lists into `group_index_lists` slots `0, 1, 2, …` in **map iteration (bucket) order**, but reads each entry's list from its **original offset**:
https://github.com/apache/datafusion/blob/main/datafusion/physical-plan/src/aggregates/group_values/multi_group_by/mod.rs#L1264-L1277
```rust
let group_index_list =
&mut self.group_index_lists[next_new_list_offset]; // write slot: visit order
group_index_list.clear();
group_index_list
.extend(self.emit_group_index_list_buffer.iter()); // read was from the entry's
// *original* offset (line ~1250)
*group_idx_view = GroupIndexView::new_non_inlined(next_new_list_offset as u64);
next_new_list_offset += 1;
```
Bucket iteration order is unrelated to the order list offsets were allocated. If an entry with a *higher* original offset is visited *before* an entry with a lower one, its compaction write lands on the not-yet-visited entry's slot and destroys that list. The damaged entry then reads the clobbered slot and adopts the other key's group indices — so after the emit, **two different group keys can claim the same group index, and subsequent rows are aggregated into the wrong group**. Silent wrong results, no panic.
The existing test `test_hashtable_modifying_in_emit_first_n` passes only because its synthetic hashes `0..=5` happen to land in ascending bucket order, so visit order matches allocation order — it pins the coincidence, not the invariant.
### To Reproduce
Add this test to `multi_group_by/mod.rs` (uses the same helpers as the existing test). It fails on current `main`:
```rust
#[test]
fn test_emit_first_n_clobbers_collision_list() {
// Two multi-group hash entries whose hashbrown bucket order inverts
// their list-offset allocation order. Trying both allocation orders
// makes the repro independent of hashbrown's iteration direction.
let field = Field::new_list_field(DataType::Int32, true);
let schema = Arc::new(Schema::new_with_metadata(vec![field], HashMap::new()));
for &(h_first, h_second) in &[(7u64, 1u64), (1u64, 7u64)] {
let mut group_values =
GroupValuesColumn::::try_new(schema.clone()).unwrap();
// allocates list offset 0
insert_non_inline_group_index_view(&mut group_values, h_first, vec![4, 5]);
// allocates list offset 1
insert_non_inline_group_index_view(&mut group_values, h_second, vec![6, 7]);
let _ = group_values.emit(EmitTo::First(1)).unwrap();
// Emitting 1 group just shifts every group index down by one:
// [4,5] -> [3,4] and [6,7] -> [5,6].
let (first_list, _) = group_values.get_indices_by_hash(h_first).unwrap();
let (second_list, _) = group_values.get_indices_by_hash(h_second).unwrap();
assert_eq!(
(first_list.clone(), second_list.clone()),
(vec![3, 4], vec![5, 6]),
"corrupted collision lists for insertion order ({h_first}, {h_second})"
);
}
}
```
Output:
```
assertion `left == right` failed: corrupted collision lists for insertion order (7, 1)
left: ([4, 5], [5, 6])
right: ([3, 4], [5, 6])
```
Group index 5 is now claimed by **both** entries.
### Expected behavior
Compaction must not let writes alias reads. One fix (verified locally — the repro above passes and all existing `multi_group_by` tests stay green): `mem::take` the old `group_index_lists` before the `retain`, read from the taken vector, and push compacted lists into the (now empty) `self.group_index_lists`; this also removes the `next_new_list_offset` counter and the trailing `truncate`.
### Additional context
Reaching this in a real query requires: multi-column GROUP BY on `GroupValuesColumn::` (`GroupOrdering::None`), an `EmitTo::First(n)` (e.g. the emit-early-on-OOM path), and at least two full-64-bit-hash collision lists each still holding ≥ 2 groups after the emit — rare in the wild, but deterministic under `force_hash_collisions`-style conditions, and the failure is silent wrong results rather than an error. Found while auditing the aggregation emit paths; I'll follow up with a PR containing the fix + regression test.
Contributor guide
Assessment
This issue has not been assessed yet.