Opportunity
SortedColumnIndex::get_subset (core-relations/src/sorted_index.rs) runs a full binary search over the keys array on every probe. But in the `JoinStage::Intersect` arms of core-relations/src/free_join/execute.rs, probes are driven by another sorted index's for_each, which emits keys in ascending order:
- two-scan arm (~line 1180):
smaller.for_each(|val, ...| ... larger.get_subset(val))
- multi-scan
rest arm (~line 1292): probers[smallest].for_each(...) probing each probers[i].get_subset(key)
When the outer prober is a sorted variant (DynamicColumn/SparseColumn), the probe sequence into each inner index is monotonically increasing, so each probe can resume from a caller-held cursor with galloping/exponential search (amortized O(log gap), O(1) for adjacent keys) instead of O(log n) from scratch. SortedOffsetSlice::scan_for_offset (core-relations/src/offsets/mod.rs) already implements exactly this shape for sparse-sparse intersection and can be adapted to the keys: Vec<(Value, u32)> layout.
Sketch
Add SortedColumnIndex::get_subset_from(&self, cursor: &mut usize, key: Value): gallop forward when keys[*cursor].0 <= key, else fall back to a plain binary search and reset the cursor. The fallback makes it safe to plumb through Prober unconditionally — hash-driven outer loops (Cached*/Dynamic iterate in insertion order) just degrade to today's cost plus one comparison. Cursors must live in the caller (the index is a shared Arc snapshot), scoped to one for_each.
When both sides are DynamicColumn, a further step is to replace for_each + probe with a direct merge-join over the two keys arrays.
Smaller related wins
intersect_with_dense_ref (execute.rs ~line 235) does two binary_search_by_id calls; the second can start from the first's result via binary_search_from, mirroring what Subset::intersect's Sparse∩Dense arm already does in offsets/mod.rs.- The incremental-rebuild loops (
core-relations/src/table/rebuild.rs ~lines 140, 165) probe SortedRebuildIndex with distinct, order-independent ids: sorting the ids first turns the loop into a linear merge against the index.
Expected payoff is low single digits end-to-end (probe machinery is a few percent of runtime on the transformer benchmarks), but the change is small and self-contained. Verify with scripts/bench.py.
follow up of #948
Opportunity
SortedColumnIndex::get_subset(core-relations/src/sorted_index.rs) runs a full binary search over the keys array on every probe. But in the `JoinStage::Intersect` arms ofcore-relations/src/free_join/execute.rs, probes are driven by another sorted index'sfor_each, which emits keys in ascending order:smaller.for_each(|val, ...| ... larger.get_subset(val))restarm (~line 1292):probers[smallest].for_each(...)probing eachprobers[i].get_subset(key)When the outer prober is a sorted variant (
DynamicColumn/SparseColumn), the probe sequence into each inner index is monotonically increasing, so each probe can resume from a caller-held cursor with galloping/exponential search (amortized O(log gap), O(1) for adjacent keys) instead of O(log n) from scratch.SortedOffsetSlice::scan_for_offset(core-relations/src/offsets/mod.rs) already implements exactly this shape for sparse-sparse intersection and can be adapted to thekeys: Vec<(Value, u32)>layout.Sketch
Add
SortedColumnIndex::get_subset_from(&self, cursor: &mut usize, key: Value): gallop forward whenkeys[*cursor].0 <= key, else fall back to a plain binary search and reset the cursor. The fallback makes it safe to plumb throughProberunconditionally — hash-driven outer loops (Cached*/Dynamiciterate in insertion order) just degrade to today's cost plus one comparison. Cursors must live in the caller (the index is a sharedArcsnapshot), scoped to onefor_each.When both sides are
DynamicColumn, a further step is to replacefor_each+ probe with a direct merge-join over the two keys arrays.Smaller related wins
intersect_with_dense_ref(execute.rs~line 235) does twobinary_search_by_idcalls; the second can start from the first's result viabinary_search_from, mirroring whatSubset::intersect's Sparse∩Dense arm already does inoffsets/mod.rs.core-relations/src/table/rebuild.rs~lines 140, 165) probeSortedRebuildIndexwith distinct, order-independent ids: sorting the ids first turns the loop into a linear merge against the index.Expected payoff is low single digits end-to-end (probe machinery is a few percent of runtime on the transformer benchmarks), but the change is small and self-contained. Verify with
scripts/bench.py.follow up of #948