Skip to content

Commit dece2f3

Browse files
alambbranczampagent
authored
[branch-56] perf: prune oversized dictionaries before IPC spilling (backport #27015) (#27107)
## Which issue does this PR close? - Backport of #27015 to `branch-56` - Part of #24461 - Closes #27014 Co-authored-by: Frederic Branczyk <[email protected]> Co-authored-by: Amp <[email protected]>
1 parent 9795e8c commit dece2f3

3 files changed

Lines changed: 88 additions & 9 deletions

File tree

‎Cargo.lock‎

Lines changed: 1 addition & 0 deletions
Some generated files are not rendered by default. Learn more about customizing how changed files appear on GitHub.

‎datafusion/physical-plan/Cargo.toml‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -64,6 +64,7 @@ arrow-data = { workspace = true }
6464
arrow-ipc = { workspace = true, features = ["lz4", "zstd"] }
6565
arrow-ord = { workspace = true }
6666
arrow-schema = { workspace = true }
67+
arrow-select = { workspace = true }
6768
async-trait = { workspace = true }
6869
bytes = { workspace = true }
6970
datafusion-common = { workspace = true }

‎datafusion/physical-plan/src/spill/mod.rs‎

Lines changed: 86 additions & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -21,8 +21,8 @@ use std::sync::{Arc, LazyLock};
2121
use std::task::{Context, Poll};
2222

2323
use arrow::array::{
24-
Array, ArrayRef, BinaryViewArray, BufferSpec, GenericByteViewArray, StringViewArray,
25-
layout, make_array,
24+
Array, ArrayRef, AsArray, BinaryViewArray, BufferSpec, GenericByteViewArray,
25+
StringViewArray, layout, make_array,
2626
};
2727
use arrow::buffer::{Buffer, ScalarBuffer};
2828
use arrow::datatypes::DataType;
@@ -37,6 +37,7 @@ use arrow_data::{ArrayDataBuilder, ByteView, MAX_INLINE_VIEW_LEN};
3737
#[cfg(test)]
3838
use arrow_ipc::writer::StreamWriter;
3939
use arrow_ipc::{CompressionType, root_as_message};
40+
use arrow_select::dictionary::garbage_collect_any_dictionary;
4041

4142
use datafusion_common::config::SpillCompression;
4243
use datafusion_common::{Result, internal_datafusion_err};
@@ -736,7 +737,7 @@ fn get_max_alignment_for_schema(schema: &Schema) -> usize {
736737
#[cfg(test)]
737738
const VIEW_SIZE_BYTES: usize = 16;
738739

739-
/// Performs garbage collection on StringView and BinaryView arrays before spilling to reduce memory usage.
740+
/// Compacts view buffers and oversized dictionaries before spilling.
740741
///
741742
/// # Why GC is needed
742743
///
@@ -757,19 +758,25 @@ const VIEW_SIZE_BYTES: usize = 16;
757758
/// containing only the data referenced by the current views
758759
/// 4. Returns a new batch with GC'd arrays (or original arrays if GC not needed)
759760
///
761+
/// Dictionary arrays with more values than keys are also compacted using Arrow's
762+
/// dictionary garbage collector before visiting their children. This avoids spilling
763+
/// whole value tables retained by sliced or merged dictionaries.
764+
///
760765
/// # When GC is triggered
761766
///
762-
/// GC is only performed when data buffers exceed a threshold (currently 10KB).
767+
/// View GC is only performed when data buffers exceed a threshold (currently 10KB).
763768
/// This balances memory savings against the CPU overhead of garbage collection.
764-
/// Small arrays are passed through unchanged since the GC overhead would exceed
769+
/// Small view buffers are passed through unchanged since the GC overhead would exceed
765770
/// any memory savings.
766771
///
767772
/// # Performance considerations
768773
///
769-
/// - If no view arrays need compaction, the original batch is cloned cheaply
770-
/// - GC is skipped for small buffers to avoid unnecessary CPU overhead
774+
/// - If no arrays need compaction, the original batch is cloned cheaply
775+
/// - View GC is skipped for small buffers to avoid unnecessary CPU overhead
771776
/// - Nested container types are traversed recursively so view arrays inside
772777
/// `List`, `Map`, `Union`, `Dictionary`, and other child-bearing arrays are compacted too
778+
/// - Traversal uses physical children, not logical reachability. For example,
779+
/// unused ListView child entries can still retain dictionary values
773780
/// - The Arrow `gc()` method itself is optimized and only copies referenced data
774781
pub(crate) fn gc_view_arrays(batch: &RecordBatch) -> Result<RecordBatch> {
775782
let mut mutated = false;
@@ -810,6 +817,15 @@ fn gc_array(array: &ArrayRef) -> Result<(ArrayRef, bool)> {
810817
None => (Arc::clone(array), false),
811818
})
812819
}
820+
DataType::Dictionary(_, _)
821+
if array.as_any_dictionary().values().len() > array.len() =>
822+
{
823+
// Struct-valued merge dictionaries can concatenate whole value tables.
824+
// Prune the outer dictionary before compacting its retained children.
825+
let compacted = garbage_collect_any_dictionary(array.as_any_dictionary())?;
826+
let (compacted, _) = gc_array_children(&compacted)?;
827+
Ok((compacted, true))
828+
}
813829
_ => gc_array_children(array),
814830
}
815831
}
@@ -992,9 +1008,12 @@ mod tests {
9921008
use crate::metrics::SpillMetrics;
9931009
use crate::spill::spill_manager::SpillManager;
9941010
use crate::test::build_table_i32;
995-
use arrow::array::{ArrayRef, Int32Array, StringArray};
1011+
use arrow::array::{
1012+
ArrayRef, DictionaryArray, Int32Array, ListArray, StringArray, StructArray,
1013+
};
1014+
use arrow::buffer::OffsetBuffer;
9961015
use arrow::compute::cast;
997-
use arrow::datatypes::{DataType, Field};
1016+
use arrow::datatypes::{DataType, Field, Int32Type};
9981017
use arrow::ipc::reader::StreamReader;
9991018
use datafusion_execution::runtime_env::RuntimeEnv;
10001019
use futures::StreamExt as _;
@@ -2693,6 +2712,64 @@ mod tests {
26932712
Ok(())
26942713
}
26952714

2715+
#[rstest::rstest]
2716+
#[case(SpillCompression::Uncompressed)]
2717+
#[case(SpillCompression::Lz4Frame)]
2718+
#[case(SpillCompression::Zstd)]
2719+
#[tokio::test]
2720+
async fn test_spill_prunes_unused_nested_dictionary_values(
2721+
#[case] compression: SpillCompression,
2722+
) -> Result<()> {
2723+
let values = Arc::new(StructArray::from(vec![
2724+
(
2725+
Arc::new(Field::new("id", DataType::Int32, false)),
2726+
Arc::new(Int32Array::from_iter_values(0..1024)) as ArrayRef,
2727+
),
2728+
(
2729+
Arc::new(Field::new("name", DataType::Utf8View, false)),
2730+
Arc::new(StringViewArray::from_iter_values(
2731+
(0..1024).map(|id| format!("{id}:{}", "x".repeat(256))),
2732+
)) as ArrayRef,
2733+
),
2734+
])) as ArrayRef;
2735+
let batch = |keys, values| -> Result<RecordBatch> {
2736+
let dictionary = DictionaryArray::<Int32Type>::try_new(keys, values)?;
2737+
let list = ListArray::new(
2738+
Arc::new(Field::new_list_field(dictionary.data_type().clone(), true)),
2739+
OffsetBuffer::new(vec![0_i32, 1, 3, 4].into()),
2740+
Arc::new(dictionary),
2741+
None,
2742+
);
2743+
Ok(RecordBatch::try_from_iter([(
2744+
"stacktrace",
2745+
Arc::new(list) as ArrayRef,
2746+
)])?)
2747+
};
2748+
let input = batch(
2749+
Int32Array::from(vec![Some(1023), None, Some(17), Some(1023)]),
2750+
Arc::clone(&values),
2751+
)?;
2752+
let expected = batch(
2753+
Int32Array::from(vec![Some(1), None, Some(0), Some(1)]),
2754+
arrow::compute::take(&values, &Int32Array::from(vec![17, 1023]), None)?,
2755+
)?;
2756+
let metrics = SpillMetrics::new(&ExecutionPlanMetricsSet::new(), 0);
2757+
let manager =
2758+
SpillManager::new(Arc::new(RuntimeEnv::default()), metrics, input.schema())
2759+
.with_compression_type(compression);
2760+
let file = manager
2761+
.spill_record_batch_and_finish(&[input], "nested dictionary GC")?
2762+
.unwrap();
2763+
let size = file.size().unwrap();
2764+
assert!(
2765+
size < 16 * 1024,
2766+
"unused dictionary values spilled: {size} bytes"
2767+
);
2768+
let actual = collect(manager.read_spill_as_stream(file, None)?).await?;
2769+
assert_eq!(actual, vec![expected]);
2770+
Ok(())
2771+
}
2772+
26962773
#[tokio::test]
26972774
async fn test_spill_file_size_gc_verification_string_view() -> Result<()> {
26982775
use arrow::array::StringViewArray;

0 commit comments

Comments
 (0)