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

Is your feature request related to a problem or challenge?

Spill files are Arrow IPC with each buffer compressed separately (IPCStreamEncoder::new). A Utf8 offsets buffer is a running total of lengths, which never repeats, so zstd keeps about 2.5 of every 4 bytes and lz4 keeps all 4. After a sort the string bytes often compress to under a byte per row, so the offsets dominate the file.

In datafusion-cli -m 100m:

SET datafusion.execution.target_partitions = 1;
SET datafusion.execution.spill_compression = 'zstd';

CREATE TABLE events AS
SELECT
  arrow_cast(md5(arrow_cast(s, 'Utf8')), 'Utf8') AS session_id,
  arrow_cast(CASE s % 3 WHEN 0 THEN 'iphone' WHEN 1 THEN 'ipad' ELSE 'mac' END, 'Utf8') AS platform,
  arrow_cast(concat('18.', s % 7, '.', s % 3), 'Utf8') AS os_version,
  arrow_cast(CASE value % 7 WHEN 0 THEN 'purchase' WHEN 1 THEN 'click' ELSE 'impression' END, 'Utf8') AS event_type,
  arrow_cast(concat('item-', (s * 31 + value % 3) % 100000), 'Utf8') AS item_id,
  value AS event_time
FROM (SELECT value, (value * 7919) % 25000 AS s FROM generate_series(1, 2000000));

EXPLAIN ANALYZE SELECT * FROM events ORDER BY session_id, event_time;

SortExec spills 32.0 MB (54.0 MB with lz4_frame). Recompressing the captured spill files buffer by buffer:

Describe the solution you'd like

Write offsets as lengths (32, 32, 32, ...) and rebuild them with a running sum when reading the spill back. Lengths repeat, so they compress to almost nothing, the same idea as Parquet's DELTA_LENGTH_BYTE_ARRAY. Spill files are only read by the process that wrote them, and SpillReaderStream already skips IPC validation (spill/mod.rs#L331-L339), so it could restore the offsets after decoding. It is also cheaper: on the offsets above, zstd took 14.7 ms to compress the lengths (transform included) against 49.6 ms for the offsets, and 16.6 ms against 21.5 ms to decompress.

Open questions: rebuilding the arrays without an extra copy, and whether LargeUtf8, Binary, List and Map offsets belong in the same change.

Describe alternatives you've considered

• Utf8View spills this table at 7.37 bytes per row with zstd. Short strings compress well inside their views, but the 32-character session_id still costs 3.05 bytes per row from the increasing buffer offsets in its views.
• On synthetic event data, compressing the whole file as one zstd stream saved 11 to 20% (nothing with lz4), and zstd level 5 instead of 3 (feat: let SpillCompression::Zstd carry a compression level #26365) saved 1 to 2%.

Additional context

Related: #16367, #14078. Measured on an Apple M5 Max with DataFusion 55.2.0 and a datafusion-cli built on c0ec512, which spill the same bytes. Found through Apache DataFusion Comet, which uses Utf8 for Spark strings: a production sort stage spilled 44.9 bytes per row there against 11.5 in Spark, both with zstd.