Skip to content

Commit aa1abae

Browse files
committed
Avoid concat_batches
1 parent 9c3c01a commit aa1abae

4 files changed

Lines changed: 226 additions & 66 deletions

File tree

‎datafusion/physical-plan/src/joins/hash_join/exec.rs‎

Lines changed: 101 additions & 24 deletions
Original file line numberDiff line numberDiff line change
@@ -65,8 +65,7 @@ use crate::{
6565
metrics::{ExecutionPlanMetricsSet, MetricsSet},
6666
};
6767

68-
use arrow::array::{ArrayRef, BooleanBufferBuilder};
69-
use arrow::compute::concat_batches;
68+
use arrow::array::{Array, ArrayRef, BooleanBufferBuilder, new_null_array};
7069
use arrow::datatypes::SchemaRef;
7170
use arrow::record_batch::RecordBatch;
7271
use arrow::util::bit_util;
@@ -106,14 +105,14 @@ const ARRAY_MAP_CREATED_COUNT_METRIC_NAME: &str = "array_map_created_count";
106105
#[expect(clippy::too_many_arguments)]
107106
fn try_create_array_map(
108107
bounds: &Option<PartitionBounds>,
109-
schema: &SchemaRef,
108+
_schema: &SchemaRef,
110109
batches: &[RecordBatch],
111110
on_left: &[PhysicalExprRef],
112111
reservation: &mut MemoryReservation,
113112
perfect_hash_join_small_build_threshold: usize,
114113
perfect_hash_join_min_key_density: f64,
115114
null_equality: NullEquality,
116-
) -> Result<Option<(ArrayMap, RecordBatch, Vec<ArrayRef>)>> {
115+
) -> Result<Option<(ArrayMap, Vec<ArrayRef>)>> {
117116
if on_left.len() != 1 {
118117
return Ok(None);
119118
}
@@ -178,22 +177,58 @@ fn try_create_array_map(
178177
let mem_size = ArrayMap::estimate_memory_size(min_val, max_val, num_row);
179178
reservation.try_grow(mem_size)?;
180179

181-
let batch = concat_batches(schema, batches)?;
182-
let left_values = evaluate_expressions_to_arrays(on_left, &batch)?;
180+
// Evaluate key expressions per-batch and concatenate only key columns
181+
let left_values = concat_key_value_arrays(on_left, batches.iter())?;
183182

184183
let array_map = ArrayMap::try_new(&left_values[0], min_val, max_val)?;
185184

186-
Ok(Some((array_map, batch, left_values)))
185+
Ok(Some((array_map, left_values)))
186+
}
187+
188+
/// Evaluate key expressions per-batch and concatenate only the resulting key
189+
/// column arrays. This avoids `concat_batches` on the full data (which would
190+
/// duplicate all columns in memory) while still providing contiguous key arrays
191+
/// for `equal_rows_arr`.
192+
fn concat_key_value_arrays<'a>(
193+
on: &[PhysicalExprRef],
194+
batches: impl Iterator<Item = &'a RecordBatch>,
195+
) -> Result<Vec<ArrayRef>> {
196+
let batches: Vec<&RecordBatch> = batches.collect();
197+
if batches.is_empty() || on.is_empty() {
198+
return Ok(on.iter().map(|_| new_null_array(&DataType::Null, 0)).collect());
199+
}
200+
// Evaluate key expressions for each batch
201+
let per_batch_keys: Vec<Vec<ArrayRef>> = batches
202+
.iter()
203+
.map(|batch| evaluate_expressions_to_arrays(on, batch))
204+
.collect::<Result<Vec<_>>>()?;
205+
// Transpose and concatenate: for each key column, concat across all batches
206+
let num_keys = on.len();
207+
(0..num_keys)
208+
.map(|key_idx| {
209+
let arrays: Vec<&dyn Array> = per_batch_keys
210+
.iter()
211+
.map(|keys| keys[key_idx].as_ref())
212+
.collect();
213+
Ok(arrow::compute::concat(&arrays)?)
214+
})
215+
.collect()
187216
}
188217

