Skip to content

Commit 0938167

Browse files
committed
fix: keep shared view bytes and spilled view buffers charged once
- Keep `batch_size` for a run whose views share bytes, as dictionary-encoded Parquet strings do. Compacting such views copies the shared bytes once per row, so every split batch would keep and be charged for the whole buffer. - Compact view arrays with several data buffers before spilling unless their views share bytes. Read back, each buffer is a slice of one IPC message and is charged for all of it.
1 parent f8e57d3 commit 0938167

3 files changed

Lines changed: 113 additions & 20 deletions

File tree

‎datafusion/physical-plan/src/sorts/sort.rs‎

Lines changed: 8 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -35,7 +35,7 @@ use crate::sorts::streaming_merge::{
3535
};
3636
use crate::spill::in_progress_spill_file::InProgressSpillFile;
3737
use crate::spill::spill_manager::{GetSlicedSize, SpillManager};
38-
use crate::spill::{gc_view_arrays, get_record_batch_memory_size};
38+
use crate::spill::{gc_view_arrays, get_record_batch_memory_size, views_share_bytes};
3939
use crate::statistics::{ChildStats, StatisticsArgs, with_per_partition_fetch};
4040
use crate::stream::ReservationStream;
4141
use crate::stream::{ObservedStream, RecordBatchStreamAdapter};
@@ -1037,6 +1037,12 @@ impl ExternalSorter {
10371037
let expressions = self.expr.clone();
10381038
let merge_pool = Arc::clone(&self.merge_pool);
10391039
let elapsed_compute = self.metrics.baseline.elapsed_compute().clone();
1040+
// Split batches of views sharing bytes would each be charged for them
1041+
let batch_size = if batch_size < self.batch_size && views_share_bytes(&batch) {
1042+
self.batch_size
1043+
} else {
1044+
batch_size
1045+
};
10401046
// Set when `merge_run_batch_size` split this run
10411047
let split = batch_size < self.batch_size;
10421048

@@ -1107,7 +1113,7 @@ impl ExternalSorter {
11071113
/// small. The merge output still uses `batch_size`. Runs keep `batch_size`
11081114
/// when their batches would share buffers other than the data of top-level
11091115
/// view columns, such as dictionary values, since every batch is charged for
1110-
/// them.
1116+
/// them. `sort_run` also keeps it for a run whose views share bytes.
11111117
fn merge_run_batch_size(&self) -> usize {
11121118
let limited = !matches!(
11131119
self.runtime.memory_pool.memory_limit(),

‎datafusion/physical-plan/src/sorts/sort/spill_tests.rs‎

Lines changed: 62 additions & 12 deletions
Original file line numberDiff line numberDiff line change
@@ -215,6 +215,13 @@ fn sorter(
215215
}
216216

217217
async fn assert_released(pool: &AdjustablePool, runtime: &RuntimeEnv) {
218+
wait_until_released(pool, runtime).await;
219+
let state = pool.state.lock().unwrap();
220+
assert!(state.peak <= pool.capacity);
221+
assert_eq!(state.unchecked_over_limit, 0);
222+
}
223+
224+
async fn wait_until_released(pool: &AdjustablePool, runtime: &RuntimeEnv) {
218225
// Buffered readers may finish dropping their state after the owning stream.
219226
tokio::time::timeout(Duration::from_secs(5), async {
220227
while pool.reserved() != 0
@@ -227,9 +234,6 @@ async fn assert_released(pool: &AdjustablePool, runtime: &RuntimeEnv) {
227234
.await
228235
.expect("sort reservations and spill files must be released");
229236
assert_eq!(runtime.disk_manager.used_disk_space(), 0);
230-
let state = pool.state.lock().unwrap();
231-
assert!(state.peak <= pool.capacity);
232-
assert_eq!(state.unchecked_over_limit, 0);
233237
}
234238

235239
async fn check_spill_preserves_merge_workspace_after_limit_decreases() -> Result<()> {
@@ -696,7 +700,7 @@ async fn check_merge_keys_larger_than_batches() -> Result<()> {
696700
]
697701
};
698702
let int_fields = [("a", DataType::Int32), ("b", DataType::Int32)];
699-
check_merge_keys(&int_fields, 2, |batch| Ok(int_keys(batch))).await?;
703+
check_merge_keys(&int_fields, 2, 16, true, |batch| Ok(int_keys(batch))).await?;
700704
// Longer than 12 bytes, so views keep them in data buffers.
701705
let strings = |batch: i32| -> StringArray {
702706
(0..rows)
@@ -707,25 +711,66 @@ async fn check_merge_keys_larger_than_batches() -> Result<()> {
707711
DataType::Dictionary(Box::new(DataType::Int32), Box::new(DataType::Utf8));
708712
for payload in [DataType::Utf8View, dictionary] {
709713
let fields = [&int_fields[..], &[("c", payload.clone())]].concat();
710-
check_merge_keys(&fields, 2, |batch| {
714+
check_merge_keys(&fields, 2, 16, true, |batch| {
711715
let payload = cast(&strings(batch), &payload)?;
712716
Ok([int_keys(batch), vec![payload]].concat())
713717
})
714718
.await?;
715719
}
716-
check_merge_keys(&[("k", DataType::FixedSizeBinary(16))], 1, |batch| {
717-
let keys = (0..rows).map(|i| u128::from(((i * 31 + batch) % 1000) as u32));
718-
let keys = FixedSizeBinaryArray::try_from_iter(keys.map(u128::to_be_bytes))?;
719-
Ok(vec![Arc::new(keys)])
720+
// Views into 1024 dictionary values share their bytes, as a
721+
// dictionary-encoded Parquet column produces. Sorting the buffered batches
722+
// before a spill grows past the pool, on `main` too.
723+
let fields = [&int_fields[..], &[("c", DataType::Utf8View)]].concat();
724+
check_merge_keys(&fields, 2, 16, false, |batch| {
725+
let values: StringArray = (0..1024)
726+
.map(|v| Some(format!("{batch:>4}-{v:0>59}")))
727+
.collect();
728+
let keys =
729+
Int32Array::from_iter_values((0..rows).map(|i| (i * 7 + batch) % 1024));
730+
let views = cast(
731+
&DictionaryArray::try_new(keys, Arc::new(values))?,
732+
&DataType::Utf8View,
733+
)?;
734+
Ok([int_keys(batch), vec![views]].concat())
735+
})
736+
.await?;
737+
// Batches that do not overlap, so a merged batch takes the strings of
738+
// several split batches of one run, in as many buffers.
739+
let view_keys = [("a", DataType::Utf8View), ("b", DataType::Utf8View)];
740+
check_merge_keys(&view_keys, 2, 8, true, |batch| {
741+
let keys = |key: &str| -> Result<ArrayRef> {
742+
let strings: StringArray = (0..rows)
743+
.rev()
744+
.map(|i| Some(format!("{batch:0>4}{key}{i:0>61}")))
745+
.collect();
746+
Ok(cast(&strings, &DataType::Utf8View)?)
747+
};
748+
Ok(vec![keys("a")?, keys("b")?])
720749
})
750+
.await?;
751+
check_merge_keys(
752+
&[("k", DataType::FixedSizeBinary(16))],
753+
1,
754+
16,
755+
true,
756+
|batch| {
757+
let keys = (0..rows).map(|i| u128::from(((i * 31 + batch) % 1000) as u32));
758+
let keys = FixedSizeBinaryArray::try_from_iter(keys.map(u128::to_be_bytes))?;
759+
Ok(vec![Arc::new(keys)])
760+
},
761+
)
721762
.await
722763
}
723764

724765
/// Sorts 64 batches of `columns` by the first `keys` fields with room to buffer
725-
/// 16 of them, then checks the spilled output and that all memory is released.
766+
/// `buffered` of them, then checks the spilled output and that all memory is
767+
/// released. Unless `within_pool`, the pool may have been exceeded by an
768+
/// unchecked `grow`.
726769
async fn check_merge_keys(
727770
fields: &[(&str, DataType)],
728771
keys: usize,
772+
buffered: usize,
773+
within_pool: bool,
729774
columns: impl Fn(i32) -> Result<Vec<ArrayRef>>,
730775
) -> Result<()> {
731776
let schema = Arc::new(Schema::new(
@@ -742,7 +787,8 @@ async fn check_merge_keys(
742787
PhysicalSortExpr::new_default(Arc::new(Column::new(fields[i].0, i)))
743788
}))
744789
.expect("at least one sort key");
745-
let capacity = MERGE_BYTES + 16 * get_reserved_bytes_for_record_batch(&batches[0])?;
790+
let capacity =
791+
MERGE_BYTES + buffered * get_reserved_bytes_for_record_batch(&batches[0])?;
746792
let pool = AdjustablePool::new(capacity);
747793
let runtime = RuntimeEnvBuilder::new()
748794
.with_memory_pool(Arc::clone(&pool) as Arc<dyn MemoryPool>)
@@ -766,7 +812,11 @@ async fn check_merge_keys(
766812
let expected = sort_batch(&concat_batches(&schema, &batches)?, &ordering, None)?;
767813
assert_eq!(concat_batches(&schema, &output)?, expected);
768814
drop(sorter);
769-
assert_released(&pool, &runtime).await;
815+
if within_pool {
816+
assert_released(&pool, &runtime).await;
817+
} else {
818+
wait_until_released(&pool, &runtime).await;
819+
}
770820
Ok(())
771821
}
772822

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

Lines changed: 43 additions & 6 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;
@@ -823,9 +823,11 @@ fn gc_array(array: &ArrayRef) -> Result<(ArrayRef, bool)> {
823823
/// batch, and `gc()` copies it once per row
824824
/// (<https://github.com/apache/datafusion/issues/23564>).
825825
///
826-
/// Repeated buffer entries are merged first. `gc()` then runs only if it
827-
/// writes less than the merged buffers hold, and runs on the original array
828-
/// so that the views are rewritten at most once.
826+
/// Repeated buffer entries are merged first. `gc()` then runs if it writes
827+
/// less than the merged buffers hold, or if several buffers remain and the
828+
/// views share no bytes, since each buffer read back from the spill is a slice
829+
/// of one IPC message and is charged for all of it. It runs on the original
830+
/// array so that the views are rewritten at most once.
829831
fn compact_view_array<T: ByteViewType>(
830832
array: &GenericByteViewArray<T>,
831833
) -> Option<GenericByteViewArray<T>> {
@@ -836,7 +838,9 @@ fn compact_view_array<T: ByteViewType>(
836838

837839
let (remap, unique) = dedup_buffer_entries(buffers);
838840
let unique_size: usize = unique.iter().map(|b| b.len()).sum();
839-
if should_gc_view_array(array, unique_size) {
841+
if should_gc_view_array(array, unique_size)
842+
|| (unique.len() > 1 && array.total_buffer_bytes_used() <= unique_size)
843+
{
840844
return Some(array.gc());
841845
}
842846
if unique.len() == buffers.len() {
@@ -895,6 +899,21 @@ fn dedup_buffer_entries(buffers: &[Buffer]) -> (Vec<u32>, Vec<Buffer>) {
895899
(remap, unique)
896900
}
897901

902+
/// Returns whether a view column of `batch` references more bytes than its
903+
/// data buffers hold, as the views of a dictionary-encoded Parquet column do.
904+
/// Compacting such views would copy the shared bytes once per row.
905+
pub(crate) fn views_share_bytes(batch: &RecordBatch) -> bool {
906+
fn shares_bytes<T: ByteViewType>(array: &GenericByteViewArray<T>) -> bool {
907+
let (_, unique) = dedup_buffer_entries(array.data_buffers());
908+
array.total_buffer_bytes_used() > unique.iter().map(|b| b.len()).sum::<usize>()
909+
}
910+
batch.columns().iter().any(|array| match array.data_type() {
911+
DataType::Utf8View => shares_bytes(array.as_string_view()),
912+
DataType::BinaryView => shares_bytes(array.as_binary_view()),
913+
_ => false,
914+
})
915+
}
916+
898917
fn gc_array_children(array: &ArrayRef) -> Result<(ArrayRef, bool)> {
899918
let data = array.to_data();
900919
if data.child_data().is_empty() {
@@ -2519,6 +2538,24 @@ mod tests {
25192538
Ok((dictionary, merged.as_string_view().clone()))
25202539
}
25212540

2541+
#[test]
2542+
fn test_views_share_bytes() -> Result<()> {
2543+
use arrow::array::UInt32Array;
2544+
use arrow::compute::take;
2545+
2546+
// 8192 views over 1024 values reference 8x the dictionary's bytes
2547+
let dictionary = dictionary_array(1024)?;
2548+
let indices = UInt32Array::from_iter_values((0..8192).map(|i| i % 1024));
2549+
let batch =
2550+
RecordBatch::try_from_iter([("c", take(&dictionary, &indices, None)?)])?;
2551+
assert!(views_share_bytes(&batch));
2552+
// 8192 values used once each reference exactly the buffer's bytes
2553+
let views: ArrayRef = Arc::new(dictionary_array(8192)?);
2554+
let batch = RecordBatch::try_from_iter([("c", views)])?;
2555+
assert!(!views_share_bytes(&batch));
2556+
Ok(())
2557+
}
2558+
25222559
#[test]
25232560
fn test_gc_keeps_shared_dictionary_buffer() -> Result<()> {
25242561
let (dictionary, merged) = shared_dictionary_views(1000, 8, 1024)?;

0 commit comments

Comments
 (0)