[C++] Implement basic array-by-array reassembly logic

[asfimport]

This logic would attempt to create the data necessary for each field by passing through the levels once for each field.  it is expected that due to once we can put SIMD/bitmap code in place this will perform better for nested data with shallow nesting, but due to repetitive computation might perform worse for deep nested that include List-types.  The SIMD/bitmap enhancements are covered in: ARROW-9985

 

At a high level the logic would be structured as:

for each field:

   for each rep/def level entry:

           update null bitmask and offsets.

Reporter: Micah Kornfield / @emkornfield
Assignee: Micah Kornfield / @emkornfield

PRs and other links:

• GitHub Pull Request #8177

_{Note: This issue was originally created as ARROW-8494. Please see the migration documentation for further details.}

[asfimport]

Antoine Pitrou / @pitrou:
If I understand correctly, for a non-list nullable field, we only need to update the null bitmap:

• if def level >= field's def level, append non-null

• otherwise, append null

  For a non-nullable list field, we must update the offsets:

• if rep level < field's rep level and def level < field's def level , append current_offset (empty list)

• if rep level < field's rep level and def level >= field's def level , append current_offset++ (first item in new list)

• otherwise, just current_offset++ (next item in same list)

  For a nullable list field, the ancestor_def_level must also be taken into account?

  So non-list fields are easy, list fields have more sophisticated logic that might be less easy to do efficiently.

[asfimport]

Micah Kornfield / @emkornfield:
Yes @pitrou  that matches my understanding, I have an algorithm that I think might work fairly well for the more complicated  list cases but probably has diminishing returns as the level of nesting grows.

[asfimport]

Antoine Pitrou / @pitrou:
Issue resolved by pull request 8177
#8177