[jira] [Created] (IMPALA-14701) Use non-power-of-two sizing for large hash joins

["Joe McDonnell (Jira)" <ji...@apache.org>]

Joe McDonnell created IMPALA-14701:
--------------------------------------

             Summary: Use non-power-of-two sizing for large hash joins
                 Key: IMPALA-14701
                 URL: https://issues.apache.org/jira/browse/IMPALA-14701
             Project: IMPALA
          Issue Type: Task
          Components: Backend
    Affects Versions: Impala 5.0.0
            Reporter: Joe McDonnell


The hash tables for hash joins use a power of two for the number of buckets. This uses a simple bit-mask to get the bucket from the lower bits of the hash value. For larger hash tables, the cost of the hash table is dominated by memory accesses rather than actual CPU cycles. Being able to use a number of buckets that is not a power of two would reduce memory usage and allow some workloads to fit in cache that otherwise would exceed it. There are a few different ways to efficiently map the hash to the buckets:
 * The "fast modulo" (which is not really a modulo) from [https://lemire.me/blog/2016/06/27/a-fast-alternative-to-the-modulo-reduction/] would be most influenced by high bits in the hash
 * Compilers use strength reduction to convert modulus to multiplication and shift. [https://www.vldb.org/pvldb/vol12/p502-lang.pdf] refers to this as "magic modulo". This should behave like regular modulo and use low bits.
 * Either way, this needs to ignore the top bits that we use for partitioning, as those bits will be constant within each partition and can't give entropy.

Hash joins know the number of tuples before creating the hash table, so this can be calculated once before creating the hash table. It doesn't need to handle resizes.

A few complications:
 * The memory for the hash table comes from a Suballocator, which only supports power of two sizes. To support other sizes, we would need a different way to get memory. Suballocator is not very useful for this case, because we would only use this for large hash tables where the buckets/hash arrays are larger than the page size. Also, Suballocator is not very useful when we aren't resizing the hash table.
 * The quadratic probing relies on a power of two sizing to guarantee that it can reach every element. Quadratic probing can work with prime sizes, but we may not want to restrict ourselves that way. For very large hash tables, linear probing should be fine.
 * Codegen is happening before we know the size of the hash table, so we would need additional codegen functions specializing in large non-power-of-two hash tables.



--
This message was sent by Atlassian Jira
(v8.20.10#820010)