Range, interval and as-of joins

Why can range and interval joins not be hashed, and why does the as-of join exist as a named operator?

Range and interval joins: where equality was the assumption

A range join is R.x BETWEEN S.lo AND S.hi, or two intervals that overlap. Hashing is unavailable, and not by accident. A hash function that put nearby values in the same bucket and stayed uniform would be a contradiction: uniformity is precisely the destruction of value locality. Locality-sensitive hashes exist, but a locality-preserving hash is range partitioning under another name.

So every solution is order-based. There are two shapes.

Band merge join. Sort both sides and walk through them with a moving window. The cost is the sorts plus O(|R| + |S| + output). It is the natural extension of sort-merge, which is why sort-merge's ability to handle inequalities matters even when equality is available.

Range partitioning with replication. Cut the value domain into buckets of width w. An interval that spans k buckets is copied into all k. The replication factor is (average interval length) / w.

• Wider buckets reduce replication but put more rows in each bucket, and the local join in a bucket is quadratic in the rows it holds.
• So the total work is roughly N·L/w for replication, plus a per-bucket term that grows with w. There is an optimal w, set by the distribution of interval lengths, which is the statistic nobody collects.
• If interval lengths have a heavy tail (one contract valid for a decade among millions valid for a day), replication explodes on the tail.

This is the maximum, not mean principle in a form that is easy to miss: the variance that hurts here is not in the key frequencies but in the interval widths.

The structural difference from an equijoin: a range join has no cardinality anchor. An equijoin's output is a dot product of frequency vectors, so you can at least bound it per key. A range join's output is the number of overlapping pairs. That is a property of the geometry, and it can be quadratic with no warning from any statistic the optimizer has.

As-of joins: the best case here for a special-purpose operator

For each left row at time t, find the right row with the greatest time ≤ t. (This is Omar's "price at the time of the order".) It looks like a range join, but it is a range join with an argmax embedded: among all qualifying rows, return exactly one.

That difference is the whole point. Written relationally, as a correlated subquery or as a range join followed by ROW_NUMBER() = 1, the engine builds every qualifying pair before reducing to one row per left row. With n left rows and m right rows that is O(n·m) intermediate tuples to produce n output rows.

-- Relational form: materializes every (order, earlier price) pair first.
SELECT * FROM (
  SELECT o.order_id, p.price,
         ROW_NUMBER() OVER (PARTITION BY o.order_id ORDER BY p.valid_from DESC) AS rn
  FROM orders o JOIN prices p
    ON p.product_id = o.product_id AND p.valid_from <= o.order_ts
) WHERE rn = 1;

-- Named operator form (syntax varies by engine):
SELECT o.order_id, p.price
FROM orders o ASOF JOIN prices p
  MATCH_CONDITION (o.order_ts >= p.valid_from)
  ON o.product_id = p.product_id;

Written as a merge, it is linear: sort both sides by (key, time), walk them together, and carry one row of state per group. Advance the carried row as the left side advances. The output is exactly |left| rows, memory is O(groups), and the total cost is the sorts plus one linear pass.

No general-purpose optimizer finds this transformation. The argmax is written as a window function or correlated subquery, and rewriting either into a merge with a one-row carry is in no rewrite catalogue. So the linear algorithm exists only if the engine offers as-of join as a named operator. That is why kdb+, ClickHouse, DuckDB, Polars and Flink all have one, and why general engines often do not. Five independent systems converging on a first-class operator for one predicate shape is strong evidence that the rewrite is not reachable.

It is also cheap where it exists for a second reason: it is a merge, so it needs sortedness on (key, time), and time-series data is already stored in time order. The sort was paid by the physical layout. In a general engine over an unsorted table the sort is real, and the advantage shrinks to the avoided quadratic intermediate, which is still usually decisive.

This is generality versus specialization at its sharpest here. The price of generality here is not a constant factor but a complexity class.