zanmato1984 opened a new pull request, #44053:
URL: https://github.com/apache/arrow/pull/44053
<!--
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
As described in #44052, currently `AnyKeysSegmenter::GetNextSegment` has
`O(n*m)` complexity, where `n` is the number of rows in a batch, and `m` is the
number of segments in this batch (a "segment" is the group of contiguous rows
who have the same segment key). This is because in each invocation of the
method, it computes all the group ids of the remaining rows in this batch,
where it's only interested in the first group, making the rest of the
computation a waste.
In this PR I introduced a new API `GetSegments` (and subsequently deprecated
the old `GetNextSegment`) to compute the group ids only once and iterate all
the segments outside to avoid the duplicated computation. This reduces the
complexity from `O(n*m)` to `O(n)`.
<!--
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.
-->
### What changes are included in this PR?
1. Because `grouper.h` is a [public
header](https://github.com/apache/arrow/blob/8556001e6a8b4c7f35d4e18c28704d7811005904/cpp/src/arrow/compute/api.h#L47),
so I assume `RowSegmenter::GetNextSegment` is a public API and only deprecate
it instead of removing it.
2. Implement new API `RowSegmenter::GetSegments` and update the call-sites.
3. Some code reorg of the segmenter code (mostly moving to inside a class).
4. A new benchmark for the segmented aggregation. (The benchmark result is
shown in the comments below.)
<!--
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.
-->
### Are these changes tested?
Legacy tests are sufficient.
<!--
We typically require tests for all PRs in order to:
1. Prevent the code from being accidentally broken by subsequent changes
5. 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)?
-->
### Are there any user-facing changes?
Yes.
<!--
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.**
The API `RowSegmenter::GetNextSegment` is deprecated due to its inefficiency
and replaced with a more efficient one `RowSegmenter::GetSegments`.
<!--
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: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
