You are viewing a plain text version of this content. The canonical link for it is here.
Posted to github@arrow.apache.org by "Rossil2012 (via GitHub)" <gi...@apache.org> on 2024/04/01 09:38:12 UTC
[I] Potential hash conflict in `symmetric_hash_join` implementation [arrow-datafusion]
Rossil2012 opened a new issue, #9896:
URL: https://github.com/apache/arrow-datafusion/issues/9896
In the `symmetric_hash_join` implementation, when a `RecordBatch` arrives, the probe side update the `(hash_value, indicies)` in its inner hashmap. The calling chain is `update_internal_state` -> `update_hash` -> `update_from_iter`.
However, when there is already a hash key in the hashmap, it simply insert new indices into the list but do not check whether the key is actually equal, which makes a confilct possible.
I'm wondering if you do notice the vulnerablility here, but ignore it because the hash conflict in u64 is rare, or there is safe guard elsewhere overlooked by me. Thanks for your time.
https://github.com/apache/arrow-datafusion/blob/cd7a00b08309f7229073e4bba686d6271726ab1c/datafusion/physical-plan/src/joins/symmetric_hash_join.rs#L1017-L1039
https://github.com/apache/arrow-datafusion/blob/cd7a00b08309f7229073e4bba686d6271726ab1c/datafusion/physical-plan/src/joins/hash_join.rs#L910-L948
https://github.com/apache/arrow-datafusion/blob/cd7a00b08309f7229073e4bba686d6271726ab1c/datafusion/physical-plan/src/joins/utils.rs#L203-L229
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [I] Potential hash conflict in `symmetric_hash_join` implementation [arrow-datafusion]
Posted by "metesynnada (via GitHub)" <gi...@apache.org>.
metesynnada commented on issue #9896:
URL: https://github.com/apache/arrow-datafusion/issues/9896#issuecomment-2030025691
You may check this method and its usage
```rust
pub fn equal_rows_arr(
indices_left: &UInt64Array,
indices_right: &UInt32Array,
left_arrays: &[ArrayRef],
right_arrays: &[ArrayRef],
null_equals_null: bool,
) -> Result<(UInt64Array, UInt32Array)> {
let mut iter = left_arrays.iter().zip(right_arrays.iter());
let (first_left, first_right) = iter.next().ok_or_else(|| {
DataFusionError::Internal(
"At least one array should be provided for both left and right".to_string(),
)
})?;
let arr_left = take(first_left.as_ref(), indices_left, None)?;
let arr_right = take(first_right.as_ref(), indices_right, None)?;
let mut equal: BooleanArray = eq_dyn_null(&arr_left, &arr_right, null_equals_null)?;
// Use map and try_fold to iterate over the remaining pairs of arrays.
// In each iteration, take is used on the pair of arrays and their equality is determined.
// The results are then folded (combined) using the and function to get a final equality result.
equal = iter
.map(|(left, right)| {
let arr_left = take(left.as_ref(), indices_left, None)?;
let arr_right = take(right.as_ref(), indices_right, None)?;
eq_dyn_null(arr_left.as_ref(), arr_right.as_ref(), null_equals_null)
})
.try_fold(equal, |acc, equal2| and(&acc, &equal2?))?;
let filter_builder = FilterBuilder::new(&equal).optimize().build();
let left_filtered = filter_builder.filter(indices_left)?;
let right_filtered = filter_builder.filter(indices_right)?;
Ok((
downcast_array(left_filtered.as_ref()),
downcast_array(right_filtered.as_ref()),
))
}
```
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [I] Potential hash conflict in `symmetric_hash_join` implementation [arrow-datafusion]
Posted by "Rossil2012 (via GitHub)" <gi...@apache.org>.
Rossil2012 commented on issue #9896:
URL: https://github.com/apache/arrow-datafusion/issues/9896#issuecomment-2030984124
Oh now I see how the hash conflict is resolved. Thanks for your kindly reply!
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [I] Potential hash conflict in `symmetric_hash_join` implementation [arrow-datafusion]
Posted by "Rossil2012 (via GitHub)" <gi...@apache.org>.
Rossil2012 closed issue #9896: Potential hash conflict in `symmetric_hash_join` implementation
URL: https://github.com/apache/arrow-datafusion/issues/9896
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [I] Potential hash conflict in `symmetric_hash_join` implementation [arrow-datafusion]
Posted by "metesynnada (via GitHub)" <gi...@apache.org>.
metesynnada commented on issue #9896:
URL: https://github.com/apache/arrow-datafusion/issues/9896#issuecomment-2030022388
Hash collision tests are in place to guard against these types of issues, which is why I don't foresee any problem in this area.
To explain further, the hash table algorithm stores the raw hash values. As you've pointed out, hash collisions can occur for different keys. However, after retrieving the indices, we perform a vectorized equality check. This step allows us to resolve any hash collisions that may arise.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org