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

Abierto
  • ¿Algo no está bien?
#27,233 0 comentarios 0 reacciones 0 asignados Ver en GitHub

Los mantenedores suelen responder en 1 día

Nadie ha tomado este issue todavía.

Evaluación

Dificultad
3/5
Tiempo estimado
1-2 días
Aptitud para principiantes
72/100
Tipo de issue
Documentación
Claridad
Bien especificado
Estado de actividad
Activo
Stack tecnológico
rust, sql
Área
documentation

Línea de trabajo

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.

Escrito por el modelo de indexación a partir del texto del issue.

Descripción

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:

Lenguaje dominante
Rust
Estrellas
9.6k
Forks
2.6k
Merge medio
3 d 4 h
PR fusionados (30 d)
345

Preparar el entorno

Abrir en Codespaces

Inicia el contenedor de desarrollo del proyecto en tu navegador, con tu propia cuenta de GitHub.

Primeros pasos

  1. Lee el issue completo y luego la guía de contribución del proyecto.
  2. Comenta en el issue que vas a ocuparte — evita que dos personas hagan lo mismo.
  3. Haz un fork del repositorio y trabaja en una rama.
  4. Abre un pull request que haga referencia al número del issue.

Más de apache/datafusion

Todos los issues de apache/datafusion

Issues similares

Más issues de Rust

Recibe los nuevos issues en tu correo

Un resumen breve de issues de GitHub para principiantes.