Skip to content

perf: write offsets to compressed spill files as lengths - #26698

Closed
comphead wants to merge 2 commits into
apache:mainfrom
comphead:spill-offsets-as-lengths
Closed

comphead wants to merge 2 commits into
apache:mainfrom
comphead:spill-offsets-as-lengths

Conversation

@comphead

Copy link
Copy Markdown
Contributor

Which issue does this PR close?

Stacked on #26688, because lengths are not valid offsets and only read back when spill reads skip validation. Only the last commit is new here.

Rationale for this change

See #26627: spill files are mostly Utf8 offsets, which zstd and lz4 barely compress, while lengths repeat.

What changes are included in this PR?

  • Compressed spill files (lz4_frame and zstd) hold lengths instead of offsets for Utf8, Binary, List, Map and their large variants, at any depth through Struct and FixedSizeList. The buffer is [0, len_0, ..., len_(n-2), total]. The IPC writer reads only its first and last entries, to slice the values, so the stock encoder writes it as is.
  • The reader rebuilds the offsets of compressed record batches with a running sum, in place in the decompressed buffer. It copies only a buffer that the IPC writer stored raw because compressing it did not help.
  • Uncompressed spill files are unchanged.

The issue's reproducer (datafusion-cli -m 100m, median of 7 interleaved runs):

codec spilled, main -> PR query
zstd 32.0 -> 8.6 MB 314 -> 274 ms
lz4_frame 54.0 -> 16.8 MB 258 -> 250 ms

TPC-H SF1 sorts with Utf8 columns (schema_force_view_types = false, one partition, -m 200m, median of 5 runs):

query lz4_frame zstd
sort-tpch Q3 92.4 -> 78.0 MB, +0.8% 61.4 -> 50.3 MB, +1.1%
sort-tpch Q7 306.3 -> 229.5 MB, +0.6% 171.3 -> 122.0 MB, -2.5%
sort-tpch Q10 398.9 -> 308.7 MB, +3.0% 228.2 -> 168.4 MB, -2.7%

In the spill_io benchmark against #26688, files with strings are 27% to 41% smaller. Writing plus reading them takes up to 7% less time with zstd and about 8.5% more with lz4, because lz4 stored the incompressible offsets raw and now compresses the lengths.

Open question: should lz4_frame keep this, or only zstd?

What is the testing strategy for this PR?

  • test_spill_offsets_as_lengths_round_trip spills every rewritten type, nested and sliced, with all three codecs. Its empty and two-row batches cover buffers the IPC writer stores raw.
  • test_spill_offsets_as_lengths_compress checks that a zstd spill of similar strings is under a quarter of plain zstd IPC.
  • test_restore_offsets_in_place_unless_shared checks that the restore reuses an unshared buffer.

Are there any user-facing changes?

Smaller spill files with lz4_frame or zstd. No configuration or API changes.

apache#15454 stopped re-validating spill files on read. apache#21882 moved the reader to
`StreamDecoder`, whose `with_skip_validation` only applies to dictionary
batches, so every offset and string of a spilled record batch is validated
again. Decode the framed messages with `RecordBatchDecoder` instead, which
honors the flag.
Closes apache#26627.

Offsets are a running total, so zstd keeps about 2.5 of every 4 bytes and
lz4 all of them, while the lengths of similar values repeat. Compressed
spill files now hold the lengths of `Utf8`, `Binary`, `List` and `Map`
arrays, their large variants included, at any nesting depth through `Struct`
and `FixedSizeList`. The reader rebuilds the offsets with a running sum, in
place in the decompressed buffer.
@github-actions github-actions Bot added the physical-plan Changes to the physical-plan crate label Oct 24, 2026
@comphead comphead closed this Oct 24, 2026
@comphead

Copy link
Copy Markdown
Contributor Author

doesn't seem to benefit a lot

lyne7-sc pushed a commit to lyne7-sc/datafusion that referenced this pull request Nov 6, 2026
…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.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

physical-plan Changes to the physical-plan crate

Projects

None yet

Development

Successfully merging this pull request may close these issues.

Spill files are mostly Utf8 offsets, which zstd and lz4 barely compress

1 participant