Repository navigation
Commit 36f3935
authored
fix: WindowTopN resolves the filter column through intermediate proje… (apache#26417)
## Which issue does this PR close?
- Closes apache#26416
- Part of apache#24608.
## Rationale for this change
With `datafusion.optimizer.enable_window_topn = true`, some top-K window
queries return wrong results:
SELECT pk, id, rn, rk FROM (
SELECT pk, v, id,
row_number() OVER (PARTITION BY pk ORDER BY v) AS rn,
rank() OVER (PARTITION BY pk ORDER BY v) AS rk
FROM t)
WHERE rk <= 1;
returns only one row per partition and drops the rows tied at `rk = 1`.
With the two functions swapped and
`WHERE rn <= 1`, it returns rows with `rn = 2`.
`WindowTopN` reads the filter's column index from the predicate, which
indexes the projection between the
filter and the window, and used it as if it indexed the window's output.
When that projection drops a column
(here `v`, which the outer query doesn't select), every later index
shifts down by one. With two ranking
functions the rule then builds `PartitionedTopKExec` from the wrong one,
and since it also removes the
`FilterExec`, nothing corrects the result.
With a single ranking function, the same shifted index made the rule
decline instead. So queries such as
`row_number() OVER (PARTITION BY pk ORDER BY v, s)` with `s` unused
afterwards never got the optimization.
## What changes are included in this PR?
- New `column_index_below`, which maps the filter's column index down
through the nodes `find_window_below`
walks: a `ProjectionExec` must pass the column through as a bare
`Column`, and the index follows it; a
`RepartitionExec` leaves it unchanged; a column the projection computes
(e.g. `rk + 1`) makes the rule decline.
- `try_transform` resolves the index before checking that it names a
window column. Everything after that
already reads the resolved window expression.
- The rule's doc comment lists the new condition.
## What is the testing strategy for this PR?
`window_topn.slt`, each case checking both the rows (identical to
`enable_window_topn = false`) and the
`fn=` in `EXPLAIN`:
- the two wrong-result queries above (`fn=rank`, `fn=row_number`), and a
`dense_rank()` variant;
- `row_number() OVER (PARTITION BY pk ORDER BY v, id)` with `v` dropped
by the outer query, which is now
rewritten;
- `rank() OVER (...) + 1 AS x ... WHERE x <= 2`, which is still not
rewritten: filter pushdown moves the
expression into the predicate.
`core/tests/physical_optimizer/window_topn.rs`, with hand-built plans
for shapes the default optimizer pipeline doesn't produce but the rule
accepts:
- two stacked projections, which only resolve correctly top-down;
- a projection over a `RepartitionExec` (the rule runs before
`EnsureRequirements` inserts any);
- a column the projection computes, e.g. `rk + 1`: unchanged plan.
## Are there any user-facing changes?
With `enable_window_topn = true`, the affected queries now return
correct results, and more query shapes are
rewritten to `PartitionedTopKExec`. That includes `dense_rank()`, whose
memory use is tracked in #.
No API changes. The option is off by default.1 parent 6aef019 commit 36f3935
3 files changed
Lines changed: 346 additions & 5 deletions
File tree
- datafusion
- core/tests/physical_optimizer
- physical-optimizer/src
- sqllogictest/test_files
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
46 | 46 | | |
47 | 47 | | |
48 | 48 | | |
49 | | - | |
| 49 | + | |
| 50 | + | |
| 51 | + | |
| 52 | + | |
50 | 53 | | |
51 | 54 | | |
52 | | - | |
| 55 | + | |
53 | 56 | | |
54 | 57 | | |
55 | 58 | | |
| |||
458 | 461 | | |
459 | 462 | | |
460 | 463 | | |
| 464 | + | |
| 465 | + | |
| 466 | + | |
| 467 | + | |
| 468 | + | |
| 469 | + | |
| 470 | + | |
| 471 | + | |
| 472 | + | |
| 473 | + | |
| 474 | + | |
| 475 | + | |
| 476 | + | |
| 477 | + | |
| 478 | + | |
| 479 | + | |
| 480 | + | |
| 481 | + | |
| 482 | + | |
| 483 | + | |
| 484 | + | |
| 485 | + | |
| 486 | + | |
| 487 | + | |
| 488 | + | |
| 489 | + | |
| 490 | + | |
| 491 | + | |
| 492 | + | |
| 493 | + | |
| 494 | + | |
| 495 | + | |
| 496 | + | |
| 497 | + | |
| 498 | + | |
| 499 | + | |
| 500 | + | |
| 501 | + | |
| 502 | + | |
| 503 | + | |
| 504 | + | |
| 505 | + | |
| 506 | + | |
| 507 | + | |
| 508 | + | |
| 509 | + | |
| 510 | + | |
| 511 | + | |
| 512 | + | |
| 513 | + | |
| 514 | + | |
| 515 | + | |
| 516 | + | |
| 517 | + | |
| 518 | + | |
| 519 | + | |
| 520 | + | |
| 521 | + | |
| 522 | + | |
| 523 | + | |
| 524 | + | |
| 525 | + | |
| 526 | + | |
| 527 | + | |
| 528 | + | |
| 529 | + | |
| 530 | + | |
| 531 | + | |
| 532 | + | |
| 533 | + | |
| 534 | + | |
| 535 | + | |
| 536 | + | |
| 537 | + | |
| 538 | + | |
| 539 | + | |
| 540 | + | |
| 541 | + | |
| 542 | + | |
| 543 | + | |
| 544 | + | |
| 545 | + | |
| 546 | + | |
| 547 | + | |
| 548 | + | |
| 549 | + | |
| 550 | + | |
| 551 | + | |
| 552 | + | |
| 553 | + | |
| 554 | + | |
| 555 | + | |
| 556 | + | |
| 557 | + | |
| 558 | + | |
| 559 | + | |
| 560 | + | |
| 561 | + | |
| 562 | + | |
| 563 | + | |
| 564 | + | |
| 565 | + | |
| 566 | + | |
| 567 | + | |
| 568 | + | |
| 569 | + | |
| 570 | + | |
| 571 | + | |
| 572 | + | |
| 573 | + | |
| 574 | + | |
| 575 | + | |
| 576 | + | |
| 577 | + | |
| 578 | + | |
| 579 | + | |
| 580 | + | |
| 581 | + | |
| 582 | + | |
| 583 | + | |
| 584 | + | |
| 585 | + | |
| 586 | + | |
| 587 | + | |
| 588 | + | |
| 589 | + | |
| 590 | + | |
| 591 | + | |
| 592 | + | |
| 593 | + | |
| 594 | + | |
| 595 | + | |
| 596 | + | |
| 597 | + | |
| 598 | + | |
| 599 | + | |
| 600 | + | |
| 601 | + | |
| 602 | + | |
| 603 | + | |
| 604 | + | |
| 605 | + | |
| 606 | + | |
461 | 607 | | |
462 | 608 | | |
463 | 609 | | |
| |||
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
122 | 122 | | |
123 | 123 | | |
124 | 124 | | |
| 125 | + | |
| 126 | + | |
| 127 | + | |
125 | 128 | | |
126 | 129 | | |
127 | 130 | | |
| |||
193 | 196 | | |
194 | 197 | | |
195 | 198 | | |
196 | | - | |
| 199 | + | |
| 200 | + | |
| 201 | + | |
| 202 | + | |
197 | 203 | | |
198 | 204 | | |
199 | 205 | | |
| |||
455 | 461 | | |
456 | 462 | | |
457 | 463 | | |
458 | | - | |
459 | | - | |
| 464 | + | |
| 465 | + | |
| 466 | + | |
| 467 | + | |
460 | 468 | | |
461 | 469 | | |
462 | 470 | | |
| |||
478 | 486 | | |
479 | 487 | | |
480 | 488 | | |
| 489 | + | |
| 490 | + | |
| 491 | + | |
| 492 | + | |
| 493 | + | |
| 494 | + | |
| 495 | + | |
| 496 | + | |
| 497 | + | |
| 498 | + | |
| 499 | + | |
| 500 | + | |
| 501 | + | |
| 502 | + | |
| 503 | + | |
| 504 | + | |
| 505 | + | |
| 506 | + | |
| 507 | + | |
| 508 | + | |
| 509 | + | |
| 510 | + | |
| 511 | + | |
| 512 | + | |
| 513 | + | |
0 commit comments