Prefetch hints for arrangement reads (joins, reduces)

Motivation

Arrangements backed by large batches can incur cache misses or page faults when cursors seek through cold data. With a custom allocator that supports prefetching (e.g., madvise(MADV_WILLNEED) or explicit page-in), we could hide this latency — if operators can express what data they'll need next.

This issue explores where prefetch hints could be injected and what API shapes might work.

Current access pattern

The join loop (join.rs:367–396) is a synchronized merge of two cursors:

while let (Some(batch_key), Some(trace_key), ..) = (..) {
    match trace_key.cmp(&batch_key) {
        Less    => trace.seek_key(trace_storage, batch_key),
        Greater => batch.seek_key(batch_storage, trace_key),
        Equal   => { /* load vals/times, compute, step both */ }
    }
}

Key observations:

• The batch cursor drives the access pattern. Its keys are known upfront (small, new batch). The trace cursor seeks to match.
• CursorList::seek_key fans out to every inner cursor (cursor_list.rs:151–155), each doing exponential+binary search in its keys container.
• After a key match, all vals and (time, diff) pairs are loaded — ValueHistory::load walks the full value/time structure for that key.
• No lookahead exists today. The join processes one key at a time with zero knowledge of the next.

Reduce is better positioned: it maintains a pending_keys list and could prefetch the full batch of upcoming keys.

Where prefetch helps

1. Key lookup across batches — when seeking k in the trace, prefetch the approximate landing position for the next batch key in each spine batch.
2. Value/update loading — once we know key_cursor, prefetch the vals and upds ranges before starting the Cartesian product for the previous key.
3. Parallel prefetch across CursorList — issue prefetches to all batches before performing the actual seeks.

Possible API shapes

A) Cursor-level hint (operator-facing, minimal)

trait Cursor {
    /// Hint that the cursor will soon seek to `key`. Default: no-op.
    fn prefetch_key(&self, _storage: &Self::Storage, _key: Self::Key<'_>) {}
}

The join peeks at the next batch key and calls trace.prefetch_key(storage, next_key) one iteration ahead. CursorList fans out to all inner cursors.

Pros: Simple, opt-in, no breaking changes.
Cons: Only one key ahead; the operator must drive it.

B) Container-level hint (storage-facing, transparent)

trait BatchContainer {
    /// Hint that indices in [start, end) will be accessed soon. Default: no-op.
    fn prefetch(&self, _start: usize, _end: usize) {}
}

OrdValCursor::seek_key could, after computing the destination index, prefetch the associated value/update offset and data ranges. Invisible to operators.

Pros: Transparent; also benefits merge cursors.
Cons: Container must know its memory layout to compute addresses.

C) Trace-level batch hint (maximum information)

trait TraceReader {
    /// Hint that these keys will be looked up soon. Default: no-op.
    fn prefetch_keys<I: IntoIterator<Item = ...>>(&self, keys: I) {}
}

The operator extracts the next N keys from the batch cursor and passes them all at once. The spine fans out to each batch; the allocator gets a batch of prefetch requests.

Pros: Maximum information for the allocator; amortizable.
Cons: More invasive; trace must expose inner structure.

Pieces not yet in place

• Allocator ↔ container connection. BatchContainer / Layout have no reference to an allocator. Containers would need either an allocator handle or a global/thread-local prefetch mechanism.
• Address computation. Translating "key index N" to a byte range is trivial for Vec<T> (ptr + N * size_of::<T>()) but encoding-dependent for columnar containers.
• Peek-ahead in cursors. The Cursor trait has no peek_next_key(). The join could read ahead in the batch directly (it owns the storage), or a small API addition could formalize this.

Suggested starting point

Combine A + B: add prefetch_key on Cursor (default no-op) and prefetch on BatchContainer (default no-op). In OrdValCursor::prefetch_key, estimate the key's landing position and prefetch the key/val/update byte ranges. In the join loop, peek at the next batch key and call the hint one iteration ahead. All zero-cost until a container opts in.

For reduce, prefetch the full pending_keys list upfront since it's known ahead of time.

Start by reading the join loop in join.rs:367–396, CursorList::seek_key in cursor_list.rs:151–155, and ValueHistory::load. Then trace OrdValCursor::seek_key and the Cursor and BatchContainer traits to compare the proposed hinting layers. Done means settling an API and its scope for join and reduce prefetching, including how containers connect to allocation and address ranges.