189218
/// HashTable and input data for the left (build side) of a join
190219
pub(super) struct JoinLeftData {
191220
/// The hash table with indices into `batch`
192221
/// Arc is used to allow sharing with SharedBuildAccumulator for hash map pushdown
193222
pub(super) map: Arc<Map>,
194-
/// The input rows for the build side
195-
batch: RecordBatch,
196-
/// The build side on expressions values
223+
/// The schema of the build side input
224+
schema: SchemaRef,
225+
/// The input batches for the build side (kept separate to avoid concat_batches)
226+
batches: Vec<RecordBatch>,
227+
/// Prefix-sum of batch sizes for converting flat indices to (batch_idx, row_idx).
228+
/// batch_offsets[i] is the starting flat index for batches[i].
229+
/// Has length batches.len() + 1 (last element is total row count).
230+
batch_offsets: Vec<usize>,
231+
/// The build side on expressions values (concatenated key columns only)
197232
values: Vec<ArrayRef>,
198233
/// Shared bitmap builder for visited left indices
199234
visited_indices_bitmap: SharedBitmapBuilder,
@@ -225,9 +260,29 @@ impl JoinLeftData {
225260
&self.map
226261
}
227262

228-
/// returns a reference to the build side batch
229-
pub(super) fn batch(&self) -> &RecordBatch {
230-
&self.batch
263+
/// Returns a reference to a build-side batch for schema/data-type lookups.
264+
/// If batches exist, returns the first one; otherwise creates an empty batch
265+
/// with the correct build-side schema.
266+
pub(super) fn batch(&self) -> RecordBatch {
267+
self.batches
268+
.first()
269+
.cloned()
270+
.unwrap_or_else(|| RecordBatch::new_empty(Arc::clone(&self.schema)))
271+
}
272+
273+
/// returns a reference to the build side batches
274+
pub(super) fn batches(&self) -> &[RecordBatch] {
275+
&self.batches
276+
}
277+
278+
/// returns the batch offsets for flat-to-(batch,row) index conversion
279+
pub(super) fn batch_offsets(&self) -> &[usize] {
280+
&self.batch_offsets
281+
}
282+
283+
/// returns total number of rows across all build batches
284+
pub(super) fn num_rows(&self) -> usize {
285+
*self.batch_offsets.last().unwrap_or(&0)
231286
}
232287

233288
/// returns a reference to the build side expressions values
@@ -1965,8 +2020,8 @@ async fn collect_left_input(
19652020
_ => None,
19662021
};
19672022

1968-
let (join_hash_map, batch, left_values) =
1969-
if let Some((array_map, batch, left_value)) = try_create_array_map(
2023+
let (join_hash_map, left_values, should_reverse_batches) =
2024+
if let Some((array_map, left_value)) = try_create_array_map(
19702025
&bounds,
19712026
&schema,
19722027
&batches,
@@ -1979,7 +2034,7 @@ async fn collect_left_input(
19792034
array_map_created_count.add(1);
19802035
metrics.build_mem_used.add(array_map.size());
19812036

1982-
(Map::ArrayMap(array_map), batch, left_value)
2037+
(Map::ArrayMap(array_map), left_value, false)
19832038
} else {
19842039
// Estimation of memory size, required for hashtable, prior to allocation.
19852040
// Final result can be verified using `RawTable.allocation_info()`
@@ -2025,21 +2080,41 @@ async fn collect_left_input(
20252080
offset += batch.num_rows();
20262081
}
20272082

2028-
// Merge all batches into a single batch, so we can directly index into the arrays
2029-
let batch = concat_batches(&schema, batches_iter.clone())?;
2030-
2031-
let left_values = evaluate_expressions_to_arrays(&on_left, &batch)?;
2083+
// Evaluate key expressions per-batch and concatenate only the key columns
2084+
// (avoids concat_batches on the full data, saving memory)
2085+
let left_values = concat_key_value_arrays(&on_left, batches_iter.clone())?;
20322086

2033-
(Map::HashMap(hashmap), batch, left_values)
2087+
(Map::HashMap(hashmap), left_values, true)
20342088
};
20352089

2090+
// For HashMap: reverse the batches to match the hash map's flat index ordering.
2091+
// The hash map is built iterating in reverse (last batch first), so flat index 0
2092+
// corresponds to the first row of the last original batch. By reversing, batches[0]
2093+
// is the last original batch, matching the hash map's indexing scheme.
2094+
// For ArrayMap: batches are already in the correct (forward) order since the
2095+
// ArrayMap is built from forward-ordered concatenated key columns.
2096+
let mut batches = batches;
2097+
if should_reverse_batches {
2098+
batches.reverse();
2099+
}
2100+
2101+
// Compute batch_offsets (prefix sum of batch sizes) for flat-to-(batch,row) conversion
2102+
let batch_offsets = {
2103+
let mut offsets = Vec::with_capacity(batches.len() + 1);
2104+
offsets.push(0usize);
2105+
for b in &batches {
2106+
offsets.push(offsets.last().unwrap() + b.num_rows());
2107+
}
2108+
offsets
2109+
};
2110+
20362111
// Reserve additional memory for visited indices bitmap and create shared builder
20372112
let visited_indices_bitmap = if with_visited_indices_bitmap {
2038-
let bitmap_size = bit_util::ceil(batch.num_rows(), 8);
2113+
let bitmap_size = bit_util::ceil(num_rows, 8);
20392114
reservation.try_grow(bitmap_size)?;
20402115
metrics.build_mem_used.add(bitmap_size);
20412116

2042-
let mut bitmap_buffer = BooleanBufferBuilder::new(batch.num_rows());
2117+
let mut bitmap_buffer = BooleanBufferBuilder::new(num_rows);
20432118
bitmap_buffer.append_n(num_rows, false);
20442119
bitmap_buffer
20452120
} else {
@@ -2080,7 +2155,9 @@ async fn collect_left_input(
20802155

20812156
let data = JoinLeftData {
20822157
map,
2083-
batch,
2158+
schema: Arc::clone(&schema),
2159+
batches,
2160+
batch_offsets,
20842161
values: left_values,
20852162
visited_indices_bitmap: Mutex::new(visited_indices_bitmap),
20862163
probe_threads_counter: AtomicUsize::new(probe_threads_count),

‎datafusion/physical-plan/src/joins/hash_join/stream.rs‎

Lines changed: 31 additions & 20 deletions
Original file line numberDiff line numberDiff line change
@@ -649,7 +649,7 @@ impl HashJoinStream {
649649
if is_empty && self.filter.is_none() {
650650
let result = build_batch_empty_build_side(
651651
&self.schema,
652-
build_side.left_data.batch(),
652+
&build_side.left_data.batch(),
653653
&state.batch,
654654
&self.column_indices,
655655
self.join_type,
@@ -706,7 +706,8 @@ impl HashJoinStream {
706706
// apply join filter if exists
707707
let (left_indices, right_indices) = if let Some(filter) = &self.filter {
708708
apply_join_filter_to_indices(
709-
build_side.left_data.batch(),
709+
build_side.left_data.batches(),
710+
build_side.left_data.batch_offsets(),
710711
&state.batch,
711712
left_indices,
712713
right_indices,
@@ -767,23 +768,32 @@ impl HashJoinStream {
767768
)?;
768769

769770
// Build output batch and push to coalescer
770-
let (build_batch, probe_batch, join_side) =
771-
if self.join_type == JoinType::RightMark {
772-
(&state.batch, build_side.left_data.batch(), JoinSide::Right)
773-
} else {
774-
(build_side.left_data.batch(), &state.batch, JoinSide::Left)
775-
};
776-
777-
let batch = build_batch_from_indices(
778-
&self.schema,
779-
build_batch,
780-
probe_batch,
781-
&left_indices,
782-
&right_indices,
783-
&self.column_indices,
784-
join_side,
785-
self.join_type,
786-
)?;
771+
let batch = if self.join_type == JoinType::RightMark {
772+
let num_rows = state.batch.num_rows();
773+
build_batch_from_indices(
774+
&self.schema,
775+
std::slice::from_ref(&state.batch),
776+
&[0, num_rows],
777+
&build_side.left_data.batch(),
778+
&left_indices,
779+
&right_indices,
780+
&self.column_indices,
781+
JoinSide::Right,
782+
self.join_type,
783+
)?
784+
} else {
785+
build_batch_from_indices(
786+
&self.schema,
787+
build_side.left_data.batches(),
788+
build_side.left_data.batch_offsets(),
789+
&state.batch,
790+
&left_indices,
791+
&right_indices,
792+
&self.column_indices,
793+
JoinSide::Left,
794+
self.join_type,
795+
)?
796+
};
787797

788798
let push_status = self.output_buffer.push_batch(batch)?;
789799

@@ -895,7 +905,8 @@ impl HashJoinStream {
895905
let empty_right_batch = RecordBatch::new_empty(self.right.schema());
896906
let batch = build_batch_from_indices(
897907
&self.schema,
898-
build_side.left_data.batch(),
908+
build_side.left_data.batches(),
909+
build_side.left_data.batch_offsets(),
899910
&empty_right_batch,
900911
&left_side,
901912
&right_side,

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

Lines changed: 9 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -951,9 +951,11 @@ pub(crate) fn build_side_determined_results(
951951
// Create an empty probe record batch:
952952
let empty_probe_batch = RecordBatch::new_empty(probe_schema);
953953
// Build the final result from the indices of build and probe sides:
954+
let num_rows = build_hash_joiner.input_buffer.num_rows();
954955
build_batch_from_indices(
955956
output_schema.as_ref(),
956-
&build_hash_joiner.input_buffer,
957+
std::slice::from_ref(&build_hash_joiner.input_buffer),
958+
&[0, num_rows],
957959
&empty_probe_batch,
958960
&build_indices,
959961
&probe_indices,
@@ -1015,8 +1017,10 @@ pub(crate) fn join_with_probe_batch(
10151017
)?;
10161018

10171019
let (build_indices, probe_indices) = if let Some(filter) = filter {
1020+
let num_rows = build_hash_joiner.input_buffer.num_rows();
10181021
apply_join_filter_to_indices(
1019-
&build_hash_joiner.input_buffer,
1022+
std::slice::from_ref(&build_hash_joiner.input_buffer),
1023+
&[0, num_rows],
10201024
probe_batch,
10211025
build_indices,
10221026
probe_indices,
@@ -1054,9 +1058,11 @@ pub(crate) fn join_with_probe_batch(
10541058
) {
10551059
Ok(None)
10561060
} else {
1061+
let num_rows = build_hash_joiner.input_buffer.num_rows();
10571062
build_batch_from_indices(
10581063
schema,
1059-
&build_hash_joiner.input_buffer,
1064+
std::slice::from_ref(&build_hash_joiner.input_buffer),
1065+
&[0, num_rows],
10601066
probe_batch,
10611067
&build_indices,
10621068
&probe_indices,

0 commit comments

Comments
 (0)