Sorted-list intersection

Deep dive

How it works

In: k sorted, duplicate-free lists of u32 ids · Out: sorted ids present in all lists · State: none (cursor per list) · Cost: merge O(m+n); galloping O(m log(n/m)); SvS: the sum over lists of the same bound, with m shrinking to the running result

1. Sort the lists by length (or estimated cost). Take the shortest as the candidate set.
2. Merge: advance the cursor of the smaller head; emit on equality. Cursors advance by comparison results, branch-free.
3. Galloping: for each id x of the short list, probe the long list at offsets 0, 1, 2, 4, 8, ... from the cursor until an element >= x; then binary search that last gap. The cursor never moves back.
4. SvS (small versus small): intersect the two shortest lists, then intersect the result with the next shortest, and so on; stop when the result is empty.
5. Compressed lists: store ids in blocks of 128 (delta-coded, bit-packed), with each block's last id in a skip array. To find x, binary search or step the skip array, then decode only the one block that can contain x.
6. Dense lists: switch the container to a bitmap and AND words (Roaring chooses per 65,536-id chunk).
7. Union (OR) is a merge emitting both heads; difference (NOT) emits left ids with no match, and can gallop too.

Code

use std::time::Instant;

/// Linear merge: O(m+n).
pub fn merge(a: &[u32], b: &[u32]) -> Vec<u32> {
    let (mut i, mut j, mut out) = (0, 0, Vec::new());
    while i < a.len() && j < b.len() {
        let (x, y) = (a[i], b[j]);
        if x == y { out.push(x); }
        i += (x <= y) as usize; // branch-free advance
        j += (y <= x) as usize;
    }
    out
}

/// First index in s[from..] with s[idx] >= t: exponential probe, then binary search.
fn gallop(s: &[u32], from: usize, t: u32) -> usize {
    let mut step = 1;
    let mut hi = from;
    while hi < s.len() && s[hi] < t {
        hi = from + step; // probe from, from+1, from+2, from+4, ...
        step *= 2;
    }
    let lo = from + step / 4; // last probe known < t (or from)
    let hi = hi.min(s.len());
    lo + s[lo..hi].partition_point(|&v| v < t)
}

/// Galloping: iterate the short list, gallop in the long one. O(m log(n/m)).
pub fn galloping(short: &[u32], long: &[u32]) -> Vec<u32> {
    let (mut j, mut out) = (0, Vec::new());
    for &x in short {
        j = gallop(long, j, x);
        if j == long.len() { break; }
        if long[j] == x { out.push(x); j += 1; }
    }
    out
}

/// SvS: sort lists by length, intersect the two shortest, probe the result into the rest.
pub fn svs(lists: &[&[u32]]) -> Vec<u32> {
    let mut ls: Vec<&[u32]> = lists.to_vec();
    ls.sort_by_key(|l| l.len());
    let Some((first, rest)) = ls.split_first() else { return vec![] };
    let mut cur = first.to_vec();
    for l in rest {
        if cur.is_empty() { break; }
        cur = galloping(&cur, l);
    }
    cur
}

struct Rng(u64);
impl Rng {
    fn next(&mut self) -> u64 { // xorshift64*
        self.0 ^= self.0 >> 12; self.0 ^= self.0 << 25; self.0 ^= self.0 >> 27;
        self.0.wrapping_mul(0x2545F4914F6CDD1D)
    }
    fn list(&mut self, n: usize, universe: u32) -> Vec<u32> {
        let mut v: Vec<u32> = (0..n).map(|_| (self.next() % universe as u64) as u32).collect();
        v.sort_unstable(); v.dedup(); v
    }
}

fn main() {
    let mut r = Rng(0x9E3779B97F4A7C15);
    for t in 0..2000 {
        let u = [10, 100, 5000][t % 3];
        let ls: Vec<Vec<u32>> = (0..3).map(|_| { let n = (r.next() % 40) as usize; r.list(n, u) }).collect();
        let m = merge(&ls[0], &ls[1]);
        assert_eq!(m, galloping(&ls[0], &ls[1]));
        assert_eq!(m, galloping(&ls[1], &ls[0])); // galloping is also correct with the long list first
        let m3 = merge(&m, &ls[2]);
        assert_eq!(m3, svs(&[&ls[2], &ls[0], &ls[1]]));
    }
    assert!(merge(&[1, 3, 5], &[2, 4, 6]).is_empty() && svs(&[&[1, 2], &[]]).is_empty());
    println!("all agree");

    let big = r.list(1_200_000, 4_000_000_000);
    let other = r.list(1_200_000, 4_000_000_000); // independent list: almost no common ids
    let rows: Vec<(&str, Vec<u32>)> = vec![
        ("subset", big.iter().step_by(1200).copied().collect()),
        ("subset", big.iter().step_by(12).copied().collect()),
        ("same  ", big.clone()),
        ("random", other),
    ];
    for (kind, small) in rows {
        let time = |f: &dyn Fn() -> Vec<u32>| (0..7).map(|_| { let t = Instant::now(); f(); t.elapsed().as_secs_f64() * 1e6 })
            .fold(f64::MAX, f64::min);
        println!("{kind} {:>8} vs {}: merge {:>8.1} us, galloping {:>8.1} us", small.len(), big.len(),
            time(&|| merge(&small, &big)), time(&|| galloping(&small, &big)));
    }
}

