Vectorize hash join collision check

[Dandandan]

Is your feature request related to a problem or challenge? Please describe what you are trying to do.
Further optimize the hash join algorithm

Describe the solution you'd like
There are a couple of optimizations we could implement:

• Vectorize the row-equality check which now uses the equal_rows functions. We should be able to speed this up by vectorizing this, and also specialize it for handling non-null batches too. We probably can utilize the kernels take and eq here.
• Don't use a Hashmap but a Vec (or similar) with a certain amount of buckets (proportional to the number of rows or the expected number of keys in the left side). I tried this, but as it causes much more collisions than we have currently, it causes a big (3x) slowdown, so vectorizing the collision check is a prerequisite.

Additional context

https://www.cockroachlabs.com/blog/vectorized-hash-joiner/
https://dare.uva.nl/search?identifier=5ccbb60a-38b8-4eeb-858a-e7735dd37487

[Dandandan]

FYI @metesynnada I'm working on a prototype.

Translated the code out of https://dare.uva.nl/search?identifier=5ccbb60a-38b8-4eeb-858a-e7735dd37487 to this, which seems roughly equivalent:

    let mut to_check: Vec<(u64, usize)> = hash_values
        .iter()
        .enumerate()
        .flat_map(|(row, hash_value)| {
            build_hashmap
                .map
                .get(*hash_value, |(hash, _)| *hash_value == *hash)
                .map(|(_, v)| (*v - 1, row))
        })
        .collect();

    while to_check.len() > 0 {
        // TODO Perform column-wise (vectorized) equality check

        // check next items
        to_check = to_check
            .iter()
            .flat_map(|(index, row)| {
                let next = build_hashmap.next[*index as usize];
                (next != 0).then(|| (next - 1, *row))
            })
            .collect();
    }

[metesynnada]

I will be thinking about this as well. Building an array for the equality check might improve the equality check performance, however, compute::take will copy the elements so I am not sure without a performance test on different cases.

[Dandandan]

Yeah - we sure have to test real-world performance :)

[Dandandan]

Looks like on TPC-H we get some nice improvements overall #6724