Problem or motivation
Arrays are lazy and execute/execute_scalar do not memoize: every force of the same encoded array re-runs its decode chain. Any consumer that performs repeated random access — execute_scalar in a row loop, or many small takes over the same column — silently multiplies decode work by the number of accesses.
The failure mode is easy to hit with the aggregate_fn::Accumulator API: grouped aggregation that feeds one Accumulator per group via one take per group over a still-encoded column forces the full decode chain once per group (Accumulator::accumulate → ArrayRef::execute → RLE::execute → rle_decompress → delta_decompress → untranspose). At high group cardinality that is near-quadratic, and profiles show the decode kernels dominating while the actual aggregation is a rounding error.
The blunt workaround — canonicalize the column once before the loop — works but has two problems: it relies on every call site remembering the convention ("never force in a loop" is not an API property), and it over-decodes encodings that are already better than canonical under random access — constants trivially, dictionaries via O(1) code indirection with values canonicalized once — while the truly pathological cases are block-positional codecs (bitpacking, delta, transposed fastlanes) and lazy compute chains.
Proposed solution
An encoding-owned random-access handle, roughly:
pub struct ProbeHints {
/// Expected probes relative to array length (density → policy).
pub density: ProbeDensity, // e.g. Sparse | Dense | Exhaustive
}
pub trait Probe {
fn scalar_at(&mut self, row: usize) -> VortexResult<Scalar>;
// plus typed accessors where cheap, e.g. fn u64_at(&mut self, row) -> ...
}
impl ArrayRef {
pub fn probe(&self, hints: ProbeHints, ctx: &mut ExecutionCtx) -> VortexResult<Box<dyn Probe>>;
}Each encoding chooses its policy from the hint:
- Direct probing where random access is already O(1): canonical primitives/varbinview, constant, dictionary (canonicalize values once, index by code).
- Canonicalize-and-cache once for block codecs under dense probing — the decode happens exactly once regardless of how many probes follow.
- Per-block cached probing for sparse probing over large arrays — decode only the blocks touched, cache them.
This makes the force-in-a-loop anti-pattern unwritable: the loop-friendly API is the correct one by construction, and execute_scalar becomes the degenerate single-probe case. Prior art: Velox's DecodedVector and DuckDB's UnifiedVectorFormat are exactly this shape (decode-once wrappers preserving dictionary indirection); the density hint generalizes them with a caching policy.
Additional context
- A static complement for consumers that know their access pattern at plan time (aggregation inputs, join keys, sort keys are always consumed densely): a
Matcher for "cheap random access" — execute_until::<RandomAccessible> stopping at canonical | constant | dict-over-canonical, forcing block codecs and compute chains — lets them force once without probe machinery. The Probe API covers the dynamic/unknown-density cases.
- Cached canonicalization is invisible memory; the probe's cache should be queryable/reservable so consumers with memory accounting can charge it to someone.
- Alternative considered: memoize canonicalization on the array itself (
OnceLock<Canonical> per lazy node). Simpler, but it spends memory invisibly on every consumer including single-pass ones, and loses the dictionary-preserving fast path; the probe handle scopes the cache to the consumer that needs it.
Problem or motivation
Arrays are lazy and
execute/execute_scalardo not memoize: every force of the same encoded array re-runs its decode chain. Any consumer that performs repeated random access —execute_scalarin a row loop, or many smalltakes over the same column — silently multiplies decode work by the number of accesses.The failure mode is easy to hit with the
aggregate_fn::AccumulatorAPI: grouped aggregation that feeds oneAccumulatorper group via onetakeper group over a still-encoded column forces the full decode chain once per group (Accumulator::accumulate → ArrayRef::execute → RLE::execute → rle_decompress → delta_decompress → untranspose). At high group cardinality that is near-quadratic, and profiles show the decode kernels dominating while the actual aggregation is a rounding error.The blunt workaround — canonicalize the column once before the loop — works but has two problems: it relies on every call site remembering the convention ("never force in a loop" is not an API property), and it over-decodes encodings that are already better than canonical under random access — constants trivially, dictionaries via O(1) code indirection with values canonicalized once — while the truly pathological cases are block-positional codecs (bitpacking, delta, transposed fastlanes) and lazy compute chains.
Proposed solution
An encoding-owned random-access handle, roughly:
Each encoding chooses its policy from the hint:
This makes the force-in-a-loop anti-pattern unwritable: the loop-friendly API is the correct one by construction, and
execute_scalarbecomes the degenerate single-probe case. Prior art: Velox'sDecodedVectorand DuckDB'sUnifiedVectorFormatare exactly this shape (decode-once wrappers preserving dictionary indirection); the density hint generalizes them with a caching policy.Additional context
Matcherfor "cheap random access" —execute_until::<RandomAccessible>stopping at canonical | constant | dict-over-canonical, forcing block codecs and compute chains — lets them force once without probe machinery. The Probe API covers the dynamic/unknown-density cases.OnceLock<Canonical>per lazy node). Simpler, but it spends memory invisibly on every consumer including single-pass ones, and loses the dictionary-preserving fast path; the probe handle scopes the cache to the consumer that needs it.