Struct JoinHashTable 

pub struct JoinHashTable { /* private fields */ }

Optimized hash table for join operations.

This hash table is specifically designed for the build phase of hash joins. It uses chaining with linked entries stored in a flat vector for cache efficiency.

Example

// Build phase
let mut table = JoinHashTable::with_capacity(build_rows.len());
for (idx, row) in build_rows.iter().enumerate() {
    let hash = hash_row_keys(row, &key_indices);
    table.insert(hash, idx as u32);
}

// Probe phase
for probe_row in probe_rows {
    let hash = hash_row_keys(probe_row, &probe_key_indices);
    for build_idx in table.probe(hash) {
        // Verify actual key equality and produce output
    }
}

Implementations

impl JoinHashTable

pub fn estimated_retained_bytes(row_count: usize) -> Option<usize>

Exact retained size of bucket heads and compact entries before Vec allocator rounding. Overflow or row indices outside u32 are rejected.

pub fn fits_retained_budget(row_count: usize, max_bytes: usize) -> bool

pub fn with_capacity(row_count: usize) -> Self

Create a new hash table with capacity for the given number of rows.

The table is pre-allocated to avoid resizing during build. Bucket count is sized to achieve ~75% load factor.

pub fn empty() -> Self

Create an empty hash table (for cases where build side is empty).

pub fn build(rows: &[Row], key_indices: &[usize]) -> Self

Build a hash table from rows using the specified key indices.

This is the main entry point for creating a join hash table.

pub fn build_with_observer( rows: &[Row], key_indices: &[usize], observer: &mut impl JoinHashObserver, ) -> Self

Build hash table and populate bloom filter in a single pass.

This is more efficient than building separately because we only extract and hash key values once for both structures.

Arguments

• rows - Build side rows
• key_indices - Indices of join key columns
• bloom_builder - Bloom filter builder to populate

Returns

The built hash table (bloom filter is populated in-place)

pub fn insert(&mut self, hash: u64, row_idx: u32)

Insert a row index with its pre-computed hash.

Arguments

• hash - The hash of the row’s key columns
• row_idx - The index of the row in the build rows vector

pub fn probe(&self, hash: u64) -> ProbeIter<'_>

Probe the hash table for matching row indices.

Returns an iterator that yields row indices for entries with matching hashes. The caller must verify actual key equality for each returned index (to handle hash collisions).

This is a zero-allocation operation - the iterator only holds a reference to the table.

pub fn probe_cursor(&self, hash: u64) -> ProbeCursor

Start a resumable zero-allocation probe. Unlike ProbeIter, the cursor owns no borrow and can therefore live inside a streaming operator while that operator mutates its other state between emitted matches.

pub fn probe_next(&self, cursor: &mut ProbeCursor) -> Option<usize>

Advance one resumable probe and return the next matching row index.

pub fn len(&self) -> usize

Get the number of entries in the table.

pub fn is_empty(&self) -> bool

Check if the table is empty.

pub fn bucket_count(&self) -> usize

Get the number of buckets.

pub fn load_factor(&self) -> f64

Get the load factor (entries / buckets).