You are viewing a plain text version of this content. The canonical link for it is here.
Posted to github@arrow.apache.org by "js8544 (via GitHub)" <gi...@apache.org> on 2023/07/27 08:50:50 UTC
[GitHub] [arrow] js8544 opened a new pull request, #36906: GH-36905: [C++] Add support for SparseUnion to selection functions
js8544 opened a new pull request, #36906:
URL: https://github.com/apache/arrow/pull/36906
<!--
Thanks for opening a pull request!
If this is your first pull request you can find detailed information on how
to contribute here:
* [New Contributor's Guide](https://arrow.apache.org/docs/dev/developers/guide/step_by_step/pr_lifecycle.html#reviews-and-merge-of-the-pull-request)
* [Contributing Overview](https://arrow.apache.org/docs/dev/developers/overview.html)
If this is not a [minor PR](https://github.com/apache/arrow/blob/main/CONTRIBUTING.md#Minor-Fixes). Could you open an issue for this pull request on GitHub? https://github.com/apache/arrow/issues/new/choose
Opening GitHub issues ahead of time contributes to the [Openness](http://theapacheway.com/open/#:~:text=Openness%20allows%20new%20users%20the,must%20happen%20in%20the%20open.) of the Apache Arrow project.
Then could you also rename the pull request title in the following format?
GH-${GITHUB_ISSUE_ID}: [${COMPONENT}] ${SUMMARY}
or
MINOR: [${COMPONENT}] ${SUMMARY}
In the case of PARQUET issues on JIRA the title also supports:
PARQUET-${JIRA_ISSUE_ID}: [${COMPONENT}] ${SUMMARY}
-->
### Rationale for this change
<!--
Why are you proposing this change? If this is already explained clearly in the issue then this section is not needed.
Explaining clearly why changes are proposed helps reviewers understand your changes and offer better suggestions for fixes.
-->
Dense unions are already supported in Take, Filter and DropNull but sparse ones are not.
### What changes are included in this PR?
<!--
There is no need to duplicate the description in the issue here but it is sometimes worth providing a summary of the individual changes in this PR.
-->
Add kernels for sparse unions to those functions.
### Are these changes tested?
<!--
We typically require tests for all PRs in order to:
1. Prevent the code from being accidentally broken by subsequent changes
2. Serve as another way to document the expected behavior of the code
If tests are not included in your PR, please explain why (for example, are they covered by existing tests)?
-->
Yes.
### Are there any user-facing changes?
No.
<!--
If there are user-facing changes then we may require documentation to be updated before approving the PR.
-->
<!--
If there are any breaking changes to public APIs, please uncomment the line below and explain which changes are breaking.
-->
<!-- **This PR includes breaking changes to public APIs.** -->
<!--
Please uncomment the line below (and provide explanation) if the changes fix either (a) a security vulnerability, (b) a bug that caused incorrect or invalid data to be produced, or (c) a bug that causes a crash (even when the API contract is upheld). We use this to highlight fixes to issues that may affect users without their knowledge. For this reason, fixing bugs that cause errors don't count, since those are usually obvious.
-->
<!-- **This PR contains a "Critical Fix".** -->
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [arrow] js8544 commented on a diff in pull request #36906: GH-36905: [C++] Add support for SparseUnion to selection functions
Posted by "js8544 (via GitHub)" <gi...@apache.org>.
js8544 commented on code in PR #36906:
URL: https://github.com/apache/arrow/pull/36906#discussion_r1288803219
##########
docs/source/cpp/compute.rst:
##########
@@ -1680,28 +1680,26 @@ These functions select and return a subset of their input.
+---------------+--------+--------------+--------------+--------------+-------------------------+-----------+
| Function name | Arity | Input type 1 | Input type 2 | Output type | Options class | Notes |
+===============+========+==============+==============+==============+=========================+===========+
-| array_filter | Binary | Any | Boolean | Input type 1 | :struct:`FilterOptions` | \(1) \(3) |
+| array_filter | Binary | Any | Boolean | Input type 1 | :struct:`FilterOptions` | \(2) |
+---------------+--------+--------------+--------------+--------------+-------------------------+-----------+
-| array_take | Binary | Any | Integer | Input type 1 | :struct:`TakeOptions` | \(1) \(4) |
+| array_take | Binary | Any | Integer | Input type 1 | :struct:`TakeOptions` | \(3) |
+---------------+--------+--------------+--------------+--------------+-------------------------+-----------+
-| drop_null | Unary | Any | - | Input type 1 | | \(1) \(2) |
+| drop_null | Unary | Any | - | Input type 1 | | \(1) |
+---------------+--------+--------------+--------------+--------------+-------------------------+-----------+
-| filter | Binary | Any | Boolean | Input type 1 | :struct:`FilterOptions` | \(1) \(3) |
+| filter | Binary | Any | Boolean | Input type 1 | :struct:`FilterOptions` | \(3) |
+---------------+--------+--------------+--------------+--------------+-------------------------+-----------+
-| take | Binary | Any | Integer | Input type 1 | :struct:`TakeOptions` | \(1) \(4) |
+| take | Binary | Any | Integer | Input type 1 | :struct:`TakeOptions` | \(4) |
Review Comment:
Fixed, and the previous line was also wrong.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [arrow] js8544 commented on pull request #36906: GH-36905: [C++] Add support for SparseUnion to selection functions
Posted by "js8544 (via GitHub)" <gi...@apache.org>.
js8544 commented on PR #36906:
URL: https://github.com/apache/arrow/pull/36906#issuecomment-1671514678
> We don't, but would it improve anything to use different indices for each child?
Judging from https://github.com/apache/arrow/blob/main/cpp/src/arrow/compute/kernels/vector_selection_take_internal.cc#L369, we can make the unneeded indices the same as the needed ones, so that accessing `values_data[indices_data[position]]` is more cache friendly. But I agree that this is very subtle.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [arrow] js8544 commented on a diff in pull request #36906: GH-36905: [C++] Add support for SparseUnion to selection functions
Posted by "js8544 (via GitHub)" <gi...@apache.org>.
js8544 commented on code in PR #36906:
URL: https://github.com/apache/arrow/pull/36906#discussion_r1288800804
##########
cpp/src/arrow/compute/kernels/vector_selection_internal.cc:
##########
@@ -863,6 +920,22 @@ Status DenseUnionFilterExec(KernelContext* ctx, const ExecSpan& batch, ExecResul
return FilterExec<DenseUnionSelectionImpl>(ctx, batch, out);
}
+Status SparseUnionFilterExec(KernelContext* ctx, const ExecSpan& batch, ExecResult* out) {
Review Comment:
Moved and extracted a `FilterWithTakeExec`.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [arrow] pitrou commented on pull request #36906: GH-36905: [C++] Add support for SparseUnion to selection functions
Posted by "pitrou (via GitHub)" <gi...@apache.org>.
pitrou commented on PR #36906:
URL: https://github.com/apache/arrow/pull/36906#issuecomment-1670947061
It seems that it reuses the DenseUnion approach, but it would be more efficient to reuse the Struct approach. What do you think?
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [arrow] js8544 commented on a diff in pull request #36906: GH-36905: [C++] Add support for SparseUnion to selection functions
Posted by "js8544 (via GitHub)" <gi...@apache.org>.
js8544 commented on code in PR #36906:
URL: https://github.com/apache/arrow/pull/36906#discussion_r1288798946
##########
cpp/src/arrow/compute/kernels/vector_selection_internal.cc:
##########
@@ -741,6 +741,63 @@ struct DenseUnionSelectionImpl
}
};
+struct SparseUnionSelectionImpl
+ : public Selection<SparseUnionSelectionImpl, SparseUnionType> {
+ using Base = Selection<SparseUnionSelectionImpl, SparseUnionType>;
+ LIFT_BASE_MEMBERS();
+
+ TypedBufferBuilder<int8_t> child_id_buffer_builder_;
+ std::vector<int8_t> type_codes_;
+
+ SparseUnionSelectionImpl(KernelContext* ctx, const ExecSpan& batch,
+ int64_t output_length, ExecResult* out)
+ : Base(ctx, batch, output_length, out),
+ child_id_buffer_builder_(ctx->memory_pool()),
+ type_codes_(checked_cast<const UnionType&>(*this->values.type).type_codes()) {}
+
+ template <typename Adapter>
+ Status GenerateOutput() {
+ SparseUnionArray typed_values(this->values.ToArrayData());
+ Adapter adapter(this);
+ RETURN_NOT_OK(adapter.Generate(
+ [&](int64_t index) {
+ int8_t child_id = typed_values.child_id(index);
+ child_id_buffer_builder_.UnsafeAppend(type_codes_[child_id]);
Review Comment:
Fixed
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [arrow] js8544 commented on pull request #36906: GH-36905: [C++] Add support for SparseUnion to selection functions
Posted by "js8544 (via GitHub)" <gi...@apache.org>.
js8544 commented on PR #36906:
URL: https://github.com/apache/arrow/pull/36906#issuecomment-1671262057
> It seems that it reuses the DenseUnion approach, but it would be more efficient to reuse the Struct approach. What do you think?
Right, I've changed it to the struct approach. But there is room for improvement for SparseUnion: the unselect children can have any value, so we don't have to call take with the same indices for every child. I've left a TODO comment in the code for this.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [arrow] js8544 commented on pull request #36906: GH-36905: [C++] Add support for SparseUnion to selection functions
Posted by "js8544 (via GitHub)" <gi...@apache.org>.
js8544 commented on PR #36906:
URL: https://github.com/apache/arrow/pull/36906#issuecomment-1673146015
Thanks for the improvements!
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [arrow] github-actions[bot] commented on pull request #36906: GH-36905: [C++] Add support for SparseUnion to selection functions
Posted by "github-actions[bot] (via GitHub)" <gi...@apache.org>.
github-actions[bot] commented on PR #36906:
URL: https://github.com/apache/arrow/pull/36906#issuecomment-1653181865
:warning: GitHub issue #36905 **has been automatically assigned in GitHub** to PR creator.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [arrow] pitrou commented on pull request #36906: GH-36905: [C++] Add support for SparseUnion to selection functions
Posted by "pitrou (via GitHub)" <gi...@apache.org>.
pitrou commented on PR #36906:
URL: https://github.com/apache/arrow/pull/36906#issuecomment-1671453176
> But there is room for improvement for SparseUnion: the unselect children can have any value, so we don't have to call take with the same indices for every child.
We don't, but would it improve anything to use different indices for each child?
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [arrow] pitrou commented on pull request #36906: GH-36905: [C++] Add support for SparseUnion to selection functions
Posted by "pitrou (via GitHub)" <gi...@apache.org>.
pitrou commented on PR #36906:
URL: https://github.com/apache/arrow/pull/36906#issuecomment-1671548081
Yes, this is quite subtle. Generating the indices arrays would cost much more, so I'm not sure it would be beneficial at the end.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [arrow] pitrou merged pull request #36906: GH-36905: [C++] Add support for SparseUnion to selection functions
Posted by "pitrou (via GitHub)" <gi...@apache.org>.
pitrou merged PR #36906:
URL: https://github.com/apache/arrow/pull/36906
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [arrow] pitrou commented on a diff in pull request #36906: GH-36905: [C++] Add support for SparseUnion to selection functions
Posted by "pitrou (via GitHub)" <gi...@apache.org>.
pitrou commented on code in PR #36906:
URL: https://github.com/apache/arrow/pull/36906#discussion_r1288578701
##########
cpp/src/arrow/compute/kernels/vector_selection_internal.cc:
##########
@@ -741,6 +741,63 @@ struct DenseUnionSelectionImpl
}
};
+struct SparseUnionSelectionImpl
+ : public Selection<SparseUnionSelectionImpl, SparseUnionType> {
+ using Base = Selection<SparseUnionSelectionImpl, SparseUnionType>;
+ LIFT_BASE_MEMBERS();
+
+ TypedBufferBuilder<int8_t> child_id_buffer_builder_;
+ std::vector<int8_t> type_codes_;
+
+ SparseUnionSelectionImpl(KernelContext* ctx, const ExecSpan& batch,
+ int64_t output_length, ExecResult* out)
+ : Base(ctx, batch, output_length, out),
+ child_id_buffer_builder_(ctx->memory_pool()),
+ type_codes_(checked_cast<const UnionType&>(*this->values.type).type_codes()) {}
+
+ template <typename Adapter>
+ Status GenerateOutput() {
+ SparseUnionArray typed_values(this->values.ToArrayData());
+ Adapter adapter(this);
+ RETURN_NOT_OK(adapter.Generate(
+ [&](int64_t index) {
+ int8_t child_id = typed_values.child_id(index);
+ child_id_buffer_builder_.UnsafeAppend(type_codes_[child_id]);
Review Comment:
This seems to be doing a pointless back-and-forth between type codes and child ids?
```suggestion
child_id_buffer_builder_.UnsafeAppend(typed_values.type_code(index));
```
##########
cpp/src/arrow/compute/kernels/vector_selection_internal.cc:
##########
@@ -863,6 +920,22 @@ Status DenseUnionFilterExec(KernelContext* ctx, const ExecSpan& batch, ExecResul
return FilterExec<DenseUnionSelectionImpl>(ctx, batch, out);
}
+Status SparseUnionFilterExec(KernelContext* ctx, const ExecSpan& batch, ExecResult* out) {
Review Comment:
Nit: move this into `vector_filter_internal.cc` along `StructFilterExec`? (can probably also share some code between them...)
##########
docs/source/cpp/compute.rst:
##########
@@ -1680,28 +1680,26 @@ These functions select and return a subset of their input.
+---------------+--------+--------------+--------------+--------------+-------------------------+-----------+
| Function name | Arity | Input type 1 | Input type 2 | Output type | Options class | Notes |
+===============+========+==============+==============+==============+=========================+===========+
-| array_filter | Binary | Any | Boolean | Input type 1 | :struct:`FilterOptions` | \(1) \(3) |
+| array_filter | Binary | Any | Boolean | Input type 1 | :struct:`FilterOptions` | \(2) |
+---------------+--------+--------------+--------------+--------------+-------------------------+-----------+
-| array_take | Binary | Any | Integer | Input type 1 | :struct:`TakeOptions` | \(1) \(4) |
+| array_take | Binary | Any | Integer | Input type 1 | :struct:`TakeOptions` | \(3) |
+---------------+--------+--------------+--------------+--------------+-------------------------+-----------+
-| drop_null | Unary | Any | - | Input type 1 | | \(1) \(2) |
+| drop_null | Unary | Any | - | Input type 1 | | \(1) |
+---------------+--------+--------------+--------------+--------------+-------------------------+-----------+
-| filter | Binary | Any | Boolean | Input type 1 | :struct:`FilterOptions` | \(1) \(3) |
+| filter | Binary | Any | Boolean | Input type 1 | :struct:`FilterOptions` | \(3) |
+---------------+--------+--------------+--------------+--------------+-------------------------+-----------+
-| take | Binary | Any | Integer | Input type 1 | :struct:`TakeOptions` | \(1) \(4) |
+| take | Binary | Any | Integer | Input type 1 | :struct:`TakeOptions` | \(4) |
Review Comment:
I suppose this should be
```suggestion
| take | Binary | Any | Integer | Input type 1 | :struct:`TakeOptions` | \(3) |
```
##########
cpp/src/arrow/compute/kernels/vector_selection_internal.cc:
##########
@@ -863,6 +920,22 @@ Status DenseUnionFilterExec(KernelContext* ctx, const ExecSpan& batch, ExecResul
return FilterExec<DenseUnionSelectionImpl>(ctx, batch, out);
}
+Status SparseUnionFilterExec(KernelContext* ctx, const ExecSpan& batch, ExecResult* out) {
+ // Transform filter to selection indices and then use Take.
+ std::shared_ptr<ArrayData> indices;
+ RETURN_NOT_OK(GetTakeIndices(batch[1].array,
+ FilterState::Get(ctx).null_selection_behavior,
+ ctx->memory_pool())
+ .Value(&indices));
+
+ Datum result;
+ RETURN_NOT_OK(Take(batch[0].array.ToArrayData(), Datum(indices),
Review Comment:
Perhaps we can call `SparseUnionTakeExec` directly instead of going through the function lookup and execution machinery again?
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [arrow] js8544 commented on pull request #36906: GH-36905: [C++] Add support for SparseUnion to selection functions
Posted by "js8544 (via GitHub)" <gi...@apache.org>.
js8544 commented on PR #36906:
URL: https://github.com/apache/arrow/pull/36906#issuecomment-1671585901
> Yes, this is quite subtle. Generating the indices arrays would cost much more, so I'm not sure it would be beneficial at the end.
OK I'll remove that comment.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [arrow] js8544 commented on a diff in pull request #36906: GH-36905: [C++] Add support for SparseUnion to selection functions
Posted by "js8544 (via GitHub)" <gi...@apache.org>.
js8544 commented on code in PR #36906:
URL: https://github.com/apache/arrow/pull/36906#discussion_r1288801734
##########
cpp/src/arrow/compute/kernels/vector_selection_internal.cc:
##########
@@ -863,6 +920,22 @@ Status DenseUnionFilterExec(KernelContext* ctx, const ExecSpan& batch, ExecResul
return FilterExec<DenseUnionSelectionImpl>(ctx, batch, out);
}
+Status SparseUnionFilterExec(KernelContext* ctx, const ExecSpan& batch, ExecResult* out) {
+ // Transform filter to selection indices and then use Take.
+ std::shared_ptr<ArrayData> indices;
+ RETURN_NOT_OK(GetTakeIndices(batch[1].array,
+ FilterState::Get(ctx).null_selection_behavior,
+ ctx->memory_pool())
+ .Value(&indices));
+
+ Datum result;
+ RETURN_NOT_OK(Take(batch[0].array.ToArrayData(), Datum(indices),
Review Comment:
Done
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [arrow] conbench-apache-arrow[bot] commented on pull request #36906: GH-36905: [C++] Add support for SparseUnion to selection functions
Posted by "conbench-apache-arrow[bot] (via GitHub)" <gi...@apache.org>.
conbench-apache-arrow[bot] commented on PR #36906:
URL: https://github.com/apache/arrow/pull/36906#issuecomment-1675168222
After merging your PR, Conbench analyzed the 5 benchmarking runs that have been run so far on merge-commit ebcf7bc25fcd47137523cb934a740cac0fc0fb76.
There were 2 benchmark results indicating a performance regression:
- Commit Run on `ursa-i9-9960x` at [2023-08-10 15:59:43Z](http://conbench.ursa.dev/compare/runs/7fd3a5ebdb7543c49fde91780e697703...ad8f9f30fcd24dabb7bc1d8c3e5e9bf0/)
- [`file-read` (Python) with compression=uncompressed, dataset=fanniemae_2016Q4, file_type=feather, output_type=table](http://conbench.ursa.dev/compare/benchmarks/064d413184427c4c80001f194ec40e2b...064d516bcfba7b888000dbc5fbaa5b5c)
- [`file-read` (Python) with compression=uncompressed, dataset=fanniemae_2016Q4, file_type=feather, output_type=dataframe](http://conbench.ursa.dev/compare/benchmarks/064d41330f8577f6800051da449df6cb...064d516d927e7790800045a6df4bea14)
The [full Conbench report](https://github.com/apache/arrow/runs/15827461532) has more details.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org