Repository navigation
Commit 3d9037c
authored
fix: avoid quadratic row-buffer accounting in sort merges (apache#26366)
## Which issue does this PR close?
Follow-up to apache#25372, related to apache#23174.
## Rationale for this change
Multi-key sorts over many small batches spend quadratic time accounting
for retained row buffers, delaying their first merged output.
The merge caches one encoded row buffer per input stream. Each new batch
currently scans every cache slot to recalculate the reservation. Reading
the first batch from each of N streams therefore requires N full scans.
A large merge can spend seconds doing this bookkeeping in a single Tokio
poll.
## What changes are included in this PR?
- Track each stream's reserved bytes and update the total by that
stream's change, making each accounting update constant-time.
- Keep the existing charge while a buffer is reused. Failed buffer
growth and stream completion release only that stream's charge.
- Add a SQL-based case to the existing `sort` benchmark that sorts two
million rows loaded in 32-row batches. Two sort keys exercise the
affected row-format merge. Data generation happens before timing.
## What is the testing strategy for this PR?
A focused regression test fills a bounded memory pool, then rejects
growth of a reused row buffer. It checks that the failed stream releases
its previous reservation while another stream remains accounted for.
The SQL benchmark runs a single query, with no concurrent workload:
```bash
cargo bench -p datafusion --bench sort -- small_batches/two_keys
```
[Benchmark bot
results](apache#26366 (comment)):
**13.9 s → 3.4 s (4.09× faster)** for `small_batches/two_keys`.
## Are there any user-facing changes?
Large row-format merges perform less bookkeeping while preserving their
memory reservations. The internal reservation invariant is documented
alongside the per-stream sizes.
Developed with AI assistance.1 parent 0ee3978 commit 3d9037c
2 files changed
Lines changed: 108 additions & 9 deletions
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
1065 | 1065 | | |
1066 | 1066 | | |
1067 | 1067 | | |
1068 | | - | |
| 1068 | + | |
| 1069 | + | |
| 1070 | + | |
| 1071 | + | |
| 1072 | + | |
| 1073 | + | |
| 1074 | + | |
| 1075 | + | |
| 1076 | + | |
| 1077 | + | |
| 1078 | + | |
| 1079 | + | |
| 1080 | + | |
| 1081 | + | |
| 1082 | + | |
| 1083 | + | |
| 1084 | + | |
| 1085 | + | |
| 1086 | + | |
| 1087 | + | |
| 1088 | + | |
| 1089 | + | |
| 1090 | + | |
| 1091 | + | |
| 1092 | + | |
| 1093 | + | |
| 1094 | + | |
| 1095 | + | |
| 1096 | + | |
| 1097 | + | |
| 1098 | + | |
| 1099 | + | |
| 1100 | + | |
| 1101 | + | |
| 1102 | + | |
| 1103 | + | |
| 1104 | + | |
| 1105 | + | |
| 1106 | + | |
| 1107 | + | |
| 1108 | + | |
| 1109 | + | |
| 1110 | + | |
| 1111 | + | |
| 1112 | + | |
| 1113 | + | |
| 1114 | + | |
| 1115 | + | |
| 1116 | + | |
| 1117 | + | |
| 1118 | + | |
| 1119 | + | |
| 1120 | + | |
| 1121 | + | |
| 1122 | + | |
| 1123 | + | |
| 1124 | + | |
| 1125 | + | |
| 1126 | + | |
| 1127 | + | |
1069 | 1128 | | |
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
103 | 103 | | |
104 | 104 | | |
105 | 105 | | |
| 106 | + | |
| 107 | + | |
| 108 | + | |
106 | 109 | | |
107 | 110 | | |
108 | 111 | | |
| |||
130 | 133 | | |
131 | 134 | | |
132 | 135 | | |
133 | | - | |
134 | | - | |
| 136 | + | |
| 137 | + | |
135 | 138 | | |
136 | 139 | | |
137 | | - | |
138 | | - | |
| 140 | + | |
139 | 141 | | |
140 | 142 | | |
| 143 | + | |
| 144 | + | |
141 | 145 | | |
142 | 146 | | |
143 | 147 | | |
144 | 148 | | |
145 | 149 | | |
146 | 150 | | |
147 | | - | |
148 | | - | |
149 | | - | |
| 151 | + | |
| 152 | + | |
| 153 | + | |
| 154 | + | |
| 155 | + | |
| 156 | + | |
150 | 157 | | |
151 | 158 | | |
152 | 159 | | |
| |||
200 | 207 | | |
201 | 208 | | |
202 | 209 | | |
| 210 | + | |
203 | 211 | | |
204 | 212 | | |
205 | 213 | | |
| |||
442 | 450 | | |
443 | 451 | | |
444 | 452 | | |
445 | | - | |
| 453 | + | |
446 | 454 | | |
447 | 455 | | |
448 | 456 | | |
| |||
907 | 915 | | |
908 | 916 | | |
909 | 917 | | |
| 918 | + | |
| 919 | + | |
| 920 | + | |
| 921 | + | |
| 922 | + | |
| 923 | + | |
| 924 | + | |
| 925 | + | |
| 926 | + | |
| 927 | + | |
| 928 | + | |
| 929 | + | |
| 930 | + | |
| 931 | + | |
| 932 | + | |
| 933 | + | |
| 934 | + | |
| 935 | + | |
| 936 | + | |
| 937 | + | |
| 938 | + | |
| 939 | + | |
| 940 | + | |
| 941 | + | |
| 942 | + | |
| 943 | + | |
| 944 | + | |
| 945 | + | |
| 946 | + | |
| 947 | + | |
| 948 | + | |
| 949 | + | |
910 | 950 | | |
0 commit comments