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

Offen
  • Stimmt etwas nicht?
#27,233 0 Kommentare 0 Reaktionen 0 zugewiesene Personen Auf GitHub ansehen

Maintainer antworten meist innerhalb von 1 Tag

Dieses Issue hat noch niemand übernommen.

Bewertung

Schwierigkeit
3/5
Geschätzter Aufwand
1-2 Tage
Anfängerfreundlichkeit
72/100
Issue-Typ
Dokumentation
Klarheit
Klar beschrieben
Aktivitätsstatus
Aktiv
Tech-Stack
rust, sql
Bereich
documentation

Rechercherichtung

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.

Vom Indexierungsmodell aus dem Issue-Text verfasst.

Beschreibung

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:

Vorherrschende Sprache
Rust
Sterne
9.6k
Forks
2.6k
Ø Merge
3 T. 4 Std.
Gemergte PRs (30 T.)
345

Entwicklungsumgebung

In Codespaces öffnen

Startet den Dev-Container des Projekts im Browser, mit Ihrem eigenen GitHub-Konto.

Erste Schritte

  1. Lesen Sie das ganze Issue und danach den Beitragsleitfaden des Projekts.
  2. Schreiben Sie ins Issue, dass Sie es übernehmen — das erspart doppelte Arbeit.
  3. Forken Sie das Repository und arbeiten Sie in einem Branch.
  4. Öffnen Sie einen Pull Request, der die Issue-Nummer nennt.

Mehr aus apache/datafusion

Alle Issues in apache/datafusion

Ähnliche Issues

Weitere Issues zu Rust

Neue Issues direkt in Ihr Postfach

Eine kurze Übersicht über anfängerfreundliche GitHub-Issues.