Blog post about TopK per partition (`PartitionedTopKExec` / `enable_window_topn`)

未關閉
  • 哪裡不對？
#27,233 0 則留言 0 個 reaction 已指派 0 人 在 GitHub 檢視

維護者通常 1 天內回覆

還沒有人認領這個 Issue。

評估

難度
3/5
預估耗時
1-2 天
新手友好度
72/100
Issue 類型
文件
描述清晰度
描述清楚
活躍度
活躍
技術堆疊
rust, sql
領域
documentation

研究方向

Start with the draft in this issue and the linked DataFusion site pull request #203; use the referenced TopK per partition issues and pull requests to check behavior, implementation details, and whether the optimization is enabled by default for the target release. Write a self-contained post for the DataFusion blog using the suggested outline, examples, and related posts for style. Done means a site PR explains the use case, how the operator works and is used, implementation highlights, and remaining work.

由索引模型根據 Issue 內容生成。

描述

documentation enhancement
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

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:

The optimization landed in DataFusion 55 behind datafusion.optimizer.enable_window_topn, and the EPIC to turn it on by default is

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
  3. 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

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

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 / 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:
  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

Per-Partition TopK for Window Functions

A common analytics pattern selects the top N rows per group using a window
function:

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

Additional context

Tracking issues:

Core operator and optimizer rule:

Closing the high cardinality gap:

Correctness fixes and metrics:

Benchmarks:

Open follow on work:

Related prior posts for style / context:

主要語言
Rust
星號
9.6k
分支
2.6k
平均合併
3 天 4 小時
30 天內合併 PR
345

環境準備

在 Codespaces 中開啟

在瀏覽器裡用你自己的 GitHub 帳號啟動這個專案的開發容器。

從這裡開始

  1. 先讀完整個 Issue，再讀專案的貢獻指南。
  2. 在 Issue 下留言說明你要接手 —— 這能避免兩個人做同樣的事。
  3. Fork 儲存庫，在一個分支上完成修改。
  4. 送出 Pull Request，並在描述裡引用這個 Issue 編號。

apache/datafusion 的其他 Issue

查看 apache/datafusion 的全部 Issue

相似的 Issue

更多 Rust Issue

把新 issue 寄到你的電子郵件信箱

精選適合新手參與的 GitHub issue 摘要。