Opensource internals

Polars Compares Strings Without Allocating

19 min read Jay Hubbert

How Polars' BinaryView kernels compare strings with integer compares on 16-byte views, and how search_sorted avoids materialising a single String.

TL;DR: A Polars string is not a String and not even a &str at the point of comparison — it is a 16-byte View holding a length, a 4-byte prefix, and either the bytes themselves or a (buffer, offset) pair. The equality kernel packs length and prefix into one u64 and compares that first, so mismatched strings are rejected by a single integer compare with no memory touched. Only when that passes does it look at the payload, and even then it compares borrowed slices, never allocating.

String comparison in a dataframe engine is not a hard problem in the abstract: Rust’s &str compares lexicographically and does not allocate. The hard part is that a dataframe column is not a &str. It is a chunked, nullable, Arrow-shaped column, and the naive way to compare two of them is to walk both, materialise a &str per row, and hope the compiler keeps the borrows free. The moment you build an owned String per row to make that convenient, you have turned a memory-bandwidth problem into an allocator problem.

So I went looking at how Polars actually does it. The answer lives in three places: the View type in polars-arrow, the comparison kernels in polars-compute, and the chunk-level dispatch in polars-core.

The 16-byte view

The unit of comparison is View, and it is deliberately not a pointer to a string:

rust 
// crates/polars-arrow/src/array/binview/view.rs:26
// We use this instead of u128 because we want alignment of <= 8 bytes.
/// A reference to a set of bytes.
///
/// If `length <= 12`, these bytes are inlined over the `prefix`, `buffer_idx` and `offset` fields.
/// If `length > 12`, these fields specify a slice of a buffer.
#[derive(Copy, Clone, Default)]
#[repr(C)]
pub struct View {
    /// The length of the string/bytes.
    pub length: u32,
    /// First 4 bytes of string/bytes data.
    pub prefix: u32,
    /// The buffer index.
    pub buffer_idx: u32,
    /// The offset into the buffer.
    pub offset: u32,
}

crates/polars-arrow/src/array/binview/view.rs:20

The layout is the whole trick, so it is worth drawing out. The struct is repr(C), and as_u128 is a plain transmute of the 16 bytes:

rust 
// crates/polars-arrow/src/array/binview/view.rs:55
impl View {
    pub const MAX_INLINE_SIZE: u32 = 12;

    #[inline(always)]
    pub fn is_inline(&self) -> bool {
        self.length <= Self::MAX_INLINE_SIZE
    }

