Skip to content

Commit 9f2595a

Browse files
Dandandanclaude
andcommitted
perf: slice instead of take when probe indices are a contiguous run
When every probe row matches exactly once, the hash join emits probe indices [k, k+1, ..., k+n-1]. Taking a column by those indices copies it element by element to reproduce a range it already has, so slice it instead. The check is one short-circuiting pass over the indices, computed once per batch and reused for every probe-side column. Co-Authored-By: Claude Opus 5 <[email protected]> Claude-Session: https://claude.ai/code/session_01JHNpPfJeJj4qbDxvRvxTMk
1 parent bb038a6 commit 9f2595a

1 file changed

Lines changed: 67 additions & 0 deletions

File tree

  • datafusion/physical-plan/src/joins

‎datafusion/physical-plan/src/joins/utils.rs‎

Lines changed: 67 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1326,6 +1326,27 @@ fn new_empty_schema_batch(schema: &Schema, row_count: usize) -> Result<RecordBat
13261326
)?)
13271327
}
13281328

1329+
/// If `indices` is a contiguous ascending run — `[k, k+1, ..., k+n-1]` — returns
1330+
/// `k`.
1331+
///
1332+
/// A join where every probe row matches exactly once emits exactly that: the
1333+
/// probe rows in order, none skipped. Taking a column by such indices copies it
1334+
/// element by element to reproduce what it already is, so the caller can slice
1335+
/// instead. The scan is one sequential pass over the indices and is amortised
1336+
/// over every column of the output.
1337+
fn contiguous_run_start(indices: &UInt32Array) -> Option<usize> {
1338+
if indices.null_count() > 0 {
1339+
return None;
1340+
}
1341+
let values = indices.values();
1342+
let first = *values.first()? as usize;
1343+
values
1344+
.iter()
1345+
.enumerate()
1346+
.all(|(offset, &value)| value as usize == first + offset)
1347+
.then_some(first)
1348+
}
1349+
13291350
/// Returns a new [RecordBatch] by combining the `left` and `right` according to `indices`.
13301351
/// The resulting batch has [Schema] `schema`.
13311352
#[expect(clippy::too_many_arguments)]
@@ -1355,6 +1376,9 @@ pub(crate) fn build_batch_from_indices(
13551376
// 2. based on the pick, `take` items from the different RecordBatches
13561377
let mut columns: Vec<Arc<dyn Array>> = Vec::with_capacity(schema.fields().len());
13571378

1379+
// Computed once and reused for every probe-side column.
1380+
let probe_run_start = contiguous_run_start(probe_indices);
1381+
13581382
for column_index in column_indices {
13591383
let array = if column_index.side == JoinSide::None {
13601384
// For mark joins, the mark column is a true if the indices is not null, otherwise it will be false
@@ -1375,6 +1399,9 @@ pub(crate) fn build_batch_from_indices(
13751399
if array.is_empty() || probe_indices.null_count() == probe_indices.len() {
13761400
assert_eq!(probe_indices.null_count(), probe_indices.len());
13771401
new_null_array(array.data_type(), probe_indices.len())
1402+
} else if let Some(start) = probe_run_start {
1403+
// The gather would reproduce this range verbatim.
1404+
array.slice(start, probe_indices.len())
13781405
} else {
13791406
take(array.as_ref(), probe_indices, None)?
13801407
}
@@ -4968,4 +4995,44 @@ mod tests {
49684995
Inexact(10)
49694996
);
49704997
}
4998+
4999+
#[test]
5000+
fn contiguous_run_start_detects_runs() {
5001+
// A run starting at zero, and one starting mid-batch: both sliceable.
5002+
assert_eq!(
5003+
contiguous_run_start(&UInt32Array::from(vec![0, 1, 2, 3])),
5004+
Some(0)
5005+
);
5006+
assert_eq!(
5007+
contiguous_run_start(&UInt32Array::from(vec![5, 6, 7])),
5008+
Some(5)
5009+
);
5010+
assert_eq!(contiguous_run_start(&UInt32Array::from(vec![9])), Some(9));
5011+
5012+
// Gaps, repeats and descending order all need a real gather.
5013+
assert_eq!(
5014+
contiguous_run_start(&UInt32Array::from(vec![0, 2, 3])),
5015+
None
5016+
);
5017+
assert_eq!(
5018+
contiguous_run_start(&UInt32Array::from(vec![1, 1, 2])),
5019+
None
5020+
);
5021+
assert_eq!(
5022+
contiguous_run_start(&UInt32Array::from(vec![3, 2, 1])),
5023+
None
5024+
);
5025+
5026+
// Nulls mean unmatched probe rows, so the range is not reproducible.
5027+
assert_eq!(
5028+
contiguous_run_start(&UInt32Array::from(vec![Some(0), None, Some(2)])),
5029+
None
5030+
);
5031+
5032+
// Empty emits nothing; there is no offset to slice from.
5033+
assert_eq!(
5034+
contiguous_run_start(&UInt32Array::from(Vec::<u32>::new())),
5035+
None
5036+
);
5037+
}
49715038
}

0 commit comments

Comments
 (0)