Skip to content

Commit b808be6

Browse files
committed
WIP
1 parent c4be04d commit b808be6

4 files changed

Lines changed: 261 additions & 188 deletions

File tree

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

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

68-
use arrow::array::{Array, ArrayRef, BooleanBufferBuilder, new_null_array};
68+
use arrow::array::{Array, ArrayRef, BooleanBufferBuilder, UInt64Array, new_null_array};
6969
use arrow::datatypes::SchemaRef;
7070
use arrow::record_batch::RecordBatch;
7171
use arrow::util::bit_util;
@@ -177,43 +177,50 @@ fn try_create_array_map(
177177
let mem_size = ArrayMap::estimate_memory_size(min_val, max_val, num_row);
178178
reservation.try_grow(mem_size)?;
179179

180-
// Evaluate key expressions per-batch and concatenate only key columns
181-
let left_values = concat_key_value_arrays(on_left, batches.iter())?;
180+
// Evaluate key expressions per-batch and concatenate for ArrayMap construction
181+
let per_batch_keys: Vec<Vec<ArrayRef>> = batches
182+
.iter()
183+
.map(|batch| evaluate_expressions_to_arrays(on_left, batch))
184+
.collect::<Result<Vec<_>>>()?;
185+
let left_values: Vec<ArrayRef> = if per_batch_keys.is_empty() || on_left.is_empty() {
186+
on_left
187+
.iter()
188+
.map(|_| new_null_array(&DataType::Null, 0))
189+
.collect()
190+
} else {
191+
let num_keys = on_left.len();
192+
(0..num_keys)
193+
.map(|key_idx| {
194+
let arrays: Vec<&dyn Array> = per_batch_keys
195+
.iter()
196+
.map(|keys| keys[key_idx].as_ref())
197+
.collect();
198+
Ok(arrow::compute::concat(&arrays)?)
199+
})
200+
.collect::<Result<Vec<_>>>()?
201+
};
182202

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

185205
Ok(Some((array_map, left_values)))
186206
}
187207

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
199-
.iter()
200-
.map(|_| new_null_array(&DataType::Null, 0))
201-
.collect());
202-
}
203-
// Evaluate key expressions for each batch
204-
let per_batch_keys: Vec<Vec<ArrayRef>> = batches
208+
/// Convert flat indices (used in the visited bitmap) to packed composite indices
209+
/// `(batch_idx << 32) | row_idx` used by `build_batch_from_indices`.
210+
pub(super) fn flat_to_packed_indices(
211+
flat_indices: &UInt64Array,
212+
batch_offsets: &[usize],
213+
) -> UInt64Array {
214+
flat_indices
215+
.values()
205216
.iter()
206-
.map(|batch| evaluate_expressions_to_arrays(on, batch))
207-
.collect::<Result<Vec<_>>>()?;
208-
// Transpose and concatenate: for each key column, concat across all batches
209-
let num_keys = on.len();
210-
(0..num_keys)
211-
.map(|key_idx| {
212-
let arrays: Vec<&dyn Array> = per_batch_keys
213-
.iter()
214-
.map(|keys| keys[key_idx].as_ref())
215-
.collect();
216-
Ok(arrow::compute::concat(&arrays)?)
217+
.map(|&flat_val| {
218+
let flat = flat_val as usize;
219+
let batch_idx = batch_offsets
220+
.partition_point(|&o| o <= flat)
221+
.saturating_sub(1);
222+
let row_idx = flat - batch_offsets[batch_idx];
223+
((batch_idx as u64) << 32) | (row_idx as u64)
217224
})
218225
.collect()
219226
}
@@ -231,8 +238,9 @@ pub(super) struct JoinLeftData {
231238
/// batch_offsets[i] is the starting flat index for batches[i].
232239
/// Has length batches.len() + 1 (last element is total row count).
233240
batch_offsets: Vec<usize>,
234-
/// The build side on expressions values (concatenated key columns only)
235-
values: Vec<ArrayRef>,
241+
/// The build side key expression values, per batch.
242+
/// values_per_batch[batch_idx][key_idx] is the key column array for that batch.
243+
values_per_batch: Vec<Vec<ArrayRef>>,
236244
/// Shared bitmap builder for visited left indices
237245
visited_indices_bitmap: SharedBitmapBuilder,
238246
/// Counter of running probe-threads, potentially
@@ -283,9 +291,9 @@ impl JoinLeftData {
283291
&self.batch_offsets
284292
}
285293

286-
/// returns a reference to the build side expressions values
287-
pub(super) fn values(&self) -> &[ArrayRef] {
288-
&self.values
294+
/// returns a reference to the build side key expressions values, per batch
295+
pub(super) fn values_per_batch(&self) -> &[Vec<ArrayRef>] {
296+
&self.values_per_batch
289297
}
290298

291299
/// returns a reference to the visited indices bitmap
@@ -2018,8 +2026,8 @@ async fn collect_left_input(
20182026
_ => None,
20192027
};
20202028

2021-
let (join_hash_map, left_values, should_reverse_batches) =
2022-
if let Some((array_map, left_value)) = try_create_array_map(
2029+
let (join_hash_map, should_reverse_batches) = if let Some((array_map, _left_value)) =
2030+
try_create_array_map(
20232031
&bounds,
20242032
&schema,
20252033
&batches,
@@ -2029,61 +2037,57 @@ async fn collect_left_input(
20292037
config.execution.perfect_hash_join_min_key_density,
20302038
null_equality,
20312039
)? {
2032-
array_map_created_count.add(1);
2033-
metrics.build_mem_used.add(array_map.size());
2040+
array_map_created_count.add(1);
2041+
metrics.build_mem_used.add(array_map.size());
20342042

2035-
(Map::ArrayMap(array_map), left_value, false)
2043+
(Map::ArrayMap(array_map), false)
2044+
} else {
2045+
// Estimation of memory size, required for hashtable, prior to allocation.
2046+
// Final result can be verified using `RawTable.allocation_info()`
2047+
let fixed_size_u32 = size_of::<JoinHashMapU32>();
2048+
let fixed_size_u64 = size_of::<JoinHashMapU64>();
2049+
2050+
// Use `u32` indices for the JoinHashMap when num_rows ≤ u32::MAX, otherwise use the
2051+
// `u64` indice variant
2052+
// Arc is used instead of Box to allow sharing with SharedBuildAccumulator for hash map pushdown
2053+
let mut hashmap: Box<dyn JoinHashMapType> = if num_rows > u32::MAX as usize {
2054+
let estimated_hashtable_size =
2055+
estimate_memory_size::<(u64, u64)>(num_rows, fixed_size_u64)?;
2056+
reservation.try_grow(estimated_hashtable_size)?;
2057+
metrics.build_mem_used.add(estimated_hashtable_size);
2058+
Box::new(JoinHashMapU64::with_capacity(num_rows))
20362059
} else {
2037-
// Estimation of memory size, required for hashtable, prior to allocation.
2038-
// Final result can be verified using `RawTable.allocation_info()`
2039-
let fixed_size_u32 = size_of::<JoinHashMapU32>();
2040-
let fixed_size_u64 = size_of::<JoinHashMapU64>();
2041-
2042-
// Use `u32` indices for the JoinHashMap when num_rows ≤ u32::MAX, otherwise use the
2043-
// `u64` indice variant
2044-
// Arc is used instead of Box to allow sharing with SharedBuildAccumulator for hash map pushdown
2045-
let mut hashmap: Box<dyn JoinHashMapType> = if num_rows > u32::MAX as usize {
2046-
let estimated_hashtable_size =
2047-
estimate_memory_size::<(u64, u64)>(num_rows, fixed_size_u64)?;
2048-
reservation.try_grow(estimated_hashtable_size)?;
2049-
metrics.build_mem_used.add(estimated_hashtable_size);
2050-
Box::new(JoinHashMapU64::with_capacity(num_rows))
2051-
} else {
2052-
let estimated_hashtable_size =
2053-
estimate_memory_size::<(u32, u64)>(num_rows, fixed_size_u32)?;
2054-
reservation.try_grow(estimated_hashtable_size)?;
2055-
metrics.build_mem_used.add(estimated_hashtable_size);
2056-
Box::new(JoinHashMapU32::with_capacity(num_rows))
2057-
};
2058-
2059-
let mut hashes_buffer = Vec::new();
2060-
let mut offset = 0;
2061-
2062-
let batches_iter = batches.iter().rev();
2063-
2064-
// Updating hashmap starting from the last batch
2065-
for batch in batches_iter.clone() {
2066-
hashes_buffer.clear();
2067-
hashes_buffer.resize(batch.num_rows(), 0);
2068-
update_hash(
2069-
&on_left,
2070-
batch,
2071-
&mut *hashmap,
2072-
offset,
2073-
&random_state,
2074-
&mut hashes_buffer,
2075-
0,
2076-
true,
2077-
)?;
2078-
offset += batch.num_rows();
2079-
}
2060+
let estimated_hashtable_size =
2061+
estimate_memory_size::<(u32, u64)>(num_rows, fixed_size_u32)?;
2062+
reservation.try_grow(estimated_hashtable_size)?;
2063+
metrics.build_mem_used.add(estimated_hashtable_size);
2064+
Box::new(JoinHashMapU32::with_capacity(num_rows))
2065+
};
20802066

2081-
// Evaluate key expressions per-batch and concatenate only the key columns
2082-
// (avoids concat_batches on the full data, saving memory)
2083-
let left_values = concat_key_value_arrays(&on_left, batches_iter.clone())?;
2067+
let mut hashes_buffer = Vec::new();
2068+
let mut offset = 0;
2069+
2070+
let batches_iter = batches.iter().rev();
2071+
2072+
// Updating hashmap starting from the last batch
2073+
for batch in batches_iter.clone() {
2074+
hashes_buffer.clear();
2075+
hashes_buffer.resize(batch.num_rows(), 0);
2076+
update_hash(
2077+
&on_left,
2078+
batch,
2079+
&mut *hashmap,
2080+
offset,
2081+
&random_state,
2082+
&mut hashes_buffer,
2083+
0,
2084+
true,
2085+
)?;
2086+
offset += batch.num_rows();
2087+
}
20842088

2085-
(Map::HashMap(hashmap), left_values, true)
2086-
};
2089+
(Map::HashMap(hashmap), true)
2090+
};
20872091

20882092
// For HashMap: reverse the batches to match the hash map's flat index ordering.
20892093
// The hash map is built iterating in reverse (last batch first), so flat index 0
@@ -2096,7 +2100,27 @@ async fn collect_left_input(
20962100
batches.reverse();
20972101
}
20982102

2099-
// Compute batch_offsets (prefix sum of batch sizes) for flat-to-(batch,row) conversion
2103+
// Evaluate key expressions per-batch (no concatenation needed for equal_rows_arr)
2104+
let values_per_batch: Vec<Vec<ArrayRef>> = if batches.is_empty() {
2105+
let empty_batch = RecordBatch::new_empty(Arc::clone(&schema));
2106+
let empty_keys = on_left
2107+
.iter()
2108+
.map(|c| c.evaluate(&empty_batch)?.into_array(0))
2109+
.collect::<Result<Vec<_>>>()?;
2110+
vec![empty_keys]
2111+
} else {
2112+
batches
2113+
.iter()
2114+
.map(|batch| {
2115+
on_left
2116+
.iter()
2117+
.map(|c| c.evaluate(batch)?.into_array(batch.num_rows()))
2118+
.collect::<Result<Vec<_>>>()
2119+
})
2120+
.collect::<Result<Vec<_>>>()?
2121+
};
2122+
2123+
// Compute batch_offsets (prefix sum of batch sizes) for flat-to-packed index conversion
21002124
let batch_offsets = {
21012125
let mut offsets = Vec::with_capacity(batches.len() + 1);
21022126
offsets.push(0usize);
@@ -2124,23 +2148,38 @@ async fn collect_left_input(
21242148
let membership = if num_rows == 0 {
21252149
PushdownStrategy::Empty
21262150
} else {
2127-
// If the build side is small enough we can use IN list pushdown.
2128-
// If it's too big we fall back to pushing down a reference to the hash table.
2129-
// See `PushdownStrategy` for more details.
2130-
let estimated_size = left_values
2151+
// For membership testing, we need concatenated key columns.
2152+
// Concat from the per-batch values.
2153+
let concat_values: Vec<ArrayRef> =
2154+
if values_per_batch.is_empty() || values_per_batch[0].is_empty() {
2155+
vec![]
2156+
} else {
2157+
let num_keys = values_per_batch[0].len();
2158+
(0..num_keys)
2159+
.map(|key_idx| {
2160+
let arrays: Vec<&dyn Array> = values_per_batch
2161+
.iter()
2162+
.map(|keys| keys[key_idx].as_ref())
2163+
.collect();
2164+
Ok(arrow::compute::concat(&arrays)?)
2165+
})
2166+
.collect::<Result<Vec<_>>>()?
2167+
};
2168+
2169+
let estimated_size = concat_values
21312170
.iter()
21322171
.map(|arr| arr.get_array_memory_size())
21332172
.sum::<usize>();
2134-
if left_values.is_empty()
2135-
|| left_values[0].is_empty()
2173+
if concat_values.is_empty()
2174+
|| concat_values[0].is_empty()
21362175
|| estimated_size > config.optimizer.hash_join_inlist_pushdown_max_size
21372176
|| map.num_of_distinct_key()
21382177
> config
21392178
.optimizer
21402179
.hash_join_inlist_pushdown_max_distinct_values
21412180
{
21422181
PushdownStrategy::Map(Arc::clone(&map))
2143-
} else if let Some(in_list_values) = build_struct_inlist_values(&left_values)? {
2182+
} else if let Some(in_list_values) = build_struct_inlist_values(&concat_values)? {
21442183
PushdownStrategy::InList(in_list_values)
21452184
} else {
21462185
PushdownStrategy::Map(Arc::clone(&map))
@@ -2156,7 +2195,7 @@ async fn collect_left_input(
21562195
schema: Arc::clone(&schema),
21572196
batches,
21582197
batch_offsets,
2159-
values: left_values,
2198+
values_per_batch,
21602199
visited_indices_bitmap: Mutex::new(visited_indices_bitmap),
21612200
probe_threads_counter: AtomicUsize::new(probe_threads_count),
21622201
_reservation: reservation,
@@ -4416,7 +4455,8 @@ mod tests {
44164455
let mut build_indices_buffer = Vec::new();
44174456
let (l, r, _) = lookup_join_hashmap(
44184457
&join_hash_map,
4419-
&[left_keys_values],
4458+
&[vec![left_keys_values]],
4459+
&[0, left.num_rows()],
44204460
&[right_keys_values],
44214461
NullEquality::NullEqualsNothing,
44224462
&hashes_buffer,
@@ -4477,7 +4517,8 @@ mod tests {
44774517
let mut build_indices_buffer = Vec::new();
44784518
let (l, r, _) = lookup_join_hashmap(
44794519
&join_hash_map,
4480-
&[left_keys_values],
4520+
&[vec![left_keys_values]],
4521+
&[0, left.num_rows()],
44814522
&[right_keys_values],
44824523
NullEquality::NullEqualsNothing,
44834524
&hashes_buffer,

0 commit comments

Comments
 (0)