You are viewing a plain text version of this content. The canonical link for it is here.
Posted to github@arrow.apache.org by GitBox <gi...@apache.org> on 2021/07/19 12:13:08 UTC
[GitHub] [arrow-rs] alamb opened a new issue #563: Add a compute comparator interface that doesn't bind array instances
alamb opened a new issue #563:
URL: https://github.com/apache/arrow-rs/issues/563
**Is your feature request related to a problem or challenge? Please describe what you are trying to do.**
In DataFusion we are working on a Merge operator that needs to compare multiple sorted streams of record batches, merge them together, and produce a single sorted output stream (see more context in https://github.com/apache/arrow-datafusion/pull/722)
The current interface for comparing arrays in Arrow is getting a [`DynComparator`](https://github.com/apache/arrow-rs/blob/f873d77bc77847b95921374aa66ba1d38e9cebf8/arrow/src/array/ord.rs#L30)
Which is a function that you give two indexes and get the result. You effectively have to do
```rust
let cmp = build_compare(array1, array2);
...
if cmp(index1, index2) == OrderingEqual:: {
}
```
This has two problems for the merge operator:
1. it has to keep track of different comparators for each pairs of arrays that are used
2. (unobviously) by memoizing the comparators it will prevent the underlying array memory from being freed (as each comparator has a reference to the underlying array data)
**Describe the solution you'd like**
I would ideally like a comparator that does not have the array bound and instead was passed array indexes. Something like
```rust
let cmp = build_compare(array1.data_type(), array2.data_type());
...
if cmp(&array1, index1, &array2, index2) == OrderingEqual:: {
}
```
We can probably also keep the existing interface
**Describe alternatives you've considered**
None
**Additional context**
See discussion with @Dandandan and @e-dard here: https://github.com/apache/arrow-datafusion/pull/722#discussion_r671825464
--
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-rs] alamb commented on issue #563: Add a compute comparator interface that doesn't bind array instances
Posted by GitBox <gi...@apache.org>.
alamb commented on issue #563:
URL: https://github.com/apache/arrow-rs/issues/563#issuecomment-891048484
> There is some nice article and references on this blog:
>
> https://www.cockroachlabs.com/blog/vectorized-hash-joiner/
I agree -- that article is a good read (though I did find the last bits somewhat hard to follow)
--
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-rs] Dandandan commented on issue #563: Add a compute comparator interface that doesn't bind array instances
Posted by GitBox <gi...@apache.org>.
Dandandan commented on issue #563:
URL: https://github.com/apache/arrow-rs/issues/563#issuecomment-890531292
There is some possibilty to use some totally different data structures too in the hash join, also to make this check more vectorized and maybe further improve efficiency and memory usage.
There is some nice article and references on this blog:
https://www.cockroachlabs.com/blog/vectorized-hash-joiner/
--
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-rs] alamb commented on issue #563: Add a compute comparator interface that doesn't bind array instances
Posted by GitBox <gi...@apache.org>.
alamb commented on issue #563:
URL: https://github.com/apache/arrow-rs/issues/563#issuecomment-890497670
While looking through the hash join code from @Dandandan in DataFusion, I found another implementation of a comparator that is similar to the comparator interface proposed in this PR. It is called `equal_rows` and could potentially benefit from not dispatching on the type (to then have to downcast as well) on each comparison
```rust
/// Left and right row have equal values
fn equal_rows(
left: usize,
right: usize,
left_arrays: &[ArrayRef],
right_arrays: &[ArrayRef],
) -> Result<bool> {
```
https://github.com/apache/arrow-datafusion/blob/18c581c4dbfbc3b5d135b3bc0d1cdb5c16af9c78/datafusion/src/physical_plan/hash_join.rs#L813
--
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-rs] jorgecarleitao commented on issue #563: Add a compute comparator interface that doesn't bind array instances
Posted by GitBox <gi...@apache.org>.
jorgecarleitao commented on issue #563:
URL: https://github.com/apache/arrow-rs/issues/563#issuecomment-886107343
Not sure this will be performant because each comparison requires a `match` followed by two `downcast`s. I.e. this interface would push the downcasting to inside the hot loop, while the current interface places these operations outside the loop.
--
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