[C++] Add chunked builder classes

[asfimport]

I think it would be useful to have chunked builders for list, string and binary types. A chunked builder would produce a chunked array as output, circumventing the 32-bit offset limit of those types. There's some special-casing scatterred around our Numpy conversion routines right now.

Reporter: Antoine Pitrou / @pitrou

Related issues:

• [C++] Parquet arrow::Table reads error when overflowing capacity of BinaryArray (relates to)

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

[asfimport]

Antoine Pitrou / @pitrou:
See PARQUET-1239 for an example where this comes up.

[asfimport]

Antoine Pitrou / @pitrou:
@wesm I have been thinking about this a bit. I think there are several possible designs:

1. An entirely duplicate class hierarchy and implementation. The main downside is obviously the development work, and later maintenance to try to keep the interfaces consistent as one of the hierarchies evolves.

2. A refactor of the current ArrayBuilder classes to take a template type that implements either chunking or raising CapacityError. Very heavy in terms of implementation, but is conceptually "clean" and avoids code duplication.

3. A set of "heavy" wrappers that redefine all overloads of Append and AppendValues, but delegate some of the work to an underlying ArrayBuilder.

4. A set of "light-weight" wrappers that define templated Append and AppendValues methods that simply redirect to an underlying ArrayBuilder, but catch CapacityError to finalize the current chunk and try again.

5. A set of "very thin" wrappers that only have a couple methods for space reservation. So ChunkedBuilder::Reserve would either reserve some space on the underlying ArrayBuilder, or finalize the current chunk and reserve space in the new chunk. Actual appending would need the user to call the underlying ArrayBuilder directly, taking care to sequence calls to the ChunkedBuilder and the ArrayBuilder carefully: you must first ask the ChunkedBuilder for space reservation, then append on the ArrayBuilder.

   The fifth approach is probably the most light-weight in terms of implementation. The main downside is it requires a bit more care from the user in how they interact with the two builders.

   Specialized implementations will be needed for binary, list and struct arrays, and I'm not sure what we can do for dictionary arrays.

   To make testing easier, we should ideally make the maximum chunk size parametrizable.

[asfimport]

Wes McKinney / @wesm:
Not sure if this comment is prompted by my working on https://issues.apache.org/jira/browse/ARROW-3762 but I'm running into the need for this also.

For the time being, I have implemented very simple ChunkedBinaryBuilder, ChunkedStringBuilder for this: https://github.com/wesm/arrow/blob/ARROW-3762/cpp/src/arrow/columnar/builder_binary.h#L239 (I took the liberty of reorganizing the builder code a little bit). I think these count as Option 4 as you've listed them. I have made them internal for now so that we have the option to do something more involved as you are describing.

My plan this week is to do the bare minimum of work (which is already quite a lot) for now to resolve ARROW-3762 and ARROW-2970.

What do you think we need beyond chunked builders for binary and string? There is also the issue of chunked fields in a struct, where the other fields have to be split up after the fact.

[asfimport]

Antoine Pitrou / @pitrou:
There are lists too. I think if we want to encourage use of chunked arrays, we may want chunked primitive builders too.

[asfimport]

Wes McKinney / @wesm:
Let's take a closer look after I get my patches up for those issues (as I've taken the butcher's blade to builder.h/builder*.cc).

I think that introducing chunking into the base ArrayBuilder would introduce too much API complexity for simple use cases – so having as minimal-as-possible builders that produce single arrays is a good thing. I would say we should define the public API that we desire for chunked builders and work backwards to the most efficient and easiest-to-maintain (in terms of code duplication or lack thereof) implementation.

I was surprised to see that the chunked binary builder I implemented outperformed the non-chunked benchmark on identical data (unless I made a mistake in the implementation). This suggests that we might want to use chunking more liberally in data ingest code (CSV, Parquet, etc.) – e.g. capping array chunks at 8-16MB or so.

[asfimport]

Antoine Pitrou / @pitrou:
Yes, resizing data is not free, limiting chunk size to some application-specific heuristic makes sense.

[asfimport]

Wes McKinney / @wesm:
Looking at this a little bit. From a "cleanness" point of view I think we should explore option 2 a bit more thoroughly. If we introduced a "growth strategy" template argument then this could theoretically be done with good code reuse.

There are some questions like how to handle the differing output type. In the chunking case, its a vector of arrays. In the non-chunking case, it's a single array. So you'd have something like:

class Int16Builder : public ArrayBuilder, public internal::NonChunkedBuilder<Int16Type> {
 public:
  using _Impl = internal::NonChunkedBuilder<Int16Type>;

  using _Impl::Append;
  using _Impl::AppendValues;
  // etc

  // Implement the ArrayBuilder public API
  Status Finish(std::shared_ptr<Array>* out) override;
};

I've suffered enough from extern template visibility issues that I'd like to avoid going down that rabbit hole if it can be avoided

Obviously this is not urgent work – I place it in the bucket of future performance optimization (I would guess that chunking at the 16MB/32MB granularity will improve the performance of many applications)

[github-actions]

This issue has been marked as stale because it has had no activity in the past 365 days. Please remove the stale label or comment below, or this issue will be closed in 14 days. If this improvement is still desired but has no current owner, please add the 'Status: needs champion' label.