Rich-T-kid opened a new issue, #11117: URL: https://github.com/apache/arrow-rs/issues/11117
**Is your feature request related to a problem or challenge?** Part of https://github.com/apache/arrow-rs/issues/7761 `DenseUnion` goes through `GenericInProgressArray` → `concat_fallback` → `MutableArrayData`. The MutableArrayData `build_extend_dense` processes **row by row**: for each row it copies the type_id, does a linear scan through all union fields to find the child index, reads the per-type offset, then extends one child element at a time. This is O(n_rows × n_types) and prevents batched child copies. **Describe the solution you'd like** A specialized `InProgressDenseUnionArray` processes rows in batch by type: ```rust pub(crate) struct InProgressDenseUnionArray { union_fields: UnionFields, type_ids: Vec<i8>, // Accumulated type_id buffer offsets: Vec<i32>, // Accumulated per-row offsets into children children: Vec<Box<dyn InProgressArray>>, // One per union type child_row_counts: Vec<usize>, // Current length of each child } ``` **`copy_rows(offset, len)` logic (batch-by-type approach):** 1. Collect type_ids[offset..offset+len] in one pass → append to `self.type_ids` 2. For the offsets buffer: for each row i, `self.offsets.push(self.child_row_counts[type_id[i]])` then `self.child_row_counts[type_id[i]] += 1` 3. For each child type: find all rows in [offset, offset+len) with that type_id, batch-copy them via `child.copy_rows` — this enables the child to benefit from its own specialized path **Implementation ideas:** - Step 3 can use PEXT-style scattered index collection (collect indices per type_id using counting sort O(n_rows + n_types)) followed by one `copy_rows_by_indices` per type - This transforms O(n_rows × n_types) per-row linear scan into O(n_rows + n_types) batched processing - Children use `create_in_progress_array()` for recursive specialization **Note:** Dense union is relatively rare in practice. Prioritize after List, Struct, and RunEndEncoded. **Benchmarks** ``` cargo bench --bench coalesce_kernels --features test_utils -- union ``` -- 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]
