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

オープン
  • 何か問題がありますか？
#27,233 コメント 0 件 リアクション 0 件 担当者 0 名 GitHub で見る

メンテナーはふだん 1 日以内に返信

まだ誰も着手していません。

評価

難易度
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時間
マージ済み PR（30日）
345

環境構築

Codespaces で開く

このプロジェクトの開発コンテナを、あなたの GitHub アカウントでブラウザ上に起動します。

はじめの一歩

  1. issue を最後まで読み、次にプロジェクトのコントリビューションガイドを読みます。
  2. 着手することを issue にコメントします — 二人が同じ作業をするのを防げます。
  3. リポジトリをフォークし、ブランチを切って変更します。
  4. issue 番号を参照したプルリクエストを送ります。

apache/datafusion のほかの issue

apache/datafusion の issue をすべて見る

似ている issue

Rust の issue をもっと見る

新しい issue をメールで受け取る

初心者向けの GitHub issue を短くまとめたダイジェスト。