The Perfect Hash Join: Turning a Hash Table Into a Plain Array When the Keys Are Dense Integers

TL;DR: A hash join’s probe costs a hash computation, a bucket lookup and a chain walk. But if the build side’s key is an integer in a narrow range — say customer_id between 0 and 100,000 — you do not need a hash table at all. You need an array. DataFusion detects this case, builds a flat Vec<u32> indexed by the key, and turns the probe into a single array load. The interesting part is the detection: the decision has to be made at runtime, from the build side’s actual key distribution, and it has to survive the fact that a partitioned build side may destroy the density.

Hash joins are the workhorse of analytical query processing, and the classic implementation is a hash table: hash the key, index a bucket array, walk a chain of colliding entries. It is a good design, and it handles arbitrary keys.

But it is the wrong design for a large class of real joins.

SELECT f.*, d.dim_name
FROM facts f
JOIN dimensions d ON f.dim_id = d.dim_id;   -- dim_id is an integer 0..100000

The build side has 100,000 rows with keys drawn from [0, 100000). The keys are dense. A hash table spends a hash computation, a modulo, a bucket load, a chain walk and a comparison to find a row that is sitting at a known offset in an array.

The right structure here is an array.

The array map

pub struct ArrayMap {
    // data[probSideVal-offset] -> valIdxInBuildSide + 1; 0 for absent
    data: Vec<u32>,
    // min val in buildSide
    offset: u64,
    // next[buildSideIdx] -> next matching valIdxInBuildSide + 1; 0 for end of chain.
    // If next is empty, it means there are no duplicate keys (no conflicts).
    // It uses the same chain-based conflict resolution as [`JoinHashMapType`].
    next: Vec<u32>,
    num_of_distinct_key: usize,
}

Three arrays, and each one is doing something specific.

data is the lookup table. It has one slot per possible key value in the range [min, max], and each slot holds the build-side row index plus one (so that zero can mean “absent”). The probe is:

slot = probe_key - offset
if slot out of range: no match
row  = data[slot]
if row == 0: no match

That is one memory load and two comparisons. No hash, no modulo, no chain.

offset is the minimum key value, so that the array is indexed from zero even when the keys start at, say, 1,000,000.

next handles duplicate keys. If the build side has two rows with the same key, the array can only point at one of them, so the second is chained. And the comment notes the important optimisation:

If next is empty, it means there are no duplicate keys (no conflicts).

When there are no duplicates — the common case for a dimension table — the chain array is not allocated at all, and the probe is a single load with no chain walk.

When to use it

The decision is made in array_map_key_range (datafusion/physical-plan/src/joins/hash_join/exec.rs), and the conditions are documented on HashJoinExec:

For joins with a single integer-based join key, HashJoinExec may use an ArrayMap (also known as a “perfect hash join”) instead of a general-purpose hash map. This optimization is used when:

1. There is exactly one join key.
2. The join key is an integer type up to 64 bits wide that can be losslessly converted to u64 (128-bit integer types such as i128 and u128 are not supported).
3. The range of keys is small enough (controlled by perfect_hash_join_small_build_threshold) OR the keys are sufficiently dense (controlled by perfect_hash_join_min_key_density).
4. build_side.num_rows() < u32::MAX
5. NullEqualsNothing || (NullEqualsNull && build side doesn’t contain null)

Five conditions. Let’s take them one at a time, because each one is a subtle correctness or resource constraint.

Condition 2 — integer types only. The array is indexed by the key, so the key must be an integer that can be losslessly converted to u64. i128 and u128 are excluded because they do not fit.

Condition 4 — num_rows < u32::MAX. The payload index in data is a u32. A build side with more than 4 billion rows cannot be indexed. The source has a TODO: support create ArrayMap<u64> — a 64-bit index would double the memory of the lookup table, which is why it is not done by default.

Condition 5 — null handling. If the join treats NULLs as equal to each other (NullEqualsNull), then a build-side NULL key must be findable. The array has no slot for “null” (nulls are not a number), so the optimisation is disabled if the build side contains any NULL key:

if null_equality == NullEquality::NullEqualsNull {
    for batch in batches.iter() {
        let arrays = evaluate_expressions_to_arrays(on_left, batch)?;
        if arrays[0].null_count() > 0 {
            return Ok(None);
        }
    }
}

The density heuristic

Condition 3 is the interesting one, and it has two ways to be satisfied, because there are two different ways the array map can be a bad idea.

The array map’s memory is O(max - min), not O(num_rows). So a build side with 10 rows and keys {0, 1_000_000, 2_000_000, ...} would allocate a 20-million-element array to store 10 rows. Catastrophic.

The two escape hatches:

