optimize(parquet): write list without repeated child write call

[mapleFU]

Is your feature request related to a problem or challenge? Please describe what you are trying to do.

Previously I wrote #10037 . This optimize list type writing when it's last level. However for types like list<struct<a: int, b: f32, c:list<...>>, the writes would not optimized. We should thinking a algorithm to optimize it.

Describe the solution you'd like

Here I'd like to introducing a "batch" algorithm, this is a bit more complex. It's purpose it's batching the write call and rep-level back-filling.

1. get self's max_rep_level for list, as list_max_rep_level
2. when write [start, end) for child
3. If its max_rep_level is equal to parent's list_max_rep_level + 1, do as perf(parquet): LevelInfoBuilder batch write when no repetition childs #10037 , which sets rep-levels at offsets, it's O(list-length) call
4. Otherwise, it's larger than list_max_rep_level + 1. Then our target it's to find the list start of currently and mark them.

For 2.2, we have list lengths, and we can batching find the list length in childs equal to write list length. For example: [ [2], [3], [4, 5], [6, 7, 8]], the lengths is 1, 1, 2, 3, we should find the rep of child list reaches 1, 1, 2, 3, and mark the list start to level.

This algorithm didn't reduce the work, it just reduce the cost of number of write calls.

Describe alternatives you've considered

This algorithm introducing a backward scan in every write. Maybe we can mark the [lengths] or how to get the lengths in writer.

Additional context

no

[mapleFU]

@alamb I would try this this two weeks, we have some nested complex list in this scenerio, I may first add a benchmark and then optimize it.

[alamb]

@alamb I would try this this two weeks, we have some nested complex list in this scenerio, I may first add a benchmark and then optimize it.

Thank you @mapleFU -- I hope to review your other outstanding PRs soon too

[mapleFU]

I've let AI generated some benchmarking code here: #10083 , will start to implement algorithm

[mapleFU]

And the impl is added now