Skip to content

Commit 3284dc6

Browse files
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/in_progress_spill_file.rs‎

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -78,6 +78,7 @@ impl InProgressSpillFile {
7878
spill_writer,
7979
schema.as_ref(),
8080
self.spill_manager.compression,
81+
gc_batch.num_rows(),
8182
)?));
8283

8384
// Update metrics
@@ -116,6 +117,7 @@ impl InProgressSpillFile {
116117
let encoder = IPCStreamEncoder::new(
117118
schema.as_ref(),
118119
self.spill_manager.compression,
120+
gc_batch.num_rows(),
119121
)?;
120122
let spill_writer = in_progress_file.open_async_writer().await?;
121123

Lines changed: 307 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,307 @@
1+
// SPDX-License-Identifier: Apache-2.0
2+
// SPDX-FileCopyrightText: See the NOTICE file distributed with this work for additional information regarding copyright ownership
3+
// SPDX-FileContributor: Licensed to the Apache Software Foundation (ASF) under one or more contributor license agreements
4+
5+
//! Spills byte arrays as the lengths of their values.
6+
//!
7+
//! The offsets of a `Utf8` array are a running total that zstd and lz4 barely
8+
//! compress, while the lengths of similar values repeat, see
9+
//! <https://github.com/apache/datafusion/issues/26627>. Compressed spill files
10+
//! therefore store each top level `Utf8`, `LargeUtf8`, `Binary` and
11+
//! `LargeBinary` column as a struct of its lengths, which keep its nulls, and
12+
//! of all its value bytes as a single run:
13+
//!
14+
//! ```text
15+
//! Utf8 ["ab", null, "cde"]
16+
//!
17+
//! Struct {
18+
//! lengths: Int32 [2, null, 3]
19+
//! values: RunEndEncoded { run_ends: [3], values: Binary ["abcde"] }
20+
//! }
21+
//! ```
22+
//!
23+
//! Both are valid arrays, so the IPC reader decodes them as usual before
24+
//! [`decode`] rebuilds the offsets with a running sum. Files whose first batch
25+
//! has fewer than [`MIN_LENGTHS_ROWS`](super::MIN_LENGTHS_ROWS) rows keep their
26+
//! offsets.
27+
28+
use std::sync::Arc;
29+
30+
use arrow::array::{
31+
Array, ArrayRef, ArrowPrimitiveType, AsArray, GenericBinaryArray, GenericByteArray,
32+
Int64Array, OffsetSizeTrait, PrimitiveArray, RecordBatch, RunArray, StructArray,
33+
new_empty_array,
34+
};
35+
use arrow::buffer::OffsetBuffer;
36+
use arrow::datatypes::{
37+
ArrowNativeType, BinaryType, ByteArrayType, DataType, Field, Fields,
38+
GenericBinaryType, Int32Type, Int64Type, LargeBinaryType, LargeUtf8Type, Schema,
39+
SchemaRef, Utf8Type,
40+
};
41+
use datafusion_common::utils::offset_span;
42+
use datafusion_common::{Result, internal_datafusion_err, internal_err};
43+
44+
/// Returns the schema that `schema` is spilled as, or `None` if it has no byte
45+
/// array columns
46+
pub(super) fn encode_schema(schema: &Schema) -> Option<SchemaRef> {
47+
let mut encoded = false;
48+
let fields: Vec<_> = schema
49+
.fields()
50+
.iter()
51+
.map(|field| match encoded_type(field.data_type()) {
52+
Some(data_type) => {
53+
encoded = true;
54+
Arc::new(Field::new(field.name(), data_type, field.is_nullable()))
55+
}
56+
None => Arc::clone(field),
57+
})
58+
.collect();
59+
encoded
60+
.then(|| Arc::new(Schema::new_with_metadata(fields, schema.metadata().clone())))
61+
}
62+
63+
/// Encodes the byte array columns of `batch` as [`encode_schema`] returned
64+
/// `schema`, see the [module docs](self)
65+
///
66+
/// The other columns keep the fields of `batch`, which can differ from the
67+
/// spill schema in nested nullability, see `InProgressSpillFile::append_batch`.
68+
pub(super) fn encode(batch: &RecordBatch, schema: &SchemaRef) -> Result<RecordBatch> {
69+
let mut fields = Vec::with_capacity(batch.num_columns());
70+
let mut columns = Vec::with_capacity(batch.num_columns());
71+
for ((field, spilled), column) in batch
72+
.schema_ref()
73+
.fields()
74+
.iter()
75+
.zip(schema.fields())
76+
.zip(batch.columns())
77+
{
78+
let encoded = match (column.data_type(), spilled.data_type()) {
79+
(DataType::Utf8, DataType::Struct(struct_fields)) => {
80+
encode_bytes::<_, Int32Type>(struct_fields, column.as_string::<i32>())?
81+
}
82+
(DataType::LargeUtf8, DataType::Struct(struct_fields)) => {
83+
encode_bytes::<_, Int64Type>(struct_fields, column.as_string::<i64>())?
84+
}
85+
(DataType::Binary, DataType::Struct(struct_fields)) => {
86+
encode_bytes::<_, Int32Type>(struct_fields, column.as_binary::<i32>())?
87+
}
88+
(DataType::LargeBinary, DataType::Struct(struct_fields)) => {
89+
encode_bytes::<_, Int64Type>(struct_fields, column.as_binary::<i64>())?
90+
}
91+
_ => {
92+
fields.push(Arc::clone(field));
93+
columns.push(Arc::clone(column));
94+
continue;
95+
}
96+
};
97+
fields.push(Arc::clone(spilled));
98+
columns.push(encoded);
99+
}
100+
let schema = Schema::new_with_metadata(fields, batch.schema_ref().metadata().clone());
101+
Ok(RecordBatch::try_new(Arc::new(schema), columns)?)
102+
}
103+
104+
/// Restores a batch that [`encode`] wrote for `schema`
105+
pub(super) fn decode(batch: &RecordBatch, schema: &SchemaRef) -> Result<RecordBatch> {
106+
let columns = schema
107+
.fields()
108+
.iter()
109+
.zip(batch.columns())
110+
.map(|(field, column)| decode_array(field.data_type(), column))
111+
.collect::<Result<_>>()?;
112+
Ok(RecordBatch::try_new(Arc::clone(schema), columns)?)
113+
}
114+
115+
fn encoded_type(data_type: &DataType) -> Option<DataType> {
116+
let fields = match data_type {
117+
DataType::Utf8 | DataType::Binary => encoded_fields::<Int32Type>(),
118+
DataType::LargeUtf8 | DataType::LargeBinary => encoded_fields::<Int64Type>(),
119+
_ => return None,
120+
};
121+
Some(DataType::Struct(fields))
122+
}
123+
124+
/// The fields of the struct a byte array with `L` offsets is spilled as
125+
fn encoded_fields<L>() -> Fields
126+
where
127+
L: ArrowPrimitiveType,
128+
L::Native: OffsetSizeTrait,
129+
{
130+
let run_ends = Field::new("run_ends", DataType::Int64, false);
131+
let bytes = Field::new("values", GenericBinaryType::<L::Native>::DATA_TYPE, true);
132+
let values = DataType::RunEndEncoded(Arc::new(run_ends), Arc::new(bytes));
133+
Fields::from(vec![
134+
Field::new("lengths", L::DATA_TYPE, true),
135+
Field::new("values", values, false),
136+
])
137+
}
138+
139+
fn decode_array(data_type: &DataType, array: &ArrayRef) -> Result<ArrayRef> {
140+
match data_type {
141+
DataType::Utf8 => decode_bytes::<Utf8Type, Int32Type>(array),
142+
DataType::LargeUtf8 => decode_bytes::<LargeUtf8Type, Int64Type>(array),
143+
DataType::Binary => decode_bytes::<BinaryType, Int32Type>(array),
144+
DataType::LargeBinary => decode_bytes::<LargeBinaryType, Int64Type>(array),
145+
_ => Ok(Arc::clone(array)),
146+
}
147+
}
148+
149+
fn encode_bytes<T, L>(fields: &Fields, array: &GenericByteArray<T>) -> Result<ArrayRef>
150+
where
151+
T: ByteArrayType,
152+
L: ArrowPrimitiveType<Native = T::Offset>,
153+
{
154+
if array.is_empty() {
155+
return Ok(new_empty_array(&DataType::Struct(fields.clone())));
156+
}
157+
let offsets = array.offsets();
158+
let lengths = offsets.windows(2).map(|w| w[1] - w[0]).collect();
159+
let lengths = PrimitiveArray::<L>::new(lengths, array.nulls().cloned());
160+
161+
let (start, len) = offset_span(offsets);
162+
let bytes = GenericBinaryArray::<T::Offset>::new(
163+
OffsetBuffer::from_lengths([len]),
164+
array.values().slice_with_length(start, len),
165+
None,
166+
);
167+
let run_ends = Int64Array::from(vec![array.len() as i64]);
168+
let values = RunArray::try_new(&run_ends, &bytes)?;
169+
170+
let array = StructArray::try_new(
171+
fields.clone(),
172+
vec![Arc::new(lengths), Arc::new(values)],
173+
None,
174+
)?;
175+
Ok(Arc::new(array))
176+
}
177+
178+
fn decode_bytes<T, L>(array: &ArrayRef) -> Result<ArrayRef>
179+
where
180+
T: ByteArrayType,
181+
L: ArrowPrimitiveType<Native = T::Offset>,
182+
{
183+
let array = array.as_struct();
184+
let lengths = array.column(0).as_primitive::<L>();
185+
let offsets = OffsetBuffer::<T::Offset>::try_from_lengths(
186+
lengths.values().iter().map(|len| len.as_usize()),
187+
)
188+
.map_err(|e| {
189+
internal_datafusion_err!("Invalid spilled {} lengths: {e}", T::DATA_TYPE)
190+
})?;
191+
192+
let bytes = array.column(1).as_run::<Int64Type>().values();
193+
let bytes = bytes.as_binary::<T::Offset>();
194+
let (start, len) = offset_span(bytes.offsets());
195+
let end = offsets.last().as_usize();
196+
if end != len {
197+
return internal_err!(
198+
"Spilled {} lengths add up to {end}, but there are {len} value bytes",
199+
T::DATA_TYPE
200+
);
201+
}
202+
203+
let array = GenericByteArray::<T>::try_new(
204+
offsets,
205+
bytes.values().slice_with_length(start, len),
206+
lengths.nulls().cloned(),
207+
)?;
208+
Ok(Arc::new(array))
209+
}
210+
211+
#[cfg(test)]
212+
mod tests {
213+
use super::*;
214+
use crate::common::collect;
215+
use crate::metrics::{ExecutionPlanMetricsSet, SpillMetrics};
216+
use crate::spill::spill_manager::SpillManager;
217+
use arrow::array::StringArray;
218+
use arrow::compute::cast;
219+
use arrow_ipc::CompressionType;
220+
use arrow_ipc::writer::{IpcWriteOptions, StreamWriter};
221+
use datafusion_common::config::SpillCompression;
222+
use datafusion_execution::runtime_env::RuntimeEnv;
223+
224+
fn spill_manager(schema: SchemaRef, compression: SpillCompression) -> SpillManager {
225+
let env = Arc::new(RuntimeEnv::default());
226+
let metrics = SpillMetrics::new(&ExecutionPlanMetricsSet::new(), 0);
227+
SpillManager::new(env, metrics, schema).with_compression_type(compression)
228+
}
229+
230+
/// Sliced and empty byte arrays with nulls read back as written
231+
#[tokio::test]
232+
async fn test_spill_lengths_round_trip() -> Result<()> {
233+
let utf8: ArrayRef = Arc::new(StringArray::from_iter(
234+
(0..1000).map(|i| (i % 7 != 0).then(|| "x".repeat(i % 5))),
235+
));
236+
let batch = RecordBatch::try_from_iter(vec![
237+
("large_utf8", cast(&utf8, &DataType::LargeUtf8)?),
238+
("binary", cast(&utf8, &DataType::Binary)?),
239+
("large_binary", cast(&utf8, &DataType::LargeBinary)?),
240+
("utf8", utf8),
241+
])?;
242+
let batches = [batch.slice(3, 500), batch.slice(998, 2), batch.slice(0, 0)];
243+
for compression in [SpillCompression::Lz4Frame, SpillCompression::Zstd] {
244+
let spill_manager = spill_manager(batch.schema(), compression);
245+
let spill_file = spill_manager
246+
.spill_record_batch_and_finish(&batches, "Test")?
247+
.unwrap();
248+
let stream = spill_manager.read_spill_as_stream(spill_file, None)?;
249+
assert_eq!(collect(stream).await?, batches, "{compression}");
250+
}
251+
Ok(())
252+
}
253+
254+
/// The lengths of similar values compress to almost nothing, unlike their
255+
/// offsets
256+
#[test]
257+
fn test_spill_lengths_compress() -> Result<()> {
258+
let schema = Arc::new(Schema::new(vec![Field::new("a", DataType::Utf8, false)]));
259+
let values = (0..8192).map(|i| format!("item-{}", i / 64));
260+
let batch = RecordBatch::try_new(
261+
Arc::clone(&schema),
262+
vec![Arc::new(StringArray::from_iter_values(values))],
263+
)?;
264+
265+
let spill_manager = spill_manager(Arc::clone(&schema), SpillCompression::Zstd);
266+
spill_manager
267+
.spill_record_batch_and_finish(std::slice::from_ref(&batch), "Test")?;
268+
let spilled = spill_manager.metrics.spilled_bytes.value();
269+
270+
let options = IpcWriteOptions::default()
271+
.try_with_compression(Some(CompressionType::ZSTD))?;
272+
let mut ipc = vec![];
273+
let mut writer = StreamWriter::try_new_with_options(&mut ipc, &schema, options)?;
274+
writer.write(&batch)?;
275+
writer.finish()?;
276+
assert!(
277+
spilled * 4 < ipc.len(),
278+
"spilled {spilled} bytes, against {} bytes of IPC",
279+
ipc.len()
280+
);
281+
Ok(())
282+
}
283+
284+
/// Files whose first batch is too small for the lengths to pay off keep
285+
/// their offsets
286+
#[test]
287+
fn test_spill_lengths_skipped_for_small_batches() -> Result<()> {
288+
let schema = Arc::new(Schema::new(vec![Field::new("a", DataType::Utf8, false)]));
289+
for (rows, encoded) in [(127, false), (128, true)] {
290+
let values = (0..rows).map(|i| format!("item-{}", i / 64));
291+
let batch = RecordBatch::try_new(
292+
Arc::clone(&schema),
293+
vec![Arc::new(StringArray::from_iter_values(values))],
294+
)?;
295+
let spill_manager =
296+
spill_manager(Arc::clone(&schema), SpillCompression::Zstd);
297+
let spill_file = spill_manager
298+
.spill_record_batch_and_finish(std::slice::from_ref(&batch), "Test")?
299+
.unwrap();
300+
let file = std::fs::File::open(spill_file.path().unwrap())?;
301+
let reader = arrow_ipc::reader::StreamReader::try_new(file, None)?;
302+
let spilled_type = reader.schema().field(0).data_type().clone();
303+
assert_eq!(spilled_type != DataType::Utf8, encoded, "{rows} rows");
304+
}
305+
Ok(())
306+
}
307+
}

0 commit comments

Comments
 (0)