Skip to content

Commit 8ea3769

Browse files
felipecrvzagto
andauthored
GH-32338: [C++] Add IPC support for Run-End Encoded Arrays (#34550)
* Closes #14340 * Closes #32773 * Closes #14179 * Closes: #32338 Lead-authored-by: Felipe Oliveira Carvalho <[email protected]> Co-authored-by: Tobias Zagorni <[email protected]> Signed-off-by: Matt Topol <[email protected]>
1 parent 8732b27 commit 8ea3769

15 files changed

Lines changed: 348 additions & 14 deletions

‎cpp/src/arrow/array/array_run_end.cc‎

Lines changed: 78 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -16,6 +16,7 @@
1616
// under the License.
1717

1818
#include "arrow/array/array_run_end.h"
19+
#include "arrow/array/builder_primitive.h"
1920
#include "arrow/array/util.h"
2021
#include "arrow/util/logging.h"
2122
#include "arrow/util/ree_util.h"
@@ -85,6 +86,83 @@ void RunEndEncodedArray::SetData(const std::shared_ptr<ArrayData>& data) {
8586
values_array_ = MakeArray(this->data()->child_data[1]);
8687
}
8788

89+
namespace {
90+
91+
template <typename RunEndType>
92+
Result<std::shared_ptr<Array>> MakeLogicalRunEnds(const RunEndEncodedArray& self,
93+
MemoryPool* pool) {
94+
using RunEndCType = typename RunEndType::c_type;
95+
if (self.offset() == 0) {
96+
const auto& run_ends = *self.run_ends();
97+
if (self.length() == 0) {
98+
return run_ends.Slice(0, 0);
99+
}
100+
101+
// If offset==0 and the non-zero logical length aligns perfectly with a
102+
// physical run-end, we can return a slice of the run-ends array.
103+
const int64_t physical_length = self.FindPhysicalLength();
104+
const auto* run_end_values = self.data()->child_data[0]->GetValues<RunEndCType>(1);
105+
if (run_end_values[physical_length - 1] == self.length()) {
106+
return run_ends.Slice(0, physical_length);
107+
}
108+
109+
// Otherwise we need to copy the run-ends array and adjust only the very
110+
// last run-end.
111+
auto new_run_ends_data = ArrayData::Make(run_ends.type(), physical_length, 0, 0);
112+
{
113+
ARROW_ASSIGN_OR_RAISE(auto buffer,
114+
AllocateBuffer(physical_length * sizeof(RunEndCType), pool));
115+
new_run_ends_data->buffers = {NULLPTR, std::move(buffer)};
116+
}
117+
auto* new_run_end_values = new_run_ends_data->GetMutableValues<RunEndCType>(1);
118+
memcpy(new_run_end_values, run_end_values,
119+
(physical_length - 1) * sizeof(RunEndCType));
120+
new_run_end_values[physical_length - 1] = static_cast<RunEndCType>(self.length());
121+
return MakeArray(std::move(new_run_ends_data));
122+
}
123+
124+
// When the logical offset is non-zero, all run-end values need to be adjusted.
125+
int64_t physical_offset = self.FindPhysicalOffset();
126+
int64_t physical_length = self.FindPhysicalLength();
127+
128+
const auto* run_end_values = self.data()->child_data[0]->GetValues<RunEndCType>(1);
129+
NumericBuilder<RunEndType> builder(pool);
130+
RETURN_NOT_OK(builder.Resize(physical_length));
131+
if (physical_length > 0) {
132+
for (int64_t i = 0; i < physical_length - 1; i++) {
133+
const auto run_end = run_end_values[physical_offset + i] - self.offset();
134+
DCHECK_LT(run_end, self.length());
135+
RETURN_NOT_OK(builder.Append(static_cast<RunEndCType>(run_end)));
136+
}
137+
DCHECK_GE(run_end_values[physical_offset + physical_length - 1] - self.offset(),
138+
self.length());
139+
RETURN_NOT_OK(builder.Append(static_cast<RunEndCType>(self.length())));
140+
}
141+
return builder.Finish();
142+
}
143+
144+
} // namespace
145+
146+
Result<std::shared_ptr<Array>> RunEndEncodedArray::LogicalRunEnds(
147+
MemoryPool* pool) const {
148+
DCHECK(data()->child_data[0]->buffers[1]->is_cpu());
149+
switch (run_ends_array_->type_id()) {
150+
case Type::INT16:
151+
return MakeLogicalRunEnds<Int16Type>(*this, pool);
152+
case Type::INT32:
153+
return MakeLogicalRunEnds<Int32Type>(*this, pool);
154+
default:
155+
DCHECK_EQ(run_ends_array_->type_id(), Type::INT64);
156+
return MakeLogicalRunEnds<Int64Type>(*this, pool);
157+
}
158+
}
159+
160+
std::shared_ptr<Array> RunEndEncodedArray::LogicalValues() const {
161+
const int64_t physical_offset = FindPhysicalOffset();
162+
const int64_t physical_length = FindPhysicalLength();
163+
return MakeArray(data()->child_data[1]->Slice(physical_offset, physical_length));
164+
}
165+
88166
int64_t RunEndEncodedArray::FindPhysicalOffset() const {
89167
const ArraySpan span(*this->data_);
90168
return ree_util::FindPhysicalIndex(span, 0, span.offset);

‎cpp/src/arrow/array/array_run_end.h‎

Lines changed: 13 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -87,6 +87,19 @@ class ARROW_EXPORT RunEndEncodedArray : public Array {
8787
/// The physical offset to the array is applied.
8888
const std::shared_ptr<Array>& values() const { return values_array_; }
8989

90+
/// \brief Returns an array holding the logical indexes of each run end
91+
///
92+
/// If a non-zero logical offset is set, this function allocates a new
93+
/// array and rewrites all the run end values to be relative to the logical
94+
/// offset and cuts the end of the array to the logical length.
95+
Result<std::shared_ptr<Array>> LogicalRunEnds(MemoryPool* pool) const;
96+
97+
/// \brief Returns an array holding the values of each run
98+
///
99+
/// If a non-zero logical offset is set, this function allocates a new
100+
/// array containing only the values within the logical range.
101+
std::shared_ptr<Array> LogicalValues() const;
102+
90103
/// \brief Find the physical offset of this REE array
91104
///
92105
/// This function uses binary-search, so it has a O(log N) cost.

‎cpp/src/arrow/array/array_run_end_test.cc‎

Lines changed: 49 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -153,6 +153,55 @@ TEST_P(TestRunEndEncodedArray, FindOffsetAndLength) {
153153
ASSERT_EQ(zero_length_at_end->FindPhysicalLength(), 0);
154154
}
155155

156+
TEST_P(TestRunEndEncodedArray, LogicalRunEnds) {
157+
auto run_ends = ArrayFromJSON(run_end_type, "[100, 200, 300, 400, 500]");
158+
auto values = ArrayFromJSON(utf8(), R"(["Hello", "beautiful", "world", "of", "REE"])");
159+
ASSERT_OK_AND_ASSIGN(auto ree_array, RunEndEncodedArray::Make(500, run_ends, values));
160+
161+
auto* pool = default_memory_pool();
162+
ASSERT_OK_AND_ASSIGN(auto logical_run_ends, ree_array->LogicalRunEnds(pool));
163+
ASSERT_ARRAYS_EQUAL(*logical_run_ends, *run_ends);
164+
165+
// offset=0, length=0
166+
auto slice = ree_array->Slice(0, 0);
167+
auto ree_slice = checked_cast<const RunEndEncodedArray*>(slice.get());
168+
ASSERT_OK_AND_ASSIGN(logical_run_ends, ree_slice->LogicalRunEnds(pool));
169+
ASSERT_ARRAYS_EQUAL(*logical_run_ends, *ArrayFromJSON(run_end_type, "[]"));
170+
171+
// offset=0, length=<a run-end>
172+
for (int i = 1; i < 5; i++) {
173+
auto expected_run_ends = run_ends->Slice(0, i);
174+
slice = ree_array->Slice(0, i * 100);
175+
ree_slice = checked_cast<const RunEndEncodedArray*>(slice.get());
176+
ASSERT_OK_AND_ASSIGN(logical_run_ends, ree_slice->LogicalRunEnds(pool));
177+
ASSERT_ARRAYS_EQUAL(*logical_run_ends, *expected_run_ends);
178+
}
179+
180+
// offset=0, length=<length in the middle of a run>
181+
for (int i = 2; i < 5; i++) {
182+
std::shared_ptr<Array> expected_run_ends;
183+
{
184+
std::string expected_run_ends_json = "[100";
185+
for (int j = 2; j < i; j++) {
186+
expected_run_ends_json += ", " + std::to_string(j * 100);
187+
}
188+
expected_run_ends_json += ", " + std::to_string(i * 100 - 50) + "]";
189+
expected_run_ends = ArrayFromJSON(run_end_type, expected_run_ends_json);
190+
}
191+
slice = ree_array->Slice(0, i * 100 - 50);
192+
ree_slice = checked_cast<const RunEndEncodedArray*>(slice.get());
193+
ASSERT_OK_AND_ASSIGN(logical_run_ends, ree_slice->LogicalRunEnds(pool));
194+
ASSERT_ARRAYS_EQUAL(*logical_run_ends, *expected_run_ends);
195+
}
196+
197+
// offset != 0
198+
slice = ree_array->Slice(50, 400);
199+
ree_slice = checked_cast<const RunEndEncodedArray*>(slice.get());
200+
const auto expected_run_ends = ArrayFromJSON(run_end_type, "[50, 150, 250, 350, 400]");
201+
ASSERT_OK_AND_ASSIGN(logical_run_ends, ree_slice->LogicalRunEnds(pool));
202+
ASSERT_ARRAYS_EQUAL(*logical_run_ends, *expected_run_ends);
203+
}
204+
156205
TEST_P(TestRunEndEncodedArray, Builder) {
157206
auto value_type = utf8();
158207
auto ree_type = run_end_encoded(run_end_type, value_type);

‎cpp/src/arrow/ipc/feather_test.cc‎

Lines changed: 2 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -345,7 +345,8 @@ const std::vector<test::MakeRecordBatch*> kBatchCases = {
345345
&ipc::test::MakeDecimal,
346346
&ipc::test::MakeBooleanBatch,
347347
&ipc::test::MakeFloatBatch,
348-
&ipc::test::MakeIntervals};
348+
&ipc::test::MakeIntervals,
349+
&ipc::test::MakeRunEndEncoded};
349350

350351
} // namespace
351352

‎cpp/src/arrow/ipc/metadata_internal.cc‎

Lines changed: 16 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -386,8 +386,19 @@ Status ConcreteTypeFromFlatbuffer(flatbuf::Type type, const void* type_data,
386386
case flatbuf::Type::Union:
387387
return UnionFromFlatbuffer(static_cast<const flatbuf::Union*>(type_data), children,
388388
out);
389+
case flatbuf::Type::RunEndEncoded:
390+
if (children.size() != 2) {
391+
return Status::Invalid("RunEndEncoded must have exactly 2 child fields");
392+
}
393+
if (!is_run_end_type(children[0]->type()->id())) {
394+
return Status::Invalid(
395+
"RunEndEncoded run_ends field must be typed as: int16, int32, or int64");
396+
}
397+
*out =
398+
std::make_shared<RunEndEncodedType>(children[0]->type(), children[1]->type());
399+
return Status::OK();
389400
default:
390-
return Status::Invalid("Unrecognized type:" + ToChars(static_cast<int>(type)));
401+
return Status::Invalid("Unrecognized type: " + ToChars(static_cast<int>(type)));
391402
}
392403
}
393404

@@ -691,7 +702,10 @@ class FieldToFlatbufferVisitor {
691702
}
692703

693704
Status Visit(const RunEndEncodedType& type) {
694-
return Status::NotImplemented("run-end encoded type in IPC");
705+
fb_type_ = flatbuf::Type::RunEndEncoded;
706+
RETURN_NOT_OK(VisitChildFields(type));
707+
type_offset_ = flatbuf::CreateRunEndEncoded(fbb_).Union();
708+
return Status::OK();
695709
}
696710

697711
Status Visit(const ExtensionType& type) {

‎cpp/src/arrow/ipc/reader.cc‎

Lines changed: 3 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -422,7 +422,9 @@ class ArrayLoader {
422422
}
423423

424424
Status Visit(const RunEndEncodedType& type) {
425-
return Status::NotImplemented("run-end encoded array in IPC");
425+
out_->buffers.resize(1);
426+
RETURN_NOT_OK(LoadCommon(type.id()));
427+
return LoadChildren(type.fields());
426428
}
427429

428430
Status Visit(const ExtensionType& type) { return LoadType(*type.storage_type()); }

‎cpp/src/arrow/ipc/test_common.cc‎

Lines changed: 53 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -44,7 +44,9 @@
4444
#include "arrow/util/bit_util.h"
4545
#include "arrow/util/bitmap_builders.h"
4646
#include "arrow/util/checked_cast.h"
47+
#include "arrow/util/key_value_metadata.h"
4748
#include "arrow/util/logging.h"
49+
#include "arrow/util/ree_util.h"
4850

4951
namespace arrow {
5052

@@ -539,6 +541,57 @@ Status MakeStruct(std::shared_ptr<RecordBatch>* out) {
539541
return Status::OK();
540542
}
541543

544+
Status AddArtificialOffsetInChildArray(ArrayData* array, int64_t offset) {
545+
auto& child = array->child_data[1];
546+
auto builder = MakeBuilder(child->type).ValueOrDie();
547+
ARROW_RETURN_NOT_OK(builder->AppendNulls(offset));
548+
ARROW_RETURN_NOT_OK(builder->AppendArraySlice(ArraySpan(*child), 0, child->length));
549+
array->child_data[1] = builder->Finish().ValueOrDie()->Slice(offset)->data();
550+
return Status::OK();
551+
}
552+
553+
Status MakeRunEndEncoded(std::shared_ptr<RecordBatch>* out) {
554+
const int64_t logical_length = 10000;
555+
const int64_t slice_offset = 2000;
556+
random::RandomArrayGenerator rand(/*seed =*/1);
557+
std::vector<std::shared_ptr<Array>> all_arrays;
558+
std::vector<std::shared_ptr<Field>> all_fields;
559+
for (const bool sliced : {false, true}) {
560+
const int64_t generate_length =
561+
sliced ? logical_length + 2 * slice_offset : logical_length;
562+
563+
std::vector<std::shared_ptr<Array>> arrays = {
564+
rand.RunEndEncoded(int32(), generate_length, 0.5),
565+
rand.RunEndEncoded(int32(), generate_length, 0),
566+
rand.RunEndEncoded(utf8(), generate_length, 0.5),
567+
rand.RunEndEncoded(list(int32()), generate_length, 0.5),
568+
};
569+
std::vector<std::shared_ptr<Field>> fields = {
570+
field("ree_int32", run_end_encoded(int32(), int32())),
571+
field("ree_int32_not_null", run_end_encoded(int32(), int32()), false),
572+
field("ree_string", run_end_encoded(int32(), utf8())),
573+
field("ree_list", run_end_encoded(int32(), list(int32()))),
574+
};
575+
576+
if (sliced) {
577+
for (auto& array : arrays) {
578+
ARROW_RETURN_NOT_OK(
579+
AddArtificialOffsetInChildArray(array->data().get(), slice_offset));
580+
array = array->Slice(slice_offset, logical_length);
581+
}
582+
for (auto& item : fields) {
583+
item = field(item->name() + "_sliced", item->type(), item->nullable(),
584+
item->metadata());
585+
}
586+
}
587+
588+
all_arrays.insert(all_arrays.end(), arrays.begin(), arrays.end());
589+
all_fields.insert(all_fields.end(), fields.begin(), fields.end());
590+
}
591+
*out = RecordBatch::Make(schema(all_fields), logical_length, all_arrays);
592+
return Status::OK();
593+
}
594+
542595
Status MakeUnion(std::shared_ptr<RecordBatch>* out) {
543596
// Define schema
544597
std::vector<std::shared_ptr<Field>> union_fields(

‎cpp/src/arrow/ipc/test_common.h‎

Lines changed: 3 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -122,6 +122,9 @@ Status MakeDeeplyNestedList(std::shared_ptr<RecordBatch>* out);
122122
ARROW_TESTING_EXPORT
123123
Status MakeStruct(std::shared_ptr<RecordBatch>* out);
124124

125+
ARROW_TESTING_EXPORT
126+
Status MakeRunEndEncoded(std::shared_ptr<RecordBatch>* out);
127+
125128
ARROW_TESTING_EXPORT
126129
Status MakeUnion(std::shared_ptr<RecordBatch>* out);
127130

‎cpp/src/arrow/ipc/writer.cc‎

Lines changed: 12 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -522,8 +522,18 @@ class RecordBatchSerializer {
522522
return VisitType(*array.indices());
523523
}
524524

525-
Status Visit(const RunEndEncodedArray& type) {
526-
return Status::NotImplemented("run-end encoded array in IPC");
525+
Status Visit(const RunEndEncodedArray& array) {
526+
// NOTE: LogicalRunEnds() copies the whole run ends array to add an offset and
527+
// clip the ends. To improve performance (by avoiding the extra allocation
528+
// and memory writes) we could fuse this process with serialization.
529+
ARROW_ASSIGN_OR_RAISE(const auto run_ends,
530+
array.LogicalRunEnds(options_.memory_pool));
531+
const auto values = array.LogicalValues();
532+
--max_recursion_depth_;
533+
RETURN_NOT_OK(VisitArray(*run_ends));
534+
RETURN_NOT_OK(VisitArray(*values));
535+
++max_recursion_depth_;
536+
return Status::OK();
527537
}
528538

529539
Status Visit(const ExtensionArray& array) { return VisitType(*array.storage()); }

‎cpp/src/arrow/testing/json_integration_test.cc‎

Lines changed: 14 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -748,8 +748,9 @@ void TestSchemaRoundTrip(const Schema& schema) {
748748

749749
DictionaryMemo in_memo;
750750
std::shared_ptr<Schema> out;
751-
if (!json::ReadSchema(d, default_memory_pool(), &in_memo, &out).ok()) {
752-
FAIL() << "Unable to read JSON schema: " << json_schema;
751+
const auto status = json::ReadSchema(d, default_memory_pool(), &in_memo, &out);
752+
if (!status.ok()) {
753+
FAIL() << "Unable to read JSON schema: " << json_schema << "\nStatus: " << status;
753754
}
754755

755756
if (!schema.Equals(*out)) {
@@ -830,6 +831,9 @@ TEST(TestJsonSchemaWriter, FlatTypes) {
830831
{0, 1})),
831832
field("f19", large_list(uint8())),
832833
field("f20", null()),
834+
field("f21", run_end_encoded(int16(), utf8())),
835+
field("f22", run_end_encoded(int32(), utf8())),
836+
field("f23", run_end_encoded(int64(), utf8())),
833837
};
834838

835839
Schema schema(fields);
@@ -923,6 +927,14 @@ TEST(TestJsonArrayWriter, NestedTypes) {
923927
StructArray struct_array(struct_type, static_cast<int>(struct_is_valid.size()), fields,
924928
struct_bitmap, 2);
925929
TestArrayRoundTrip(struct_array);
930+
931+
// Run-End Encoded Type
932+
auto run_ends = ArrayFromJSON(int32(), "[100, 200, 300, 400, 500, 600, 700]");
933+
ASSERT_OK_AND_ASSIGN(auto ree_array,
934+
RunEndEncodedArray::Make(700, run_ends, i16_values_array));
935+
TestArrayRoundTrip(*ree_array);
936+
auto sliced_ree_array = ree_array->Slice(150, 300);
937+
TestArrayRoundTrip(*sliced_ree_array);
926938
}
927939

928940
TEST(TestJsonArrayWriter, Unions) {

0 commit comments

Comments
 (0)