You are viewing a plain text version of this content. The canonical link for it is here.
Posted to github@datafusion.apache.org by "lyne7-sc (via GitHub)" <gi...@apache.org> on 2026/09/22 09:02:53 UTC
[PR] perf: avoid capturing unused evicted rows in TopK [datafusion]
lyne7-sc opened a new pull request, #25599:
URL: https://github.com/apache/datafusion/pull/25599
## Which issue does this PR close?
<!--
We generally require a GitHub issue to be filed for all bug fixes and enhancements and this helps us generate change logs for our releases. You can link an issue to this PR using the GitHub syntax. For example `Closes #123` indicates that this PR will close issue #123.
-->
- Closes #.
## 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.
Please explain the problem you are trying to solve in terms of the user-visible
behavior, rather than the implementation.
For example, "The code in `foo.rs` doesn't handle nulls" is a symptom of the
implementation. "COUNT(DISTINCT) returns wrong results when the column contains
nulls" is the user-visible problem.
-->
TopK queries with frequent heap replacements spend time capturing evicted rows that ordinary TopK and partitioned `ROW_NUMBER` TopK immediately discard. Avoiding this work reduces allocation, encoded-key copying, and RecordBatch column-reference cloning.
## 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.
-->
- Split heap insertion into `add()` and `add_with_eviction()`, sharing heap maintenance through a const-generic implementation.
- Skip eviction capture for ordinary TopK and partitioned ROW_NUMBER TopK.
- Preserve eviction capture for RANK, which needs evicted rows to retain boundary ties.
## What is the testing strategy for this PR?
<!--
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
Briefly describe how this PR is tested, and point to the specific tests you added. For example: 'This new feature is covered by the `sqllogictest` cases added in `foo.slt`'.
If this PR does not add tests, explain why. For example, if the change is already covered by existing tests, please mention it.
You should also check the `codecov` bot reply on this PR to confirm the changed code is exercised.
-->
- Add `test_topk_heap_same_and_cross_batch_eviction` to cover both capture and discard modes, checking evicted values, encoded keys, batch release, and final output.
- Existing SLT coverage in `topk.slt` and `window_topn.slt` verifies ordinary TopK and partitioned `ROW_NUMBER/RANK` behavior.
## Are there any user-facing changes?
<!--
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 add the `api change` label.
-->
This is an internal performance improvement. Query results and public APIs are unchanged.
## Benchmarks
```text
group before new
----- ------ ---
topk_replacements/u64_narrow_k128/ascending 1.01 58.0±3.93µs ? ?/sec 1.00 57.5±0.80µs ? ?/sec
topk_replacements/u64_narrow_k128/descending 1.49 7.9±0.04ms ? ?/sec 1.00 5.3±0.20ms ? ?/sec
topk_replacements/u64_narrow_k128/random 1.10 235.3±3.58µs ? ?/sec 1.00 213.1±4.72µs ? ?/sec
topk_replacements/utf8_64_narrow_k128/ascending 1.05 406.2±63.66µs ? ?/sec 1.00 387.7±13.97µs ? ?/sec
topk_replacements/utf8_64_narrow_k128/descending 1.36 12.7±0.20ms ? ?/sec 1.00 9.4±0.42ms ? ?/sec
topk_replacements/utf8_64_narrow_k128/random 1.01 667.4±8.85µs ? ?/sec 1.00 659.2±34.78µs ? ?/sec
topk_replacements/utf8_64_wide_k1024/ascending 1.00 556.5±17.64µs ? ?/sec 1.01 559.9±21.18µs ? ?/sec
topk_replacements/utf8_64_wide_k1024/descending 1.44 23.7±0.45ms ? ?/sec 1.00 16.4±2.02ms ? ?/sec
topk_replacements/utf8_64_wide_k1024/random 1.12 3.8±0.07ms ? ?/sec 1.00 3.4±0.07ms ? ?/sec
topk_replacements/utf8_64_wide_k128/ascending 1.02 397.62µs ? ?/sec 1.00 390.92µs ? ?/sec
topk_replacements/utf8_64_wide_k128/descending 1.96 18.1±0.31ms ? ?/sec 1.00 9.2±0.05ms ? ?/sec
topk_replacements/utf8_64_wide_k128/random 1.11 806.7±22.68µs ? ?/sec 1.00 724.9±13.62µs ? ?/sec
```
--
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@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] perf: avoid capturing unused evicted rows in TopK [datafusion]
Posted by "lyne7-sc (via GitHub)" <gi...@apache.org>.
lyne7-sc commented on PR #25599:
URL: https://github.com/apache/datafusion/pull/25599#issuecomment-6182661206
Thanks @kosiew for taking a look!
After checking the conflicts, I found that #25968 already eliminates the unnecessary eviction capture this PR targeted, so I'll close this PR.
--
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@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] perf: avoid capturing unused evicted rows in TopK [datafusion]
Posted by "lyne7-sc (via GitHub)" <gi...@apache.org>.
lyne7-sc closed pull request #25599: perf: avoid capturing unused evicted rows in TopK
URL: https://github.com/apache/datafusion/pull/25599
--
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@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] perf: avoid capturing unused evicted rows in TopK [datafusion]
Posted by "codecov-commenter (via GitHub)" <gi...@apache.org>.
codecov-commenter commented on PR #25599:
URL: https://github.com/apache/datafusion/pull/25599#issuecomment-5774668770
## [Codecov](https://app.codecov.io/gh/apache/datafusion/pull/25599?dropdown=coverage&src=pr&el=h1&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) Report
:white_check_mark: All modified and coverable lines are covered by tests.
:white_check_mark: Project coverage is 82.42%. Comparing base ([`6574a8c`](https://app.codecov.io/gh/apache/datafusion/commit/6574a8c3b2c93ef9689a677c1cc1c0a4a844617f?dropdown=coverage&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache)) to head ([`0cd6760`](https://app.codecov.io/gh/apache/datafusion/commit/0cd676085790b3bcc1b360be54b4f471c531a8ad?dropdown=coverage&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache)).
:warning: Report is 12 commits behind head on main.
<details><summary>Additional details and impacted files</summary>
```diff
@@ Coverage Diff @@
## main #25599 +/- ##
==========================================
- Coverage 82.42% 82.42% -0.01%
==========================================
Files 1138 1139 +1
Lines 435501 435483 -18
Branches 435501 435483 -18
==========================================
- Hits 358955 358927 -28
- Misses 54841 54843 +2
- Partials 21705 21713 +8
```
</details>
[:umbrella: View full report in Codecov by Harness](https://app.codecov.io/gh/apache/datafusion/pull/25599?dropdown=coverage&src=pr&el=continue&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache).
:loudspeaker: Have feedback on the report? [Share it here](https://about.codecov.io/codecov-pr-comment-feedback/?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache).
<details><summary> :rocket: New features to boost your workflow: </summary>
- :snowflake: [Test Analytics](https://docs.codecov.com/docs/test-analytics): Detect flaky tests, report on failures, and find test suite problems.
- :package: [JS Bundle Analysis](https://docs.codecov.com/docs/javascript-bundle-analysis): Save yourself from yourself by tracking and limiting bundle sizes in JS merges.
</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@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] perf: avoid capturing unused evicted rows in TopK [datafusion]
Posted by "kosiew (via GitHub)" <gi...@apache.org>.
kosiew commented on PR #25599:
URL: https://github.com/apache/datafusion/pull/25599#issuecomment-6162128006
@lyne7-sc
I would love to review this after you resolve the merge conflicts.
--
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@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org