Skip to content

Commit 0e71291

Browse files
committed
perf: size fixed-width computed sort keys from their type
A computed key counted as larger than the run, so its runs were always split under a memory limit. With a computed integer key and a `Utf8View` payload, the compaction of split batches copied every string. Size such keys from their type when it has a fixed width. The shared-views case now sorts by a string cast, which still counts as larger.
1 parent b29d5b0 commit 0e71291

2 files changed

Lines changed: 42 additions & 23 deletions

File tree

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

Lines changed: 18 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -1123,19 +1123,30 @@ impl ExternalSorter {
11231123
}
11241124

11251125
/// Returns whether the row-format keys of `run` may be larger than `run`. A
1126-
/// computed key counts as larger, since sizing it would evaluate it again.
1126+
/// computed key is sized from its type if that has a fixed width, and
1127+
/// otherwise counts as larger, since sizing it would evaluate it again.
11271128
fn encoded_keys_may_exceed(&self, run: &RecordBatch) -> Result<bool> {
11281129
// An 8-byte offset per row, then a null byte and the bytes of each key
11291130
let mut encoded = run.num_rows() * size_of::<usize>();
11301131
for sort_expr in self.expr.iter() {
1131-
let Some(column) = sort_expr.expr.downcast_ref::<Column>() else {
1132-
return Ok(true);
1133-
};
1134-
encoded += run.num_rows()
1135-
+ run
1132+
let key_bytes = match sort_expr.expr.downcast_ref::<Column>() {
1133+
Some(column) => run
11361134
.column(column.index())
11371135
.to_data()
1138-
.get_slice_memory_size()?;
1136+
.get_slice_memory_size()?,
1137+
None => {
1138+
let width = sort_expr
1139+
.expr
1140+
.data_type(self.schema.as_ref())
1141+
.ok()
1142+
.and_then(|data_type| data_type.primitive_width());
1143+
let Some(width) = width else {
1144+
return Ok(true);
1145+
};
1146+
run.num_rows() * width
1147+
}
1148+
};
1149+
encoded += run.num_rows() + key_bytes;
11391150
}
11401151
Ok(encoded > run.get_sliced_size()?)
11411152
}

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

Lines changed: 24 additions & 16 deletions
Original file line numberDiff line numberDiff line change
@@ -721,14 +721,14 @@ async fn check_merge_keys_larger_than_batches() -> Result<()> {
721721
.await?;
722722
}
723723
// Views into 1024 dictionary values share their bytes, as a
724-
// dictionary-encoded Parquet column produces. A computed key counts as
725-
// larger than the run, so only the shared views keep these runs at
726-
// `batch_size`. Sorting the buffered batches before a spill grows past the
727-
// pool, on `main` too.
724+
// dictionary-encoded Parquet column produces. A computed key without a
725+
// fixed width counts as larger than the run, so only the shared views keep
726+
// these runs at `batch_size`. Sorting the buffered batches before a spill
727+
// grows past the pool, on `main` too.
728728
let fields = [&int_fields[..], &[("c", DataType::Utf8View)]].concat();
729729
let a: Arc<dyn PhysicalExpr> = Arc::new(Column::new("a", 0));
730730
let keys = vec![
731-
Arc::new(CastExpr::new(a, DataType::Int64, None)) as Arc<dyn PhysicalExpr>,
731+
Arc::new(CastExpr::new(a, DataType::Utf8, None)) as Arc<dyn PhysicalExpr>,
732732
Arc::new(Column::new("b", 1)),
733733
];
734734
check_merge_exprs(&fields, keys, 16, false, |batch| {
@@ -856,20 +856,21 @@ async fn test_merge_keys_larger_than_batches_multithreaded() -> Result<()> {
856856
fn test_merge_run_batch_size_follows_key_size() -> Result<()> {
857857
let batch_size = 8192;
858858
let rows = batch_size as i32;
859-
let check = |payload: Option<ArrayRef>, expected: usize| -> Result<()> {
859+
// Sorts by `first`, then `b`
860+
let check = |first: Arc<dyn PhysicalExpr>,
861+
payload: Option<ArrayRef>,
862+
expected: usize|
863+
-> Result<()> {
860864
let mut columns: Vec<(&str, ArrayRef)> = vec![
861865
("a", Arc::new(Int64Array::from_iter_values(0..rows as i64))),
862866
("b", Arc::new(Int64Array::from_iter_values(0..rows as i64))),
863867
];
864868
columns.extend(payload.map(|payload| ("c", payload)));
865869
let batch = RecordBatch::try_from_iter(columns)?;
866-
let ordering = LexOrdering::new((0..2).map(|i| {
867-
PhysicalSortExpr::new_default(Arc::new(Column::new(
868-
batch.schema().field(i).name(),
869-
i,
870-
)))
871-
}))
872-
.expect("two sort keys");
870+
let b: Arc<dyn PhysicalExpr> = Arc::new(Column::new("b", 1));
871+
let ordering =
872+
LexOrdering::new([first, b].into_iter().map(PhysicalSortExpr::new_default))
873+
.expect("two sort keys");
873874
let runtime = RuntimeEnvBuilder::new()
874875
.with_memory_limit(1024 * 1024 * 1024, 1.0)
875876
.build_arc()?;
@@ -887,14 +888,21 @@ fn test_merge_run_batch_size_follows_key_size() -> Result<()> {
887888
assert_eq!(sorter.merge_run_batch_size(&batch)?, expected);
888889
Ok(())
889890
};
891+
let a = || Arc::new(Column::new("a", 0)) as Arc<dyn PhysicalExpr>;
890892
// Encoded keys: 26 bytes a row, against 16 bytes a row
891-
check(None, batch_size / 8)?;
893+
check(a(), None, batch_size / 8)?;
892894
// Against 16 + 16 bytes a row: inlined views add more than the keys need
893895
let short: StringViewArray = (0..rows).map(|i| Some(format!("{i}"))).collect();
894-
check(Some(Arc::new(short)), batch_size)?;
896+
check(a(), Some(Arc::new(short)), batch_size)?;
895897
// Against 16 + 16 + 64 bytes a row
896898
let long: StringViewArray = (0..rows).map(|i| Some(format!("{i:0>64}"))).collect();
897-
check(Some(Arc::new(long)), batch_size)
899+
let long: ArrayRef = Arc::new(long);
900+
check(a(), Some(Arc::clone(&long)), batch_size)?;
901+
// A computed key is sized from its type if that has a fixed width, and
902+
// otherwise counts as larger than the run
903+
let cast = |to| Arc::new(CastExpr::new(a(), to, None)) as Arc<dyn PhysicalExpr>;
904+
check(cast(DataType::Int64), Some(Arc::clone(&long)), batch_size)?;
905+
check(cast(DataType::Utf8), Some(long), batch_size / 8)
898906
}
899907

900908
#[tokio::test]

0 commit comments

Comments
 (0)