Repository navigation
Commit 20a4629
authored
perf: Partitioned topk emit row number (apache#26133)
## Which issue does this PR close?
- Part of [apache#24608](apache#24608)
## Rationale for this change
With `enable_window_topn`, `WindowTopN` rewrites `Filter(rn <= K) →
BoundedWindowAggExec → SortExec` into:
```text
BoundedWindowAggExec: row_number() PARTITION BY [pk] ORDER BY [val], mode=Sorted
PartitionedTopKExec: fn=row_number, fetch=2, partition=[pk], order=[val ASC]
```
The window node stays only to produce `rn`, but the operator already
knows every retained row's rank when it emits it: rows leave in
`(partition keys, order keys)` order, and the retained set is exactly
the rows with rank ≤ K. The node's cost scales with the operator's
output (K × partitions) and never amortizes, because every batch it sees
is dense in partition boundaries.
## What changes are included in this PR?
- `PartitionedTopKExec::try_new` takes `ranking_field:
Option<FieldRef>`. When set, the operator appends a `UInt64` column with
each row's rank, and `WindowTopN` drops the window node:
```text
PartitionedTopKExec: fn=row_number, fetch=2, partition=[pk], order=[val
ASC], emit=[rn]
```
- Each policy derives the rank from what it already holds. `ROW_NUMBER`:
position in the partition's drain. `RANK`: position of the first row
with the same key; boundary ties take the boundary key's. `DENSE_RANK`:
index of the distinct-key group. All three rely on the retained set
being a complete order-prefix of its partition.
- Applied only when the window node has exactly one expression, since
the operator appends one column. Otherwise the node is kept, as today.
The output schema is the node's (input fields plus that field), so
column indices above are unchanged and `schema_check()` holds.
- `compute_properties` declares the ordering the removed node published,
`[partition keys..., rank ASC NULLS LAST]`, so `ORDER BY pk, rn` stays
sort-free.
## Are these changes tested?
- `topk/mod.rs`: the rank column for each policy, including boundary
ties, an eviction that moves a row to the tie list, a `DENSE_RANK` group
gathered from several input batches, and output spanning several
`batch_size` chunks.
- `sorts/partitioned_topk.rs`: the widened schema, and the `[pk, rn]`
ordering (but not `[rn]` alone).
- `core/tests/physical_optimizer/window_topn.rs`: the node is removed
for one expression and kept for two; `ORDER BY pk, rn` plans no
`SortExec` for all three functions; end to end, the emitted column
equals the flag-off result (ties, 4 partitions, batch size 4).
- `window_topn.slt` and `range_partitioning.slt`: EXPLAIN output
updated, query results unchanged.
## Benchmark
h2o `window.sql` k=2 sweeps on `J1_1e7_1e7_NA.parquet` (10 M rows, 14
partitions), `enable_window_topn = true` in both arms.
| partitions | `ROW_NUMBER` | `RANK` | `DENSE_RANK` |
|---|---|---|---|
| 100 | 0.037 → 0.035 s (1.06×) | 0.036 → 0.037 s (0.97×) | 0.037 →
0.037 s (1.00×) |
| 1 K | 0.036 → 0.035 s (1.03×) | 0.038 → 0.039 s (0.97×) | 0.040 →
0.040 s (1.00×) |
| 10 K | 0.041 → 0.038 s (1.08×) | 0.034 → 0.032 s (1.06×) | 0.047 →
0.044 s (1.07×) |
| 100 K | **0.075 → 0.050 s (1.50×)** | **0.092 → 0.060 s (1.53×)** |
**0.147 → 0.118 s (1.25×)** |
## Are there any user-facing changes?
Only with enable_window_topn (default false): EXPLAIN no longer shows
the window node for single-expression ranking queries, and
PartitionedTopKExec shows emit=[...]. Results for the built-in functions
are unchanged.
A user-defined window function registered as row_number, rank or
dense_rank is no longer rewritten. WindowTopN used to match these
functions by name; it now compares the WindowUDF with the built-in
(row_number_udwf(), rank_udwf(), dense_rank_udwf()). Without this, the
operator's column would replace the custom evaluator's output, or the
query would fail at execution if the return type isn't UInt64. On main,
such a function already had its input pruned.
datafusion-functions-window becomes a regular dependency of
datafusion-physical-optimizer.
No breaking API change: PartitionedTopKExec::try_new keeps its
signature. with_ranking_field() and ranking_field() are new public
methods.1 parent d5f5ad4 commit 20a4629
8 files changed
Lines changed: 1499 additions & 338 deletions
File tree
- datafusion
- core/tests/physical_optimizer
- physical-optimizer
- src
- physical-plan/src
- sorts
- topk
- sqllogictest/test_files
Large diffs are not rendered by default.
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
46 | 46 | | |
47 | 47 | | |
48 | 48 | | |
| 49 | + | |
49 | 50 | | |
50 | 51 | | |
51 | 52 | | |
| |||
57 | 58 | | |
58 | 59 | | |
59 | 60 | | |
60 | | - | |
61 | 61 | | |
62 | 62 | | |
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
124 | 124 | | |
125 | 125 | | |
126 | 126 | | |
127 | | - | |
128 | | - | |
| 127 | + | |
| 128 | + | |
| 129 | + | |
| 130 | + | |
129 | 131 | | |
130 | 132 | | |
131 | 133 | | |
| |||
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
36 | 36 | | |
37 | 37 | | |
38 | 38 | | |
39 | | - | |
40 | | - | |
| 39 | + | |
| 40 | + | |
| 41 | + | |
| 42 | + | |
41 | 43 | | |
42 | 44 | | |
43 | 45 | | |
| |||
56 | 58 | | |
57 | 59 | | |
58 | 60 | | |
| 61 | + | |
| 62 | + | |
59 | 63 | | |
60 | 64 | | |
61 | 65 | | |
| |||
85 | 89 | | |
86 | 90 | | |
87 | 91 | | |
88 | | - | |
| 92 | + | |
| 93 | + | |
| 94 | + | |
| 95 | + | |
| 96 | + | |
| 97 | + | |
| 98 | + | |
| 99 | + | |
| 100 | + | |
89 | 101 | | |
90 | 102 | | |
91 | 103 | | |
92 | | - | |
93 | | - | |
94 | | - | |
95 | | - | |
96 | | - | |
| 104 | + | |
| 105 | + | |
| 106 | + | |
| 107 | + | |
| 108 | + | |
| 109 | + | |
| 110 | + | |
| 111 | + | |
97 | 112 | | |
98 | 113 | | |
99 | 114 | | |
| |||
233 | 248 | | |
234 | 249 | | |
235 | 250 | | |
236 | | - | |
| 251 | + | |
| 252 | + | |
| 253 | + | |
| 254 | + | |
| 255 | + | |
| 256 | + | |
| 257 | + | |
| 258 | + | |
| 259 | + | |
| 260 | + | |
| 261 | + | |
| 262 | + | |
| 263 | + | |
| 264 | + | |
| 265 | + | |
237 | 266 | | |
238 | 267 | | |
239 | 268 | | |
240 | 269 | | |
241 | 270 | | |
242 | 271 | | |
243 | 272 | | |
244 | | - | |
245 | | - | |
246 | | - | |
247 | | - | |
| 273 | + | |
| 274 | + | |
| 275 | + | |
248 | 276 | | |
| 277 | + | |
| 278 | + | |
| 279 | + | |
| 280 | + | |
| 281 | + | |
| 282 | + | |
| 283 | + | |
| 284 | + | |
| 285 | + | |
| 286 | + | |
| 287 | + | |
| 288 | + | |
| 289 | + | |
| 290 | + | |
| 291 | + | |
249 | 292 | | |
250 | 293 | | |
251 | 294 | | |
| |||
362 | 405 | | |
363 | 406 | | |
364 | 407 | | |
365 | | - | |
366 | | - | |
367 | | - | |
368 | | - | |
369 | | - | |
| 408 | + | |
| 409 | + | |
| 410 | + | |
| 411 | + | |
| 412 | + | |
370 | 413 | | |
| 414 | + | |
| 415 | + | |
| 416 | + | |
| 417 | + | |
| 418 | + | |
371 | 419 | | |
372 | 420 | | |
373 | 421 | | |
374 | 422 | | |
375 | 423 | | |
376 | 424 | | |
377 | | - | |
378 | | - | |
379 | | - | |
380 | | - | |
381 | | - | |
| 425 | + | |
| 426 | + | |
| 427 | + | |
| 428 | + | |
| 429 | + | |
| 430 | + | |
| 431 | + | |
| 432 | + | |
| 433 | + | |
382 | 434 | | |
383 | 435 | | |
384 | 436 | | |
| |||
0 commit comments