alamb opened a new issue, #27233:
URL: https://github.com/apache/datafusion/issues/27233
### Is your feature request related to a problem or challenge?
There is a lot of great work from @SubhamSinghal, @jayzhan211 and others on
the "TopK per partition" optimization for window queries like
```sql
SELECT * FROM (
SELECT ROW_NUMBER() OVER (PARTITION BY category ORDER BY revenue DESC)
AS rn, *
FROM sales
) WHERE rn <= 5;
```
The original request is from 2023:
- https://github.com/apache/datafusion/issues/6899
The optimization landed in DataFusion 55 behind
`datafusion.optimizer.enable_window_topn`, and the EPIC to turn it on by
default is
- https://github.com/apache/datafusion/issues/24608
- https://github.com/apache/datafusion/pull/27197
As always, telling the community about it will be good
1. To advertise the feature for others who have the same use case,
2. To document in an easier to understand way how the feature works
2. The authors to raise their visibility.
I had drafted a section about it for the DataFusion 55 release post (see
below) but a release post isn't great as it has limited space to explain how
the operator works
- https://github.com/apache/datafusion/issues/24216
- https://github.com/apache/datafusion-site/pull/203
### Describe the solution you'd like
Thus I suggest a complete self contained blog post on
https://datafusion.apache.org/blog/ (make a PR to
https://github.com/apache/datafusion-site) about TopK per partition.
I suggest the standard structure of "informative post with low key
DataFusion pitch"
For example, the pattern of
- Dynamic Filters (TopK and hash join, 25x faster):
https://datafusion.apache.org/blog/2025/09/10/dynamic-filters/
- Fast high cardinality grouping:
https://datafusion.apache.org/blog/2023/08/05/datafusion_fast_grouping/
Here are some ideas for an outline:
1. **An understandable representative usecase**: "top N per group" (e.g
latest N events per device) so readers can tell if it applies to them. Mention
this is [db-benchmark](https://github.com/apache/datafusion/issues/13586) / h2o
query 8 shape.
2. **Background / technical intuition**: the naive plan sorts the entire
input to compute the window function and then throws almost all of it away. The
TopK per partition operator keeps a bounded heap per partition instead. Explain
how `ROW_NUMBER`, `RANK` and `DENSE_RANK` differ in what has to be retained.
3. **How to use it in DataFusion**: What version is it introduced in (57 I
hope, show `EXPLAIN` before/after with `PartitionedTopKExec`), and how to turn
it off)
4. **A bit about how it is implemented**: the `WindowTopN` physical
optimizer rule, `PartitionedTopKExec`, and then some of the highlights of
making it work for high cardinality:
- the 100K+ partition cliff,
https://github.com/apache/datafusion/pull/21479#issuecomment-4221809099
- Memory optimizations, etc
- Emitting the rank column directly from the operator so the window node
can be removed (#26133)
5. **Call for help** 🎣: Any remaining work that needs to happen
I think the best time to publish is around 57 release (when #27197 is merged
and released, so the post can say the optimization is on by default.
### Describe alternatives you've considered
Here is the original text I had drafted for the 55 release post (from
https://github.com/apache/datafusion/issues/24608), which could be a starting
point:
<details><summary>Details</summary>
<p>
### Per-Partition TopK for Window Functions
A common analytics pattern selects the top N rows per group using a window
function:
```sql
SELECT * FROM (
SELECT ROW_NUMBER() OVER (PARTITION BY category ORDER BY revenue DESC)
AS rn, *
FROM sales
) WHERE rn <= 5;
```
DataFusion previously sorted the *entire* input to evaluate the window
function, even though only a handful of rows per partition survive the
filter.
DataFusion 55 recognizes this pattern and uses a new `PartitionedTopKExec`
operator that keeps only the top N rows per partition, dramatically reducing
sorting and memory for high-cardinality inputs. The optimization applies to
`ROW_NUMBER` and `RANK`, resolving a feature request first filed in 2023
(#6899).
Thanks to @SubhamSinghal for implementing this feature, with reviews from
@2010YOUY01 and @kosiew. Related PRs: #21479, #22885, #23096
</p>
</details>
### Additional context
Tracking issues:
- https://github.com/apache/datafusion/issues/6899 (original 2023 request)
- https://github.com/apache/datafusion/issues/24608 (enable by default EPIC)
- https://github.com/apache/datafusion/issues/24060 (follow on optimizations)
- https://github.com/apache/datafusion/issues/23197 (window function
performance EPIC)
Core operator and optimizer rule:
- https://github.com/apache/datafusion/pull/21479 (`ROW_NUMBER`,
@SubhamSinghal)
- https://github.com/apache/datafusion/pull/22885 (`RANK`, @SubhamSinghal)
- https://github.com/apache/datafusion/pull/23869 (`DENSE_RANK`,
@SubhamSinghal)
- https://github.com/apache/datafusion/pull/24191 (run `WindowTopN` before
`EnforceRequirements`, @saadtajwar)
- https://github.com/apache/datafusion/pull/23355 (range partitioned inputs,
@stuhood)
- https://github.com/apache/datafusion/pull/26133 (emit the rank column from
the operator, @SubhamSinghal)
- https://github.com/apache/datafusion/pull/27197 (enable by default,
@SubhamSinghal)
Closing the high cardinality gap:
- https://github.com/apache/datafusion/pull/23096 (share encoder and
reservation across partitions)
- https://github.com/apache/datafusion/pull/24591 (`RANK` memory from
O(input) to O(K + ties), @jayzhan211)
- https://github.com/apache/datafusion/pull/25468 (interleave retained rows
at emit)
- https://github.com/apache/datafusion/pull/25730 (shared `RecordBatchStore`
for `ROW_NUMBER`)
- https://github.com/apache/datafusion/pull/25968 (`RANK` on the shared
store with decide-then-gather)
Correctness fixes and metrics:
- https://github.com/apache/datafusion/pull/24405 (@viirya)
- https://github.com/apache/datafusion/pull/23599 (@zhuqi-lucas)
- https://github.com/apache/datafusion/pull/24495 (metrics, @shinzoxD)
- https://github.com/apache/datafusion/pull/26417 (filter column through
projections)
- https://github.com/apache/datafusion/pull/25535 (@jayzhan211)
Benchmarks:
- https://github.com/apache/datafusion/pull/24050 (`dense_rank` benchmark)
- https://github.com/apache/datafusion/pull/24732 (h2o `window_sorted` sweep)
Open follow on work:
- https://github.com/apache/datafusion/issues/26381 (`Utf8View` buffers kept
alive)
- https://github.com/apache/datafusion/issues/26876 /
https://github.com/apache/datafusion/pull/27136 (`DENSE_RANK` on the shared
store)
- https://github.com/apache/datafusion/issues/21596 (filters with embedded
projections)
- https://github.com/apache/datafusion/pull/26160 (`rn = 1`)
- https://github.com/apache/datafusion/issues/23600 (`ROW_NUMBER() = 1` /
`DISTINCT ON` dedup)
- https://github.com/apache/datafusion/pull/24629 (streaming path for
pre-sorted input, closed but a good idea)
Related prior posts for style / context:
- [Optimizing for Almost Sorted Data: Sort
Pushdown](https://datafusion.apache.org/blog/2026/07/20/sort-pushdown/)
- [Dynamic Filters](https://github.com/apache/datafusion-site/pull/103)
- Previous blog post tickets:
https://github.com/apache/datafusion/issues/15513,
https://github.com/apache/datafusion/issues/24667
--
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]
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
