Clinker engine internals · ← Combine Internals

Range joins,
block by block

A Combine whose where: compares ranges (a.t >= b.lo and a.t < b.hi, with or without an equality) runs on the block-band IEJoin path. Both sides are sorted and cut into blocks tagged with their key ranges; block pairs that cannot match are skipped; each surviving pair runs the IEJoin kernel, or a bounded nested loop when its matches would not fit; and the matches go through match: and on_miss: into one sorted output. This page runs that algorithm on small inputs, step by step, and checks every result against a brute-force join.

Example
Rows per block
Pair budget
match
on_miss
Operators
Driver with a null key
01

PlanWhich strategy the planner picks, and what the kernel checks

The Combine

Conjuncts

02

Sort & sliceEach side sorted by (equality hash, k1, k2, input index), then cut into blocks

03

Block pairsRows are driver blocks, columns build blocks. Tap a pair.

Solid green: kept, kernel ran · solid yellow: kept, too many matches for the pair budget, so the bounded nested loop ran · dashed: pruned by the min/max test · striped: different equality hash, never paired.

Why

04

KernelIEJoin on the selected block pair: two sorted lists, a permutation, a bit array

05

Outputmatch:, on_miss:, and one sort by (driver index, build index)

Rows out

Checks