Skip to content

Commit 3df5ba8

Browse files
authored
GH-34561: [C++] Implement RunEndEncodedBuilder::AppendEmptyValues() (#34562)
* Closes: #34561 Authored-by: Felipe Oliveira Carvalho <[email protected]> Signed-off-by: Matt Topol <[email protected]>
1 parent 8ea3769 commit 3df5ba8

3 files changed

Lines changed: 59 additions & 16 deletions

File tree

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

Lines changed: 23 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -301,22 +301,40 @@ TEST_P(TestRunEndEncodedArray, Builder) {
301301
R"(["unique", null, "common", "common", "appended", "common", "common", "appended"])"));
302302
continue;
303303
}
304-
if (step == 10) {
305-
ASSERT_EQ(builder->length(), 505);
304+
// Append empty values
305+
ASSERT_OK(builder->AppendEmptyValues(10));
306+
if (step == 11) {
307+
ASSERT_EQ(builder->length(), 515);
308+
ASSERT_OK(BuilderEquals(
309+
*builder, 515, "[1, 3, 105, 165, 205, 305, 405, 505, 515]",
310+
R"(["unique", null, "common", "common", "appended", "common", "common", "appended", ""])"));
311+
continue;
312+
}
313+
// Append NULL after empty
314+
ASSERT_OK(builder->AppendNull());
315+
if (step == 12) {
316+
ASSERT_EQ(builder->length(), 516);
317+
ASSERT_OK(BuilderEquals(
318+
*builder, 516, "[1, 3, 105, 165, 205, 305, 405, 505, 515, 516]",
319+
R"(["unique", null, "common", "common", "appended", "common", "common", "appended", "", null])"));
320+
continue;
321+
}
322+
if (step == 13) {
323+
ASSERT_EQ(builder->length(), 516);
306324
ASSERT_EQ(*builder->type(), *run_end_encoded(run_end_type, utf8()));
307325

308326
auto expected_run_ends =
309-
ArrayFromJSON(run_end_type, "[1, 3, 105, 165, 205, 305, 405, 505]");
327+
ArrayFromJSON(run_end_type, "[1, 3, 105, 165, 205, 305, 405, 505, 515, 516]");
310328
auto expected_values = ArrayFromJSON(
311329
value_type,
312-
R"(["unique", null, "common", "common", "appended", "common", "common", "appended"])");
330+
R"(["unique", null, "common", "common", "appended", "common", "common", "appended", "", null])");
313331

314332
ASSERT_OK_AND_ASSIGN(auto array, builder->Finish());
315333
auto ree_array = std::dynamic_pointer_cast<RunEndEncodedArray>(array);
316334
ASSERT_NE(ree_array, NULLPTR);
317335
ASSERT_ARRAYS_EQUAL(*expected_run_ends, *ree_array->run_ends());
318336
ASSERT_ARRAYS_EQUAL(*expected_values, *ree_array->values());
319-
ASSERT_EQ(array->length(), 505);
337+
ASSERT_EQ(array->length(), 516);
320338
ASSERT_EQ(array->offset(), 0);
321339
break;
322340
}

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

Lines changed: 20 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -76,7 +76,21 @@ Status RunCompressorBuilder::AppendNulls(int64_t length) {
7676
}
7777

7878
Status RunCompressorBuilder::AppendEmptyValues(int64_t length) {
79-
return Status::NotImplemented("Append empty values to a run-compressed array.");
79+
if (ARROW_PREDICT_FALSE(length == 0)) {
80+
return Status::OK();
81+
}
82+
// Empty values are usually appended as placeholders for future values, so
83+
// we make no attempt at making the empty values appended now part of the
84+
// current run. Each AppendEmptyValues() creates its own run of the given length.
85+
ARROW_RETURN_NOT_OK(FinishCurrentRun());
86+
{
87+
ARROW_RETURN_NOT_OK(WillCloseRunOfEmptyValues(length));
88+
ARROW_RETURN_NOT_OK(inner_builder_->AppendEmptyValue());
89+
UpdateDimensions();
90+
}
91+
// Current run remains cleared after FinishCurrentRun() as we don't want to
92+
// extend it with empty values potentially coming in the future.
93+
return Status::OK();
8094
}
8195

