alamb opened a new issue, #24608: URL: https://github.com/apache/datafusion/issues/24608
### Is your feature request related to a problem or challenge? While writing the [DataFusion 55.0.0 blog post](https://github.com/apache/datafusion/issues/24216) I wrote up the per-partition TopK window optimization as one of the headline performance improvements of the release — and only then discovered that `datafusion.optimizer.enable_window_topn` **defaults to `false`**, so nobody actually gets it unless they opt in. I pulled the section from the post. That is a shame, because it is a genuinely great optimization with a great story, built over several releases by a bunch of people. But we can't tell users about a feature that is off by default, and I could not find any issue tracking turning it on. Filing this so we don't forget, and so the remaining blockers live in one place rather than scattered across PR review threads. #### The story we want to be able to tell This is the text I had drafted for the 55.0.0 blog post before pulling it, included so it's clear what we're aiming for and so whoever finishes this work can reuse it: > ### Per-Partition TopK for Window Functions > > A common analytics pattern selects the top N rows per group using a window > function: > > ```sql > 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 #### Why it is currently off `datafusion/common/src/config.rs`: ```rust /// When set to true, the optimizer will replace Filter(rn<=K) → Window(ROW_NUMBER) → Sort /// patterns with a PartitionedTopKExec that maintains per-partition heaps, avoiding /// a full sort of the input. /// When the window partition key has low cardinality, enabling this optimization /// can improve performance. However, for high cardinality keys, it may /// cause regressions in both memory usage and runtime. pub enable_window_topn: bool, default = false ``` The default was set to `false` in #21479 because of severe high-cardinality regressions against the plain-sort baseline: | Partitions | Enabled | Disabled | Speedup | |---|---:|---:|---:| | 100 (100K rows/part) | 43 ms | 174 ms | **4.0x faster** | | 1K (10K rows/part) | 71 ms | 146 ms | **2.1x faster** | | 10K (1K rows/part) | 619 ms | 128 ms | 0.2x — regression | | 100K (100 rows/part) | 4368 ms | 135 ms | 0.03x — regression | > If it has regressions as large as `0.03x` it should [be] off by default (and > we should look if we can automatically enable it via a heuristic / stats based > on partition cardinality / rows) > — @Dandandan, https://github.com/apache/datafusion/pull/21479#issuecomment-4221809099 #23096 (in 55.0.0) closed most of that gap by sharing the encoder and memory reservation across partitions: | Partitions | `main` | with #23096 | vs sort baseline | |---|---:|---:|---| | 100 | 110 ms | 105 ms | ~1.0x | | 1,000 | 117 ms | 110 ms | ~1.0x | | 10,000 | 640 ms | 137 ms | **1.7x faster than sort** (was a regression) | | 100,000 | 4,327 ms | 320 ms | 320 ms vs 238 ms — still slower | but explicitly did not flip the default: > `enable_window_topn` default stays `false` per the #21479 discussion — 100K+ > remains slower than sort on average, so this PR doesn't motivate flipping the > default. It's the prerequisite for further optimizations that would attack the > residual 100K+ cliff. > — #23096 ### Describe the solution you'd like Set `enable_window_topn` to `true` by default, once we are confident it does not regress. Known work items: - [ ] **Close the high-cardinality cliff.** 100K partitions is still slower than a plain sort (320 ms vs 238 ms). Either optimize further, or add a cardinality/statistics-based heuristic so the rewrite only fires when it wins — @Dandandan's original suggestion in #21479. - [ ] **Fix RANK memory blowup** — #24591: `PartitionedTopKRank` retains O(input) rather than O(K + ties), reporting ~35x the real cost and failing with `Resources exhausted` on input where the same query written with `ROW_NUMBER` succeeds. - [ ] **Fix wide-payload OOM** — the #23600 epic measured an OOM against a 16 GB pool even with `K = 1`, due to `#groups × K × wide_row` scaling. - [ ] **Expose metrics** — #24470: `PartitionedTopKExec::metrics()` returns `None`, so we can't see what the operator is doing in `EXPLAIN ANALYZE`. Hard to justify on-by-default without observability. (PR: #24495) - [ ] **Broaden pattern coverage** — #21596 / #23599: `FilterExec` with an embedded projection isn't matched, so the optimization silently doesn't fire on common plan shapes. - [ ] **Benchmark coverage in CI** so a default flip is backed by the standard benchmark suite rather than ad-hoc runs. #24050 added a `dense_rank` benchmark; we should make sure the sweep covers the partition-cardinality range where the cliff lives. - [ ] Flip the default, run the full benchmark suite, and update `docs/source/user-guide/configs.md`. ### Describe alternatives you've considered **Leave it opt-in indefinitely.** I don't love this: an optimization nobody turns on is close to an optimization that doesn't exist, and it means the substantial work in #21479, #22885, #23096, #23355, and #24191 never reaches users. **Enable it via a heuristic instead of a flag.** Rather than a global default, have the optimizer consult partition-cardinality statistics and only rewrite when the estimate says it wins. This is arguably the better end state and would sidestep the 100K cliff entirely, but it depends on having usable cardinality estimates at that point in physical optimization. ### Additional context #24404 (panic on `WHERE rn < 1`) was fixed in #24405, but that landed after the `branch-55` cut, so 55.0.0 will panic on that input if the flag is enabled. Another reason it was right to leave this out of the 55.0.0 blog post. Related: #6899 (original 2023 request), #21479, #22885, #23096, #23355, #24191, #23600, #24470, #24591. -- This is an automated message from the Apache Git Service. To respond to the message, please log on to GitHub and use the URL above to go to the specific comment. To unsubscribe, e-mail: [email protected] For queries about this service, please contact Infrastructure at: [email protected] --------------------------------------------------------------------- To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
