Skip to content

Commit 1264e40

Browse files
felipecrvzagto
andauthored
apacheGH-32104: [C++] Add support for Run-End encoded data to Arrow (apache#33641)
This PR gathers work from multiple PRs that can be closed after this one is merged: - Closes apache#13752 - Closes apache#13754 - Closes apache#13842 - Closes apache#13882 - Closes apache#13916 - Closes apache#14063 - Closes apache#13970 And the issues associated with those PRs can also be closed: - Fixes apache#20350 - Add RunEndEncodedScalarType - Fixes apache#32543 - Fixes apache#32544 - Fixes apache#32688 - Fixes apache#32731 - Fixes apache#32772 - Fixes apache#32774 * Closes: apache#32104 Lead-authored-by: Felipe Oliveira Carvalho <[email protected]> Co-authored-by: Tobias Zagorni <[email protected]> Signed-off-by: Matt Topol <[email protected]>
1 parent 157b8f5 commit 1264e40

46 files changed

Lines changed: 2814 additions & 13 deletions

Some content is hidden

Large Commits have some content hidden by default. Use the searchbox below for content that may be hidden.

‎cpp/src/arrow/CMakeLists.txt‎

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -142,11 +142,13 @@ set(ARROW_SRCS
142142
array/array_dict.cc
143143
array/array_nested.cc
144144
array/array_primitive.cc
145+
array/array_run_end.cc
145146
array/builder_adaptive.cc
146147
array/builder_base.cc
147148
array/builder_binary.cc
148149
array/builder_decimal.cc
149150
array/builder_dict.cc
151+
array/builder_run_end.cc
150152
array/builder_nested.cc
151153
array/builder_primitive.cc
152154
array/builder_union.cc
@@ -218,6 +220,7 @@ set(ARROW_SRCS
218220
util/key_value_metadata.cc
219221
util/memory.cc
220222
util/mutex.cc
223+
util/ree_util.cc
221224
util/string.cc
222225
util/string_builder.cc
223226
util/task_group.cc
@@ -746,6 +749,7 @@ add_arrow_test(array_test
746749
array/array_binary_test.cc
747750
array/array_dict_test.cc
748751
array/array_list_test.cc
752+
array/array_run_end_test.cc
749753
array/array_struct_test.cc
750754
array/array_union_test.cc
751755
array/array_view_test.cc

‎cpp/src/arrow/array.h‎

Lines changed: 5 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -34,11 +34,16 @@
3434
/// @{
3535
/// @}
3636

37+
/// \defgroup run-end-encoded-arrays Concrete classes for run-end encoded arrays
38+
/// @{
39+
/// @}
40+
3741
#include "arrow/array/array_base.h" // IWYU pragma: keep
3842
#include "arrow/array/array_binary.h" // IWYU pragma: keep
3943
#include "arrow/array/array_decimal.h" // IWYU pragma: keep
4044
#include "arrow/array/array_dict.h" // IWYU pragma: keep
4145
#include "arrow/array/array_nested.h" // IWYU pragma: keep
4246
#include "arrow/array/array_primitive.h" // IWYU pragma: keep
47+
#include "arrow/array/array_run_end.h" // IWYU pragma: keep
4348
#include "arrow/array/data.h" // IWYU pragma: keep
4449
#include "arrow/array/util.h" // IWYU pragma: keep

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

Lines changed: 11 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -39,6 +39,7 @@
3939
#include "arrow/type_fwd.h"
4040
#include "arrow/type_traits.h"
4141
#include "arrow/util/logging.h"
42+
#include "arrow/util/ree_util.h"
4243
#include "arrow/visit_array_inline.h"
4344
#include "arrow/visitor.h"
4445

@@ -143,6 +144,15 @@ struct ScalarFromArraySlotImpl {
143144
return Status::OK();
144145
}
145146

147+
Status Visit(const RunEndEncodedArray& a) {
148+
ArraySpan span{*a.data()};
149+
const int64_t physical_index = ree_util::FindPhysicalIndex(span, index_, span.offset);
150+
ScalarFromArraySlotImpl scalar_from_values(*a.values(), physical_index);
151+
ARROW_ASSIGN_OR_RAISE(auto value, std::move(scalar_from_values).Finish());
152+
out_ = std::make_shared<RunEndEncodedScalar>(std::move(value), a.type());
153+
return Status::OK();
154+
}
155+
146156
Status Visit(const ExtensionArray& a) {
147157
ARROW_ASSIGN_OR_RAISE(auto storage, a.storage()->GetScalar(index_));
148158
out_ = std::make_shared<ExtensionScalar>(std::move(storage), a.type());
@@ -165,7 +175,7 @@ struct ScalarFromArraySlotImpl {
165175
array_.length());
166176
}
167177

168-
if (array_.IsNull(index_)) {
178+
if (array_.type()->id() != Type::RUN_END_ENCODED && array_.IsNull(index_)) {
169179
auto null = MakeNullScalar(array_.type());
170180
if (is_dictionary(array_.type()->id())) {
171181
auto& dict_null = checked_cast<DictionaryScalar&>(*null);
Lines changed: 98 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,98 @@
1+
// Licensed to the Apache Software Foundation (ASF) under one
2+
// or more contributor license agreements. See the NOTICE file
3+
// distributed with this work for additional information
4+
// regarding copyright ownership. The ASF licenses this file
5+
// to you under the Apache License, Version 2.0 (the
6+
// "License"); you may not use this file except in compliance
7+
// with the License. You may obtain a copy of the License at
8+
//
9+
// http://www.apache.org/licenses/LICENSE-2.0
10+
//
11+
// Unless required by applicable law or agreed to in writing,
12+
// software distributed under the License is distributed on an
13+
// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
14+
// KIND, either express or implied. See the License for the
15+
// specific language governing permissions and limitations
16+
// under the License.
17+
18+
#include "arrow/array/array_run_end.h"
19+
#include "arrow/array/util.h"
20+
#include "arrow/util/logging.h"
21+
#include "arrow/util/ree_util.h"
22+
23+
namespace arrow {
24+
25+
// ----------------------------------------------------------------------
26+
// RunEndEncodedArray
27+
28+
RunEndEncodedArray::RunEndEncodedArray(const std::shared_ptr<ArrayData>& data) {
29+
this->SetData(data);
30+
}
31+
32+
RunEndEncodedArray::RunEndEncodedArray(const std::shared_ptr<DataType>& type,
33+
int64_t length,
34+
const std::shared_ptr<Array>& run_ends,
35+
const std::shared_ptr<Array>& values,
36+
int64_t offset) {
37+
this->SetData(ArrayData::Make(type, length,
38+
/*buffers=*/{NULLPTR},
39+
/*child_data=*/{run_ends->data(), values->data()},
40+
/*null_count=*/0, offset));
41+
}
42+
43+
Result<std::shared_ptr<RunEndEncodedArray>> RunEndEncodedArray::Make(
44+
int64_t logical_length, const std::shared_ptr<Array>& run_ends,
45+
const std::shared_ptr<Array>& values, int64_t logical_offset) {
46+
auto run_end_type = run_ends->type();
47+
auto values_type = values->type();
48+
if (!RunEndEncodedType::RunEndTypeValid(*run_end_type)) {
49+
return Status::Invalid("Run end type must be int16, int32 or int64");
50+
}
51+
if (run_ends->null_count() != 0) {
52+
return Status::Invalid("Run ends array cannot contain null values");
53+
}
54+
if (values->length() < run_ends->length()) {
55+
return Status::Invalid("Values array has to be at least as long as run ends array");
56+
}
57+
58+
return std::make_shared<RunEndEncodedArray>(
59+
run_end_encoded(std::move(run_end_type), std::move(values_type)), logical_length,
60+
run_ends, values, logical_offset);
61+
}
62+
63+
void RunEndEncodedArray::SetData(const std::shared_ptr<ArrayData>& data) {
64+
ARROW_CHECK_EQ(data->type->id(), Type::RUN_END_ENCODED);
65+
const auto* ree_type =
66+
internal::checked_cast<const RunEndEncodedType*>(data->type.get());
67+
ARROW_CHECK_EQ(ree_type->run_end_type()->id(), data->child_data[0]->type->id());
68+
ARROW_CHECK_EQ(ree_type->value_type()->id(), data->child_data[1]->type->id());
69+
70+
DCHECK_EQ(data->child_data.size(), 2);
71+
72+
// A non-zero number of logical values in this array (offset + length) implies
73+
// a non-zero number of runs and values.
74+
DCHECK(data->offset + data->length == 0 || data->child_data[0]->length > 0);
75+
DCHECK(data->offset + data->length == 0 || data->child_data[1]->length > 0);
76+
// At least as many values as run_ends
77+
DCHECK_GE(data->child_data[1]->length, data->child_data[0]->length);
78+
79+
// The null count for run-end encoded arrays is always 0. Actual number of
80+
// nulls needs to be calculated through other means.
81+
DCHECK_EQ(data->null_count, 0);
82+
83+
Array::SetData(data);
84+
run_ends_array_ = MakeArray(this->data()->child_data[0]);
85+
values_array_ = MakeArray(this->data()->child_data[1]);
86+
}
87+
88+
int64_t RunEndEncodedArray::FindPhysicalOffset() const {
89+
const ArraySpan span(*this->data_);
90+
return ree_util::FindPhysicalIndex(span, 0, span.offset);
91+
}
92+
93+
int64_t RunEndEncodedArray::FindPhysicalLength() const {
94+
const ArraySpan span(*this->data_);
95+
return ree_util::FindPhysicalLength(span);
96+
}
97+
98+
} // namespace arrow
Lines changed: 109 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,109 @@
1+
// Licensed to the Apache Software Foundation (ASF) under one
2+
// or more contributor license agreements. See the NOTICE file
3+
// distributed with this work for additional information
4+
// regarding copyright ownership. The ASF licenses this file
5+
// to you under the Apache License, Version 2.0 (the
6+
// "License"); you may not use this file except in compliance
7+
// with the License. You may obtain a copy of the License at
8+
//
9+
// http://www.apache.org/licenses/LICENSE-2.0
10+
//
11+
// Unless required by applicable law or agreed to in writing,
12+
// software distributed under the License is distributed on an
13+
// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
14+
// KIND, either express or implied. See the License for the
15+
// specific language governing permissions and limitations
16+
// under the License.
17+
18+
// Array accessor classes run-end encoded arrays
19+
20+
#pragma once
21+
22+
#include <cstdint>
23+
#include <memory>
24+
#include <string>
25+
#include <utility>
26+
#include <vector>
27+
28+
#include "arrow/array/array_base.h"
29+
#include "arrow/array/data.h"
30+
#include "arrow/result.h"
31+
#include "arrow/status.h"
32+
#include "arrow/type.h"
33+
#include "arrow/type_fwd.h"
34+
#include "arrow/util/checked_cast.h"
35+
#include "arrow/util/macros.h"
36+
#include "arrow/util/visibility.h"
37+
38+
namespace arrow {
39+
40+
/// \addtogroup run-end-encoded-arrays
41+
///
42+
/// @{
43+
44+
// ----------------------------------------------------------------------
45+
// RunEndEncoded
46+
47+
/// \brief Array type for run-end encoded data
48+
class ARROW_EXPORT RunEndEncodedArray : public Array {
49+
private:
50+
std::shared_ptr<Array> run_ends_array_;
51+
std::shared_ptr<Array> values_array_;
52+
53+
public:
54+
using TypeClass = RunEndEncodedType;
55+
56+
explicit RunEndEncodedArray(const std::shared_ptr<ArrayData>& data);
57+
58+
/// \brief Construct a RunEndEncodedArray from all parameters
59+
///
60+
/// The length and offset parameters refer to the dimensions of the logical
61+
/// array which is the array we would get after expanding all the runs into
62+
/// repeated values. As such, length can be much greater than the lenght of
63+
/// the child run_ends and values arrays.
64+
RunEndEncodedArray(const std::shared_ptr<DataType>& type, int64_t length,
65+
const std::shared_ptr<Array>& run_ends,
66+
const std::shared_ptr<Array>& values, int64_t offset = 0);
67+
68+
/// \brief Construct a RunEndEncodedArray from values and run ends arrays
69+
///
70+
/// The data type is automatically inferred from the arguments.
71+
/// The run_ends and values arrays must have the same length.
72+
static Result<std::shared_ptr<RunEndEncodedArray>> Make(
73+
int64_t logical_length, const std::shared_ptr<Array>& run_ends,
74+
const std::shared_ptr<Array>& values, int64_t logical_offset = 0);
75+
76+
protected:
77+
void SetData(const std::shared_ptr<ArrayData>& data);
78+
79+
public:
80+
/// \brief Returns an array holding the logical indexes of each run-end
81+
///
82+
/// The physical offset to the array is applied.
83+
const std::shared_ptr<Array>& run_ends() const { return run_ends_array_; }
84+
85+
/// \brief Returns an array holding the values of each run
86+
///
87+
/// The physical offset to the array is applied.
88+
const std::shared_ptr<Array>& values() const { return values_array_; }
89+
90+
/// \brief Find the physical offset of this REE array
91+
///
92+
/// This function uses binary-search, so it has a O(log N) cost.
93+
int64_t FindPhysicalOffset() const;
94+
95+
/// \brief Find the physical length of this REE array
96+
///
97+
/// The physical length of an REE is the number of physical values (and
98+
/// run-ends) necessary to represent the logical range of values from offset
99+
/// to length.
100+
///
101+
/// Avoid calling this function if the physical length can be estabilished in
102+
/// some other way (e.g. when iterating over the runs sequentially until the
103+
/// end). This function uses binary-search, so it has a O(log N) cost.
104+
int64_t FindPhysicalLength() const;
105+
};
106+
107+
/// @}
108+
109+
} // namespace arrow

0 commit comments

Comments
 (0)