8296
Status RunCompressorBuilder::AppendScalar(const Scalar& scalar, int64_t n_repeats) {
@@ -183,7 +197,10 @@ Status RunEndEncodedBuilder::AppendNulls(int64_t length) {
183197
}
184198

185199
Status RunEndEncodedBuilder::AppendEmptyValues(int64_t length) {
186-
return Status::NotImplemented("Append empty values to run-end encoded array.");
200+
RETURN_NOT_OK(value_run_builder_->AppendEmptyValues(length));
201+
DCHECK_EQ(value_run_builder_->open_run_length(), 0);
202+
UpdateDimensions(committed_logical_length_, 0);
203+
return Status::OK();
187204
}
188205

189206
Status RunEndEncodedBuilder::AppendScalar(const Scalar& scalar, int64_t n_repeats) {
@@ -313,8 +330,7 @@ Status RunEndEncodedBuilder::AppendRunEnd(int64_t run_end) {
313330
return Status::OK();
314331
}
315332

316-
Status RunEndEncodedBuilder::CloseRun(const std::shared_ptr<const Scalar>& value,
317-
int64_t run_length) {
333+
Status RunEndEncodedBuilder::CloseRun(int64_t run_length) {
318334
// TODO(felipecrv): gracefully fragment runs bigger than INT32_MAX
319335
if (ARROW_PREDICT_FALSE(run_length > std::numeric_limits<int32_t>::max())) {
320336
return Status::Invalid(

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

Lines changed: 16 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -79,6 +79,15 @@ class RunCompressorBuilder : public ArrayBuilder {
7979
return Status::OK();
8080
}
8181

82+
/// \brief Called right before a run of empty values is being closed
83+
///
84+
/// Subclasses can override this function to perform an additional action when
85+
/// a run of empty values is appended (i.e. run-length is known and a single
86+
/// empty value is appended to the inner builder).
87+
///
88+
/// \param length the greater than 0 length of the value run being closed
89+
virtual Status WillCloseRunOfEmptyValues(int64_t length) { return Status::OK(); }
90+
8291
/// \brief Allocate enough memory for a given number of array elements.
8392
///
8493
/// NOTE: Conservatively resizing a run-length compressed array for a given
@@ -103,8 +112,6 @@ class RunCompressorBuilder : public ArrayBuilder {
103112
Status AppendNull() final { return AppendNulls(1); }
104113
Status AppendNulls(int64_t length) override;
105114

106-
// These two fail with Status::NotImplemented as it is impossible to compress
107-
// unknown placeholder values.
108115
Status AppendEmptyValue() final { return AppendEmptyValues(1); }
109116
Status AppendEmptyValues(int64_t length) override;
110117

@@ -179,9 +186,12 @@ class ARROW_EXPORT RunEndEncodedBuilder : public ArrayBuilder {
179186

180187
~ValueRunBuilder() override = default;
181188

182-
Status WillCloseRun(const std::shared_ptr<const Scalar>& value,
183-
int64_t length) override {
184-
return ree_builder_.CloseRun(value, length);
189+
Status WillCloseRun(const std::shared_ptr<const Scalar>&, int64_t length) override {
190+
return ree_builder_.CloseRun(length);
191+
}
192+
193+
Status WillCloseRunOfEmptyValues(int64_t length) override {
194+
return ree_builder_.CloseRun(length);
185195
}
186196

187197
private:
@@ -276,8 +286,7 @@ class ARROW_EXPORT RunEndEncodedBuilder : public ArrayBuilder {
276286
/// length_ to reflect the new run.
277287
///
278288
/// Pre-condition: run_length > 0.
279-
[[nodiscard]] Status CloseRun(const std::shared_ptr<const Scalar>& value,
280-
int64_t run_length);
289+
[[nodiscard]] Status CloseRun(int64_t run_length);
281290

282291
ArrayBuilder& run_end_builder();
283292
ArrayBuilder& value_builder();

0 commit comments

Comments
 (0)