Repository navigation
Commit 3284dc6
authored
perf: spill byte arrays as lengths and coalesce spill writes (apache#26960)
## Which issue does this PR close?
- Closes apache#26627.
## Rationale for this change
Compressed spill files are mostly string offsets, which zstd and lz4
barely compress, see apache#26627. Spilling is also slower than it needs to
be: a batch of the table in apache#26627 takes about 35 `write` calls, one per
IPC buffer.
This replaces apache#26698, which needed spill reads to skip validation
(apache#26688).
## What changes are included in this PR?
- With `lz4_frame` or `zstd`, each top level `Utf8`, `LargeUtf8`,
`Binary` and `LargeBinary` column is spilled as a struct of its value
lengths and of its value bytes as one run-end encoded value. Both are
valid arrays, so the IPC reader decodes them as usual before the spill
reader rebuilds and validates the original arrays. Files whose first
batch has fewer than 128 rows keep their offsets, since the struct and
run-end metadata would cost more than the lengths save. Uncompressed
spills keep their layout.
- The small IPC buffers of a batch are copied into one write, so a
spilled batch takes a few writes instead of one per buffer.
## Benchmarks
Apple M5 Max, interleaved runs against `main`.
The reproducer from apache#26627 (`datafusion-cli -m 100m`, median of 7):
| codec | main | this PR |
|---|---:|---:|
| uncompressed | 210 ms, 171.7 MB spilled | 205 ms, 171.7 MB spilled |
| lz4_frame | 252 ms, 54.0 MB spilled | 240 ms, 17.1 MB spilled |
| zstd | 306 ms, 32.0 MB spilled | 259 ms, 8.9 MB spilled |
The same query with small batches (`batch_size` 64, 128 and 256, median
of 3), spilled bytes and time:
| rows per batch | lz4_frame, main → this PR | zstd, main → this PR |
|---:|---:|---:|
| 64 | 83.9 → 83.9 MB, 11.8 → 10.0 s | 62.1 → 62.1 MB, 11.8 → 11.1 s |
| 128 | 70.3 → 52.5 MB, 3.35 → 2.92 s | 44.9 → 44.3 MB, 3.67 → 3.06 s |
| 256 | 63.3 → 36.6 MB, 1.40 → 1.18 s | 37.6 → 27.9 MB, 1.70 → 1.28 s |
`sort_tpch` queries at SF1 on `Utf8` columns (one partition, `-m 200m`,
median of 5), spilled bytes and time against `main`:
| query | uncompressed | lz4_frame | zstd |
|---|---:|---:|---:|
| Q3 | -0.2% | 92.4 → 78.1 MB, +0.1% | 61.4 → 50.5 MB, +1.6% |
| Q7 | -4.0% | 306.3 → 230.2 MB, -1.5% | 171.3 → 122.6 MB, -3.5% |
| Q10 | -3.5% | 398.9 → 309.7 MB, -1.2% | 228.2 → 169.2 MB, -2.8% |
In the `spill_io` benchmark, writing and reading spill files is 2-14%
faster uncompressed, 4-8% faster with zstd and unchanged to 10% faster
with lz4, and the string datasets spill 27-41% smaller.
<details><summary><code>spill_io</code> results and setup</summary>
`cargo bench -p datafusion-physical-plan --bench spill_io`, median of
three alternating runs per build.
| benchmark | main | this PR | spilled, main → this PR |
|---|---:|---:|---:|
| q2/uncompressed | 3.81 ms | 3.73 ms (-2.1%) | unchanged |
| q2/zstd | 17.42 ms | 16.70 ms (-4.1%) | unchanged |
| q2/lz4_frame | 11.60 ms | 10.64 ms (-8.3%) | unchanged |
| q16/uncompressed | 9.68 ms | 8.80 ms (-9.1%) | unchanged |
| q16/zstd | 41.03 ms | 37.84 ms (-7.8%) | 4.4 MB → 2.6 MB |
| q16/lz4_frame | 23.44 ms | 23.43 ms (-0.1%) | 7.8 MB → 5.2 MB |
| q20/uncompressed | 5.68 ms | 5.46 ms (-3.8%) | unchanged |
| q20/zstd | 26.82 ms | 25.58 ms (-4.6%) | unchanged |
| q20/lz4_frame | 16.84 ms | 15.23 ms (-9.6%) | unchanged |
| wide/uncompressed | 26.19 ms | 22.60 ms (-13.7%) | unchanged |
| wide/zstd | 102.29 ms | 95.98 ms (-6.2%) | 11.6 MB → 8.2 MB |
| wide/lz4_frame | 57.86 ms | 56.12 ms (-3.0%) | 19.9 MB → 14.6 MB |
The `sort_tpch` runs set:
```sql
SET datafusion.execution.target_partitions = 1;
SET datafusion.execution.parquet.schema_force_view_types = false;
SET datafusion.execution.spill_compression = 'zstd'; -- or 'lz4_frame', 'uncompressed'
```
</details>
## What is the testing strategy for this PR?
- `aggregate_memory_spill.slt` spills `Utf8`, `LargeUtf8`, `Binary` and
`LargeBinary` group keys with nulls under `zstd` and `lz4_frame` and
checks their values.
- `test_spill_lengths_round_trip` covers sliced and empty batches,
`test_spill_lengths_compress` checks that a zstd spill of similar
strings is under a quarter of plain zstd IPC, and
`test_spill_lengths_skipped_for_small_batches` checks the 128-row
threshold.
- `test_async_ipc_stream_writer` checks that each batch takes one write.
## Are there any user-facing changes?
Smaller compressed spill files and faster spilling. No configuration or
API changes.1 parent 90b55e3 commit 3284dc6
4 files changed
Lines changed: 452 additions & 11 deletions
File tree
- datafusion
- physical-plan/src/spill
- sqllogictest/test_files
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
78 | 78 | | |
79 | 79 | | |
80 | 80 | | |
| 81 | + | |
81 | 82 | | |
82 | 83 | | |
83 | 84 | | |
| |||
116 | 117 | | |
117 | 118 | | |
118 | 119 | | |
| 120 | + | |
119 | 121 | | |
120 | 122 | | |
121 | 123 | | |
| |||
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
| 1 | + | |
| 2 | + | |
| 3 | + | |
| 4 | + | |
| 5 | + | |
| 6 | + | |
| 7 | + | |
| 8 | + | |
| 9 | + | |
| 10 | + | |
| 11 | + | |
| 12 | + | |
| 13 | + | |
| 14 | + | |
| 15 | + | |
| 16 | + | |
| 17 | + | |
| 18 | + | |
| 19 | + | |
| 20 | + | |
| 21 | + | |
| 22 | + | |
| 23 | + | |
| 24 | + | |
| 25 | + | |
| 26 | + | |
| 27 | + | |
| 28 | + | |
| 29 | + | |
| 30 | + | |
| 31 | + | |
| 32 | + | |
| 33 | + | |
| 34 | + | |
| 35 | + | |
| 36 | + | |
| 37 | + | |
| 38 | + | |
| 39 | + | |
| 40 | + | |
| 41 | + | |
| 42 | + | |
| 43 | + | |
| 44 | + | |
| 45 | + | |
| 46 | + | |
| 47 | + | |
| 48 | + | |
| 49 | + | |
| 50 | + | |
| 51 | + | |
| 52 | + | |
| 53 | + | |
| 54 | + | |
| 55 | + | |
| 56 | + | |
| 57 | + | |
| 58 | + | |
| 59 | + | |
| 60 | + | |
| 61 | + | |
| 62 | + | |
| 63 | + | |
| 64 | + | |
| 65 | + | |
| 66 | + | |
| 67 | + | |
| 68 | + | |
| 69 | + | |
| 70 | + | |
| 71 | + | |
| 72 | + | |
| 73 | + | |
| 74 | + | |
| 75 | + | |
| 76 | + | |
| 77 | + | |
| 78 | + | |
| 79 | + | |
| 80 | + | |
| 81 | + | |
| 82 | + | |
| 83 | + | |
| 84 | + | |
| 85 | + | |
| 86 | + | |
| 87 | + | |
| 88 | + | |
| 89 | + | |
| 90 | + | |
| 91 | + | |
| 92 | + | |
| 93 | + | |
| 94 | + | |
| 95 | + | |
| 96 | + | |
| 97 | + | |
| 98 | + | |
| 99 | + | |
| 100 | + | |
| 101 | + | |
| 102 | + | |
| 103 | + | |
| 104 | + | |
| 105 | + | |
| 106 | + | |
| 107 | + | |
| 108 | + | |
| 109 | + | |
| 110 | + | |
| 111 | + | |
| 112 | + | |
| 113 | + | |
| 114 | + | |
| 115 | + | |
| 116 | + | |
| 117 | + | |
| 118 | + | |
| 119 | + | |
| 120 | + | |
| 121 | + | |
| 122 | + | |
| 123 | + | |
| 124 | + | |
| 125 | + | |
| 126 | + | |
| 127 | + | |
| 128 | + | |
| 129 | + | |
| 130 | + | |
| 131 | + | |
| 132 | + | |
| 133 | + | |
| 134 | + | |
| 135 | + | |
| 136 | + | |
| 137 | + | |
| 138 | + | |
| 139 | + | |
| 140 | + | |
| 141 | + | |
| 142 | + | |
| 143 | + | |
| 144 | + | |
| 145 | + | |
| 146 | + | |
| 147 | + | |
| 148 | + | |
| 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 | + | |
| 175 | + | |
| 176 | + | |
| 177 | + | |
| 178 | + | |
| 179 | + | |
| 180 | + | |
| 181 | + | |
| 182 | + | |
| 183 | + | |
| 184 | + | |
| 185 | + | |
| 186 | + | |
| 187 | + | |
| 188 | + | |
| 189 | + | |
| 190 | + | |
| 191 | + | |
| 192 | + | |
| 193 | + | |
| 194 | + | |
| 195 | + | |
| 196 | + | |
| 197 | + | |
| 198 | + | |
| 199 | + | |
| 200 | + | |
| 201 | + | |
| 202 | + | |
| 203 | + | |
| 204 | + | |
| 205 | + | |
| 206 | + | |
| 207 | + | |
| 208 | + | |
| 209 | + | |
| 210 | + | |
| 211 | + | |
| 212 | + | |
| 213 | + | |
| 214 | + | |
| 215 | + | |
| 216 | + | |
| 217 | + | |
| 218 | + | |
| 219 | + | |
| 220 | + | |
| 221 | + | |
| 222 | + | |
| 223 | + | |
| 224 | + | |
| 225 | + | |
| 226 | + | |
| 227 | + | |
| 228 | + | |
| 229 | + | |
| 230 | + | |
| 231 | + | |
| 232 | + | |
| 233 | + | |
| 234 | + | |
| 235 | + | |
| 236 | + | |
| 237 | + | |
| 238 | + | |
| 239 | + | |
| 240 | + | |
| 241 | + | |
| 242 | + | |
| 243 | + | |
| 244 | + | |
| 245 | + | |
| 246 | + | |
| 247 | + | |
| 248 | + | |
| 249 | + | |
| 250 | + | |
| 251 | + | |
| 252 | + | |
| 253 | + | |
| 254 | + | |
| 255 | + | |
| 256 | + | |
| 257 | + | |
| 258 | + | |
| 259 | + | |
| 260 | + | |
| 261 | + | |
| 262 | + | |
| 263 | + | |
| 264 | + | |
| 265 | + | |
| 266 | + | |
| 267 | + | |
| 268 | + | |
| 269 | + | |
| 270 | + | |
| 271 | + | |
| 272 | + | |
| 273 | + | |
| 274 | + | |
| 275 | + | |
| 276 | + | |
| 277 | + | |
| 278 | + | |
| 279 | + | |
| 280 | + | |
| 281 | + | |
| 282 | + | |
| 283 | + | |
| 284 | + | |
| 285 | + | |
| 286 | + | |
| 287 | + | |
| 288 | + | |
| 289 | + | |
| 290 | + | |
| 291 | + | |
| 292 | + | |
| 293 | + | |
| 294 | + | |
| 295 | + | |
| 296 | + | |
| 297 | + | |
| 298 | + | |
| 299 | + | |
| 300 | + | |
| 301 | + | |
| 302 | + | |
| 303 | + | |
| 304 | + | |
| 305 | + | |
| 306 | + | |
| 307 | + | |
0 commit comments