Polars Encodes Group Keys as Rows to Make Hashing Cheap

TL;DR: A composite group key is a tuple, and tuples are awkward to hash: you have to combine the hashes of the parts in a way that cannot collide across different arities or orderings. Polars sidesteps that by encoding each row of the key into a byte blob — a null sentinel, big-endian bytes for numbers, a terminator for strings — and then hashing the blob. One hash, one comparison, one allocation.
The encoder is not a black box: it is written so that the encoded bytes sort in the same order as the values, which is what lets the same representation be used for sorting, grouping and joining.

Grouping on one numeric column is easy. The physical value is the key, and the hash of that value is the hash of the key. Grouping on three columns is a different problem. Now the key is a tuple, and a tuple needs a hash function that is consistent across the whole query: two rows are in the same group if and only if their hashes agree and their keys are equal, and the “if and only if” has to survive the hashing.

The tempting shortcut — hash each column and XOR the hashes — is wrong in subtle ways. (a, b) and (b, a) can hash the same; (1, 2) and (1, 2, 0) can hash the same; the fix is to mix in the arity and the position of each column, and then you are maintaining a hand-rolled hash combiner with all the collision risk that implies.

Polars takes the other route: turn the tuple into a byte string, and let a well-tested byte hash do the work.

Encoding a row

The generic encoder lives in the polars-row crate and is used for the “row encoded” key representation. A key column’s contribution to a row is decided by its dtype, and the decision is made by a trait:

rust
// crates/polars-row/src/fixed/numeric.rs:28
/// Encodes a value of a particular fixed width type into bytes
pub trait FixedLengthEncoding: Copy + Debug {
    // 1 is validity 0 or 1
    // bit repr of encoding
    const ENCODED_LEN: usize = 1 + size_of::<Self::Encoded>();

    type Encoded: Sized + Copy + AsRef<[u8]> + AsMut<[u8]>;

    fn encode(self) -> Self::Encoded;

    fn decode(encoded: Self::Encoded) -> Self;

    /// Invert all bits of an encoded value. Used for descending order.
    fn invert(encoded: Self::Encoded) -> Self::Encoded;

    /// Keep the encoded value if `keep`, otherwise all zeros.
    fn keep_or_zero(encoded: Self::Encoded, keep: bool) -> Self::Encoded;

    fn decode_reverse(encoded: Self::Encoded) -> Self {
        Self::decode(Self::invert(encoded))
    }
}

Every fixed-width value is written as one sentinel byte followed by the value’s bytes. The sentinel is 1 for a valid value and 0xFF (or 0x00, when sorting descending) for null:

rust
// crates/polars-row/src/fixed/numeric.rs:230
pub unsafe fn encode<T: NativeType + FixedLengthEncoding>(
    buffer: &mut [MaybeUninit<u8>],
    arr: &PrimitiveArray<T>,
    opt: RowEncodingOptions,
    offsets: &mut [usize],
) {
    if arr.null_count() == 0 {
        encode_slice(buffer, arr.values().as_slice(), opt, offsets)
    } else {
        encode_slice_with_validity(
            buffer,
            arr.values().as_slice(),
            arr.validity().unwrap(),
            opt,
            offsets,
        )
    }
}

/// Write the sentinel byte and the encoded value.
#[inline(always)]
unsafe fn write_value<T: FixedLengthEncoding>(
    dst: *mut MaybeUninit<u8>,
    sentinel: u8,
    encoded: T::Encoded,
) {
    *dst = MaybeUninit::new(sentinel);
    std::ptr::write_unaligned(dst.add(1) as *mut T::Encoded, encoded);
}

/// Write the null sentinel followed by zeros.
#[inline(always)]
unsafe fn write_null<T: FixedLengthEncoding>(dst: *mut MaybeUninit<u8>, null_sentinel: u8) {
    *dst = MaybeUninit::new(null_sentinel);
    std::ptr::write_bytes(dst.add(1), 0, T::ENCODED_LEN - 1);
}

Note that a null is written as the sentinel plus zeros. That matters: it means a null key and a zero-valued key never produce the same bytes, and it means the encoding of a row is fixed width, so the row encoder can compute row offsets before it writes anything.

The value bytes themselves are chosen so that byte order equals value order. Unsigned integers are stored big-endian, which already sorts correctly. Signed integers need one extra step, because in two’s complement -1 sorts after 1 if you compare bytes:

