Wrong results: EmitTo::First(n) collision-list compaction in GroupValuesColumn can overwrite a not-yet-visited entry's list #25233

Describe the bug

In GroupValuesColumn::<false>::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

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:

#[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::<false>::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::<false> (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.