arrow: [C++] Take kernel can't handle ChunkedArrays that don't fit in an Array
Take() currently concatenates ChunkedArrays first. However, this breaks down when calling Take() from a ChunkedArray or Table where concatenating the arrays would result in an array that’s too large. While inconvenient to implement, it would be useful if this case were handled.
This could be done as a higher-level wrapper around Take(), perhaps.
Example in Python:
>>> import pyarrow as pa
>>> pa.__version__
'1.0.0'
>>> rb1 = pa.RecordBatch.from_arrays([["a" * 2**30]], names=["a"])
>>> rb2 = pa.RecordBatch.from_arrays([["b" * 2**30]], names=["a"])
>>> table = pa.Table.from_batches([rb1, rb2], schema=rb1.schema)
>>> table.take([1, 0])
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
File "pyarrow/table.pxi", line 1145, in pyarrow.lib.Table.take
File "/home/lidavidm/Code/twosigma/arrow/venv/lib/python3.8/site-packages/pyarrow/compute.py", line 268, in take
return call_function('take', [data, indices], options)
File "pyarrow/_compute.pyx", line 298, in pyarrow._compute.call_function
File "pyarrow/_compute.pyx", line 192, in pyarrow._compute.Function.call
File "pyarrow/error.pxi", line 122, in pyarrow.lib.pyarrow_internal_check_status
File "pyarrow/error.pxi", line 84, in pyarrow.lib.check_status
pyarrow.lib.ArrowInvalid: offset overflow while concatenating arrays
In this example, it would be useful if Take() or a higher-level wrapper could generate multiple record batches as output.
Reporter: Will Jones / @wjones127 Assignee: Will Jones / @wjones127
Related issues:
- https://github.com/apache/arrow/issues/28385 (is a child of)
- https://github.com/apache/arrow/issues/26738 (duplicate)
- https://github.com/apache/arrow/issues/31249 (duplicate)
- https://github.com/apache/arrow/issues/26738 (duplicate)
- https://github.com/apache/arrow/issues/34583 (duplicate)
- https://github.com/apache/arrow/issues/37766 (relates to)
- https://github.com/apache/arrow/issues/23539 (relates to)
- https://github.com/apache/arrow/issues/33049 (relates to)
- https://github.com/apache/arrow/issues/40207 (relates to)
PRs and other links:
Note: This issue was originally created as ARROW-9773. Please see the migration documentation for further details.
About this issue
- Original URL
- State: open
- Created 6 years ago
- Reactions: 4
- Comments: 16 (3 by maintainers)
I’m working on this.
Will Jones / @wjones127: I’ve looked through the code and I think there are three related issues. I’ll try to describe them here. If you think I am missing some case, let me know. Otherwise, I’ll open three sub-tasks and start work on those.
Problem 1: We concatenate when we shouldn’t need to
This fails:
because we concatenate input values here. If that were corrected, it would then fail on the concatenation here if the indices were a chunked array.
The first concatenation could be avoided somewhat easily in special cases (sorted / fall in same chunk), which was partially implement in R. For the general case, we’d need to address this within the kernel rather than within pre-processing (see Problem 3).
The second concatenation shouldn’t always be eliminated, but we might want to add a check to validate that there is enough room in offset buffers of arrays to concatenate. TBD if there is an efficient way to test that.
Problem 2: take_array kernel doesn’t handle case of offset overflow
This is what Antoine was pointing out:
To solve this, I think we’d either have to:
(optionally?) promote arrays to Large variants of type. Problem is we’d need to do this cast consistently across chunks.
Switch to returning chunked arrays, and create new chunks as needed. (TBD: Could we do that in some cases (String, Binary, List types) and not others?)
Problem 3: there isn’t a take_array kernel that handles ChunkedArrays
Finally, for sorting chunked arrays of type string/binary/list (that is, the case for take where the indices are out-of-order), I think we need to implement kernels specialized for chunked arrays. IIUC, everything but string/binary/list types could simply do the concatenation we do now; it’s just those three types that need special logic to chunk as necessary to avoid offset overflows.
Hi! Issue 3 is bothering us a lot when sorting huge tables. Do we have any updates on this?