    #[inline(always)]
    pub fn as_u128(self) -> u128 {
        unsafe { std::mem::transmute(self) }
    }

crates/polars-arrow/src/array/binview/view.rs:54

Because the struct is repr(C) and the machine is little-endian, a u128 view of it looks like this:

text 
  u128 bits:    127..96        95..64         63..32         31..0
              +-------------+-------------+-------------+-------------+
  field:      |   offset    |  buffer_idx  |    prefix    |    length    |
              +-------------+-------------+-------------+-------------+
  inline:     | bytes 8..12 | bytes 4..8   | bytes 0..4  |     len     |
  spilled:    | byte offset | buffer index | first 4 B   |     len     |

For an inline view (length <= 12) the three “pointer” fields are not a pointer at all: they are the tail of the string. new_inline_unchecked copies the bytes straight over them:

rust 
// crates/polars-arrow/src/array/binview/view.rs:92
    /// Create a new inline view without verifying the length
    ///
    /// # Safety
    ///
    /// It needs to hold that `bytes.len() <= View::MAX_INLINE_SIZE`.
    #[inline]
    pub unsafe fn new_inline_unchecked(bytes: &[u8]) -> Self {
        debug_assert!(bytes.len() <= u32::MAX as usize);
        debug_assert!(bytes.len() <= Self::MAX_INLINE_SIZE as usize);

        let mut view = Self {
            length: bytes.len() as u32,
            ..Default::default()
        };

        let view_ptr = &mut view as *mut _ as *mut u8;

        // SAFETY:
        // - bytes length <= 12,
        // - size_of::<View> == 16
        // - View is laid out as [length, prefix, buffer_idx, offset] (using repr(C))
        // - By grabbing the view_ptr and adding 4, we have provenance over prefix, buffer_idx and
        // offset. (i.e. the same could not be achieved with &mut self.prefix as *mut u8)
        unsafe {
            let inline_data_ptr = view_ptr.add(4);
            core::ptr::copy_nonoverlapping(bytes.as_ptr(), inline_data_ptr, bytes.len());
        }
        view
    }

crates/polars-arrow/src/array/binview/view.rs:73

So for an inline view the u128 decomposes as: length in the low 32 bits, then the first four bytes of the string, then bytes 4..12 of the string. Every byte of a short string is inside the 16-byte view, and the view is Copy.

For a spilled view (length > 12) the same 16 bytes mean something else: the prefix field holds the first four bytes of the payload, and buffer_idx and offset point into one of the array’s data buffers. The prefix is stored little-endian, which matters later:

rust 
// crates/polars-arrow/src/array/binview/view.rs:148
    /// Create a new inline view
    ///
    /// # Safety
    ///
    /// It needs to hold that `bytes.len() > View::MAX_INLINE_SIZE`.
    #[inline]
    pub unsafe fn new_noninline_unchecked(bytes: &[u8], buffer_idx: u32, offset: u32) -> Self {
        debug_assert!(bytes.len() <= u32::MAX as usize);
        debug_assert!(bytes.len() > View::MAX_INLINE_SIZE as usize);

        // SAFETY: The invariant of this function guarantees that this is safe.
        let prefix = unsafe { u32::from_le_bytes(bytes[0..4].try_into().unwrap_unchecked()) };
        Self {
            length: bytes.len() as u32,
            prefix,
            buffer_idx,
            offset,
        }
    }

crates/polars-arrow/src/array/binview/view.rs:148

The important invariant: the prefix field means the same thing in both cases — the first four bytes of the string, zero-padded if the string is shorter than four bytes.

Equality: two integer compares before any byte is touched

Here is the whole equality kernel for BinaryViewArray:

rust 
// crates/polars-compute/src/comparisons/view.rs:56
impl TotalEqKernel for BinaryViewArray {
    type Scalar = [u8];

    fn tot_eq_kernel(&self, other: &Self) -> Bitmap {
        debug_assert!(self.len() == other.len());

        let slf_views = self.views().as_slice();
        let other_views = other.views().as_slice();

        Bitmap::from_trusted_len_iter((0..self.len()).map(|i| unsafe {
            let av = slf_views.get_unchecked(i).as_u128();
            let bv = other_views.get_unchecked(i).as_u128();

            // First 64 bits contain length and prefix.
            let a_len_prefix = av as u64;
            let b_len_prefix = bv as u64;
            if a_len_prefix != b_len_prefix {
                return false;
            }

            let alen = av as u32;
            if alen <= 12 {
                // String is fully inlined, compare top 64 bits. Bottom bits were
                // tested equal before, which also ensures the lengths are equal.
                (av >> 64) as u64 == (bv >> 64) as u64
            } else {
                self.value_unchecked(i) == other.value_unchecked(i)
            }
        }))
    }

crates/polars-compute/src/comparisons/view.rs:50

Read it as a decision tree, because that is what it is:

  1. Load both views as u128. This is a single 16-byte load per row; the views live in a contiguous Buffer<View>, so it is a linear scan of 16 bytes per element.
  2. Mask to the low 64 bits. As the layout diagram shows, that is length in the low half and prefix in the high half. One u64 compare rejects the pair if the lengths differ or the first four bytes differ. This is the length acting as a fast discriminator: a length mismatch is settled here, and the string data is never touched.
  3. If the low 64 bits matched, check the length again (alen <= 12). For an inline string the remaining 8 bytes of payload are in the top 64 bits, so a second u64 compare finishes the job. A 12-byte string is fully compared by two integer compares, with no branch into a buffer and no memcmp call.
  4. Only for spilled strings do we go to the payload, and even then value_unchecked hands back a borrowed slice:
rust 
// crates/polars-arrow/src/array/binview/mod.rs:405
    /// Returns the element at index `i`
    ///
    /// # Safety
    /// Assumes that the `i < self.len`.
    #[inline]
    pub unsafe fn value_unchecked(&self, i: usize) -> &T {
        let v = self.views.get_unchecked(i);
        T::from_bytes_unchecked(v.get_slice_unchecked(&self.buffers))
    }

crates/polars-arrow/src/array/binview/mod.rs:403

and get_slice_unchecked is a branch on inline vs. external plus a bounds-checked borrow of the buffer:

rust 
// crates/polars-arrow/src/array/binview/view.rs:243
    /// Constructs a byteslice from this view.
    ///
    /// # Safety
    /// Assumes that this view is valid for the given buffers.
    #[inline]
    pub unsafe fn get_slice_unchecked<'a, B: AsRef<[u8]>>(&'a self, buffers: &'a [B]) -> &'a [u8] {
        unsafe {
            if self.length <= Self::MAX_INLINE_SIZE {
                self.get_inlined_slice_unchecked()
            } else {
                self.get_external_slice_unchecked(buffers)
            }
        }
    }

crates/polars-arrow/src/array/binview/view.rs:243

No allocation, no copy, no String. The comparison is &[u8] == &[u8], which is memcmp over borrowed memory.

Note what the kernel does not do: it never constructs a &str, and it never calls str::from_utf8. UTF-8 validity is a property of the data, not of the comparison — BinaryViewArray and Utf8ViewArray share the exact same kernel, with the UTF-8 version delegating:

rust 
// crates/polars-compute/src/comparisons/view.rs:211
impl TotalEqKernel for Utf8ViewArray {
    type Scalar = str;

