[C++] Add a Tensor logical value type with varying dimensions, implemented using ExtensionType

[asfimport]

Support for tensor in Table, RecordBatch, etc. where each row is a tensor of a different shape (e.g images of different sizes), but of the same underlying type (e.g. int32). Implemented as an ExtensionType, so no need to change the format. 

I don't see needing each row being a tensor with a different number of dimensions, so if the implementation for that falls out easily of the use case with each row in the table having a tensor with the same number of dimensions, great. If it adds a lot of complexity, that case would be postponed.

Reporter: Christian Hudon / @chrish42
Watchers: Rok Mihevc / @rok

Related issues:

• [C++] Add a Tensor logical value type with constant shape, implemented using ExtensionType (relates to)

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

[asfimport]

Christian Hudon / @chrish42:
Proposed approach: a first column containing the elements from all the tensors (in row-major order), and a second containing a tuple with that tensor's shape. The start offset of the data for the next tensor can be computed from the shape of the previous one. Does that sound like the right approach? Would we also need a separate column containing the pre-computed start index of for each tensor?

 

[asfimport]

Joris Van den Bossche / @jorisvandenbossche:
I think a struct with one field with the actual values and one field keeping track of the shape of each tensor sounds good.

The start offset of the data for the next tensor can be computed from the shape of the previous one.

The field storing the values of the actual tensors will be a variable size binary or list layout, I suppose. That way, since this is a normal arrow array, you already have access to the start offset of each tensor (without needing to calculate it from all previous ones), see https://arrow.apache.org/docs/format/Columnar.html#variable-size-binary-layout

For variable size binary vs variable size list layout, in the end both will be same physical storage. But using a list array instead of binary array might make it a bit easier to work with (the data type of the individual values is then already coded in the list type as well, and eg in the python APIs of pyarrow, you can easily access the flat array of values of the ListArray as a single numpy array (from which a part can be sliced and reshaped to get the tensor).

[asfimport]

Bryan Cutler / @BryanCutler:
+1 on the proposal of having a list array for the data (of same type as the tensor) and second array for the shape. For the shape, a list array of ints would work but it could also be possible to modify Tensor.fbs slightly to have a TensorShape message. That might have some benefit to keep the size down for lots of small tensors, but not sure if it's worth the added complexity.

I also had another thought, if the shape for each tensor added an additional outer dimension to represent how many records are in each tensor, that would allow us to use a single tensor extension type for both variable and constant shapes. For example, say you have 10 tensors of shape (2, 3) stacked in a single ndarray of (10, 2, 3), then the shape array would have a single entry [(10, 2, 3)], if you have 10 tensors of varying shapes, then each one will have a 1 added to the outer dimension, so 10 entries with [(1, 2, 3), (1, 5, 3), (1, 4, 3), ...]. It would be a little redundant having the 1's in this case, but this would also allow to combine smaller batches, say 10 tensors where 5 are same shape, as an example would give you [(5, 2, 3), (5, 4, 6). What do you think of this @chrish42 and @jorisvandenbossche ?

[asfimport]

Rok Mihevc / @rok:
I like idea of batching into equally shaped Tensors. It would require a bit extra complexity for keeping original order of elements and taking into account cases where Tensors with equal shapes would have different strides. I suppose this will become clearer with ARROW-1614 resolved.

[asfimport]

Joris Van den Bossche / @jorisvandenbossche:

I also had another thought, if the shape for each tensor added an additional outer dimension to represent how many records are in each tensor, that would allow us to use a single tensor extension type for both variable and constant dimensions.

To clarify, this is only about constant vs variable dimensions, and not about constant shape ?

My understanding was that ARROW-1614 is also about constant shape (although the title only says dimension), and then I don't see how that would be possible to combine in the way described?

[asfimport]

Bryan Cutler / @BryanCutler:
Sorry, I mistyped dimension when I meant shape above (fixed now). I was trying to think of a way to use a single extension type for constant and variable shapes, with a fixed dimension. Although there is a problem with my suggestion in that the arrays won't be able to be sliced without recomputing the shapes, and I don't see a way around that. So I guess it seems better to stay with 2 different extension types, this one for variable shapes and ARROW-1614 for constant shapes.

[raulcd]

I was going to cherry-pick this due to it being milestoned for 14.0.0 before, should I pick it @jorisvandenbossche or should I leave it for 15.0.0?

[jorisvandenbossche]

Yeah, I was just going to comment on the PR to ask about it. It's the merge script that changed the milestone again to 15.0. @rok how important is it to have this in 14.0? In practice it doesn't matter much because it's only the extension type specification that anyone can implement (on any version of arrow), and the actual C++ implementation will only be for 15.0.
On the other hand, for rendering it in the documentation, it's maybe nice to have for 14.0 (and it's also an easy backport)

[rok]

I'm +0 for 14.0.0 for the same reasons as Joris. Since it's just a doc change it'd not expect it to cause issues with the release. I defer to @raulcd as I don't know how much work it is to include.

[raulcd]

I'll cherry-pick it