Repository navigation
Commit e0d64fc
authored
fix: count buffers shared between sort input batches once (apache#25820)
## Which issue does this PR close?
- Part of apache#25804 (finding 5).
- Related to apache#22526.
## Rationale for this change
A grouped aggregate emits its output as zero-copy slices of one batch.
`SortExec` reserves every buffered batch's full buffer capacity, so each
slice is charged for the whole aggregate output. A sort after a `GROUP
BY` therefore reserves several times the memory it holds: it spills when
it doesn't need to, and with spilling disabled it fails with
`ResourcesExhausted`. For example, `select group_key, sum(payload) as s
from t group by group_key order by group_key` over 100,000 groups needs
a 24 MB memory limit on `main` and runs in 6 MB with this change.
## What changes are included in this PR?
- `ExternalSorter` counts its buffered batches with a
`RecordBatchMemoryCounter`, as apache#22862 did for the hash join build side,
so a buffer shared between batches is reserved once. Each batch still
reserves its sliced size for sorting it.
- When the buffered batches are sorted as separate runs and the runs
share buffers, the reservation for the runs' input is held until every
run is sorted, because a run still waiting to be sorted keeps the shared
buffers alive. Runs that share nothing release their input as soon as
they are sorted, as before.
- Coalescing batches into runs for single-column sorts sizes the batches
the same way.
- Schemas with view, dictionary or list view types keep reserving each
batch on its own. Sorting those types keeps referencing the input's data
buffers or values, and the sorted runs and the merge charge those
buffers once per run. Counting them once at insert would let a spill
take more runs than the merge can then hold
(`sort_spill_is_compacted_for_view_arrays` fails that way). Counting
them once needs the merge side to change too; see apache#25800 and apache#25791.
## What is the testing strategy for this PR?
- `sort_after_group_by_reserves_shared_output_once` in `memory_limit`
runs `GROUP BY ... ORDER BY` with one sort key and with two, under a 12
MB limit with spilling disabled. It fails on `main` with `Memory
Exhausted while Sorting` for either ordering.
- The `spill_tests` fixture now builds each batch separately. Its
batches were slices of one batch, and the tests relied on each slice
being charged for the whole batch to create memory pressure.
Benchmarks: `cargo bench -p datafusion --bench sort` with the
`release-nonlto` profile, running `main` and this PR alternately, median
of three runs:
| benchmark | `main` | this PR | change |
|---|---|---|---|
| sort i64 1M | 24.11 ms | 23.94 ms | -0.7% |
| sort partitioned i64 1M | 3.05 ms | 3.21 ms | +5.3% |
| sort utf8 high cardinality 1M | 59.54 ms | 60.72 ms | +2.0% |
| sort partitioned utf8 high cardinality 1M | 4.84 ms | 4.93 ms | +2.0%
|
| sort utf8 dictionary tuple 1M | 510.35 ms | 511.02 ms | +0.1% |
| sort partitioned utf8 dictionary tuple 1M | 10.44 ms | 10.65 ms |
+2.0% |
| sort mixed tuple 1M | 106.05 ms | 106.43 ms | +0.4% |
| sort partitioned mixed tuple 1M | 11.51 ms | 11.12 ms | -3.4% |
`sort partitioned i64 1M` was 5-12% slower across longer runs. The
difference comes from moving the shared reservation, empty in this
benchmark, into each run's sort future: a build that doesn't move it
matches `main`. The counting itself costs about 2 µs per partition. The
dictionary cases don't take the new path, which puts the noise at about
2%.
## Are there any user-facing changes?
Sorts over sliced input without view or dictionary columns, such as the
output of a grouped aggregate, reserve less memory and spill less. No
API changes.1 parent d173279 commit e0d64fc
3 files changed
Lines changed: 213 additions & 35 deletions
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
446 | 446 | | |
447 | 447 | | |
448 | 448 | | |
| 449 | + | |
| 450 | + | |
| 451 | + | |
| 452 | + | |
| 453 | + | |
| 454 | + | |
| 455 | + | |
| 456 | + | |
| 457 | + | |
| 458 | + | |
| 459 | + | |
| 460 | + | |
| 461 | + | |
| 462 | + | |
| 463 | + | |
| 464 | + | |
| 465 | + | |
| 466 | + | |
| 467 | + | |
| 468 | + | |
| 469 | + | |
| 470 | + | |
| 471 | + | |
| 472 | + | |
| 473 | + | |
| 474 | + | |
| 475 | + | |
| 476 | + | |
| 477 | + | |
| 478 | + | |
449 | 479 | | |
450 | 480 | | |
451 | 481 | | |
| |||
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
59 | 59 | | |
60 | 60 | | |
61 | 61 | | |
62 | | - | |
| 62 | + | |
63 | 63 | | |
64 | 64 | | |
| 65 | + | |
65 | 66 | | |
66 | 67 | | |
67 | 68 | | |
| |||
236 | 237 | | |
237 | 238 | | |
238 | 239 | | |
| 240 | + | |
| 241 | + | |
| 242 | + | |
| 243 | + | |
| 244 | + | |
| 245 | + | |
239 | 246 | | |
240 | 247 | | |
241 | 248 | | |
| |||
310 | 317 | | |
311 | 318 | | |
312 | 319 | | |
| 320 | + | |
| 321 | + | |
| 322 | + | |
| 323 | + | |
| 324 | + | |
| 325 | + | |
313 | 326 | | |
314 | 327 | | |
315 | 328 | | |
| 329 | + | |
316 | 330 | | |
317 | 331 | | |
318 | 332 | | |
| |||
643 | 657 | | |
644 | 658 | | |
645 | 659 | | |
| 660 | + | |
| 661 | + | |
| 662 | + | |
646 | 663 | | |
647 | 664 | | |
648 | 665 | | |
| |||
657 | 674 | | |
658 | 675 | | |
659 | 676 | | |
660 | | - | |
| 677 | + | |
661 | 678 | | |
662 | 679 | | |
663 | 680 | | |
| |||
674 | 691 | | |
675 | 692 | | |
676 | 693 | | |
677 | | - | |
| 694 | + | |
678 | 695 | | |
679 | 696 | | |
680 | 697 | | |
| |||
690 | 707 | | |
691 | 708 | | |
692 | 709 | | |
693 | | - | |
| 710 | + | |
| 711 | + | |
694 | 712 | | |
695 | | - | |
696 | | - | |
697 | | - | |
698 | | - | |
699 | | - | |
700 | | - | |
701 | | - | |
702 | | - | |
| 713 | + | |
| 714 | + | |
703 | 715 | | |
704 | 716 | | |
705 | 717 | | |
| |||
728 | 740 | | |
729 | 741 | | |
730 | 742 | | |
| 743 | + | |
| 744 | + | |
731 | 745 | | |
732 | 746 | | |
733 | 747 | | |
| |||
746 | 760 | | |
747 | 761 | | |
748 | 762 | | |
749 | | - | |
| 763 | + | |
| 764 | + | |
750 | 765 | | |
751 | 766 | | |
752 | 767 | | |
| |||
757 | 772 | | |
758 | 773 | | |
759 | 774 | | |
| 775 | + | |
760 | 776 | | |
761 | 777 | | |
762 | | - | |
| 778 | + | |
763 | 779 | | |
764 | 780 | | |
765 | 781 | | |
| |||
768 | 784 | | |
769 | 785 | | |
770 | 786 | | |
| 787 | + | |
| 788 | + | |
| 789 | + | |
| 790 | + | |
| 791 | + | |
| 792 | + | |
| 793 | + | |
| 794 | + | |
| 795 | + | |
| 796 | + | |
| 797 | + | |
| 798 | + | |
| 799 | + | |
| 800 | + | |
| 801 | + | |
| 802 | + | |
| 803 | + | |
| 804 | + | |
| 805 | + | |
| 806 | + | |
| 807 | + | |
| 808 | + | |
| 809 | + | |
| 810 | + | |
| 811 | + | |
| 812 | + | |
| 813 | + | |
| 814 | + | |
| 815 | + | |
| 816 | + | |
| 817 | + | |
| 818 | + | |
| 819 | + | |
| 820 | + | |
| 821 | + | |
| 822 | + | |
| 823 | + | |
| 824 | + | |
| 825 | + | |
| 826 | + | |
| 827 | + | |
| 828 | + | |
| 829 | + | |
| 830 | + | |
| 831 | + | |
| 832 | + | |
| 833 | + | |
| 834 | + | |
| 835 | + | |
| 836 | + | |
| 837 | + | |
771 | 838 | | |
772 | 839 | | |
773 | 840 | | |
774 | 841 | | |
| 842 | + | |
| 843 | + | |
| 844 | + | |
775 | 845 | | |
776 | 846 | | |
777 | 847 | | |
| |||
781 | 851 | | |
782 | 852 | | |
783 | 853 | | |
| 854 | + | |
784 | 855 | | |
785 | | - | |
786 | | - | |
787 | | - | |
788 | | - | |
| 856 | + | |
| 857 | + | |
| 858 | + | |
| 859 | + | |
| 860 | + | |
| 861 | + | |
789 | 862 | | |
790 | 863 | | |
791 | 864 | | |
792 | 865 | | |
793 | 866 | | |
794 | 867 | | |
795 | 868 | | |
| 869 | + | |
| 870 | + | |
| 871 | + | |
796 | 872 | | |
797 | 873 | | |
798 | 874 | | |
| |||
865 | 941 | | |
866 | 942 | | |
867 | 943 | | |
868 | | - | |
| 944 | + | |
| 945 | + | |
| 946 | + | |
| 947 | + | |
869 | 948 | | |
870 | 949 | | |
871 | 950 | | |
| |||
874 | 953 | | |
875 | 954 | | |
876 | 955 | | |
877 | | - | |
| 956 | + | |
| 957 | + | |
878 | 958 | | |
| 959 | + | |
| 960 | + | |
| 961 | + | |
| 962 | + | |
879 | 963 | | |
880 | 964 | | |
881 | 965 | | |
| |||
946 | 1030 | | |
947 | 1031 | | |
948 | 1032 | | |
| 1033 | + | |
| 1034 | + | |
| 1035 | + | |
| 1036 | + | |
| 1037 | + | |
| 1038 | + | |
| 1039 | + | |
| 1040 | + | |
| 1041 | + | |
| 1042 | + | |
| 1043 | + | |
| 1044 | + | |
| 1045 | + | |
| 1046 | + | |
| 1047 | + | |
| 1048 | + | |
| 1049 | + | |
| 1050 | + | |
| 1051 | + | |
| 1052 | + | |
| 1053 | + | |
| 1054 | + | |
| 1055 | + | |
| 1056 | + | |
| 1057 | + | |
| 1058 | + | |
| 1059 | + | |
| 1060 | + | |
| 1061 | + | |
| 1062 | + | |
| 1063 | + | |
| 1064 | + | |
| 1065 | + | |
| 1066 | + | |
| 1067 | + | |
| 1068 | + | |
| 1069 | + | |
| 1070 | + | |
| 1071 | + | |
| 1072 | + | |
| 1073 | + | |
| 1074 | + | |
| 1075 | + | |
| 1076 | + | |
| 1077 | + | |
| 1078 | + | |
| 1079 | + | |
| 1080 | + | |
| 1081 | + | |
| 1082 | + | |
| 1083 | + | |
| 1084 | + | |
| 1085 | + | |
949 | 1086 | | |
950 | 1087 | | |
951 | 1088 | | |
| |||
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
146 | 146 | | |
147 | 147 | | |
148 | 148 | | |
149 | | - | |
150 | | - | |
151 | | - | |
152 | | - | |
153 | | - | |
154 | | - | |
155 | | - | |
156 | | - | |
157 | | - | |
158 | | - | |
159 | | - | |
160 | | - | |
161 | | - | |
162 | | - | |
163 | | - | |
| 149 | + | |
| 150 | + | |
| 151 | + | |
| 152 | + | |
| 153 | + | |
| 154 | + | |
| 155 | + | |
| 156 | + | |
| 157 | + | |
| 158 | + | |
| 159 | + | |
| 160 | + | |
| 161 | + | |
| 162 | + | |
| 163 | + | |
| 164 | + | |
| 165 | + | |
| 166 | + | |
| 167 | + | |
| 168 | + | |
| 169 | + | |
| 170 | + | |
| 171 | + | |
| 172 | + | |
| 173 | + | |
| 174 | + | |
164 | 175 | | |
165 | 176 | | |
166 | 177 | | |
| |||
0 commit comments