Rich-T-kid opened a new issue, #11114: URL: https://github.com/apache/arrow-rs/issues/11114
**Is your feature request related to a problem or challenge?** Part of https://github.com/apache/arrow-rs/issues/7761 \`List<T>\` and \`LargeList<T>\` go through \`GenericInProgressArray\` → \`concat_lists\`. \`concat_lists\` handles sliced arrays, reconstructs the cumulative offset buffer, and recursively calls \`concat()\` on values. A specialized implementation can accumulate offsets incrementally and dispatch values to a type-appropriate \`InProgressArray\`. **Describe the solution you'd like** \`\`\`rust pub(crate) struct InProgressListArray<OffsetSize: OffsetSizeTrait> { field: FieldRef, source: Option<ArrayRef>, batch_size: usize, nulls: NullBufferBuilder, /// Incrementally built cumulative offset buffer offsets: Vec<OffsetSize>, /// Values child: uses its own optimal InProgressArray values: Box<dyn InProgressArray>, } \`\`\` **\`copy_rows(offset, len)\` logic:** - Append outer nulls - Iterate the source list's offsets for the [offset, offset+len range - For each list element i in [offset, offset+len): compute `lengths[i] = offsets[i+1] - offsets[i]` - Append lengths to `offsets` accumulator (as cumulative sum) - Determine the total value range: `[source_offsets[offset], source_offsets[offset+len])` - Call `values.copy_rows(value_start, value_count)` on the child InProgressArray - Note: `set_source` for the child should be called with the list's values array **`finish()` logic:** - Finish child `values` → get values `ArrayRef` - Convert `offsets` vec to `OffsetBuffer` - Build `GenericListArray::try_new(field, offset_buffer, values, nulls)` **Implementation ideas to beat concat:** 1. **Incremental offset accumulation**: the offset reconstruction is O(n_rows) at finish with `concat_lists`, but O(1) per row push with incremental accumulation 2. **Child InProgressArray specialization**: values child uses `create_in_progress_array()` recursively — `List<Float32>` gets `InProgressPrimitiveArray` for values 3. **Avoid slice detection overhead**: `concat_lists` checks every input for non-zero first offset to handle slices; the incremental approach handles offsets correctly per push without a separate scan **`create_in_progress_array` dispatch:** ```rust DataType::List(field) => Box::new(InProgressListArray::<i32>::new( Arc::clone(field), create_in_progress_array(field.data_type(), batch_size), batch_size, )), DataType::LargeList(field) => Box::new(InProgressListArray::<i64>::new( Arc::clone(field), create_in_progress_array(field.data_type(), batch_size), batch_size, )), ``` **Benchmarks** Add `List<Int32>`, `List<Utf8>`, `List<Float32>` schemas: ``` cargo bench --bench coalesce_kernels --features test_utils -- list ``` EOF ) -- 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]
