You are viewing a plain text version of this content. The canonical link for it is here.
Posted to github@arrow.apache.org by "metesynnada (via GitHub)" <gi...@apache.org> on 2023/08/22 10:05:24 UTC
[GitHub] [arrow-datafusion] metesynnada opened a new pull request, #7366: Upstream/prunable hash join
metesynnada opened a new pull request, #7366:
URL: https://github.com/apache/arrow-datafusion/pull/7366
## Which issue does this PR close?
Continue on https://github.com/apache/arrow-datafusion/pull/6679.
## Rationale for this change
The current implementation of the `JoinHashMap` and `SymmetricJoinHashMap` types could benefit from being more generic and flexible. Specifically, the ability to support different types of list data structures for chaining, as well as handling resizing in a more idiomatic and efficient manner, would be advantageous. This PR introduces the `JoinHashMapType` trait and implements it for both `JoinHashMap` and `PruningJoinHashMap`, which allows for more code reuse and a clearer separation of concerns.
In this PR, Several unused hash join utilities are removed. Also, we can introduce a vectorized implementation of `SymmetricHashJoin` that includes hash collision checks.
## What changes are included in this PR?
- Added a `JoinHashMapType` trait with methods for handling the mutable map and mutable list, as well as a method `as_any_mut` for dynamic downcasting.
- Implemented the `JoinHashMapType` trait for both `JoinHashMap` and `PruningJoinHashMap`.
- Updated the `update_hash` function to use the `JoinHashMapType` trait and only resize the list in the case of `PruningJoinHashMap`.
- Updated the `build_equal_condition_join_indices` function to use the JoinHashMapType trait and introduced an offset parameter.
- Added inline comments and docstrings for better readability and documentation of the code.
## Are these changes tested?
Yes, the changes are covered by the existing tests. No new tests were required as the new implementation preserves the existing functionality. All tests passed successfully after the changes were applied.
## Are there any user-facing changes?
No, the changes made in this PR are internal and do not affect the public API or the functionality of the crate.
--
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
[GitHub] [arrow-datafusion] Dandandan commented on a diff in pull request #7366: Merge hash table implementations and remove leftover utilities
Posted by "Dandandan (via GitHub)" <gi...@apache.org>.
Dandandan commented on code in PR #7366:
URL: https://github.com/apache/arrow-datafusion/pull/7366#discussion_r1301826330
##########
datafusion/core/src/physical_plan/joins/hash_join_utils.rs:
##########
@@ -117,37 +112,201 @@ impl JoinHashMap {
}
}
-impl SymmetricJoinHashMap {
+/// Trait defining methods that must be implemented by a hash map type to be used for joins.
+pub trait JoinHashMapType {
+ /// The type of list used to store the hash values.
+ type NextType: IndexMut<usize, Output = u64>;
+ /// Returns a mutable reference to `self` as a `dyn Any` for dynamic downcasting.
+ fn extend_with_value(&mut self, len: usize, value: u64);
+ /// Returns mutable references to the hash map and the next.
+ fn get_mut(&mut self) -> (&mut RawTable<(u64, u64)>, &mut Self::NextType);
+ /// Returns a reference to the hash map.
+ fn get_map(&self) -> &RawTable<(u64, u64)>;
+ /// Returns a reference to the next.
+ fn get_list(&self) -> &Self::NextType;
+}
+
+/// Implementation of `JoinHashMapType` for `JoinHashMap`.
+impl JoinHashMapType for JoinHashMap {
+ type NextType = Vec<u64>;
+
+ // Void implementation
+ fn extend_with_value(&mut self, _: usize, _: u64) {}
+
+ /// Get mutable references to the hash map and the next.
+ fn get_mut(&mut self) -> (&mut RawTable<(u64, u64)>, &mut Self::NextType) {
+ (&mut self.map, &mut self.next)
+ }
+
+ /// Get a reference to the hash map.
+ fn get_map(&self) -> &RawTable<(u64, u64)> {
+ &self.map
+ }
+
+ /// Get a reference to the next.
+ fn get_list(&self) -> &Self::NextType {
+ &self.next
+ }
+}
+
+/// Implementation of `JoinHashMapType` for `PruningJoinHashMap`.
+impl JoinHashMapType for PruningJoinHashMap {
+ type NextType = VecDeque<u64>;
+
+ // Extend with value
+ fn extend_with_value(&mut self, len: usize, value: u64) {
+ self.next.extend(repeat_n(value, len))
+ }
Review Comment:
```suggestion
fn extend_zero(&mut self, len: usize) {
self.next.extend(self.next.len() + len, 0)
}
```
Alternative suggestion (slightly more efficient).
--
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
[GitHub] [arrow-datafusion] Dandandan commented on pull request #7366: Merge hash table implementations and remove leftover utilities
Posted by "Dandandan (via GitHub)" <gi...@apache.org>.
Dandandan commented on PR #7366:
URL: https://github.com/apache/arrow-datafusion/pull/7366#issuecomment-1688445250
I wonder whether you're seeing performance improvements in symmetric / streaming hash join as well?
--
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
[GitHub] [arrow-datafusion] Dandandan commented on a diff in pull request #7366: Merge hash table implementations and remove leftover utilities
Posted by "Dandandan (via GitHub)" <gi...@apache.org>.
Dandandan commented on code in PR #7366:
URL: https://github.com/apache/arrow-datafusion/pull/7366#discussion_r1301616477
##########
datafusion/core/src/physical_plan/joins/hash_join.rs:
##########
@@ -627,20 +620,25 @@ pub fn update_hash(
// calculate the hash values
let hash_values = create_hashes(&keys_values, random_state, hashes_buffer)?;
+ if let Some(hash_map) = hash_map.as_any_mut().downcast_mut::<PruningJoinHashMap>() {
Review Comment:
๐
##########
datafusion/core/src/physical_plan/joins/hash_join.rs:
##########
@@ -627,20 +620,25 @@ pub fn update_hash(
// calculate the hash values
let hash_values = create_hashes(&keys_values, random_state, hashes_buffer)?;
+ if let Some(hash_map) = hash_map.as_any_mut().downcast_mut::<PruningJoinHashMap>() {
Review Comment:
๐
--
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
[GitHub] [arrow-datafusion] metesynnada commented on pull request #7366: Merge hash table implementations and remove leftover utilities
Posted by "metesynnada (via GitHub)" <gi...@apache.org>.
metesynnada commented on PR #7366:
URL: https://github.com/apache/arrow-datafusion/pull/7366#issuecomment-1689863030
I created a small benchmark for streaming using tpch data.
```
Benchmark streaming.json
--------------------
โโโโโโโโโโโโโโโโณโโโโโโโโโโโโโโณโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโณโโโโโโโโโโโโโโโโ
โ Query โ apache_main โ upstream_prunable-hash-join โ Change โ
โกโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโฉ
โ QQuery 1 โ 1483.13ms โ 1483.27ms โ no change โ
โ QQuery 2 โ 11033.15ms โ 6903.41ms โ +1.60x faster โ
โโโโโโโโโโโโโโโโดโโโโโโโโโโโโโโดโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโดโโโโโโโโโโโโโโโโ
```
First query is
```sql
SELECT
o_orderkey
FROM
orders,
lineitem
WHERE
o_orderdate = l_shipdate
AND l_orderkey >= o_orderkey - 10
AND l_orderkey < o_orderkey + 10
AND l_returnflag = 'R'
```
and the second one is
```sql
SELECT
o_orderkey
FROM
orders,
lineitem
WHERE
o_orderstatus = l_linestatus
AND l_orderkey >= o_orderkey - 10
AND l_orderkey < o_orderkey + 10
AND l_returnflag = 'R'
LIMIT 10000;
```
The second query involves key pairs with low cardinality. While `smallvec` was effective in allocating new keys, deleting from it resulted in performance issues. With the removal of the `smallvec` mechanism in this PR, we have significantly improved performance.
--
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
[GitHub] [arrow-datafusion] metesynnada commented on a diff in pull request #7366: Merge hash table implementations and remove leftover utilities
Posted by "metesynnada (via GitHub)" <gi...@apache.org>.
metesynnada commented on code in PR #7366:
URL: https://github.com/apache/arrow-datafusion/pull/7366#discussion_r1301711600
##########
datafusion/core/src/physical_plan/joins/hash_join.rs:
##########
@@ -781,22 +780,33 @@ pub fn build_equal_condition_join_indices(
// (5,1)
//
// With this approach, the lexicographic order on both the probe side and the build side is preserved.
+ let hash_map = build_hashmap.get_map();
+ let next_chain = build_hashmap.get_list();
for (row, hash_value) in hash_values.iter().enumerate().rev() {
// Get the hash and find it in the build index
// For every item on the build and probe we check if it matches
// This possibly contains rows with hash collisions,
// So we have to check here whether rows are equal or not
- if let Some((_, index)) = build_hashmap
- .map
- .get(*hash_value, |(hash, _)| *hash_value == *hash)
+ if let Some((_, index)) =
+ hash_map.get(*hash_value, |(hash, _)| *hash_value == *hash)
{
let mut i = *index - 1;
loop {
- build_indices.append(i);
+ let build_row_value = if let Some(offset) = deleted_offset {
Review Comment:
```
โโโโโโโโโโโโโโโโณโโโโโโโโโโโโโโณโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโณโโโโโโโโโโโโ
โ Query โ apache_main โ upstream_prunable-hash-join โ Change โ
โกโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโฉ
โ QQuery 1 โ 549.90ms โ 549.66ms โ no change โ
โ QQuery 2 โ 71.70ms โ 72.52ms โ no change โ
โ QQuery 3 โ 172.56ms โ 170.44ms โ no change โ
โ QQuery 4 โ 110.21ms โ 110.26ms โ no change โ
โ QQuery 5 โ 210.11ms โ 207.85ms โ no change โ
โ QQuery 6 โ 106.90ms โ 106.28ms โ no change โ
โ QQuery 7 โ 307.57ms โ 301.40ms โ no change โ
โ QQuery 8 โ 246.69ms โ 243.11ms โ no change โ
โ QQuery 9 โ 366.93ms โ 375.37ms โ no change โ
โ QQuery 10 โ 284.63ms โ 292.08ms โ no change โ
โ QQuery 11 โ 63.49ms โ 61.19ms โ no change โ
โ QQuery 12 โ 207.04ms โ 206.43ms โ no change โ
โ QQuery 13 โ 311.59ms โ 310.80ms โ no change โ
โ QQuery 14 โ 148.77ms โ 148.79ms โ no change โ
โ QQuery 15 โ 103.07ms โ 101.74ms โ no change โ
โ QQuery 16 โ 57.77ms โ 59.79ms โ no change โ
โ QQuery 17 โ 240.35ms โ 230.32ms โ no change โ
โ QQuery 18 โ 460.92ms โ 464.87ms โ no change โ
โ QQuery 19 โ 316.94ms โ 315.97ms โ no change โ
โ QQuery 20 โ 174.61ms โ 175.35ms โ no change โ
โ QQuery 21 โ 442.66ms โ 444.59ms โ no change โ
โ QQuery 22 โ 74.40ms โ 74.55ms โ no change โ
โโโโโโโโโโโโโโโโดโโโโโโโโโโโโโโดโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโดโโโโโโโโโโโโ
```
--
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
[GitHub] [arrow-datafusion] metesynnada commented on a diff in pull request #7366: Merge hash table implementations and remove leftover utilities
Posted by "metesynnada (via GitHub)" <gi...@apache.org>.
metesynnada commented on code in PR #7366:
URL: https://github.com/apache/arrow-datafusion/pull/7366#discussion_r1301711600
##########
datafusion/core/src/physical_plan/joins/hash_join.rs:
##########
@@ -781,22 +780,33 @@ pub fn build_equal_condition_join_indices(
// (5,1)
//
// With this approach, the lexicographic order on both the probe side and the build side is preserved.
+ let hash_map = build_hashmap.get_map();
+ let next_chain = build_hashmap.get_list();
for (row, hash_value) in hash_values.iter().enumerate().rev() {
// Get the hash and find it in the build index
// For every item on the build and probe we check if it matches
// This possibly contains rows with hash collisions,
// So we have to check here whether rows are equal or not
- if let Some((_, index)) = build_hashmap
- .map
- .get(*hash_value, |(hash, _)| *hash_value == *hash)
+ if let Some((_, index)) =
+ hash_map.get(*hash_value, |(hash, _)| *hash_value == *hash)
{
let mut i = *index - 1;
loop {
- build_indices.append(i);
+ let build_row_value = if let Some(offset) = deleted_offset {
Review Comment:
```
โโโโโโโโโโโโโโโโณโโโโโโโโโโโโโโณโโโโโโโโโโโโโโโโโโโโโณโโโโโโโโโโโโโโโโ
โ Query โ apache_main โ fork_sym-hashtable โ Change โ
โกโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโฉ
โ QQuery 1 โ 552.79ms โ 550.33ms โ no change โ
โ QQuery 2 โ 72.21ms โ 71.10ms โ no change โ
โ QQuery 3 โ 174.05ms โ 171.05ms โ no change โ
โ QQuery 4 โ 115.42ms โ 110.86ms โ no change โ
โ QQuery 5 โ 216.56ms โ 214.26ms โ no change โ
โ QQuery 6 โ 107.64ms โ 106.45ms โ no change โ
โ QQuery 7 โ 308.30ms โ 307.71ms โ no change โ
โ QQuery 8 โ 247.63ms โ 244.98ms โ no change โ
โ QQuery 9 โ 374.71ms โ 368.62ms โ no change โ
โ QQuery 10 โ 295.30ms โ 292.97ms โ no change โ
โ QQuery 11 โ 66.83ms โ 61.84ms โ +1.08x faster โ
โ QQuery 12 โ 213.71ms โ 207.88ms โ no change โ
โ QQuery 13 โ 315.16ms โ 312.82ms โ no change โ
โ QQuery 14 โ 156.43ms โ 150.26ms โ no change โ
โ QQuery 15 โ 103.82ms โ 102.99ms โ no change โ
โ QQuery 16 โ 62.30ms โ 59.98ms โ no change โ
โ QQuery 17 โ 277.65ms โ 258.28ms โ +1.08x faster โ
โ QQuery 18 โ 569.40ms โ 535.63ms โ +1.06x faster โ
โ QQuery 19 โ 321.54ms โ 322.04ms โ no change โ
โ QQuery 20 โ 188.54ms โ 179.86ms โ no change โ
โ QQuery 21 โ 450.69ms โ 457.03ms โ no change โ
โ QQuery 22 โ 74.30ms โ 72.68ms โ no change โ
โโโโโโโโโโโโโโโโดโโโโโโโโโโโโโโดโโโโโโโโโโโโโโโโโโโโโดโโโโโโโโโโโโโโโโ
```
I think there is only measurement noise here.
##########
datafusion/core/src/physical_plan/joins/hash_join.rs:
##########
@@ -781,22 +780,33 @@ pub fn build_equal_condition_join_indices(
// (5,1)
//
// With this approach, the lexicographic order on both the probe side and the build side is preserved.
+ let hash_map = build_hashmap.get_map();
+ let next_chain = build_hashmap.get_list();
for (row, hash_value) in hash_values.iter().enumerate().rev() {
// Get the hash and find it in the build index
// For every item on the build and probe we check if it matches
// This possibly contains rows with hash collisions,
// So we have to check here whether rows are equal or not
- if let Some((_, index)) = build_hashmap
- .map
- .get(*hash_value, |(hash, _)| *hash_value == *hash)
+ if let Some((_, index)) =
+ hash_map.get(*hash_value, |(hash, _)| *hash_value == *hash)
{
let mut i = *index - 1;
loop {
- build_indices.append(i);
+ let build_row_value = if let Some(offset) = deleted_offset {
Review Comment:
```
โโโโโโโโโโโโโโโโณโโโโโโโโโโโโโโณโโโโโโโโโโโโโโโโโโโโโณโโโโโโโโโโโโโโโโ
โ Query โ apache_main โ fork_sym-hashtable โ Change โ
โกโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโฉ
โ QQuery 1 โ 552.79ms โ 550.33ms โ no change โ
โ QQuery 2 โ 72.21ms โ 71.10ms โ no change โ
โ QQuery 3 โ 174.05ms โ 171.05ms โ no change โ
โ QQuery 4 โ 115.42ms โ 110.86ms โ no change โ
โ QQuery 5 โ 216.56ms โ 214.26ms โ no change โ
โ QQuery 6 โ 107.64ms โ 106.45ms โ no change โ
โ QQuery 7 โ 308.30ms โ 307.71ms โ no change โ
โ QQuery 8 โ 247.63ms โ 244.98ms โ no change โ
โ QQuery 9 โ 374.71ms โ 368.62ms โ no change โ
โ QQuery 10 โ 295.30ms โ 292.97ms โ no change โ
โ QQuery 11 โ 66.83ms โ 61.84ms โ +1.08x faster โ
โ QQuery 12 โ 213.71ms โ 207.88ms โ no change โ
โ QQuery 13 โ 315.16ms โ 312.82ms โ no change โ
โ QQuery 14 โ 156.43ms โ 150.26ms โ no change โ
โ QQuery 15 โ 103.82ms โ 102.99ms โ no change โ
โ QQuery 16 โ 62.30ms โ 59.98ms โ no change โ
โ QQuery 17 โ 277.65ms โ 258.28ms โ +1.08x faster โ
โ QQuery 18 โ 569.40ms โ 535.63ms โ +1.06x faster โ
โ QQuery 19 โ 321.54ms โ 322.04ms โ no change โ
โ QQuery 20 โ 188.54ms โ 179.86ms โ no change โ
โ QQuery 21 โ 450.69ms โ 457.03ms โ no change โ
โ QQuery 22 โ 74.30ms โ 72.68ms โ no change โ
โโโโโโโโโโโโโโโโดโโโโโโโโโโโโโโดโโโโโโโโโโโโโโโโโโโโโดโโโโโโโโโโโโโโโโ
```
I think there is only measurement noise here.
--
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
[GitHub] [arrow-datafusion] Dandandan commented on a diff in pull request #7366: Merge hash table implementations and remove leftover utilities
Posted by "Dandandan (via GitHub)" <gi...@apache.org>.
Dandandan commented on code in PR #7366:
URL: https://github.com/apache/arrow-datafusion/pull/7366#discussion_r1301554211
##########
datafusion/core/src/physical_plan/joins/hash_join.rs:
##########
@@ -781,22 +780,33 @@ pub fn build_equal_condition_join_indices(
// (5,1)
//
// With this approach, the lexicographic order on both the probe side and the build side is preserved.
+ let hash_map = build_hashmap.get_map();
+ let next_chain = build_hashmap.get_list();
for (row, hash_value) in hash_values.iter().enumerate().rev() {
// Get the hash and find it in the build index
// For every item on the build and probe we check if it matches
// This possibly contains rows with hash collisions,
// So we have to check here whether rows are equal or not
- if let Some((_, index)) = build_hashmap
- .map
- .get(*hash_value, |(hash, _)| *hash_value == *hash)
+ if let Some((_, index)) =
+ hash_map.get(*hash_value, |(hash, _)| *hash_value == *hash)
{
let mut i = *index - 1;
loop {
- build_indices.append(i);
+ let build_row_value = if let Some(offset) = deleted_offset {
Review Comment:
Wonder if this doesn't cause any regressions?
--
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
[GitHub] [arrow-datafusion] Dandandan commented on a diff in pull request #7366: Merge hash table implementations and remove leftover utilities
Posted by "Dandandan (via GitHub)" <gi...@apache.org>.
Dandandan commented on code in PR #7366:
URL: https://github.com/apache/arrow-datafusion/pull/7366#discussion_r1301826330
##########
datafusion/core/src/physical_plan/joins/hash_join_utils.rs:
##########
@@ -117,37 +112,201 @@ impl JoinHashMap {
}
}
-impl SymmetricJoinHashMap {
+/// Trait defining methods that must be implemented by a hash map type to be used for joins.
+pub trait JoinHashMapType {
+ /// The type of list used to store the hash values.
+ type NextType: IndexMut<usize, Output = u64>;
+ /// Returns a mutable reference to `self` as a `dyn Any` for dynamic downcasting.
+ fn extend_with_value(&mut self, len: usize, value: u64);
+ /// Returns mutable references to the hash map and the next.
+ fn get_mut(&mut self) -> (&mut RawTable<(u64, u64)>, &mut Self::NextType);
+ /// Returns a reference to the hash map.
+ fn get_map(&self) -> &RawTable<(u64, u64)>;
+ /// Returns a reference to the next.
+ fn get_list(&self) -> &Self::NextType;
+}
+
+/// Implementation of `JoinHashMapType` for `JoinHashMap`.
+impl JoinHashMapType for JoinHashMap {
+ type NextType = Vec<u64>;
+
+ // Void implementation
+ fn extend_with_value(&mut self, _: usize, _: u64) {}
+
+ /// Get mutable references to the hash map and the next.
+ fn get_mut(&mut self) -> (&mut RawTable<(u64, u64)>, &mut Self::NextType) {
+ (&mut self.map, &mut self.next)
+ }
+
+ /// Get a reference to the hash map.
+ fn get_map(&self) -> &RawTable<(u64, u64)> {
+ &self.map
+ }
+
+ /// Get a reference to the next.
+ fn get_list(&self) -> &Self::NextType {
+ &self.next
+ }
+}
+
+/// Implementation of `JoinHashMapType` for `PruningJoinHashMap`.
+impl JoinHashMapType for PruningJoinHashMap {
+ type NextType = VecDeque<u64>;
+
+ // Extend with value
+ fn extend_with_value(&mut self, len: usize, value: u64) {
+ self.next.extend(repeat_n(value, len))
+ }
Review Comment:
```suggestion
fn extend_zero(&mut self, len: usize) {
self.next.extend(len, 0)
}
```
Alternative suggestion (slightly more efficient).
--
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
[GitHub] [arrow-datafusion] Dandandan commented on a diff in pull request #7366: Merge hash table implementations and remove leftover utilities
Posted by "Dandandan (via GitHub)" <gi...@apache.org>.
Dandandan commented on code in PR #7366:
URL: https://github.com/apache/arrow-datafusion/pull/7366#discussion_r1301822291
##########
datafusion/core/src/physical_plan/joins/hash_join.rs:
##########
@@ -781,22 +780,33 @@ pub fn build_equal_condition_join_indices(
// (5,1)
//
// With this approach, the lexicographic order on both the probe side and the build side is preserved.
+ let hash_map = build_hashmap.get_map();
+ let next_chain = build_hashmap.get_list();
for (row, hash_value) in hash_values.iter().enumerate().rev() {
// Get the hash and find it in the build index
// For every item on the build and probe we check if it matches
// This possibly contains rows with hash collisions,
// So we have to check here whether rows are equal or not
- if let Some((_, index)) = build_hashmap
- .map
- .get(*hash_value, |(hash, _)| *hash_value == *hash)
+ if let Some((_, index)) =
+ hash_map.get(*hash_value, |(hash, _)| *hash_value == *hash)
{
let mut i = *index - 1;
loop {
- build_indices.append(i);
+ let build_row_value = if let Some(offset) = deleted_offset {
Review Comment:
Looks good, thanks :)
--
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
[GitHub] [arrow-datafusion] metesynnada commented on a diff in pull request #7366: Merge hash table implementations and remove leftover utilities
Posted by "metesynnada (via GitHub)" <gi...@apache.org>.
metesynnada commented on code in PR #7366:
URL: https://github.com/apache/arrow-datafusion/pull/7366#discussion_r1301645131
##########
datafusion/core/src/physical_plan/joins/hash_join.rs:
##########
@@ -781,22 +780,33 @@ pub fn build_equal_condition_join_indices(
// (5,1)
//
// With this approach, the lexicographic order on both the probe side and the build side is preserved.
+ let hash_map = build_hashmap.get_map();
+ let next_chain = build_hashmap.get_list();
for (row, hash_value) in hash_values.iter().enumerate().rev() {
// Get the hash and find it in the build index
// For every item on the build and probe we check if it matches
// This possibly contains rows with hash collisions,
// So we have to check here whether rows are equal or not
- if let Some((_, index)) = build_hashmap
- .map
- .get(*hash_value, |(hash, _)| *hash_value == *hash)
+ if let Some((_, index)) =
+ hash_map.get(*hash_value, |(hash, _)| *hash_value == *hash)
{
let mut i = *index - 1;
loop {
- build_indices.append(i);
+ let build_row_value = if let Some(offset) = deleted_offset {
Review Comment:
However, I will investigate any potential performance issues
--
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
[GitHub] [arrow-datafusion] ozankabak merged pull request #7366: Merge hash table implementations and remove leftover utilities
Posted by "ozankabak (via GitHub)" <gi...@apache.org>.
ozankabak merged PR #7366:
URL: https://github.com/apache/arrow-datafusion/pull/7366
--
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
[GitHub] [arrow-datafusion] ozankabak commented on a diff in pull request #7366: Merge hash table implementations and remove leftover utilities
Posted by "ozankabak (via GitHub)" <gi...@apache.org>.
ozankabak commented on code in PR #7366:
URL: https://github.com/apache/arrow-datafusion/pull/7366#discussion_r1301647039
##########
datafusion/core/src/physical_plan/joins/hash_join.rs:
##########
@@ -781,22 +780,33 @@ pub fn build_equal_condition_join_indices(
// (5,1)
//
// With this approach, the lexicographic order on both the probe side and the build side is preserved.
+ let hash_map = build_hashmap.get_map();
+ let next_chain = build_hashmap.get_list();
for (row, hash_value) in hash_values.iter().enumerate().rev() {
// Get the hash and find it in the build index
// For every item on the build and probe we check if it matches
// This possibly contains rows with hash collisions,
// So we have to check here whether rows are equal or not
- if let Some((_, index)) = build_hashmap
- .map
- .get(*hash_value, |(hash, _)| *hash_value == *hash)
+ if let Some((_, index)) =
+ hash_map.get(*hash_value, |(hash, _)| *hash_value == *hash)
{
let mut i = *index - 1;
loop {
- build_indices.append(i);
+ let build_row_value = if let Some(offset) = deleted_offset {
Review Comment:
The compiler should be able to hoist the check above the for loop, so the check should essentially be done only once in practice and not cause any perf issues. @metesynnada will verify this, but if it turns out the compiler can not do this automatically, we can do the hoisting manually (and unfortunately duplicate ~10 line the for loop code).
--
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
[GitHub] [arrow-datafusion] metesynnada commented on a diff in pull request #7366: Merge hash table implementations and remove leftover utilities
Posted by "metesynnada (via GitHub)" <gi...@apache.org>.
metesynnada commented on code in PR #7366:
URL: https://github.com/apache/arrow-datafusion/pull/7366#discussion_r1301645131
##########
datafusion/core/src/physical_plan/joins/hash_join.rs:
##########
@@ -781,22 +780,33 @@ pub fn build_equal_condition_join_indices(
// (5,1)
//
// With this approach, the lexicographic order on both the probe side and the build side is preserved.
+ let hash_map = build_hashmap.get_map();
+ let next_chain = build_hashmap.get_list();
for (row, hash_value) in hash_values.iter().enumerate().rev() {
// Get the hash and find it in the build index
// For every item on the build and probe we check if it matches
// This possibly contains rows with hash collisions,
// So we have to check here whether rows are equal or not
- if let Some((_, index)) = build_hashmap
- .map
- .get(*hash_value, |(hash, _)| *hash_value == *hash)
+ if let Some((_, index)) =
+ hash_map.get(*hash_value, |(hash, _)| *hash_value == *hash)
{
let mut i = *index - 1;
loop {
- build_indices.append(i);
+ let build_row_value = if let Some(offset) = deleted_offset {
Review Comment:
I will investigate any potential performance issues
--
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
[GitHub] [arrow-datafusion] Dandandan commented on pull request #7366: Merge hash table implementations and remove leftover utilities
Posted by "Dandandan (via GitHub)" <gi...@apache.org>.
Dandandan commented on PR #7366:
URL: https://github.com/apache/arrow-datafusion/pull/7366#issuecomment-1688074531
> I have removed smallvec completely from the code, but I am unsure whether or not to remove it from Cargo.toml.
I think if this is the last usage, we should remove it from Cargo.toml as well
--
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
[GitHub] [arrow-datafusion] Dandandan commented on pull request #7366: Merge hash table implementations and remove leftover utilities
Posted by "Dandandan (via GitHub)" <gi...@apache.org>.
Dandandan commented on PR #7366:
URL: https://github.com/apache/arrow-datafusion/pull/7366#issuecomment-1690585496
> This is good to go from my perspective, what do you think @Dandandan?
Looks great, thank you
--
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
[GitHub] [arrow-datafusion] metesynnada commented on a diff in pull request #7366: Merge hash table implementations and remove leftover utilities
Posted by "metesynnada (via GitHub)" <gi...@apache.org>.
metesynnada commented on code in PR #7366:
URL: https://github.com/apache/arrow-datafusion/pull/7366#discussion_r1301429225
##########
datafusion/core/src/physical_plan/joins/hash_join.rs:
##########
@@ -627,20 +620,25 @@ pub fn update_hash(
// calculate the hash values
let hash_values = create_hashes(&keys_values, random_state, hashes_buffer)?;
+ if let Some(hash_map) = hash_map.as_any_mut().downcast_mut::<PruningJoinHashMap>() {
Review Comment:
I am open to ideas on this.
--
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
[GitHub] [arrow-datafusion] Dandandan commented on a diff in pull request #7366: Merge hash table implementations and remove leftover utilities
Posted by "Dandandan (via GitHub)" <gi...@apache.org>.
Dandandan commented on code in PR #7366:
URL: https://github.com/apache/arrow-datafusion/pull/7366#discussion_r1301552756
##########
datafusion/core/src/physical_plan/joins/hash_join.rs:
##########
@@ -627,20 +620,25 @@ pub fn update_hash(
// calculate the hash values
let hash_values = create_hashes(&keys_values, random_state, hashes_buffer)?;
+ if let Some(hash_map) = hash_map.as_any_mut().downcast_mut::<PruningJoinHashMap>() {
Review Comment:
It could be handled as well by a method on `JoinHashMapType` trait (void implementation for `JoinHashMap`)
--
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
[GitHub] [arrow-datafusion] metesynnada commented on a diff in pull request #7366: Merge hash table implementations and remove leftover utilities
Posted by "metesynnada (via GitHub)" <gi...@apache.org>.
metesynnada commented on code in PR #7366:
URL: https://github.com/apache/arrow-datafusion/pull/7366#discussion_r1301599672
##########
datafusion/core/src/physical_plan/joins/hash_join.rs:
##########
@@ -627,20 +620,25 @@ pub fn update_hash(
// calculate the hash values
let hash_values = create_hashes(&keys_values, random_state, hashes_buffer)?;
+ if let Some(hash_map) = hash_map.as_any_mut().downcast_mut::<PruningJoinHashMap>() {
Review Comment:
If it's alright with you, I can proceed with the implementation.
--
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
[GitHub] [arrow-datafusion] metesynnada commented on a diff in pull request #7366: Merge hash table implementations and remove leftover utilities
Posted by "metesynnada (via GitHub)" <gi...@apache.org>.
metesynnada commented on code in PR #7366:
URL: https://github.com/apache/arrow-datafusion/pull/7366#discussion_r1301602673
##########
datafusion/core/src/physical_plan/joins/hash_join.rs:
##########
@@ -781,22 +780,33 @@ pub fn build_equal_condition_join_indices(
// (5,1)
//
// With this approach, the lexicographic order on both the probe side and the build side is preserved.
+ let hash_map = build_hashmap.get_map();
+ let next_chain = build_hashmap.get_list();
for (row, hash_value) in hash_values.iter().enumerate().rev() {
// Get the hash and find it in the build index
// For every item on the build and probe we check if it matches
// This possibly contains rows with hash collisions,
// So we have to check here whether rows are equal or not
- if let Some((_, index)) = build_hashmap
- .map
- .get(*hash_value, |(hash, _)| *hash_value == *hash)
+ if let Some((_, index)) =
+ hash_map.get(*hash_value, |(hash, _)| *hash_value == *hash)
{
let mut i = *index - 1;
loop {
- build_indices.append(i);
+ let build_row_value = if let Some(offset) = deleted_offset {
Review Comment:
`let build_row_value = if let Some(offset) = deleted_offset` This operation is very fast, as it essentially just involves a single check and a variable assignment. For the usual hash join, the deleted offset will always be `None`.
--
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
[GitHub] [arrow-datafusion] metesynnada commented on a diff in pull request #7366: Merge hash table implementations and remove leftover utilities
Posted by "metesynnada (via GitHub)" <gi...@apache.org>.
metesynnada commented on code in PR #7366:
URL: https://github.com/apache/arrow-datafusion/pull/7366#discussion_r1301602673
##########
datafusion/core/src/physical_plan/joins/hash_join.rs:
##########
@@ -781,22 +780,33 @@ pub fn build_equal_condition_join_indices(
// (5,1)
//
// With this approach, the lexicographic order on both the probe side and the build side is preserved.
+ let hash_map = build_hashmap.get_map();
+ let next_chain = build_hashmap.get_list();
for (row, hash_value) in hash_values.iter().enumerate().rev() {
// Get the hash and find it in the build index
// For every item on the build and probe we check if it matches
// This possibly contains rows with hash collisions,
// So we have to check here whether rows are equal or not
- if let Some((_, index)) = build_hashmap
- .map
- .get(*hash_value, |(hash, _)| *hash_value == *hash)
+ if let Some((_, index)) =
+ hash_map.get(*hash_value, |(hash, _)| *hash_value == *hash)
{
let mut i = *index - 1;
loop {
- build_indices.append(i);
+ let build_row_value = if let Some(offset) = deleted_offset {
Review Comment:
`let build_row_value = if let Some(offset) = deleted_offset` This operation is very fast, as it essentially just involves a single check and a variable assignment.
--
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
[GitHub] [arrow-datafusion] Dandandan commented on a diff in pull request #7366: Merge hash table implementations and remove leftover utilities
Posted by "Dandandan (via GitHub)" <gi...@apache.org>.
Dandandan commented on code in PR #7366:
URL: https://github.com/apache/arrow-datafusion/pull/7366#discussion_r1301826330
##########
datafusion/core/src/physical_plan/joins/hash_join_utils.rs:
##########
@@ -117,37 +112,201 @@ impl JoinHashMap {
}
}
-impl SymmetricJoinHashMap {
+/// Trait defining methods that must be implemented by a hash map type to be used for joins.
+pub trait JoinHashMapType {
+ /// The type of list used to store the hash values.
+ type NextType: IndexMut<usize, Output = u64>;
+ /// Returns a mutable reference to `self` as a `dyn Any` for dynamic downcasting.
+ fn extend_with_value(&mut self, len: usize, value: u64);
+ /// Returns mutable references to the hash map and the next.
+ fn get_mut(&mut self) -> (&mut RawTable<(u64, u64)>, &mut Self::NextType);
+ /// Returns a reference to the hash map.
+ fn get_map(&self) -> &RawTable<(u64, u64)>;
+ /// Returns a reference to the next.
+ fn get_list(&self) -> &Self::NextType;
+}
+
+/// Implementation of `JoinHashMapType` for `JoinHashMap`.
+impl JoinHashMapType for JoinHashMap {
+ type NextType = Vec<u64>;
+
+ // Void implementation
+ fn extend_with_value(&mut self, _: usize, _: u64) {}
+
+ /// Get mutable references to the hash map and the next.
+ fn get_mut(&mut self) -> (&mut RawTable<(u64, u64)>, &mut Self::NextType) {
+ (&mut self.map, &mut self.next)
+ }
+
+ /// Get a reference to the hash map.
+ fn get_map(&self) -> &RawTable<(u64, u64)> {
+ &self.map
+ }
+
+ /// Get a reference to the next.
+ fn get_list(&self) -> &Self::NextType {
+ &self.next
+ }
+}
+
+/// Implementation of `JoinHashMapType` for `PruningJoinHashMap`.
+impl JoinHashMapType for PruningJoinHashMap {
+ type NextType = VecDeque<u64>;
+
+ // Extend with value
+ fn extend_with_value(&mut self, len: usize, value: u64) {
+ self.next.extend(repeat_n(value, len))
+ }
Review Comment:
```suggestion
fn extend_zero(&mut self, len: usize) {
self.next.resize(self.next.len() + len, 0)
}
```
Alternative suggestion (slightly more efficient).
--
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
[GitHub] [arrow-datafusion] ozankabak commented on pull request #7366: Merge hash table implementations and remove leftover utilities
Posted by "ozankabak (via GitHub)" <gi...@apache.org>.
ozankabak commented on PR #7366:
URL: https://github.com/apache/arrow-datafusion/pull/7366#issuecomment-1690500175
I will go ahead and merge this PR after CI passes. We will file a follow-on PR in case any other suggestions come in post merge
--
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
[GitHub] [arrow-datafusion] Dandandan commented on pull request #7366: Merge hash table implementations and remove leftover utilities
Posted by "Dandandan (via GitHub)" <gi...@apache.org>.
Dandandan commented on PR #7366:
URL: https://github.com/apache/arrow-datafusion/pull/7366#issuecomment-1690585065
Thanks @metesynnada @ozankabak ๐
--
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