You are viewing a plain text version of this content. The canonical link for it is here.
Posted to github@datafusion.apache.org by "SubhamSinghal (via GitHub)" <gi...@apache.org> on 2026/09/25 04:58:45 UTC
[PR] perf: PartitionedTopK hold retained rows in one shared RecordBatchStore [datafusion]
SubhamSinghal opened a new pull request, #25730:
URL: https://github.com/apache/datafusion/pull/25730
## Which issue does this PR close?
- Part of #24608. Close #13586.
## Rationale for this change
`enable_window_topn` rewrites `Filter(rn<=K) → Window(ROW_NUMBER) → Sort` into
`PartitionedTopKExec`. As its own config documentation warns, it helps at low partition cardinality
and regresses at high cardinality. Running the existing ROW_NUMBER sweep in
`benchmarks/queries/h2o/window.sql` on `J1_1e7_1e7_NA` (10M rows) and comparing the flag on vs off
on the same commit (medians of 7):
| partitions | CPU, ON vs OFF on `main` |
|---|---|
| 100 | 5.65× faster |
| 1,000 | 5.21× faster |
| 10,000 | 2.28× faster |
| 100,000 | **2.16× slower** |
The benefit decays with cardinality and inverts around 100K, so the optimization becomes a
pessimization exactly where a per-partition top-K should help most. That is why the flag still
defaults to `false`.
The cause is how retained rows are stored, not the per-partition heaps. For every
(batch, partition) pair, `insert_batch` `take`s a sub-batch of *all* that partition's rows in that
batch — qualifying or not — registers it in a `RecordBatchStore` private to that partition, then
runs `maybe_compact()`. At 100K partitions that is ~100K separate stores, one `take` per
(batch, partition), and a compaction check per (batch, partition) on every batch.
## What changes are included in this PR?
Two coupled changes to the `ROW_NUMBER` arm of `PartitionedTopKExec`. `RANK` and `DENSE_RANK` are
untouched — see the follow-ups below.
1. **One `RecordBatchStore` for the operator** instead of one per partition. Each partition holds a
lean `PartitionHeap` of `PartitionSlot { key: Vec<u8>, batch_id: u32, row: u32 }` — the
row-encoded ORDER BY key inline, output columns by reference, refcounted as `DENSE_RANK` already
does.
2. **Decide first, gather once.** A single pass over the batch admits rows and records only their
indices; then **one** `take_record_batch` of just the admitted rows becomes one store entry. If
every admission from a batch is superseded within that batch, nothing is registered at all.
Sharing the store means `TopKHeap::maybe_compact` can no longer be used on this path — it calls
`store.clear()`, which on a shared store invalidates *other* partitions' `batch_id`s, and its guard
reads a now-global `total_rows`. Since that per-heap compaction was the only thing bounding retention
on `main`, it is replaced by an operator-level one:
3. **`compact_store()`**, run at the end of every `insert_batch`, rewrites the store when it holds
more than `STORE_COMPACTION_RATIO` × the rows the heaps actually point at. Without it, retention is
**unbounded**.
## What is the testing strategy for this PR?
`datafusion-physical-plan` (1964 tests) and all 512 sqllogictest files pass. plus added new UTs
## Are there any user-facing changes?
No API changes and no change to query results. `enable_window_topn` still defaults to `false`.
## Benchmark details
Queries are the ROW_NUMBER cardinality sweep already in `benchmarks/queries/h2o/window.sql`
(k=2, `ORDER BY v2 DESC`, `WHERE v2 IS NOT NULL`), run against `J1_1e7_1e7_NA.parquet`
| partitions | main, ON vs OFF | this branch, ON vs OFF |
|---|---|---|
| 100 | 5.65× faster | 5.80× faster |
| 1,000 | 5.21× faster | 5.90× faster |
| 10,000 | 2.28× faster | 4.59× faster |
| 100,000 | **2.16× slower** | **2.01× faster** |
**"Why not just extract `RecordBatchStore` out of `TopKHeap`?"** — measured, on a throwaway branch
with a shared store and `main`'s per-(batch, partition) gather. Sharing the store is ~1.2× of the
win and is *worse* on RSS than `main` (it pins per-(batch, partition) sub-batches with nothing
reclaiming them); decide-then-gather is the remaining ~5.3×, and without it the rewrite is still
slower than the `SortExec` plan it replaces.
--
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: PartitionedTopK hold retained rows in one shared RecordBatchStore [datafusion]
Posted by "SubhamSinghal (via GitHub)" <gi...@apache.org>.
SubhamSinghal commented on PR #25730:
URL: https://github.com/apache/datafusion/pull/25730#issuecomment-5864195606
@kosiew @jayzhan211 Can you help in reviewing 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: PartitionedTopK hold retained rows in one shared RecordBatchStore [datafusion]
Posted by "jayzhan211 (via GitHub)" <gi...@apache.org>.
jayzhan211 commented on PR #25730:
URL: https://github.com/apache/datafusion/pull/25730#issuecomment-5912442968
Thanks @SubhamSinghal @kosiew , LGTM!
--
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: PartitionedTopK hold retained rows in one shared RecordBatchStore [datafusion]
Posted by "jayzhan211 (via GitHub)" <gi...@apache.org>.
jayzhan211 merged PR #25730:
URL: https://github.com/apache/datafusion/pull/25730
--
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: PartitionedTopK hold retained rows in one shared RecordBatchStore [datafusion]
Posted by "codecov-commenter (via GitHub)" <gi...@apache.org>.
codecov-commenter commented on PR #25730:
URL: https://github.com/apache/datafusion/pull/25730#issuecomment-5827271636
## [Codecov](https://app.codecov.io/gh/apache/datafusion/pull/25730?dropdown=coverage&src=pr&el=h1&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) Report
:x: Patch coverage is `88.50856%` with `94 lines` in your changes missing coverage. Please review.
:white_check_mark: Project coverage is 82.49%. Comparing base ([`23f6f94`](https://app.codecov.io/gh/apache/datafusion/commit/23f6f94c308a800748a5f8b7a5b85d5e41e5dc95?dropdown=coverage&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache)) to head ([`280f729`](https://app.codecov.io/gh/apache/datafusion/commit/280f72943b3459adaae320b5074929f39bcef551?dropdown=coverage&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache)).
:warning: Report is 17 commits behind head on main.
| [Files with missing lines](https://app.codecov.io/gh/apache/datafusion/pull/25730?dropdown=coverage&src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) | Patch % | Lines |
|---|---|---|
| [datafusion/physical-plan/src/topk/mod.rs](https://app.codecov.io/gh/apache/datafusion/pull/25730?src=pr&el=tree&filepath=datafusion%2Fphysical-plan%2Fsrc%2Ftopk%2Fmod.rs&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache#diff-ZGF0YWZ1c2lvbi9waHlzaWNhbC1wbGFuL3NyYy90b3BrL21vZC5ycw==) | 88.50% | [26 Missing and 68 partials :warning: ](https://app.codecov.io/gh/apache/datafusion/pull/25730?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) |
<details><summary>Additional details and impacted files</summary>
```diff
@@ Coverage Diff @@
## main #25730 +/- ##
==========================================
- Coverage 82.51% 82.49% -0.02%
==========================================
Files 1140 1140
Lines 438443 439224 +781
Branches 438443 439224 +781
==========================================
+ Hits 361768 362351 +583
- Misses 54832 54974 +142
- Partials 21843 21899 +56
```
</details>
[:umbrella: View full report in Codecov by Harness](https://app.codecov.io/gh/apache/datafusion/pull/25730?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