Measured on this Mac (Apple M4 Pro), best of 7, --release; subset rows probe ids taken from the long list, the random row is an independent list (about 370 common ids):

Complexity and constants

• Merge: m+n steps, about one branch-free compare-and-advance each; sequential reads. Galloping: about 2 log2(gap) probes per short-list id, each a possible cache miss on a large list.
• Break-even is data-dependent: galloping won every subset row and the identical-list row above, but lost on random equal-length lists, where each probe pays a gallop plus a binary search for a gap of about 1. Choose the length-ratio threshold by measuring.
• Adaptive analysis (Demaine, López-Ortiz, Munro): cost can be bounded by how often the lists alternate, not by their lengths.
• Memory: 4 bytes per id raw; 128 ids compressed cost bit width x 128 bits plus a skip entry.

Efficiency

• Cost: on this Mac (Apple M4 Pro), measured: merge about 1-2 ns per input id (4.2 ms for 2.4M ids, random); galloping about 51 ns per probe id (1k probes into 1.2M ids). Bound: memory latency for galloping, memory bandwidth and branch behaviour for merge.
• Levers:
  • SvS order, shortest first — later lists are probed only at surviving ids — three or more lists
  • galloping — 27x here (1k vs 1.2M, measured on this Mac) — strongly skewed lengths
  • block skip data — never decodes blocks without a candidate — compressed postings
  • SIMD all-pairs compare, advancing a block — up to 5.2x over std::set_intersection on Xeon (Inoue et al.); Lemire et al. claim 2x over a state-of-the-art approach — 32-bit ids, similar-length lists
  • bitmap containers — 64 ids per AND — chunks with over 4096 ids per 65,536 (Roaring spec switches to a bitset there)
• Naive → standard → state of the art:
  • hash one list, probe with the other · O(m+n), a hash lookup per id
  • merge, then galloping + SvS · measured above: 51 us vs 1.4 ms on 1k vs 1.2M
  • compressed blocks with skip data, SIMD galloping, Roaring for dense chunks · decode only candidate blocks (Lemire et al.; Culpepper and Moffat)

Implementation notes

• Skip data per block: last id (and, in scored engines, the block's maximum score, which is what block-max WAND reads). Tantivy keeps both beside 128-id bit-packed blocks.
• Once lists are compressed, decoding dominates: delta encoding, bit-packing/PFOR, varint.
• Branchy merge loops mispredict when the lists alternate; the (x <= y) as usize form removes the branch (branch prediction). SIMD variants compare all pairs of a few ids at once and advance a block (SIMD programming).
• A sentinel id above the maximum (Tantivy uses TERMINATED) removes end-of-list checks.
• Inputs must be deduplicated: galloping above would skip repeated ids.

Pitfalls

• Skipping the length sort in SvS loses most of the gain.
• Galloping on near-equal lists is slower than merge (measured above, about 2x): use a ratio threshold.
• Decoding whole lists before intersecting throws away the skip data.

Variants and alternatives

In production

• Tantivy sorts scorers by cost and advances the rest with seek over skip data; Lucene also intersects postings with skipping.
• Roaring bitmaps are used by Lucene and derivatives (Solr, Elasticsearch), Druid, Spark and ClickHouse (CRoaring README).
• Graph engines (adjacency lists) and databases (merge joins) intersect sorted ids as well.

Implementations

Sources

• Demaine, López-Ortiz, Munro, Adaptive set intersections, unions, and differences, SODA 2000 (citation only; no link verified). Follow-up: Experiments on Adaptive Set Intersections for Text Retrieval Systems, ALENEX 2001. doi
• Bentley, Yao, An almost optimal algorithm for unbounded searching, Information Processing Letters 5(3), 1976. doi
• Culpepper, Moffat, Efficient set intersection for inverted indexing, ACM TOIS 29(1), 2010. doi
• Lemire, Boytsov, Kurz, SIMD compression and the intersection of sorted integers, Software: Practice and Experience 46(6), 2016. arXiv · code
• Inoue, Ohara, Taura, Faster set intersection with SIMD instructions by reducing branch mispredictions, PVLDB 8(3), 2014. doi
• Chambi, Lemire, Kaser, Godin, Better bitmap performance with Roaring bitmaps, Software: Practice and Experience, 2016. arXiv
• Lemire, Ssi-Yan-Kai, Kaser, Consistently faster and smaller compressed bitmaps with Roaring, 2016. arXiv
• Roaring format specification (array containers up to 4096 values, bitset above). spec
• Tantivy source: src/postings/skip.rs, src/query/intersection.rs. code