rust
// crates/polars-row/src/fixed/numeric.rs:78
// toggle the sign bit and then encode as big indian
macro_rules! encode_signed {
    ($n:expr, $t:ty) => {
        impl FixedLengthEncoding for $t {
            type Encoded = [u8; $n];

            #[inline(always)]
            fn encode(self) -> [u8; $n] {
                #[cfg(target_endian = "big")]
                {
                    todo!()
                }

                let mut b = self.to_be_bytes();
                // Toggle top "sign" bit to ensure consistent sort order
                b[0] ^= 0x80;
                b
            }

Flipping the top bit maps the two’s complement range onto the unsigned range, which is exactly what big-endian byte comparison needs. Floats get the same treatment, plus a canonicalization step so that NaN has one representation and -0.0 sorts with 0.0:

rust
// crates/polars-row/src/fixed/numeric.rs:176
impl FixedLengthEncoding for f64 {
    type Encoded = [u8; 8];

    #[inline]
    fn encode(self) -> [u8; 8] {
        // https://github.com/rust-lang/rust/blob/9c20b2a8cc7588decb6de25ac6a7912dcef24d65/library/core/src/num/f32.rs#L1176-L1260
        let s = canonical_f64(self).to_bits() as i64;
        let val = s ^ (((s >> 63) as u64) >> 1) as i64;
        val.encode()
    }

The ^ (((s >> 63) as u64) >> 1) is the standard “flip all bits if negative” transform, which maps IEEE-754 doubles onto a monotonically increasing integer ordering. Combined with the sign-bit flip in the signed-integer macro, the float encoder reuses the integer encoder.

Descending order is handled by inverting every bit, which turns “ascending” into “descending” without a second code path:

rust
// crates/polars-row/src/fixed/numeric.rs:38
macro_rules! invert_and_keep_or_zero {
    ($t:ty) => {
        #[inline(always)]
        fn invert(encoded: Self::Encoded) -> Self::Encoded {
            (!Self::from_ne_bytes(encoded)).to_ne_bytes()
        }

Strings are the awkward case

Fixed-width values have a known size; strings do not. The string encoding solves this with a trick: since the bytes 0xFC..=0xFF never appear in valid UTF-8, every byte can be shifted by two and the result can never be confused with the terminator or the null sentinel:

rust
// crates/polars-row/src/variable/utf8.rs:1
//! Row encoding for UTF-8 strings
//!
//! This encoding is based on the fact that in UTF-8 the bytes 0xFC - 0xFF are never valid bytes.
//! To make this work with the row encoding, we add 2 to each byte which gives us two bytes which
//! never occur in UTF-8 before and after the possible byte range. The values 0x00 and 0xFF are
//! reserved for the null sentinel. The values 0x01 and 0xFE are reserved as a sequence terminator
//! byte.
//!
//! This allows the string row encoding to have a constant 1 byte overhead.

The terminator is what lets a decoder find the end of a string without a length prefix — one byte of overhead per string instead of eight — and it is found with a vectorized byte search:

rust
// crates/polars-row/src/variable/utf8.rs:107
/// Encode the bytes of a string followed by the terminator.
///
/// # Safety
/// `dst` must be writable for `s.len() + 1` bytes.
#[inline(always)]
unsafe fn encode_bytes(dst: *mut MaybeUninit<u8>, s: &[u8], xor_mask: u8) {
    if s.len() < BLOCK_SIZE {
        let mut block = [0u8; BLOCK_SIZE];
        std::ptr::copy_nonoverlapping(s.as_ptr(), block.as_mut_ptr(), s.len());
        encode_short(dst, block, s.len(), xor_mask);
    } else {
        for (i, &b) in s.iter().enumerate() {
            *dst.add(i) = MaybeUninit::new(xor_mask ^ (b + 2));
        }
        *dst.add(s.len()) = MaybeUninit::new(xor_mask ^ 0x01);
    }
}

Note that strings are not fixed width, so a row containing a string has a variable length. That is the main structural difference between the generic row encoding and the newer fixed-width key rows described at the end.

Hashing the bytes

Once the rows are encoded, hashing them is trivial — one hash per row:

rust
// crates/polars-expr/src/hash_keys.rs:146
        if use_row_encoding {
            let keys = df.columns();
            let mut keys_encoded = _get_rows_encoded_unordered(keys).unwrap().into_array();

            if !null_is_valid {
                let validities = keys
                    .iter()
                    .map(|c| c.as_materialized_series().rechunk_validity())
                    .collect_vec();
                let combined = combine_validities_and_many(&validities);
                keys_encoded.set_validity(combined);
            }

            // TODO: use vechash? Not supported yet for lists.
            // let mut hashes = Vec::with_capacity(df.height());
            // columns_to_hashes(df.columns(), Some(random_state), &mut hashes).unwrap();

            let hashes = keys_encoded
                .values_iter()
                .map(|k| random_state.hash_one(k))
                .collect();
            Self::RowEncoded(RowEncodedKeys {
                hashes: PrimitiveArray::from_vec(hashes),
                keys: keys_encoded,
            })

Two properties make this work. First, the hash is computed over the whole row, so the arity and the order of the columns are baked into the bytes — there is no way for (a, b) to collide with (b, a) unless the bytes themselves are equal. Second, the hash is computed once, up front, and stored alongside the keys:

rust
// crates/polars-expr/src/hash_keys.rs:116
/// Represents a DataFrame plus a hash per row, intended for keys in grouping
/// or joining. The hashes may or may not actually be physically pre-computed,
/// this depends per type.
#[derive(Clone, Debug)]
pub enum HashKeys {
    RowEncoded(RowEncodedKeys),
    KeyRows(KeyRowKeys),
    Binview(BinviewKeys),
    Single(SingleKeys),
}

Pre-hashing is what makes partitioned joins possible: the hash decides which partition a key belongs to, so a probe only has to look at one partition’s table instead of all of them.

The map that stores the groups

The row-encoded grouper keeps a hash map from row bytes to group index. The map is specialised for exactly this shape — pre-hashed byte keys — and it stores the key bytes in an arena of buffers rather than allocating a Vec per key:

rust
// crates/polars-utils/src/idx_map/bytes_idx_map.rs:25
/// An IndexMap where the keys are always [u8] slices which are pre-hashed.
pub struct BytesIndexMap<V> {
    table: HashTable<IdxSize>,
    tuples: Vec<(Key, V)>,
    key_data: Vec<Vec<u8>>,

    // Internal random seed used to keep hash iteration order decorrelated.
    // We simply store a random odd number and multiply the canonical hash by it.
    seed: u64,
}

The lookup is a hash compare followed by a byte compare:

rust
// crates/polars-utils/src/idx_map/bytes_idx_map.rs:79
    /// Gets the index by insertion order of the given key.
    pub fn get_index_of(&self, hash: u64, key: &[u8]) -> Option<IdxSize> {
        self.table
            .find(hash.wrapping_mul(self.seed), |i| unsafe {
                let t = self.tuples.get_unchecked(*i as usize);
                hash == t.0.key_hash && key == t.0.get(&self.key_data)
            })
            .copied()
    }

That key == t.0.get(&self.key_data) is a memcmp over the row bytes. It is the whole equality check for a composite key — no per-column dispatch, no null handling at comparison time (nulls are in the bytes), no tuple comparison.

And the grouper itself is four lines:

rust
// crates/polars-expr/src/groups/row_encoded.rs:23
    fn insert_key(&mut self, hash: u64, key: &[u8]) -> IdxSize {
        match self.idx_map.entry(hash, key) {
            Entry::Occupied(o) => o.index(),
            Entry::Vacant(v) => {
                let index = v.index();
                v.insert(());
                index
            },
        }
    }

The index handed out is the insertion order index, which is why the keys come back in group order for free.

When no encoding is needed

All of the above is machinery that exists only because there is more than one key column, or because the key is a string. For a single numeric key, Polars skips the encoding entirely:

rust
// crates/polars-expr/src/groups/single_key.rs:13
pub struct SingleKeyHashGrouper<T: PolarsDataType> {
    /// Each key with its group.
    table: HashTable<(T::Physical<'static>, IdxSize)>,
    num_groups: IdxSize,
    /// The group of the null key, IdxSize::MAX if there is none.
    null_idx: IdxSize,
    random_state: PlRandomState,
}

The hash table is keyed by the physical value itself, and the null key gets its own group index instead of being hashed at all, so it can never be confused with a real value:

rust
// crates/polars-expr/src/groups/single_key.rs:100
            for (hash, idx) in hashes.iter().zip(block) {
                let idx = *idx as usize;
                if validity.is_some_and(|v| !v.get_bit_unchecked(idx)) {
                    if null_is_valid {
                        if self.null_idx == IdxSize::MAX {
                            self.null_idx = self.num_groups;
                            self.num_groups += 1;
                        }
                        on_group(self.null_idx);
                    }
                } else {
                    let key = arr.value_unchecked(idx);
                    match self.table.entry(*hash, |(k, _)| k.tot_eq(&key), hasher) {
                        Entry::Occupied(o) => on_group(o.get().1),
                        Entry::Vacant(v) => {
                            v.insert((key, self.num_groups));
                            on_group(self.num_groups);
                            self.num_groups += 1;
                        },
                    }
                }
            }

The choice between the representations is made once, from the key schema:

rust
// crates/polars-expr/src/groups/mod.rs:92
pub fn new_hash_grouper(key_schema: Arc<Schema>) -> Box<dyn Grouper> {
    if let Some(layout) = KeyRowLayout::new(key_schema.iter_values()) {
        Box::new(key_rows::KeyRowHashGrouper::new(Arc::new(layout)))
    } else if key_schema.len() > 1 {
        Box::new(row_encoded::RowEncodedHashGrouper::new())
    } else {
        let (_name, dt) = key_schema.get_at_index(0).unwrap();
        match dt {
            dt if dt.is_primitive_numeric() | dt.is_temporal() => {
                with_match_physical_numeric_polars_type!(dt.to_physical(), |$T| {
                    Box::new(single_key::SingleKeyHashGrouper::<$T>::new())
                })
            },

Read it as a ladder: if the schema can be laid out as fixed-width key rows, use that; otherwise if there is more than one column, use generic row encoding; otherwise use the most specialized grouper the single column’s dtype allows.

Key rows: the fixed-width version

The generic row encoding has one structural weakness: string columns make rows variable length, which means row offsets are not known up front and the bytes are not word-aligned. The newer key row representation fixes both by computing a layout from the schema alone:

rust
// crates/polars-expr/src/key_rows/layout.rs:72
/// The row format of keys of one schema. It depends only on the key dtypes: the null
/// bits are always present, also when nulls are not keys, so keys that disagree on
/// whether nulls match (the two sides of an anti join) share one layout.
///
/// Rows are written into zeroed words and null values are left zero, so equal keys
/// have equal words, including padding. The one exception is the second word of a
/// long view, which holds where its bytes are stored: equality skips that word and
/// compares the bytes instead.
#[derive(Debug, PartialEq)]
pub(crate) struct KeyRowLayout {
    pub(super) cols: Vec<ColLayout>,
    /// Byte offset of the null bits, one per column.
    pub(super) null_offset: usize,
    null_width: usize,
    pub(super) stride_words: usize,
    /// The first word of each view column, in column order.
    pub(super) view_words: Vec<usize>,
    /// Every word except the second half of each view.
    pub(super) plain_words: Vec<usize>,
}

Three decisions are worth pulling out.

Columns are ordered by width, descending. The layout sorts the fields so that the widest column comes first, which (a) makes the stride a power of two number of words and (b) means the comparison bails out early on the most discriminating column:

rust
// crates/polars-expr/src/key_rows/layout.rs:90
        let null_width = cols.len().div_ceil(8).next_power_of_two();
        let mut fields: Vec<(usize, Option<usize>)> = widths
            .into_iter()
            .enumerate()
            .map(|(i, width)| (width, Some(i)))
            .chain([(null_width, None)])
            .collect();
        fields.sort_by_key(|(width, _)| Reverse(*width));

Nulls live inside the row. One bit per key column, always allocated even when no column has nulls. That is deliberate: it means the two sides of an anti join — where one side treats null as a key and the other does not — can share one layout and one hash table.

Equality is an XOR fold over words. Because rows are written into zeroed words, “equal” means “no differing bits”, which is one instruction per word for the fixed part:

rust
// crates/polars-expr/src/key_rows/layout.rs:170
    pub(super) unsafe fn rows_eq(
        &self,
        a: &[u64],
        b: &[u64],
        mut long_eq: impl FnMut(View, View) -> bool,
    ) -> bool {
        if self.view_words.is_empty() {
            return a.iter().zip(b).fold(0, |acc, (x, y)| acc | (x ^ y)) == 0;
        }
        for w in &self.plain_words {
            if a.get_unchecked(*w) != b.get_unchecked(*w) {
                return false;
            }
        }

The strings are the awkward case again. An Arrow “view” is 16 bytes: short strings are inlined, long strings point into a buffer, and the second half of the view word holds a location, not data. So the word comparison skips that word and compares the bytes instead.

The hash is derived from the columns rather than from the row bytes, by folding each column’s contribution into a per-row hash:

rust
// crates/polars-expr/src/key_rows/keys.rs:338
        let mut hashes = vec![random_state.hash_one(HASH_MULTIPLE); len];
        for col in &cols {
            col.hash_into(&mut hashes, random_state);
        }

The bottom line

The design in one sentence: encode the key once, then let bytes do all the work.

The trade-offs:

Encoding costs memory and a copy. Every distinct key is materialized as bytes and stored in the map’s arena. For a group-by on a wide string key that is a real cost, which is why single string keys get their own grouper that compares Arrow views directly instead of copying bytes.
The encoding is a format, so it has invariants. The sentinel byte, the terminator byte and the shifted UTF-8 bytes all have to be mutually exclusive, and the decoder has to know which convention a column was encoded with. RowEncodingOptions carries the descending and null-placement flags so that a row encoded one way is never decoded as another.
Fixed width buys alignment, at the cost of limits. The key-row layout needs a power-of-two word stride, one null-bit word, and at most two string columns; beyond that it gives up and the generic encoder takes over. The limits are explicit in the source (MAX_KEY_COLUMNS = 64, MAX_VIEW_COLUMNS = 2, crates/polars-expr/src/key_rows/layout.rs:13).
Sorting comes for free. Because the encoded bytes are order-preserving, the same representation can be sorted, compared and hashed. That is not an accident; it is why the sign bit is flipped and why floats are canonicalized before they are written.