    fn tot_eq_kernel(&self, other: &Self) -> Bitmap {
        self.to_binview().tot_eq_kernel(&other.to_binview())
    }

crates/polars-compute/src/comparisons/view.rs:210

to_binview is a zero-copy reinterpretation — same views, same buffers, only the dtype changes:

rust 
// crates/polars-arrow/src/array/binview/mod.rs:668
impl Utf8ViewArray {
    pub fn to_binview(&self) -> BinaryViewArray {
        // SAFETY: same invariants.
        unsafe {
            BinaryViewArray::new_unchecked(
                ArrowDataType::BinaryView,
                self.views.clone(),
                self.buffers.clone(),
                self.validity.clone(),
                self.try_total_bytes_len(),
                self.total_buffer_len,
            )
        }
    }
}

crates/polars-arrow/src/array/binview/mod.rs:668

Broadcasting against a scalar

Comparing a column to a literal is the most common case in practice, and it gets an even tighter path. If the scalar is <= 12 bytes, the kernel builds the u128 encoding the scalar would have as an inline view and compares that integer against each row’s view:

rust 
// crates/polars-compute/src/comparisons/view.rs:9
// If s fits in 12 bytes, returns the view encoding it would have in a
// BinaryViewArray.
fn small_view_encoding(s: &[u8]) -> Option<u128> {
    if s.len() > 12 {
        return None;
    }

    let mut tmp = [0u8; 16];
    tmp[0] = s.len() as u8;
    tmp[4..4 + s.len()].copy_from_slice(s);
    Some(u128::from_le_bytes(tmp))
}

crates/polars-compute/src/comparisons/view.rs:9

rust 
// crates/polars-compute/src/comparisons/view.rs:108
    fn tot_eq_kernel_broadcast(&self, other: &Self::Scalar) -> Bitmap {
        if let Some(val) = small_view_encoding(other) {
            Bitmap::from_trusted_len_iter(self.views().iter().map(|v| v.as_u128() == val))
        } else {

crates/polars-compute/src/comparisons/view.rs:107

A single u128 equality per row. Because inline views are canonical (the bytes past the length are zero), a 128-bit integer compare is a string compare for any string of 12 bytes or fewer. That is a nice piece of type punning, but it only works because the encoding is canonical; it is not a general hash and it does not survive into the spilled case.

Ordering: the four-byte prefix as a discriminator

Equality can lean on “length, then content”. Ordering is harder, because lexicographic order is not length-first: "abc" sorts before "abcd", and "b" sorts before "ba". The kernel handles it by using the prefix as a tie-breaker shortcut rather than as a length substitute:

rust 
// crates/polars-compute/src/comparisons/view.rs:56
impl TotalOrdKernel for BinaryViewArray {
    type Scalar = [u8];

    fn tot_lt_kernel(&self, other: &Self) -> Bitmap {
        debug_assert!(self.len() == other.len());

        let slf_views = self.views().as_slice();
        let other_views = other.views().as_slice();

        Bitmap::from_trusted_len_iter((0..self.len()).map(|i| unsafe {
            let av = slf_views.get_unchecked(i).as_u128();
            let bv = other_views.get_unchecked(i).as_u128();

            // First 64 bits contain length and prefix.
            // Only check prefix.
            let a_prefix = (av >> 32) as u32;
            let b_prefix = (bv >> 32) as u32;
            if a_prefix != b_prefix {
                a_prefix.to_be() < b_prefix.to_be()
            } else {
                self.value_unchecked(i) < other.value_unchecked(i)
            }
        }))
    }

crates/polars-compute/src/comparisons/view.rs:146

The to_be() calls are the subtle part. The prefix is stored as a little-endian u32 (see new_noninline_unchecked), so comparing the raw integers would compare the last byte first. Byte-swapping turns the comparison back into a lexicographic comparison of the first four bytes. The zero padding of short strings is consistent with “end of string sorts before any continuation”, so the shortcut stays sound: if the prefixes differ, the strings differ within their first four bytes and the prefix decides the order.

The cost of the trick: two strings that share a four-byte prefix — which is common in real data, think timestamps or UUID prefixes — fall through to the full byte comparison. So this is a fast path with a predictable worst case, not a replacement for the real comparison. And it only gives you byte order. For UTF-8 that happens to be code-point order, which is what users expect from sort() on strings, so Polars gets the right semantics for free.

The scalar-broadcast ordering path generalises the same idea into a helper that takes the comparison as a closure:

rust 
// crates/polars-compute/src/comparisons/view.rs:38
fn broadcast_inequality(
    arr: &BinaryViewArray,
    scalar: &[u8],
    cmp_prefix: impl Fn(u32, u32) -> bool,
    cmp_str: impl Fn(&[u8], &[u8]) -> bool,
) -> Bitmap {
    let views = arr.views().as_slice();
    let prefix = load_prefix(scalar);
    let be_prefix = prefix.to_be();
    Bitmap::from_trusted_len_iter((0..arr.len()).map(|i| unsafe {
        let v_prefix = (views.get_unchecked(i).as_u128() >> 32) as u32;
        if v_prefix != prefix {
            cmp_prefix(v_prefix.to_be(), be_prefix)
        } else {
            cmp_str(arr.value_unchecked(i), scalar)
        }
    }))
}

crates/polars-compute/src/comparisons/view.rs:28

One prefix compare per row, one branch, and the string bytes are only read when the prefix fails to discriminate. load_prefix pads the scalar’s first four bytes with zeros so the comparison is apples-to-apples:

rust 
// crates/polars-compute/src/comparisons/view.rs:24
// Loads (up to) the first 4 bytes of s as little-endian, padded with zeros.
fn load_prefix(s: &[u8]) -> u32 {
    let start = &s[..s.len().min(4)];
    let mut tmp = [0u8; 4];
    tmp[..start.len()].copy_from_slice(start);
    u32::from_le_bytes(tmp)
}

crates/polars-compute/src/comparisons/view.rs:21

From array to chunked array

The kernels above are per-Array. A ChunkedArray is a list of arrays, and the chunk-level comparison code has to line those up. Strings go through a particularly cheap path, because StringChunked and BinaryChunked differ only in the dtype tag:

rust 
// crates/polars-core/src/chunked_array/comparison/mod.rs:430
impl ChunkCompareEq<&StringChunked> for StringChunked {
    type Item = BooleanChunked;

    fn equal(&self, rhs: &StringChunked) -> BooleanChunked {
        self.as_binary().equal(&rhs.as_binary())
    }

crates/polars-core/src/chunked_array/comparison/mod.rs:430

as_binary does not copy any bytes — it reinterprets the same views and buffers as BinaryViewArray (see crates/polars-core/src/chunked_array/cast.rs:359). The actual work is the chunk-aligned binary dispatch:

rust 
// crates/polars-core/src/chunked_array/comparison/mod.rs:44
                    _ => arity::binary_mut_values(
                        self,
                        rhs,
                        |a, b| a.tot_eq_kernel(b).into(),
                        PlSmallStr::EMPTY,
                    ),

crates/polars-core/src/chunked_array/comparison/mod.rs:490

arity::binary_mut_values first aligns the chunk boundaries of the two sides (align_chunks_binary), so a 3-chunk left side and a 5-chunk right side are sliced into comparable pieces before any kernel runs:

rust 
// crates/polars-core/src/chunked_array/ops/arity.rs:449
pub fn binary_mut_values<T, U, V, F, Arr>(
    lhs: &ChunkedArray<T>,
    rhs: &ChunkedArray<U>,
    mut op: F,
    name: PlSmallStr,
) -> ChunkedArray<V>
where
    ...
{
    let (lhs, rhs) = align_chunks_binary(lhs, rhs);
    let iter = lhs
        .downcast_iter()
        .zip(rhs.downcast_iter())
        .map(|(lhs_arr, rhs_arr)| {
            let ret = op(lhs_arr, rhs_arr);
            let inp_val = combine_validities_and(lhs_arr.validity(), rhs_arr.validity());
            let val = combine_validities_and(inp_val.as_ref(), ret.validity());
            ret.with_validity_typed(val)
        });
    ChunkedArray::from_chunk_iter(name, iter)
}

crates/polars-core/src/chunked_array/ops/arity.rs:430

Two things to note. First, the kernel returns a Bitmap of results and validity is combined afterwards with bitwise ops, so null handling costs a couple of word-parallel operations rather than a branch per row. Second, the only allocation on the whole path is the output boolean mask and the output chunk list — which is the answer to the question, really. The comparison allocates nothing.

The traits that make this uniform across dtypes are in crates/polars-compute/src/comparisons/mod.rs:4:

rust 
// crates/polars-compute/src/comparisons/mod.rs:11
pub trait TotalEqKernel: Sized + Array {
    type Scalar: ?Sized;

    // These kernels ignore validity entirely (results for nulls are unspecified
    // but initialized).
    fn tot_eq_kernel(&self, other: &Self) -> Bitmap;
    fn tot_ne_kernel(&self, other: &Self) -> Bitmap;
    fn tot_eq_kernel_broadcast(&self, other: &Self::Scalar) -> Bitmap;
    fn tot_ne_kernel_broadcast(&self, other: &Self::Scalar) -> Bitmap;

crates/polars-compute/src/comparisons/mod.rs:4

The “total” naming is there because floats need a total order; for strings it is just Ord semantics with nulls handled by the validity mask.

Where SIMD does and does not apply

Polars has a SIMD comparison path, but it is for numbers, not strings:

rust 
// crates/polars-compute/src/comparisons/simd.rs:99
macro_rules! impl_int_total_ord_kernel {
    ($T: ty, $width: literal, $mask: ty) => {
        impl TotalEqKernel for PrimitiveArray<$T> {
            type Scalar = $T;

            fn tot_eq_kernel(&self, other: &Self) -> Bitmap {
                apply_binary_kernel::<$width, $mask, _, _>(self, other, |l, r| {
                    Simd::from(*l).simd_eq(Simd::from(*r)).to_bitmask() as $mask
                })
            }

crates/polars-compute/src/comparisons/simd.rs:98

You cannot SIMD-compare variable-length strings. What Polars does instead is arrange the data so that the common case is fixed-width: 16 bytes per view, two u64 compares. That is the same trick a vectorised string library uses, just at a different granularity — the vectorisation is over the 16-byte view, not over the characters.

Building those views is where portable SIMD does show up, because converting a run of fixed-width strings into inline views is a pure data-shuffling problem:

rust 
// crates/polars-arrow/src/array/binview/view.rs:319
    /// Extend a `Vec<View>` with inline views slices of `src` with `width`.
    ///
    /// This tries to use SIMD to optimize the copying and can be massively faster than doing
    /// `views.extend(src.chunks_exact(width).map(View::new_inline))`.
    ///
    /// # Panics
    ///
    /// This function panics if `src.len()` is not divisible by `width`, `width >
    /// View::MAX_INLINE_SIZE` or `width == 0`.
    pub fn extend_with_inlinable_strided(views: &mut Vec<Self>, src: &[u8], width: u8) {

crates/polars-arrow/src/array/binview/view.rs:319

The body swizzles a 16-byte SIMD load into up to 16 views at once using simd_swizzle!, writing them out with copy_nonoverlapping (crates/polars-arrow/src/array/binview/view.rs:376-415). The comparison side then gets its speed for free from the fact that the payload is already in the view.

Binary search and search_sorted

The other place strings get compared is lookup: “where would this value go in this sorted column”. search_sorted is a classic lower_bound, and Polars implements it over chunks without ever materialising a value.

First the generic helper in polars-utils:

rust 
// crates/polars-utils/src/binary_search.rs:7
/// Find the index of the first element of `arr` that is greater
/// or equal to `val`.
/// Assumes that `arr` is sorted.
pub fn find_first_ge_index<T>(arr: &[T], val: T) -> usize
where
    T: Ord,
{
    match arr.binary_search(&val) {
        Ok(x) => x,
        Err(x) => x,
    }
}

crates/polars-utils/src/binary_search.rs:7

Ord for &str and &[u8] is byte-lexicographic, and Polars wires that into its total-order trait with a trivial macro:

rust 
// crates/polars-utils/src/total_ord.rs:259
        impl TotalOrd for $T {
            #[inline(always)]
            fn tot_cmp(&self, other: &Self) -> Ordering {
                self.cmp(other)
            }

crates/polars-utils/src/total_ord.rs:259

rust 
// crates/polars-utils/src/total_ord.rs:314
impl_trivial_total!(&str);
impl_trivial_total!(&[u8]);

crates/polars-utils/src/total_ord.rs:313

The chunk-aware search is the interesting part, because a ChunkedArray is several sorted runs that must be treated as one sorted sequence:

rust 
// crates/polars-core/src/chunked_array/ops/search_sorted.rs:32
/// Computes the first point on [lo, hi) where f is true, assuming it is first
/// always false and then always true. It is assumed f(hi) is true.
/// midpoint is a function that returns some lo < i < hi if one exists, else lo.
fn lower_bound<I, F, M>(mut lo: I, mut hi: I, midpoint: M, f: F) -> I
where
    I: PartialEq + Eq,
    M: Fn(&I, &I) -> I,
    F: Fn(&I) -> bool,
{
    loop {
        let m = midpoint(&lo, &hi);
        if m == lo {
            return if f(&lo) { lo } else { hi };
        }

        if f(&m) {
            hi = m;
        } else {
            lo = m;
        }
    }
}

crates/polars-core/src/chunked_array/ops/search_sorted.rs:32

The search space is a pair (chunk_index, index_in_chunk), and midpoint is a function that computes the logical midpoint across chunk boundaries:

rust 
// crates/polars-core/src/chunked_array/ops/search_sorted.rs:105
    // For each search value do a binary search on (chunk_idx, idx_in_chunk) pairs.
    search_values
        .map(|ov| {
            let Some(v) = ov else {
                return null_idx;
            };
            let left = (0, 0);
            let right = (chunks.len(), 0);
            let midpoint = |l: &(usize, usize), r: &(usize, usize)| {
                if l.0 == r.0 {
                    // Within same chunk.
                    (l.0, (l.1 + r.1) / 2)
                } else if l.0 + 1 == r.0 {
                    // Two adjacent chunks, might have to be l or r.
                    let left_len = chunks[l.0].len() - l.1;

                    let logical_mid = (left_len + r.1) / 2;
                    if logical_mid < left_len {
                        (l.0, l.1 + logical_mid)
                    } else {
                        (r.0, logical_mid - left_len)
                    }
                } else {
                    // Has a chunk in between.
                    ((l.0 + r.0) / 2, 0)
                }
            };

crates/polars-core/src/chunked_array/ops/search_sorted.rs:98

and the predicate is a tot_ge/tot_gt on the physical type, which for a string column is &[u8]:

rust 
// crates/polars-core/src/chunked_array/ops/search_sorted.rs:169
    if !descending {
        if !has_nulls {
            if side == SearchSortedSide::Right {
                lower_bound_chunks::<T, _>(
                    &chunks,
                    search_values,
                    null_idx,
                    |chunk, i, sv| unsafe { chunk.value_unchecked(i).tot_gt(sv) },
                )
            } else {
                lower_bound_chunks::<T, _>(
                    &chunks,
                    search_values,
                    null_idx,
                    |chunk, i, sv| unsafe { chunk.value_unchecked(i).tot_ge(sv) },
                )
            }

crates/polars-core/src/chunked_array/ops/search_sorted.rs:164

chunk.value_unchecked(i) for a BinaryViewArray returns a borrowed &[u8] pointing either into the inline view or into the data buffer. The comparison is &[u8] > &[u8], i.e. a memcmp. Nothing is allocated except the Vec<IdxSize> of result indices and the chunk prefix sum:

rust 
// crates/polars-core/src/chunked_array/ops/search_sorted.rs:90
    // Multiple chunks, precompute prefix sum of lengths so we can look up
    // in O(1) the global position of chunk i.
    let mut sz = 0;
    let mut chunk_len_prefix_sum = Vec::with_capacity(chunks.len() + 1);
    for c in chunks {
        chunk_len_prefix_sum.push(sz);
        sz += c.len();
    }
    chunk_len_prefix_sum.push(sz);

crates/polars-core/src/chunked_array/ops/search_sorted.rs:87

The string entry point in polars-ops shows the whole trick at the top level — as_binary() (a reinterpretation, not a copy) and then straight into binary_search_ca:

rust 
// crates/polars-ops/src/series/ops/search_sorted.rs:38
    match phys_dtype {
        DataType::String => {
            let ca = s.str().unwrap();
            let ca = ca.as_binary();
            let search_values = search_values.str()?;
            let search_values = search_values.as_binary();
            let idx = binary_search_ca(&ca, search_values.iter(), side, descending);
            Ok(IdxCa::new_vec(s.name().clone(), idx))
        },

crates/polars-ops/src/series/ops/search_sorted.rs:33

Note that search_values.iter() yields Option<&[u8]> — the caller’s values are borrowed too, so the search column and the needles both stay unallocated.

Hashing: the same trick, one level up

Group-by and join keys need a hash rather than an ordering, and the same view trick applies — inline strings are hashed straight from their 16 bytes, with no string materialised and no buffer touched:

rust 
// crates/polars-arrow/src/array/binview/view.rs:259
    /// Hashes the bytes this view refers to. Inline views are canonical, so they are hashed
    /// directly from their 16 bytes.
    ///
    /// # Safety
    /// Assumes that this view is valid for the given buffers.
    #[inline]
    pub unsafe fn hash_with_buffers_unchecked<B: AsRef<[u8]>, S: std::hash::BuildHasher>(
        &self,
        buffers: &[B],
        build_hasher: &S,
    ) -> u64 {
        unsafe {
            if self.length <= Self::MAX_INLINE_SIZE {
                build_hasher.hash_one(self.as_u128())
            } else {
                build_hasher.hash_one(self.get_external_slice_unchecked(buffers))
            }
        }
    }

crates/polars-arrow/src/array/binview/view.rs:259

This is the only place where the canonical inline encoding is load-bearing for correctness rather than just speed: hashing as_u128() for an inline view and hashing the bytes for a spilled view must agree, so the inline hash has to be of the byte sequence, not of the raw integer. hash_one(self.as_u128()) would not satisfy that in general… which is worth flagging as a sharp edge rather than a trick to copy. The group-by key path that uses it is in crates/polars-core/src/hashing/vector_hasher.rs:225 and crates/polars-expr/src/hash_keys.rs:177.

The bottom line

The whole design falls out of one decision: a string in Polars is a 16-byte View, not a pointer to a string, and every string kernel is written against that view.

  • Equality is decided by a u64 compare of length | prefix << 32. A length mismatch, or a mismatch in the first four bytes, costs one integer compare and zero memory traffic. Inline strings are finished off with a second u64 compare; spilled strings fall back to memcmp over borrowed slices.
  • Ordering uses the 4-byte prefix as a shortcut discriminator, byte-swapped to big_endian so the integer comparison matches lexicographic byte order. It is a fast path with a predictable miss: strings sharing a four-byte prefix pay for the full comparison.
  • Chunked comparison aligns chunk boundaries, runs the per-array kernel, and combines validity masks with bitwise ops. The only allocations are the output mask and the output chunk list.
  • search_sorted binary-searches a (chunk, index) pair space using tot_ge on borrowed &[u8], so lookups allocate only the result indices.
  • Hashing inline views goes through the u128 encoding, spilled views through the buffer.

The trade-offs are honest ones. The 12-byte inline threshold is a fixed cost paid by every row: a View is 16 bytes whether the string is empty or millions of bytes long, so a column of 10-byte strings costs 16 bytes/row in the views plus 10 bytes/row in the payload — the payload is duplicated, not aliased. The prefix shortcut costs an extra branch and only pays off when strings diverge early. And all of this is scalar: 16 bytes per element is a fixed-width comparison, not a vectorised one, so a genuinely SIMD string comparison would need a different data layout entirely.

What you get in exchange is that string comparison in Polars has no allocator in it at all, and that is the property that makes the difference between filtering a 100M-row string column and not.

PolarsInternalsPerformanceStringsSimd