Repository navigation
Commit 503ceef
fix: end a sort-merge join partition once its streamed side is exhausted, and release its reservations before the final output (apache#25206)
## Which issue does this PR close?
- Closes apache#25205.
## Rationale for this change
A sort-merge join partition whose streamed side is empty still fetches,
sorts and scans its entire buffered side, because the stream loads a key
group from the buffered input before comparing anything and merge-scans
until both inputs are exhausted. Only a Full join can emit buffered rows
without a streamed match, so for every other join type that work
produces nothing. On a hash-partitioned join of a large table against a
sparse one, most partitions look like this: in the production job that
motivated this, 1,371 of 2,000 partitions had an empty streamed side,
and the join consumed 6,231,306,982 buffered rows to emit 6,144, taking
456 s for the stage where Spark, whose `SortMergeJoinExec` exits as soon
as the streamed side is empty, took 194 s. The symmetric case, an Inner
join whose buffered side is exhausted with no key group left, drains and
drops the remaining streamed rows for the same reason.
## What changes are included in this PR?
The materializing stream (Inner/Left/Right/Full) gets a `finished()`
predicate that replaces "both inputs exhausted" as the loop condition:
an exhausted streamed side finishes every join but Full, and an
exhausted buffered side finishes an Inner join. The first buffered key
group is only loaded when the join is not already finished, so an empty
streamed partition never polls the buffered input, and the `SortExec`
beneath it never runs. `on_children_exhausted` now releases both inputs
and every remaining buffered key group right after freezing the pending
pairs, so the memory the join reserved is back in the pool before its
final batches are emitted rather than when the stream is dropped;
without that, a parent operator processing the final batch can fail with
`ResourcesExhausted` against a reservation the finished child still
holds. The bitwise stream (Semi/Anti/Mark) already returns on an empty
outer side; it now also stops draining the outer side for Semi joins
once the inner side is exhausted, since the remaining rows cannot be
emitted.
## Are these changes tested?
New tests in `joins/sort_merge_join/tests.rs`:
- `join_empty_streamed_side_never_polls_buffered_side` drives the
buffered side with `PanicExec`, so it passes only if that input is never
polled, for Inner/Left/LeftSemi/LeftAnti/LeftMark and the mirrored
Right/RightSemi/RightAnti. It fails on `main` with the `PanicExec`
panic.
- `join_full_empty_left_still_emits_buffered_rows` pins that Full still
emits the buffered rows.
- `join_inner_and_semi_finish_once_buffered_side_is_exhausted` covers
the Inner and Semi exit and that Anti still emits the unmatched streamed
rows.
- `join_left_releases_buffered_reservation_before_final_batch` asserts
the pool holds no reservation when the final batch is returned, and
`join_chain_reuses_memory_released_by_completed_child` runs a two-join
plan under a 2 MB pool with spilling disabled, which fails with
`ResourcesExhausted` if the child keeps its reservation.
All existing `joins::sort_merge_join` tests pass.
## Are there any user-facing changes?
No API or result changes. Sort-merge joins read less input in the cases
above, and their `input_rows` metric drops accordingly.1 parent 5250ff9 commit 503ceef
3 files changed
Lines changed: 253 additions & 11 deletions
File tree
- datafusion/physical-plan/src/joins/sort_merge_join
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
1053 | 1053 | | |
1054 | 1054 | | |
1055 | 1055 | | |
| 1056 | + | |
| 1057 | + | |
| 1058 | + | |
| 1059 | + | |
| 1060 | + | |
1056 | 1061 | | |
1057 | 1062 | | |
1058 | 1063 | | |
| |||
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
616 | 616 | | |
617 | 617 | | |
618 | 618 | | |
619 | | - | |
| 619 | + | |
| 620 | + | |
| 621 | + | |
620 | 622 | | |
621 | | - | |
622 | | - | |
| 623 | + | |
| 624 | + | |
623 | 625 | | |
624 | 626 | | |
625 | 627 | | |
| |||
844 | 846 | | |
845 | 847 | | |
846 | 848 | | |
847 | | - | |
| 849 | + | |
| 850 | + | |
| 851 | + | |
| 852 | + | |
| 853 | + | |
| 854 | + | |
| 855 | + | |
| 856 | + | |
| 857 | + | |
| 858 | + | |
| 859 | + | |
| 860 | + | |
| 861 | + | |
| 862 | + | |
| 863 | + | |
| 864 | + | |
| 865 | + | |
| 866 | + | |
| 867 | + | |
| 868 | + | |
| 869 | + | |
| 870 | + | |
| 871 | + | |
| 872 | + | |
| 873 | + | |
| 874 | + | |
848 | 875 | | |
849 | 876 | | |
850 | 877 | | |
851 | 878 | | |
852 | | - | |
| 879 | + | |
| 880 | + | |
853 | 881 | | |
854 | 882 | | |
| 883 | + | |
855 | 884 | | |
856 | 885 | | |
857 | 886 | | |
| |||
1073 | 1102 | | |
1074 | 1103 | | |
1075 | 1104 | | |
| 1105 | + | |
| 1106 | + | |
| 1107 | + | |
| 1108 | + | |
| 1109 | + | |
| 1110 | + | |
| 1111 | + | |
| 1112 | + | |
| 1113 | + | |
| 1114 | + | |
| 1115 | + | |
1076 | 1116 | | |
1077 | 1117 | | |
1078 | 1118 | | |
| |||
1206 | 1246 | | |
1207 | 1247 | | |
1208 | 1248 | | |
1209 | | - | |
| 1249 | + | |
1210 | 1250 | | |
1211 | | - | |
1212 | | - | |
1213 | | - | |
1214 | | - | |
1215 | 1251 | | |
1216 | 1252 | | |
1217 | 1253 | | |
| |||
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
37 | 37 | | |
38 | 38 | | |
39 | 39 | | |
40 | | - | |
| 40 | + | |
41 | 41 | | |
42 | 42 | | |
43 | 43 | | |
| |||
527 | 527 | | |
528 | 528 | | |
529 | 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 | + | |
| 607 | + | |
| 608 | + | |
| 609 | + | |
| 610 | + | |
| 611 | + | |
| 612 | + | |
| 613 | + | |
| 614 | + | |
| 615 | + | |
| 616 | + | |
| 617 | + | |
| 618 | + | |
| 619 | + | |
| 620 | + | |
| 621 | + | |
| 622 | + | |
| 623 | + | |
| 624 | + | |
| 625 | + | |
| 626 | + | |
| 627 | + | |
| 628 | + | |
| 629 | + | |
| 630 | + | |
| 631 | + | |
| 632 | + | |
| 633 | + | |
| 634 | + | |
| 635 | + | |
| 636 | + | |
| 637 | + | |
| 638 | + | |
| 639 | + | |
| 640 | + | |
| 641 | + | |
| 642 | + | |
| 643 | + | |
| 644 | + | |
| 645 | + | |
| 646 | + | |
| 647 | + | |
| 648 | + | |
| 649 | + | |
| 650 | + | |
| 651 | + | |
| 652 | + | |
| 653 | + | |
| 654 | + | |
| 655 | + | |
| 656 | + | |
| 657 | + | |
| 658 | + | |
| 659 | + | |
| 660 | + | |
| 661 | + | |
| 662 | + | |
| 663 | + | |
| 664 | + | |
| 665 | + | |
| 666 | + | |
| 667 | + | |
| 668 | + | |
| 669 | + | |
| 670 | + | |
| 671 | + | |
| 672 | + | |
| 673 | + | |
| 674 | + | |
| 675 | + | |
| 676 | + | |
| 677 | + | |
| 678 | + | |
| 679 | + | |
| 680 | + | |
| 681 | + | |
| 682 | + | |
| 683 | + | |
| 684 | + | |
| 685 | + | |
| 686 | + | |
| 687 | + | |
| 688 | + | |
| 689 | + | |
| 690 | + | |
| 691 | + | |
| 692 | + | |
| 693 | + | |
| 694 | + | |
| 695 | + | |
| 696 | + | |
| 697 | + | |
| 698 | + | |
| 699 | + | |
| 700 | + | |
| 701 | + | |
| 702 | + | |
| 703 | + | |
| 704 | + | |
| 705 | + | |
| 706 | + | |
| 707 | + | |
| 708 | + | |
| 709 | + | |
| 710 | + | |
| 711 | + | |
| 712 | + | |
| 713 | + | |
| 714 | + | |
| 715 | + | |
| 716 | + | |
| 717 | + | |
| 718 | + | |
| 719 | + | |
| 720 | + | |
| 721 | + | |
| 722 | + | |
| 723 | + | |
| 724 | + | |
| 725 | + | |
| 726 | + | |
| 727 | + | |
| 728 | + | |
| 729 | + | |
| 730 | + | |
530 | 731 | | |
531 | 732 | | |
532 | 733 | | |
| |||
0 commit comments