Top N Per Group with PartitionedTopKExec in Apache DataFusion

Posted on: Fri 13 November 2026 by Vadim Lazuk

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:

  1. SortExec sorts the entire dataset by (category, revenue). The window function needs each partition's rows contiguous and in ORDER BY order, 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.

  2. BoundedWindowAggExec computes ROW_NUMBER for 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.

  3. FilterExec keeps only the rows with rn <= 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_NUMBER numbers rows 1, 2, 3, ... with no ties, so exactly K rows per partition suffice.
  • RANK gives tied rows the same rank and skips subsequent ranks, so WHERE rk <= K must 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 what RANK means.
  • DENSE_RANK gives 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_NUMBER or RANK (in DataFusion 55; see Status and Roadmap for DENSE_RANK).
  • The window has a PARTITION BY clause. A global top-N without partitioning is already handled efficiently by SortExec with a fetch limit.
  • For RANK: the window has a non-empty ORDER BY clause (with an empty ORDER 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, or K > 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.
  • PartitionedTopKExec has 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_NUMBER and RANK are supported, opt-in via datafusion.optimizer.enable_window_topn.
  • DENSE_RANK support 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:

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 = true on DataFusion 55 and compare EXPLAIN ANALYZE output. 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 PartitionedTopKExec and the WindowTopN rule (ROW_NUMBER): #21479
  • RANK support: #22885
  • DENSE_RANK support (main): #23869
  • Shared encoder and memory reservation across partitions: #23096
  • RANK memory 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

Comments