Add a compute comparator interface that doesn't bind array instances

[alamb]

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 apache/datafusion#722)

The current interface for comparing arrays in Arrow is getting a DynComparator

Which is a function that you give two indexes and get the result. You effectively have to do

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

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: apache/datafusion#722 (comment)

[jorgecarleitao]

Not sure this will be performant because each comparison requires a match followed by two downcasts. I.e. this interface would push the downcasting to inside the hot loop, while the current interface places these operations outside the loop.

[alamb]

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

/// 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

[Dandandan]

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/

[alamb]

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)

[tustvold]

I believe this use-case is covered by the comparable row format added by #2593. Feel free to reopen if I am mistaken