let dense_ratio = (num_row as f64) / ((range + 1) as f64);

if range >= perfect_hash_join_small_build_threshold as u64
    && dense_ratio <= perfect_hash_join_min_key_density
{
    return Ok(None);
}

The small-range escape. If the range is small (below perfect_hash_join_small_build_threshold, default 1024), the array is small no matter how sparse the keys are. A 1024-element array is 4 KB — negligible — so even 3 rows in it is fine. The check is range >= threshold && density <= limit, i.e. both must be bad to reject. If the range is small, the density does not matter.

The density escape. Otherwise, the keys must be dense enough: density > perfect_hash_join_min_key_density (default 0.15). So at least 15% of the slots in the range must be occupied. A build side with 150,000 rows spanning [0, 1_000_000] has a density of 0.15 — the array is 4 MB and holds 150,000 rows, which is 26 bytes per row of array space versus a hash table’s own overhead. Worth it.

And the two thresholds are configurable, because “how dense is dense enough” depends on the hardware, the key width, and the workload.

The overflow trap

There is a bug-shaped detail in the code that is worth pointing out, because it is the kind of thing that produces a wrong answer rather than a crash:

// When the key range spans the full integer domain (e.g. i64::MIN to i64::MAX),
// range is u64::MAX and `range + 1` below would overflow.
if range == usize::MAX as u64 {
    return Ok(None);
}

let dense_ratio = (num_row as f64) / ((range + 1) as f64);

range is max - min as a u64. If the build side contains both i64::MIN and i64::MAX, the range is u64::MAX. Then range + 1 overflows — in release mode, u64::MAX + 1 wraps to zero, and the density becomes num_row / 0 = infinity, which would pass the density check and allocate an astronomically large array.

The guard is placed before the division. This is exactly the kind of integer-overflow bug that a fuzzer finds and a careful reviewer prevents.

The partitioning trap

And then there is the subtlety that makes this optimisation much harder than it looks. The doc on HashJoinExec spells it out:

Note that when using PartitionMode::Partitioned, the build side is split into multiple partitions. This can cause a dense build side to become sparse within each partition, potentially disabling this optimization.

For example, consider:

sql Copy

SELECT t1.value, t2.value
FROM range(10000) AS t1
JOIN range(10000) AS t2
  ON t1.value = t2.value;

With 24 partitions, each partition will only receive a subset of the 10,000 rows. The first partition might contain values like 3, 10, 18, 39, 43, which are sparse relative to the original range, even though the overall data set is dense.

This is a beautiful example of a global property becoming a local property. The whole build side is dense — keys 0..10,000 with no gaps. But hash-partitioning by value gives partition 0 the keys 0, 417, 834, ..., and within that partition the density is 1/417, not 1.

So the array map is evaluated per partition, on that partition’s keys, and the density check uses the partition’s own min and max. Partition 0 might have min=0, max=9996, and 10,000/24 = 417 rows — density 0.04, below the 0.15 threshold. Optimisation disabled.

Which is the right answer for a local array map. But it means the perfect hash join mostly applies to CollectLeft mode (one build side, read once) or to cases where the partitioning preserves density.

The measurement

The code has a dedicated metric for this:

const ARRAY_MAP_CREATED_COUNT_METRIC_NAME: &str = "array_map_created_count";

So you can see, in EXPLAIN ANALYZE, whether the optimisation actually fired. Without such a metric, an optimisation that fires unpredictably (because it depends on the runtime key distribution) is impossible to tune. With it, you can look at a workload and see “the array map fired on 12 of 200 joins” and know that the other 188 would not have benefited from a denser key space.

The catch

• Memory is O(range), not O(rows). The density check bounds this, but the bound is a heuristic with a configurable threshold.
• Only integer keys. Strings, dates and decimals do not get the array map. (Dates could, in principle, since they are integers underneath, but the implementation does not.)
• Single key only. A composite key (a, b) would need a hash — unless the pair can be packed into one integer, which the implementation does not do.
• The decision is per-partition and therefore unstable. The same query on the same data can take the array-map path on one run and the hash-table path on another, if the partitioning changes. The metric exists precisely because of this.
• It is a fast path, not a replacement. The hash table is still there, and the hash table is still needed for the general case. The array map is an optimisation layered on top.

The general lesson

The perfect hash join is a 300-year-old idea — it is what every “lookup table” and every “direct addressing” data structure is — applied to a modern setting where the key distribution is only known at runtime.

The interesting engineering is not the array. It is the decision procedure: two thresholds, an overflow guard, a per-partition re-evaluation, and a metric so you can see what happened. A fast path that fires based on a runtime property is only useful if you can also observe whether it fired.