Top N Per Group with PartitionedTopKExec in Apache DataFusion
Posted on: Fri 13 November 2026 by Vadim Lazuk
"Find the top N rows within each group" is one of the most common shapes in analytics: the five best-selling products in each category, the three most recent events per device, the two highest-revenue rows per store. In SQL this is usually written with a ranking window function and an outer filter:
SELECT * FROM (
SELECT ROW_NUMBER() OVER (PARTITION BY category ORDER BY revenue DESC) AS rn, *
FROM sales
) WHERE rn <= 5;
Until recently, DataFusion evaluated this query by sorting the entire input
to compute the window function, and then throwing almost all of the sorted
output away. DataFusion 55 recognizes the pattern: with
datafusion.optimizer.enable_window_topn enabled, the full sort is replaced
by a new PartitionedTopKExec operator that keeps only the top N rows per
partition in a bounded heap.
The rest of this post shows how to enable the feature, what changes in the plan, how the operator works, and where it helps and where it does not.
The "Top N Per Group" Pattern¶
The query above computes the top five rows per category. The same shape
covers the latest events per device, the highest-paid employees per
department, and many other screens and reports. It is also query 8 of the
h2o group-by benchmark ("top 2 rows by value per group"), which DataFusion
tracks as part of its effort to stay competitive on db-benchmark.
What matters for the optimizer is the ratio: the filter keeps a small, fixed
number of rows per group (rn <= K), while the input per group is large.
When that holds, almost all the work of a sort-based plan is discarded.
The Default Plan Sorts Everything¶
A ranking window function must see each partition's rows as one contiguous,
ordered run. The straightforward way to guarantee that is to sort the whole
input by (partition keys, order keys) and evaluate the window over the
sorted stream. With the optimization disabled, the physical plan for the
query above is (abridged):
ProjectionExec
FilterExec: rn <= 5
BoundedWindowAggExec: ROW_NUMBER() PARTITION BY [category] ORDER BY [revenue DESC]
SortExec: expr=[category ASC, revenue DESC]
DataSourceExec
The plan is correct, but every stage does work on rows the filter later throws away:
-
SortExecsorts the entire dataset by(category, revenue). The window function needs each partition's rows contiguous and inORDER BYorder, and a full sort is the only way to guarantee that here. It is a blocking, spill-capable sort of all N rows: O(N log N) time, O(N) memory, with excess rows written to disk and merged back once the memory pool runs out. -
BoundedWindowAggExeccomputesROW_NUMBERfor every row. It walks the sorted stream and numbers each partition's rows 1, 2, 3, ... It holds state only for the partition currently open, hence "bounded", but it still touches all N rows, including the ones about to be discarded. -
FilterExeckeeps only the rows withrn <= 5. Everything the sort and the window did for the other rows is wasted here.
With 10 million rows, 1,000 partitions, and K = 3, the plan sorts all 10
million rows to keep 3,000 — 0.03% of the input. The surviving fraction is
roughly K × P / N, and it shrinks toward zero as the partition key's
cardinality grows.
How It Works¶
PartitionedTopKExec reads unsorted input and keeps one bounded top-K heap
per distinct partition key, instead of sorting the dataset. Rows are
converted to Arrow's row format with a single shared RowConverter and
grouped by their partition key. Each group's rows flow into that group's
heap, which holds the best K rows according to the ORDER BY and evicts the
rest as new rows arrive. All heaps share a single MemoryReservation, so the
operator reports its memory usage to DataFusion's memory pool as one unit
#21479, #23096.
The overall cost changes from O(N log N) time and O(N) memory to:
- O(N log K) time — each row is compared against a heap of size K.
- O(K × P × row_size) memory — K retained rows for each of the P distinct partitions.
For example, with fetch=3 and input:
store | revenue
------|--------
A | 100
B | 50
A | 200
B | 150
A | 300
A | 400
the operator keeps two heaps: store=A retains {400, 300, 200} and evicts
100; store=B retains {150, 50}. It emits the retained rows in
(partition_keys, order_keys) order — A/400, A/300, A/200, B/150, B/50 —
which is exactly the contiguous ordered run the window operator needs to
assign ROW_NUMBER values 1..3 per partition.
What Each Ranking Function Has to Retain¶
The three ranking functions differ in what a correct implementation must keep per partition:
ROW_NUMBERnumbers rows 1, 2, 3, ... with no ties, so exactly K rows per partition suffice.RANKgives tied rows the same rank and skips subsequent ranks, soWHERE rk <= Kmust keep K rows plus any additional rows tied with the row at the boundary. The operator therefore pairs its heap with a sibling ties list, and a query can legitimately return more than K rows per partition when ties straddle the boundary — that is whatRANKmeans.DENSE_RANKgives tied rows the same rank without gaps, which requires tracking distinct order-by values rather than just rows.
Emission Order and the Window Operator¶
Window functions do not require the partition keys to be globally sorted —
only each partition's rows must be contiguous and ordered among themselves.
PartitionedTopKExec emits rows grouped by partition and ordered by the
ORDER BY keys within each partition, which is the weaker guarantee the
window operator needs, and avoids paying for a global sort of the partition
keys. The BoundedWindowAggExec above the operator then runs in Sorted
mode: it only walks the retained rows and writes the rank column.
Work on the main branch since DataFusion 55 goes further: #26133 emits the
rank column directly from PartitionedTopKExec, allowing the window operator
to be removed from the plan entirely.
Using It in DataFusion 55¶
The optimization ships in DataFusion 55.0.0 behind the
datafusion.optimizer.enable_window_topn configuration flag, which is
disabled by default. Enable it with:
SET datafusion.optimizer.enable_window_topn = true;
With the flag on, the same query produces (abridged):
ProjectionExec
BoundedWindowAggExec: ROW_NUMBER() PARTITION BY [category] ORDER BY [revenue DESC]
RepartitionExec: partitioning=Hash([category], ...)
PartitionedTopKExec: fn=row_number, fetch=5, partition=[category], order=[revenue DESC]
DataSourceExec
The SortExec and the FilterExec are gone. PartitionedTopKExec sits
directly below the window operator and feeds it only the surviving rows,
already grouped and ordered.
Which Queries the Rewrite Applies To¶
The physical optimizer rule behind this is called WindowTopN. It fires when
all of the following hold:
- The window function is
ROW_NUMBERorRANK(in DataFusion 55; see Status and Roadmap forDENSE_RANK). - The window has a
PARTITION BYclause. A global top-N without partitioning is already handled efficiently bySortExecwith a fetch limit. - For
RANK: the window has a non-emptyORDER BYclause (with an emptyORDER BY, every row ties at rank 1 and there is nothing to prune). - The filter compares the ranking column to an integer literal using one of
rn <= K,rn < K,K >= rn, orK > rn.
The rule derives the number of rows to retain from the predicate: rn <= 5
retains 5 rows per partition, and rn < 5 retains 4.
If any of these conditions fail, the rule does not fire and the sort-based plan above is used. The flag switches only this rewrite on and off; it affects nothing else. To disable it again:
SET datafusion.optimizer.enable_window_topn = false;
Benchmarks: Where It Helps, and Where It Does Not¶
When the operator was introduced, it was measured on the h2o group-by shape — 10 million rows, top-2 rows per partition — across partition counts from 100 to 100,000 #21479. The full input is processed either way; only the sort is replaced by the heaps.
| Scenario | Enabled | Disabled | Speedup |
|---|---|---|---|
| 100 partitions (100K rows each) | 43 ms | 174 ms | 4.0x |
| 1K partitions (10K rows each) | 71 ms | 146 ms | 2.1x |
| 10K partitions (1K rows each) | 619 ms | 128 ms | 0.2x (regression) |
| 100K partitions (100 rows each) | 4368 ms | 135 ms | 0.03x (regression) |
Timings reported in #21479 when the operator was introduced — on a build that predates #23096, which shares the row encoder and memory reservation across partitions and is included in the 55.0.0 release. Hardware and absolute numbers will vary, but the shape of the curve is the point.
Fresh numbers on a released build¶
I re-ran the same shape on DataFusion 55.2.0: the exact h2o group-by Q8
query, 10M rows, K = 2, in-memory data, min of 4 runs on a single desktop
machine. Compare the shape, not the absolutes, with the table above:
| Partitions | Rows/partition | Enabled | Disabled | Enabled/Disabled |
|---|---|---|---|---|
| 100 | 100,000 | 79 ms | 342 ms | 0.23x (4.3x faster) |
| 1,000 | 10,000 | 92 ms | 610 ms | 0.15x (6.6x faster) |
| 5,000 | 2,000 | 124 ms | 848 ms | 0.15x (6.8x faster) |
| 10,000 | 1,000 | 159 ms | 885 ms | 0.18x (5.6x faster) |
| 20,000 | 500 | 205 ms | 791 ms | 0.26x (3.9x faster) |
| 50,000 | 200 | 416 ms | 500 ms | 0.83x (≈ parity) |
| 60,000 | ~167 | 454 ms | 289 ms | 1.57x (regression) |
| 100,000 | 100 | 699 ms | 530 ms | 1.32x (regression) |
| 150,000 | ~67 | 944 ms | 566 ms | 1.67x (regression) |
The crossover sits between ~50K and ~60K partitions — roughly 150–200 rows
per partition at K = 2. Past that the rewrite loses ground for two
reasons:
- Per-partition overhead grows linearly with P. Every row probes the hash map of P partition states; every distinct key owns a heap and a hash-map entry; the emit step sorts all P keys once, O(P log P). The enabled plan costs roughly 5–6 µs per distinct partition key, while the sort baseline stays roughly flat in P. The regression starts where the two curves cross.
PartitionedTopKExechas no spill path. SortExec degrades gracefully: excess data goes to disk. The heaps must hold O(K × P × row_size) in memory, and when the memory reservation cannot grow, the query fails rather than spills. The window operator on top pays ~4 µs per partition (417 µs at P=100 → 418 ms at P=100K) even though it only touches the 2×P surviving rows.
Per-partition bookkeeping grows linearly with the number of distinct keys, while the sort it replaces costs O(N log N) regardless of P. The rewrite wins while each partition still holds enough rows for the heaps to pay for themselves, and loses when they don't. That is why the feature is behind a flag rather than always-on; the configuration documentation reaches the same conclusion: the optimization helps with low-cardinality window partition keys, while high-cardinality keys can regress both memory usage and runtime.
Both follow-up optimizations from the #21479 era have since shipped:
#23096 (shared encoder and memory reservation) is part of the 55.0.0
release, and #24591 reduced RANK memory from O(input) to O(K + ties).
Status and Roadmap¶
As of DataFusion 55.0.0:
ROW_NUMBERandRANKare supported, opt-in viadatafusion.optimizer.enable_window_topn.DENSE_RANKsupport has landed on the main branch (#23869) and is expected in an upcoming release.- The optimization is not yet enabled by default. Work to flip the default is tracked in the enable-by-default EPIC (#27197 is the change itself, open at the time of writing).
Remaining Work¶
There is active work to extend and harden the optimization; good places to jump in:
- Further "per partition" top-k optimizations — the umbrella for the next round of improvements.
- Support filters with embedded projections — widen the set of queries the rule recognizes.
- Memory-efficient dedup on wide payloads — the
ROW_NUMBER() = 1/DISTINCT ONdedup pattern. - Utf8View buffers kept alive by retained rows — memory footprint when string columns are present.
Acknowledgements¶
This feature was implemented by @SubhamSinghal across a long series of patches, with reviews from @2010YOUY01 and @kosiew. @jayzhan211 drove the memory optimizations, and further contributions came from @saadtajwar, @stuhood, @viirya, and @zhuqi-lucas. The original feature request was filed in 2023 (#6899), and the draft this post is based on was written by @alamb for the DataFusion 55 announcement.
Get Involved¶
- Try it out: run your "top N per group" queries with
datafusion.optimizer.enable_window_topn = trueon DataFusion 55 and compareEXPLAIN ANALYZEoutput. If you hit the high-cardinality cliff, please report it — those numbers drive the remaining optimization work. - Work on a good first issue, or pick up one of the remaining work items above.
- File issues or join the conversation: GitHub for bugs and feature requests, Slack or Discord for discussion.
- Learn more by visiting the DataFusion project page.
References¶
- Original feature request (2023): #6899
- Introducing
PartitionedTopKExecand theWindowTopNrule (ROW_NUMBER): #21479 RANKsupport: #22885DENSE_RANKsupport (main): #23869- Shared encoder and memory reservation across partitions: #23096
RANKmemory from O(input) to O(K + ties): #24591- Emit the rank column from the operator (main): #26133
- Enable-by-default EPIC: #24608 / #27197
- This post's ticket: #27233