Polars Does Interval Joins with a Sort and a Sweep

TL;DR: An interval join asks for pairs of rows whose intervals overlap: left.start <= right.end and right.start <= left.end. Done naively that is a nested loop, O(n*m) comparisons. Polars instead sorts the combined inputs twice — once by the interval start, once by the interval end — and then sweeps, marking right-hand rows in a bit array and letting each left row look up only the right rows that can overlap it.
The pruning device is a filtered bit array: a bitmap of visited right-hand rows plus a coarse summary bitmap, so that sparse regions are skipped 1024 bits at a time.

Polars has two inequality-join code paths, and both are in crates/polars-ops/src/frame/join/iejoin/. The first is the full IEJoin, which handles two inequality operators at once — the classic interval overlap query. The second is a “piecewise merge join”, which handles a single inequality.

Both are described in the source with a reference to the paper they come from:

rust
// crates/polars-ops/src/frame/join/iejoin/mod.rs:527
/// Inequality join. Matches rows between two DataFrames using two inequality operators
/// (one of [<, <=, >, >=]).
/// Based on Khayyat et al. 2015, "Lightning Fast and Space Efficient Inequality Joins"
/// and extended to work with duplicate values.
fn iejoin_tuples(

The problem

An interval join on two tables asks: for every left interval [x1, x2] and every right interval [y1, y2], find the pairs where the intervals overlap, i.e. x1 <= y2 and y1 <= x2. That is two inequality predicates over the same pair of rows.

The naive implementation evaluates both predicates for every pair, which is O(nm) predicate evaluations and O(nm) memory if you materialize the result. For a million rows on each side that is a trillion comparisons.

The trick the inequality-join literature uses is that the two predicates pull in opposite directions. One of them (x1 <= y2) is satisfied by right rows that are “far enough right”; the other (y1 <= x2) is satisfied by right rows that are “not too far right”. If you sort the rows by their start points, the set of right rows that could possibly match a given left row is a contiguous range — and the algorithm’s job is to find that range and to enumerate the right rows inside it that also satisfy the second predicate.

text

   combined rows:        L1 order (by x)      L2 order (by y, within L1)
   ---------------        ---------------      ----------------------------
   L1: [l1]               [ l1 l2 r1 ]          [ r1 l1 l2 ]
   L2: [l2]                 |  |  |               |   |  |
   R1: [r1]                 |  |  |               |   |  |
                           v  v  v               v   v  v

   sweep over the L2 order:
     r1  -> right row: set its bit in the visited bitmap
     l1  -> left row: binary search the start of the candidate range,
                       then emit every set bit from there on

The two sorts

The algorithm concatenates the two sides into single arrays of start points x and end points y, then sorts:

rust
// crates/polars-ops/src/frame/join/iejoin/mod.rs:589
    let mut x = selected_left[0].to_physical_repr().into_owned();
    let left_height = x.len();

    x.extend(&selected_right[0].to_physical_repr())?;
    // Rechunk because we will gather.
    let x = x.rechunk();

    let mut y = selected_left[1].to_physical_repr().into_owned();
    y.extend(&selected_right[1].to_physical_repr())?;
    // Rechunk because we will gather.
    let y = y.rechunk();

    let l1_sort_options = SortOptions::default()
        .with_maintain_order(true)
        .with_nulls_last(false)
        .with_order_descending(l1_descending);
    // Get ordering of x, skipping any null entries as these cannot be matches
    let l1_order = x
        .arg_sort(l1_sort_options)
        .slice(x.null_count() as i64, x.len() - x.null_count());

    let y_ordered_by_x = unsafe { y.take_unchecked(&l1_order) };
    let l2_sort_options = SortOptions::default()
        .with_maintain_order(true)
        .with_nulls_last(false)
        .with_order_descending(l2_descending);
    // Get the indexes into l1, ordered by y values.
    // l2_order is the same as "p" from Khayyat et al.
    let l2_order = y_ordered_by_x.arg_sort(l2_sort_options).slice(
        y_ordered_by_x.null_count() as i64,
        y_ordered_by_x.len() - y_ordered_by_x.null_count(),
    );

Two sorts, and the second one is the subtle one:

L1 order sorts the combined rows by their start point x. The sort direction depends on the first operator: Lt/LtEq want ascending, Gt/ GtEq want descending. The comment above says it explicitly — “the algorithms published in Khayyat et al. have incorrect logic for determining whether to sort descending”, so Polars computes it from the operator.
L2 order sorts the end points, but in the order established by L1. That is: take y, permute it by l1_order, and then sort that permuted array by y. The result is the paper’s p: an ordering of the rows by end point, expressed as indices into the L1 array.

Both sorts use maintain_order(true) — they are stable sorts. Stability is not an optimization here, it is a correctness requirement, because the algorithm relies on rows with equal end points being processed in a well-defined relative order.

Nulls are dropped by slicing the sort result past the null count, since nulls_last(false) puts them first.

The L1 and L2 arrays

The sort results are then turned into two flat arrays of small structs. The L1 array holds one item per row, in L1 order, with a signed row index that encodes which side the row came from:

rust
// crates/polars-ops/src/frame/join/iejoin/l1_l2.rs:28
pub(super) fn build_l1_array<T>(
    ca: &ChunkedArray<T>,
    order: &IdxCa,
    right_df_offset: IdxSize,
) -> PolarsResult<Vec<L1Item<T::Native>>>
where
    T: PolarsNumericType,
{
    assert_eq!(order.null_count(), 0);
    assert_eq!(ca.chunks().len(), 1);
    let arr = ca.downcast_get(0).unwrap();
    // Even if there are nulls, they will not be selected by order.
    let values = arr.values().as_slice();

    let mut array: Vec<L1Item<T::Native>> = Vec::with_capacity(ca.len());

    for order_arr in order.downcast_iter() {
        for index in order_arr.values().as_slice().iter().copied() {
            debug_assert!(arr.get(index as usize).is_some());
            let value = unsafe { *values.get_unchecked(index as usize) };
            let row_index = if index < right_df_offset {
                // Row from LHS
                index as i64 + 1
            } else {
                // Row from RHS
                -((index - right_df_offset) as i64) - 1
            };
            array.push(L1Item { row_index, value });
        }
    }

    Ok(array)
}

The sign of row_index is the whole trick for distinguishing sides: positive means “left row”, negative means “right row”. A single i64 per row instead of a tag plus an index.

The L2 array does not store the end values at all. It only needs to know where a run of equal end points ends:

rust
// crates/polars-ops/src/frame/join/iejoin/l1_l2.rs:95
/// Item in L1 array used in the IEJoin algorithm
#[derive(Clone, Copy, Debug)]
pub(super) struct L1Item<T> {
    /// 1 based index for entries from the LHS df, or -1 based index for entries from the RHS
    pub(super) row_index: i64,
    /// X value
    pub(super) value: T,
}

/// Item in L2 array used in the IEJoin algorithm
#[derive(Clone, Copy, Debug)]
pub(super) struct L2Item {
    /// Corresponding index into the L1 array of
    pub(super) l1_index: IdxSize,
    /// Whether this is the end of a run of equal y values
    pub(super) run_end: bool,
}

The sweep

The sweep is ie_join_impl_t. It walks the L2 order and does one of two things per element: if the element is a right-hand row, mark it as visited; if it is a left-hand row, emit all the visited right-hand rows that satisfy the first operator.

rust
// crates/polars-ops/src/frame/join/iejoin/mod.rs:74
    if op2.is_strict() {
        // For strict inequalities, we rely on using a stable sort of l2 so that
        // p values only increase as we traverse a run of equal y values.
        // To handle inclusive comparisons in x and duplicate x values we also need the
        // sort of l1 to be stable, so that the left hand side entries come before the right
        // hand side entries (as we mark visited entries from the right hand side).
        for &p in l2_order {
            match_count += unsafe {
                l1_array.process_entry(
                    p as usize,
                    &mut bit_array,
                    op1,
                    &mut left_row_idx,
                    &mut right_row_idx,
                )
            };

            if slice_end.is_some_and(|end| match_count >= end) {
                break;
            }
        }
    } else {
        let l2_array = build_l2_array(&y_ordered_by_x, l2_order)?;

        // For non-strict inequalities in l2, we need to track runs of equal y values and only
        // check for matches after we reach the end of the run and have marked all rhs entries
        // in the run as visited.
        let mut run_start = 0;

        for i in 0..l2_array.len() {
            // Elide bound checks
            unsafe {
                let item = l2_array.get_unchecked(i);
                let p = item.l1_index;
                l1_array.mark_visited(p as usize, &mut bit_array);

                if item.run_end {
                    for l2_item in l2_array.get_unchecked(run_start..i + 1) {
                        let p = l2_item.l1_index;
                        match_count += l1_array.process_lhs_entry(
                            p as usize,
                            &bit_array,
                            op1,
                            &mut left_row_idx,
                            &mut right_row_idx,
                        );
                    }

                    run_start = i + 1;

The two branches exist because of < versus <= on the second operator.

With a strict operator (<), a right row with end point e only matches a left row whose end point is strictly greater than e, so processing the right row as soon as it is encountered is fine — as long as the L1 sort is stable, so that equal-x left rows come before equal-x right rows.

With a non-strict operator (<=), a left row with end point e matches every right row with end point e, including the ones that have not been visited yet. So the algorithm cannot check a left row until the whole run of equal end points has been processed. That is what run_end marks, and it is why the L2 array stores a flag per element instead of the values.

process_entry is where the two cases are unified:

rust
// crates/polars-ops/src/frame/join/iejoin/l1_l2.rs:212
impl<T> L1Array for Vec<L1Item<T>>
where
    T: NumericNative,
{
    unsafe fn process_entry(
        &self,
        l1_index: usize,
        bit_array: &mut FilteredBitArray,
        op1: InequalityOperator,
        left_row_ids: &mut Vec<IdxSize>,
        right_row_ids: &mut Vec<IdxSize>,
    ) -> i64 {
        let row_index = self.get_unchecked(l1_index).row_index;
        let from_lhs = row_index > 0;
        if from_lhs {
            find_matches_in_l1(
                self,
                l1_index,
                row_index,
                bit_array,
                op1,
                left_row_ids,
                right_row_ids,
            )
        } else {
            bit_array.set_bit_unchecked(l1_index);
            0
        }
    }

A right row sets its bit; a left row goes looking for matches.

Finding the matches

find_matches_in_l1 is where the pruning happens. Two steps:

Find the position in the L1 array where the candidate range starts. This is a binary search, but an exponential one — the search doubles its window until it brackets the answer, which is much cheaper than a full binary search when the answer is close:

rust
// crates/polars-ops/src/frame/join/iejoin/l1_l2.rs:149
unsafe fn find_search_start_index<T>(
    l1_array: &[L1Item<T>],
    index: usize,
    operator: InequalityOperator,
) -> usize
where
    T: NumericNative,
    T: TotalOrd,
{
    let sub_l1 = l1_array.get_unchecked(index..);
    let value = l1_array.get_unchecked(index).value;

    match operator {
        InequalityOperator::Gt => {
            sub_l1.partition_point_exponential(|a| a.value.tot_ge(&value)) + index
        },
        InequalityOperator::Lt => {
            sub_l1.partition_point_exponential(|a| a.value.tot_le(&value)) + index
        },
        InequalityOperator::GtEq => {
            sub_l1.partition_point_exponential(|a| value.tot_lt(&a.value)) + index
        },
        InequalityOperator::LtEq => {
            sub_l1.partition_point_exponential(|a| value.tot_gt(&a.value)) + index
        },
    }
}

Because L1 is sorted by x, all rows from that position onwards satisfy the first operator. So the remaining question is: which of those rows have already been visited? — that is, which right rows also satisfy the second operator.

Enumerate the set bits of the bit array from that position:

rust
// crates/polars-ops/src/frame/join/iejoin/l1_l2.rs:184
fn find_matches_in_l1<T>(
    l1_array: &[L1Item<T>],
    l1_index: usize,
    row_index: i64,
    bit_array: &FilteredBitArray,
    op1: InequalityOperator,
    left_row_ids: &mut Vec<IdxSize>,
    right_row_ids: &mut Vec<IdxSize>,
) -> i64
where
    T: NumericNative,
    T: TotalOrd,
{
    debug_assert!(row_index > 0);
    let mut match_count = 0;

    // This entry comes from the left hand side DataFrame.
    // Find all following entries in L1 (meaning they satisfy the first operator)
    // that have already been visited (so satisfy the second operator).
    // Because we use a stable sort for l2, we know that we won't find any
    // matches for duplicate y values when traversing forwards in l1.
    let start_index = unsafe { find_search_start_index(l1_array, l1_index, op1) };
    unsafe {
        bit_array.on_set_bits_from(start_index, |set_bit: usize| {
            // SAFETY
            // set bit is within bounds.
            let right_row_index = l1_array.get_unchecked(set_bit).row_index;
            debug_assert!(right_row_index < 0);
            left_row_ids.push((row_index - 1) as IdxSize);
            right_row_ids.push((-right_row_index) as IdxSize - 1);
            match_count += 1;
        })
    };

    match_count
}

The bit array is the “visited right rows” set. Each set bit is a right row that has been swept past in end-point order, i.e. a right row whose end point is small enough to satisfy the second predicate.

The filtered bit array

The naive way to enumerate set bits is to walk the whole bitmap from the start index to the end, which is O(n) per left row — back to O(n*m). The filtered bit array adds a summary level: one bit per 1024-bit chunk, saying “this chunk contains at least one visited row”.

rust
// crates/polars-ops/src/frame/join/iejoin/filtered_bit_array.rs:38
/// Bit array with a filter to speed up searching for set bits when sparse,
/// based on section 4.1 from Khayyat et al. 2015,
/// "Lightning Fast and Space Efficient Inequality Joins"
pub struct FilteredBitArray {
    bit_array: MutableBitmap,
    filter: MutableBitmap,
}

impl FilteredBitArray {
    const CHUNK_SIZE: usize = 1024;

    pub fn from_len_zeroed(len: usize) -> Self {
        Self {
            bit_array: MutableBitmap::from_len_zeroed(len),
            filter: MutableBitmap::from_len_zeroed(len.div_ceil(Self::CHUNK_SIZE)),
        }
    }

    pub unsafe fn set_bit_unchecked(&mut self, index: usize) {
        self.bit_array.set_unchecked(index, true);
        self.filter.set_unchecked(index / Self::CHUNK_SIZE, true);
    }

    pub unsafe fn on_set_bits_from<F>(&self, start: usize, mut action: F)
    where
        F: FnMut(usize),
    {
        let start_chunk = start / Self::CHUNK_SIZE;
        let mut chunk_offset = start % Self::CHUNK_SIZE;
        for chunk_idx in start_chunk..self.filter.len() {
            if self.filter.get_unchecked(chunk_idx) {
                // There are some set bits in this chunk
                let start = chunk_idx * Self::CHUNK_SIZE + chunk_offset;
                let end = min((chunk_idx + 1) * Self::CHUNK_SIZE, self.bit_array.len());
                for bit_idx in start..end {
                    // SAFETY: `bit_idx` is always less than `self.bit_array.len()`
                    if self.bit_array.get_unchecked(bit_idx) {
                        action(bit_idx);
                    }
                }
            }
            chunk_offset = 0;
        }
    }
}

Empty chunks are skipped with a single bit test, so the cost of enumerating matches is proportional to the number of non-empty chunks plus the number of set bits — not to the length of the array. This is the mechanism that makes the sweep sub-quadratic in practice: the “pruning” of the right side is done by the summary bitmap, which skips regions of the L1 array where no right row has been visited yet.

The single-inequality variant

When there is only one operator, the whole L1/L2 machinery is unnecessary. The condition x1 < y2 is monotone in both arguments once both sides are sorted, so a two-cursor scan suffices:

rust
// crates/polars-ops/src/frame/join/iejoin/mod.rs:133
fn piecewise_merge_join_impl_t<T, P>(
    slice: Option<(i64, usize)>,
    left_order: Option<&[IdxSize]>,
    right_order: Option<&[IdxSize]>,
    left_ordered: Series,
    right_ordered: Series,
    mut pred: P,
) -> PolarsResult<(Vec<IdxSize>, Vec<IdxSize>)>
where
    T: PolarsNumericType,
    P: FnMut(&T::Native, &T::Native) -> bool,
{
    let slice_end = slice_end_index(slice);

    let mut left_row_idx: Vec<IdxSize> = vec![];
    let mut right_row_idx: Vec<IdxSize> = vec![];

    let left_ca: &ChunkedArray<T> = left_ordered.as_ref().as_ref();
    let right_ca: &ChunkedArray<T> = right_ordered.as_ref().as_ref();

    debug_assert!(left_order.is_none_or(|order| order.len() == left_ca.len()));
    debug_assert!(right_order.is_none_or(|order| order.len() == right_ca.len()));

    let mut left_idx = 0;
    let mut right_idx = 0;
    let mut match_count = 0;

    while left_idx < left_ca.len() {
        debug_assert!(left_ca.get(left_idx).is_some());
        let left_val = unsafe { left_ca.value_unchecked(left_idx) };
        while right_idx < right_ca.len() {
            debug_assert!(right_ca.get(right_idx).is_some());
            let right_val = unsafe { right_ca.value_unchecked(right_idx) };
            if pred(&left_val, &right_val) {
                // If the predicate is true, then it will also be true for all
                // remaining rows from the right side.

The comment is the whole reason this is linear: once the predicate holds, it holds for every remaining right row, so they are all emitted at once and the right cursor does not advance. The left cursor then moves on.

The sorting for this variant reuses the column’s sorted flag when it is already there:

rust
// crates/polars-ops/src/frame/join/iejoin/mod.rs:667
    fn get_sorted(series: Series, descending: bool) -> (Series, Option<IdxCa>) {
        let expected_flag = if descending {
            IsSorted::Descending
        } else {
            IsSorted::Ascending
        };
        if (series.is_sorted_flag() == expected_flag || series.len() <= 1) && !series.has_nulls() {
            // Fast path, no need to re-sort
            (series, None)
        } else {
            let sort_options = SortOptions::default()
                .with_nulls_last(false)
                .with_order_descending(descending);

            // Get order and slice to ignore any null values, which cannot be match results
            let mut order = series.arg_sort(sort_options).slice(
                series.null_count() as i64,
                series.len() - series.null_count(),
            );

If the input is already flagged as sorted in the right direction, the sort is skipped entirely and the “order” is the identity — which is why the function returns Option<IdxCa>: None means “no permutation needed”.

Going parallel

The parallel variant partitions both sides by the first sort order and processes the partitions independently, but only after checking that the partition can contain matches at all:

rust
// crates/polars-ops/src/frame/join/iejoin/mod.rs:343
        let Some((min_l, max_l)) = get_extrema(l_l1_idx, sl) else {
            return Ok(None);
        };
        let Some((min_r, max_r)) = get_extrema(r_l1_idx, sr) else {
            return Ok(None);
        };

        let include_block = match options.operator1 {
            InequalityOperator::Lt => min_l < max_r,
            InequalityOperator::LtEq => min_l <= max_r,
            InequalityOperator::Gt => max_l > min_r,
            InequalityOperator::GtEq => max_l >= min_r,
        };

        if include_block {

min_l and max_r are the extreme values of the left and right partition. If the smallest left start is not below the largest right end, no left row in this partition can overlap any right row in the other partition, and the whole block is skipped. That is a cheap interval-overlap test, and it is what keeps the partition count from exploding.

The number of partitions is chosen with the cartesian product in mind, because each partition pair does its own join:

rust
// crates/polars-ops/src/frame/join/iejoin/mod.rs:314
    // Because we do a cartesian product, the number of partitions is squared.
    // We take the sqrt, but we don't expect every partition to produce results and work can be
    // imbalanced, so we multiply the number of partitions by 2, which leads to 2^2= 4
    let n_partitions = (_set_partition_size() as f32).sqrt() as usize * 2;

The bottom line

The design in one sentence: sort the problem into a form where the candidate set of every row is a range, then keep the survivors in a bitmap.

The trade-offs:

Two sorts up front. The algorithm pays O(n log n) for the L1 sort and O(n log n) for the L2 sort before it emits a single pair. For small inputs a nested loop would be cheaper, which is why the single-inequality variant exists at all.
The output can still be quadratic. If every interval overlaps every other, the number of output pairs is O(n*m) and no algorithm can avoid writing them out. The IEJoin makes the search sub-quadratic; it cannot make the output sub-quadratic.
Stability is a correctness requirement. Both sorts use maintain_order(true), and the non-strict branch of the sweep depends on it. This is the kind of requirement that is easy to break in a refactor and hard to notice.
The bit array is O(n) memory — one bit per row, plus one bit per 1024 rows of summary. Cheap, but it is another allocation proportional to the input size.
Only numeric types. The implementation goes through with_match_physical_numeric_polars_type!, so interval joins over strings or datetimes are not supported here; the single-inequality variant is likewise numeric-only.