vortex_array/executor.rs
1// SPDX-License-Identifier: Apache-2.0
2// SPDX-FileCopyrightText: Copyright the Vortex contributors
3
4//! Iterative array execution.
5//!
6//! The single-step [`Executable`] implementation for [`ArrayRef`] optimizes the array with the
7//! context's session, then tries `execute_parent`, then `execute` once. The matcher-driven
8//! [`ArrayRef::execute_until`] loop interprets [`ExecutionStep::ExecuteSlot`],
9//! [`ExecutionStep::AppendChild`], and [`ExecutionStep::Done`] using an explicit stack plus an
10//! optional builder, so encodings can advance without recursive descent.
11//!
12//! See <https://docs.vortex.dev/developer-guide/internals/execution> for the full execution
13//! narrative, diagrams, and walkthroughs.
14
15use std::any::TypeId;
16use std::env::VarError;
17use std::fmt;
18use std::fmt::Display;
19use std::sync::Arc;
20use std::sync::LazyLock;
21use std::sync::OnceLock;
22#[cfg(debug_assertions)]
23use std::sync::atomic::AtomicUsize;
24#[cfg(debug_assertions)]
25use std::sync::atomic::Ordering;
26
27use vortex_error::VortexExpect;
28use vortex_error::VortexResult;
29use vortex_error::vortex_bail;
30use vortex_error::vortex_ensure_eq;
31use vortex_error::vortex_panic;
32use vortex_session::VortexSession;
33
34use crate::AnyCanonical;
35use crate::ArrayRef;
36use crate::IntoArray;
37use crate::aggregate_fn::session::AggregateFnSessionExt;
38use crate::aggregate_fn::session::AggregateKernels;
39use crate::array::ArrayId;
40use crate::builders::ArrayBuilder;
41use crate::builders::builder_with_capacity_in;
42use crate::dtype::DType;
43use crate::matcher::Matcher;
44use crate::memory::BufferAllocatorRef;
45use crate::memory::MemorySessionExt;
46use crate::optimizer::ArrayOptimizer;
47use crate::optimizer::Optimizer;
48use crate::optimizer::kernels::ArrayKernels;
49use crate::optimizer::kernels::ArrayKernelsExt;
50use crate::optimizer::kernels::ParentExecutionKernels;
51use crate::optimizer::kernels::execute_parent_key;
52use crate::optimizer::kernels::execute_parent_marker_key;
53use crate::stats::ArrayStats;
54use crate::trace_op;
55
56/// Returns the maximum number of iterations to attempt when executing an array before giving up and returning
57/// an error, can be by the `VORTEX_MAX_ITERATIONS` env variables, otherwise defaults to 2^22.
58pub(crate) fn max_iterations() -> usize {
59 static MAX_ITERATIONS: LazyLock<usize> = LazyLock::new(|| {
60 match std::env::var("VORTEX_MAX_ITERATIONS") {
61 Ok(val) => val.parse::<usize>().unwrap_or_else(|e| {
62 vortex_panic!("VORTEX_MAX_ITERATIONS is not a valid usize: {e}")
63 }),
64 Err(VarError::NotPresent) => 2 << 21, // 2 ^ 22
65 Err(VarError::NotUnicode(_)) => {
66 vortex_panic!("VORTEX_MAX_ITERATIONS is not a valid unicode string")
67 }
68 }
69 });
70 *MAX_ITERATIONS
71}
72
73/// Marker trait for types that an [`ArrayRef`] can be executed into.
74///
75/// Implementors must provide an implementation of `execute` that takes
76/// an [`ArrayRef`] and an [`ExecutionCtx`], and produces an instance of the
77/// implementor type.
78///
79/// Users should use the `Array::execute` or `Array::execute_as` methods
80pub trait Executable: Sized {
81 fn execute(array: ArrayRef, ctx: &mut ExecutionCtx) -> VortexResult<Self>;
82}
83
84#[expect(clippy::same_name_method)]
85impl ArrayRef {
86 /// Execute this array to produce an instance of `E`.
87 ///
88 /// See the [`Executable`] implementation for details on how this execution is performed.
89 pub fn execute<E: Executable>(self, ctx: &mut ExecutionCtx) -> VortexResult<E> {
90 E::execute(self, ctx)
91 }
92
93 /// Execute this array, labeling the execution step with a name for tracing.
94 pub fn execute_as<E: Executable>(
95 self,
96 _name: &'static str,
97 ctx: &mut ExecutionCtx,
98 ) -> VortexResult<E> {
99 E::execute(self, ctx)
100 }
101
102 /// Iteratively execute this array until the [`Matcher`] matches, using an explicit work
103 /// stack plus an optional builder for `AppendChild`.
104 ///
105 /// Note: the returned array may not match `M`. If execution converges to a canonical form
106 /// that does not match `M`, the canonical array is returned since no further execution
107 /// progress is possible.
108 ///
109 /// For safety, this errors once execution reaches a configurable maximum number of
110 /// iterations (default `2^22`, override with `VORTEX_MAX_ITERATIONS`).
111 ///
112 /// # Loop state
113 ///
114 /// - `current_array: ArrayRef` -- the array currently in focus.
115 /// - `current_builder: Option<Box<dyn ArrayBuilder>>` -- active only for builder-mode
116 /// execution. `AppendChild` appends detached children here. `Done` finishes the builder
117 /// and turns it back into the next `current_array`.
118 /// - `stack: Vec<StackFrame>` -- suspended parents from `ExecuteSlot`, including the
119 /// detached slot index, its [`DonePredicate`], and the parent builder that was active
120 /// before focus moved into the child.
121 ///
122 /// Example after `ExecuteSlot(1, pred)` has focused slot 1 of a parent:
123 ///
124 /// ```text
125 /// stack[top].parent_array:
126 /// RunEnd <-- suspended parent
127 /// +-- slot 0: ends
128 /// +-- slot 1: _ (detached)
129 ///
130 /// current_array:
131 /// DictEncoding <-- focused child
132 /// +-- slot 0: codes
133 /// +-- slot 1: dictionary
134 ///
135 /// current_builder:
136 /// None
137 /// ```
138 ///
139 /// Each loop iteration works like this:
140 ///
141 /// ```text
142 /// loop:
143 /// Step 1: done(current_array)?
144 /// - root activation -> return current_array
145 /// - ExecuteSlot frame -> pop, reattach child, resume parent
146 ///
147 /// Step 2: current_builder active?
148 /// - yes -> skip Step 2a / 2b
149 /// - no -> try parent kernels
150 ///
151 /// Step 2a: if stack.top exists:
152 /// parent = stack.top.parent_array
153 /// child = current_array
154 /// kernels[(parent.encoding_id(), child.encoding_id())]
155 /// .try_execute_parent(child, parent, stack.top.slot_idx)
156 ///
157 /// Step 2b: if current_array's encoding has any registered kernel,
158 /// for child in current_array.children():
159 /// parent = current_array
160 /// kernels[(parent.encoding_id(), child.encoding_id())]
161 /// .try_execute_parent(child, parent, child.slot_idx)
162 ///
163 /// Step 3: match current_array.execute()
164 /// ExecuteSlot(i, pred) -> push parent on stack, focus child `i`
165 /// AppendChild(i) -> detach child `i`, append it into current_builder,
166 /// keep parent as current_array
167 /// Done -> finish current_builder if present, else use returned array
168 /// ```
169 ///
170 /// Step 2b first checks whether `current_array`'s encoding owns any execute-parent kernel at
171 /// all (a marker entry in the same kernel snapshot), so a pure compression encoding does not
172 /// probe the registry once for each of its children. Step 2a probes only one pair, so a
173 /// marker check there cannot remove a probe.
174 ///
175 /// Step 2a and Step 2b are skipped while `current_builder` is active. `AppendChild`
176 /// partially consumes `current_array`: some slots already live in the builder, so a
177 /// parent rewrite would observe inconsistent state and could discard accumulated builder
178 /// data.
179 #[allow(clippy::cognitive_complexity)]
180 pub fn execute_until<M: Matcher + 'static>(
181 self,
182 ctx: &mut ExecutionCtx,
183 ) -> VortexResult<ArrayRef> {
184 // One optimizer serves the whole execution, so a shared node that one step rewrote is
185 // reused when a later step reaches it. The session is cloned so the optimizer does not
186 // borrow `ctx`.
187 let session = ctx.session().clone();
188 let session_kernels = session.kernels();
189 let session_kernels: &ArrayKernels = &session_kernels;
190 let mut optimizer = Optimizer::new(Some(session_kernels));
191
192 // Each node is optimized when execution reaches it: the root here, with the nodes below it
193 // that were never optimized, and a child when execution focuses it.
194 let mut current_array = optimizer.optimize_array(&self)?;
195 let mut current_builder: Option<Box<dyn ArrayBuilder>> = None;
196 let mut stack: Vec<StackFrame> = Vec::new();
197 let execute_parent_kernels = Arc::clone(&ctx.execute_parent_kernels);
198 let kernels = execute_parent_kernels.as_ref();
199 let max_iterations = max_iterations();
200
201 trace_op!(record_execute_until_start::<M>(¤t_array));
202
203 for _iteration in 0..max_iterations {
204 trace_op!(record_execute_until_iteration(
205 _iteration,
206 ¤t_array,
207 stack
208 .last()
209 .map(|frame| (&frame.parent_array, frame.slot_idx)),
210 current_builder.is_some(),
211 ));
212
213 let (done_target, done_canonical) = match stack.last() {
214 None => root_done_check::<M>(¤t_array),
215 Some(frame) => (
216 (frame.done)(¤t_array),
217 AnyCanonical::matches(¤t_array),
218 ),
219 };
220 trace_op!(record_execute_until_done_check(done_target, done_canonical));
221
222 if done_target || done_canonical {
223 match stack.pop() {
224 None => {
225 debug_assert!(
226 current_builder.is_none(),
227 "root activation should not retain a builder"
228 );
229 // Kernels build their results with lazy constructors too, such as a
230 // filtered validity, so optimize whatever execution produced. This is
231 // free when the array is already marked as optimized.
232 current_array = optimizer.optimize_array(¤t_array)?;
233 trace_op!(record_execute_until_return(¤t_array));
234 return Ok(current_array);
235 }
236 Some(frame) => {
237 let _slot_idx = frame.slot_idx;
238 (current_array, current_builder) = pop_frame(frame, current_array)?;
239 trace_op!(record_execute_until_pop_frame(_slot_idx, ¤t_array));
240 continue;
241 }
242 }
243 }
244
245 // Step 2a: execute_parent against the suspended parent from ExecuteSlot.
246 //
247 // When executing a child for ExecuteSlot, try execute_parent against
248 // the suspended parent on the stack. This lets kernels like RunEnd's
249 // FilterKernel fire before the child is forced to canonical.
250 //
251 // Skip when a builder is active: the current array has been partially
252 // consumed by AppendChild (some slots are already in the builder), so
253 // a parent rewrite would see inconsistent state and the builder data
254 // would be lost when we restore frame.parent_builder.
255 if current_builder.is_none()
256 && let Some(frame) = stack.last()
257 && let Some(result) = {
258 execute_parent_for_child(
259 "stack_execute_parent",
260 &frame.parent_array,
261 ¤t_array,
262 frame.slot_idx,
263 kernels,
264 ctx,
265 )?
266 }
267 {
268 let frame = stack.pop().vortex_expect("just peeked");
269 let optimized = optimizer.optimize_array(&result)?;
270 trace_op!(record_execute_optimized(&result, &optimized));
271 current_array = optimized;
272 current_builder = frame.parent_builder;
273 continue;
274 }
275 if current_builder.is_none() && stack.last().is_some() {
276 trace_op!(record_execute_parent_none(
277 "stack_execute_parent",
278 ¤t_array,
279 ));
280 }
281
282 // Step 2b: execute_parent against current_array's own children.
283 if current_builder.is_none()
284 && has_execute_parent_kernels(kernels, ¤t_array)
285 && let Some(rewritten) = try_execute_parent(¤t_array, kernels, ctx)?
286 {
287 let optimized = optimizer.optimize_array(&rewritten)?;
288 trace_op!(record_execute_optimized(&rewritten, &optimized));
289 current_array = optimized;
290 continue;
291 }
292 if current_builder.is_none() {
293 trace_op!(record_execute_parent_none(
294 "child_execute_parent",
295 ¤t_array,
296 ));
297 }
298
299 let expected_len = current_array.len();
300 // Only the debug postcondition compares dtypes, so skip the clone otherwise.
301 let expected_dtype = cfg!(debug_assertions).then(|| current_array.dtype().clone());
302 // Share the existing stats handle instead of cloning the set; uninitialised stats stay lazy.
303 let stats = current_array.statistics().share_existing();
304 let encoding_id = current_array.encoding_id();
305 trace_op!(record_execute_encoding(¤t_array));
306 let result = current_array.execute_encoding_unchecked(ctx)?;
307 let (array, step) = result.into_parts();
308 match step {
309 ExecutionStep::ExecuteSlot(i, done) => {
310 let (parent, child) = unsafe { array.take_slot_unchecked(i) }?;
311
312 trace_op!(record_execute_slot(i, &parent, &child));
313 stack.push(StackFrame {
314 parent_array: parent,
315 parent_builder: current_builder.take(),
316 slot_idx: i,
317 done,
318 original_dtype: child.dtype().clone(),
319 original_len: child.len(),
320 });
321 current_array = optimizer.optimize_array(&child)?;
322 current_builder = None;
323 }
324 ExecutionStep::AppendChild(i) => {
325 if current_builder.is_none() {
326 trace_op!(record_builder_start(&array));
327 current_builder = Some(builder_with_capacity_in(
328 array.dtype(),
329 array.len(),
330 ctx.allocator(),
331 ));
332 }
333 let (parent, child) = unsafe { array.take_slot_unchecked(i) }?;
334
335 trace_op!(record_append_child(i, &parent, &child));
336 trace_op!(record_builder_append(&child));
337
338 // TODO(joe)[7674]: replace with a builder kernel registry so we don't
339 // need to go through the VTable append_to_builder indirection.
340 child.append_to_builder(
341 current_builder
342 .as_deref_mut()
343 .vortex_expect("builder must exist"),
344 ctx,
345 )?;
346 current_array = parent;
347 }
348 ExecutionStep::Done => {
349 let had_builder = current_builder.is_some();
350 trace_op!(record_execute_done(&array));
351 (current_array, current_builder) = finalize_done(
352 array,
353 current_builder,
354 expected_len,
355 expected_dtype,
356 stats,
357 encoding_id,
358 )?;
359 if had_builder {
360 trace_op!(record_builder_finish(¤t_array));
361 }
362 // Kernels build their results with lazy constructors, such as a cast that only
363 // changes nullability. Reduce them before execute-parent kernels see them.
364 current_array = optimizer.optimize_array(¤t_array)?;
365 }
366 }
367 }
368
369 vortex_bail!(
370 "Exceeded maximum execution iterations ({}) while executing array",
371 max_iterations,
372 )
373 }
374}
375
376struct StackFrame {
377 parent_array: ArrayRef,
378 parent_builder: Option<Box<dyn ArrayBuilder>>,
379 slot_idx: usize,
380 done: DonePredicate,
381 original_dtype: DType,
382 original_len: usize,
383}
384
385/// Execution context for batch CPU compute.
386#[derive(Debug, Clone)]
387pub struct ExecutionCtx {
388 session: VortexSession,
389 // OnceLock avoids cloning the session allocator when a context does not allocate.
390 allocator: OnceLock<BufferAllocatorRef>,
391 execute_parent_kernels: Arc<ParentExecutionKernels>,
392 // OnceLock avoids snapshotting the aggregate kernels when a context does not aggregate.
393 aggregate_kernels: OnceLock<AggregateKernels>,
394 #[cfg(debug_assertions)]
395 id: usize,
396 #[cfg(debug_assertions)]
397 ops: Vec<String>,
398}
399
400impl ExecutionCtx {
401 /// Create a new execution context with the given session.
402 ///
403 /// This captures a snapshot of the session's execute-parent kernel registry. Kernels
404 /// registered after this context is created are not visible to it; create a new
405 /// [`ExecutionCtx`] after registration to use newly registered kernels.
406 pub fn new(session: VortexSession) -> Self {
407 let execute_parent_kernels = session.kernels().execute_parent_snapshot();
408 Self {
409 session,
410 allocator: OnceLock::new(),
411 execute_parent_kernels,
412 aggregate_kernels: OnceLock::new(),
413 #[cfg(debug_assertions)]
414 id: {
415 static EXEC_CTX_ID: AtomicUsize = AtomicUsize::new(0);
416 EXEC_CTX_ID.fetch_add(1, Ordering::Relaxed)
417 },
418 #[cfg(debug_assertions)]
419 ops: Vec::new(),
420 }
421 }
422
423 /// Get the session associated with this execution context.
424 pub fn session(&self) -> &VortexSession {
425 &self.session
426 }
427
428 /// Get the allocator for this execution context.
429 pub fn allocator(&self) -> &BufferAllocatorRef {
430 self.allocator.get_or_init(|| self.session.allocator())
431 }
432
433 /// Get the aggregate kernels for this execution context.
434 ///
435 /// The session's aggregate kernel registries are snapshotted on first use. Kernels registered
436 /// after that are not visible to this context.
437 pub(crate) fn aggregate_kernels(&self) -> &AggregateKernels {
438 self.aggregate_kernels
439 .get_or_init(|| self.session.aggregate_fns().kernels_snapshot())
440 }
441
442 /// Set the allocator for this execution context.
443 pub fn with_allocator(mut self, allocator: BufferAllocatorRef) -> Self {
444 self.allocator = OnceLock::from(allocator);
445 self
446 }
447
448 /// Log an execution step at the current depth.
449 ///
450 /// Steps are accumulated and dumped as a single trace on Drop at DEBUG level.
451 /// Individual steps are also logged at TRACE level for real-time following.
452 ///
453 /// Use the [`format_args!`] macro to create the `msg` argument.
454 pub fn log(&mut self, msg: fmt::Arguments<'_>) {
455 #[cfg(debug_assertions)]
456 if tracing::enabled!(tracing::Level::TRACE) {
457 let formatted = format!(" - {msg}");
458 tracing::trace!("exec[{}]: {formatted}", self.id);
459 self.ops.push(formatted);
460 }
461 let _ = msg;
462 }
463}
464
465impl Display for ExecutionCtx {
466 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
467 #[cfg(debug_assertions)]
468 return write!(f, "exec[{}]", self.id);
469 #[cfg(not(debug_assertions))]
470 write!(f, "exec")
471 }
472}
473
474#[cfg(debug_assertions)]
475impl Drop for ExecutionCtx {
476 fn drop(&mut self) {
477 if !self.ops.is_empty() && tracing::enabled!(tracing::Level::DEBUG) {
478 // Unlike itertools `.format()` (panics in 0.14 on second format)
479 struct FmtOps<'a>(&'a [String]);
480 impl Display for FmtOps<'_> {
481 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
482 for (i, op) in self.0.iter().enumerate() {
483 if i > 0 {
484 f.write_str("\n")?;
485 }
486 f.write_str(op)?;
487 }
488 Ok(())
489 }
490 }
491 tracing::debug!("exec[{}] trace:\n{}", self.id, FmtOps(&self.ops));
492 }
493 }
494}
495
496/// Single-step execution: takes one step toward canonical form.
497///
498/// Steps through optimize, execute_parent, then execute. For `ExecuteSlot`,
499/// only a single child execution step is performed — the child is executed once and put back,
500/// making this a lightweight, bounded operation.
501///
502/// **However**, if `execute_step` returns [`ExecutionStep::AppendChild`], this implementation
503/// drives the *entire* array to completion via [`execute_into_builder`] in a single call.
504/// This can do substantially more work than a normal step because it creates a builder and
505/// fully decodes the array into that builder before returning. Callers should be aware that a
506/// single `.execute::<ArrayRef>(ctx)` call may perform O(n_children * decode_cost) work when
507/// `AppendChild` is returned.
508impl Executable for ArrayRef {
509 fn execute(array: ArrayRef, ctx: &mut ExecutionCtx) -> VortexResult<Self> {
510 trace_op!(record_single_step_start(&array));
511
512 if array.is::<AnyCanonical>() {
513 trace_op!(record_single_step_applied("canonical", &array, &array));
514 return Ok(array);
515 }
516 trace_op!(record_single_step_phase_none("canonical", &array));
517
518 let optimized = array.optimize_ctx(ctx.session())?;
519 if !ArrayRef::ptr_eq(&optimized, &array) {
520 optimized.statistics().inherit_from(array.statistics());
521 trace_op!(record_single_step_applied("optimize", &array, &optimized));
522 return Ok(optimized);
523 }
524 trace_op!(record_single_step_phase_none("optimize", &array));
525
526 let execute_parent_kernels = Arc::clone(&ctx.execute_parent_kernels);
527 let kernels = execute_parent_kernels.as_ref();
528 let has_parent_kernels = has_execute_parent_kernels(kernels, &array);
529
530 for (slot_idx, slot) in array.slots().iter().enumerate() {
531 let Some(child) = slot else { continue };
532 if has_parent_kernels
533 && let Some(executed_parent) = execute_parent_for_child(
534 "single_step_execute_parent",
535 &array,
536 child,
537 slot_idx,
538 kernels,
539 ctx,
540 )?
541 {
542 executed_parent
543 .statistics()
544 .inherit_from(array.statistics());
545 trace_op!(record_single_step_applied(
546 "execute_parent",
547 &array,
548 &executed_parent,
549 ));
550 return Ok(executed_parent);
551 }
552 }
553 trace_op!(record_single_step_phase_none("execute_parent", &array));
554 trace_op!(record_execute_encoding(&array));
555
556 let result = array.execute_encoding(ctx)?;
557 let (array, step) = result.into_parts();
558 match step {
559 ExecutionStep::Done => {
560 trace_op!(record_execute_done(&array));
561 Ok(array)
562 }
563 ExecutionStep::ExecuteSlot(i, _) => {
564 let child = array.slots()[i].clone().vortex_expect("valid slot index");
565 let executed_child = child.execute::<ArrayRef>(ctx)?;
566 // SAFETY: execution of a child slot produces a logically equivalent array in a
567 // different physical representation, preserving parent values and statistics.
568 unsafe { array.with_slot(i, executed_child) }
569 }
570 ExecutionStep::AppendChild(_) => {
571 // Single-step: build the entire parent via the builder path.
572 trace_op!(record_builder_start(&array));
573 let builder = builder_with_capacity_in(array.dtype(), array.len(), ctx.allocator());
574 let mut builder = execute_into_builder(array, builder, ctx)?;
575 let output = builder.finish();
576 trace_op!(record_builder_finish(&output));
577 Ok(output)
578 }
579 }
580 }
581}
582
583/// Execute `array` into the given `builder`.
584///
585/// This uses the encoding's [`crate::array::VTable::append_to_builder`] implementation. Most
586/// encodings use the default path of `execute::<Canonical>` followed by re-dispatching
587/// `append_to_builder` on the canonical array, while encodings like `Chunked` can override that to
588/// append child-by-child without materializing the entire parent.
589///
590/// The builder must have a [`DType`] that is a nullability-superset of `array.dtype()`.
591pub fn execute_into_builder(
592 array: ArrayRef,
593 mut builder: Box<dyn ArrayBuilder>,
594 ctx: &mut ExecutionCtx,
595) -> VortexResult<Box<dyn ArrayBuilder>> {
596 array.append_to_builder(builder.as_mut(), ctx)?;
597 Ok(builder)
598}
599
600/// Returns `(matches M, is canonical)`, scanning once when `M` is [`AnyCanonical`].
601#[inline]
602fn root_done_check<M: Matcher + 'static>(array: &ArrayRef) -> (bool, bool) {
603 if TypeId::of::<M>() == TypeId::of::<AnyCanonical>() {
604 let canonical = AnyCanonical::matches(array);
605 return (canonical, canonical);
606 }
607 (M::matches(array), AnyCanonical::matches(array))
608}
609
610/// Pop a stack frame, restoring the parent with the finished child in its slot.
611fn pop_frame(
612 frame: StackFrame,
613 child: ArrayRef,
614) -> VortexResult<(ArrayRef, Option<Box<dyn ArrayBuilder>>)> {
615 debug_assert_eq!(
616 child.dtype(),
617 &frame.original_dtype,
618 "child dtype changed during execution"
619 );
620 debug_assert_eq!(
621 child.len(),
622 frame.original_len,
623 "child len changed during execution"
624 );
625 let parent_array = unsafe { frame.parent_array.put_slot_unchecked(frame.slot_idx, child) }?;
626 Ok((parent_array, frame.parent_builder))
627}
628
629fn finalize_done(
630 result: ArrayRef,
631 mut builder: Option<Box<dyn ArrayBuilder>>,
632 expected_len: usize,
633 expected_dtype: Option<DType>,
634 stats: ArrayStats,
635 encoding_id: ArrayId,
636) -> VortexResult<(ArrayRef, Option<Box<dyn ArrayBuilder>>)> {
637 let output = if let Some(mut builder) = builder.take() {
638 builder.finish()
639 } else {
640 result
641 };
642
643 if cfg!(debug_assertions) {
644 vortex_ensure_eq!(
645 output.len(),
646 expected_len,
647 "Result length mismatch for {:?}",
648 encoding_id
649 );
650 if let Some(expected_dtype) = expected_dtype {
651 vortex_ensure_eq!(
652 output.dtype(),
653 &expected_dtype,
654 "Executed canonical dtype mismatch for {:?}",
655 encoding_id
656 );
657 }
658 }
659
660 output.statistics().transfer_from(&stats);
661 Ok((output, None))
662}
663
664fn execute_parent_for_child(
665 phase: &'static str,
666 parent: &ArrayRef,
667 child: &ArrayRef,
668 slot_idx: usize,
669 kernels: &ParentExecutionKernels,
670 ctx: &mut ExecutionCtx,
671) -> VortexResult<Option<ArrayRef>> {
672 let key = execute_parent_key(parent.encoding_id(), child.encoding_id());
673 if let Some(plugins) = kernels.get(&key) {
674 #[allow(clippy::unused_enumerate_index)]
675 for (_plugin_idx, plugin) in plugins.as_ref().iter().enumerate() {
676 if let Some(result) = plugin.execute_parent(child, parent, slot_idx, ctx)? {
677 if cfg!(debug_assertions) {
678 vortex_ensure_eq!(
679 result.len(),
680 parent.len(),
681 "Executed parent canonical length mismatch"
682 );
683 vortex_ensure_eq!(
684 result.dtype(),
685 parent.dtype(),
686 "Executed parent canonical dtype mismatch"
687 );
688 }
689 log_parent_rewrite(ctx, phase, slot_idx, parent, child, &result);
690 trace_op!(record_session_execute_parent_applied(
691 phase,
692 parent,
693 child,
694 slot_idx,
695 _plugin_idx,
696 &result,
697 ));
698 return Ok(Some(result));
699 }
700 trace_op!(record_session_execute_parent_declined(
701 phase,
702 parent,
703 child,
704 slot_idx,
705 _plugin_idx,
706 ));
707 }
708 }
709
710 Ok(None)
711}
712
713/// Log a parent rewrite to the execution log.
714fn log_parent_rewrite(
715 ctx: &mut ExecutionCtx,
716 phase: &'static str,
717 slot_idx: usize,
718 parent: &ArrayRef,
719 child: &ArrayRef,
720 output: &ArrayRef,
721) {
722 ctx.log(format_args!(
723 "{phase}: slot[{slot_idx}]({}) rewrote {parent} -> {output}",
724 child.encoding_id(),
725 ));
726}
727
728/// Whether any execute-parent kernel is registered with `parent`'s encoding as the parent.
729#[inline]
730fn has_execute_parent_kernels(kernels: &ParentExecutionKernels, parent: &ArrayRef) -> bool {
731 kernels.contains_key(&execute_parent_marker_key(parent.encoding_id()))
732}
733
734/// Try execute_parent on each occupied slot of the array.
735fn try_execute_parent(
736 array: &ArrayRef,
737 kernels: &ParentExecutionKernels,
738 ctx: &mut ExecutionCtx,
739) -> VortexResult<Option<ArrayRef>> {
740 for (slot_idx, slot) in array.slots().iter().enumerate() {
741 let Some(child) = slot else { continue };
742 if let Some(executed_parent) =
743 execute_parent_for_child("child_execute_parent", array, child, slot_idx, kernels, ctx)?
744 {
745 executed_parent
746 .statistics()
747 .inherit_from(array.statistics());
748 return Ok(Some(executed_parent));
749 }
750 }
751 Ok(None)
752}
753
754/// A predicate that determines when an array has reached a desired form during execution.
755pub type DonePredicate = fn(&ArrayRef) -> bool;
756
757/// Scheduler step indicator returned alongside an array in [`ExecutionResult`].
758///
759/// Instead of recursively executing children, encodings return an `ExecutionStep` that tells the
760/// scheduler what to do next. This enables the scheduler to manage execution iteratively using
761/// an explicit work stack plus an optional builder.
762///
763/// # Semantics
764///
765/// Each variant describes a different execution strategy with distinct cost profiles:
766///
767/// - [`Done`](ExecutionStep::Done): The current activation has finished its work. If no builder
768/// is active, the returned array is the result. If a builder is active, the scheduler ignores
769/// the placeholder array and finishes the builder instead. The scheduler may continue
770/// executing if the target form (e.g. canonical) has not yet been reached.
771///
772/// - [`ExecuteSlot`](ExecutionStep::ExecuteSlot): The encoding needs one of its children
773/// decoded before it can make further progress. The scheduler detaches that child, pushes
774/// the parent onto the explicit stack, executes the child until the [`DonePredicate`]
775/// matches, puts it back, and re-enters the parent. This is a cooperative yield: the
776/// encoding does a bounded amount of work per step while the loop tracks the parent-child
777/// relationship explicitly.
778///
779/// - [`AppendChild`](ExecutionStep::AppendChild): The encoding needs one child executed to
780/// canonical form and then appended into a builder owned by the current activation. The
781/// scheduler detaches that child, lazily creates `current_builder` if needed, appends the
782/// child into it, and keeps the parent as `current_array` for the next iteration. While the
783/// builder is active, parent-kernel rewrites are skipped because the parent is partially
784/// consumed. **Important:** in the single-step executor ([`Executable`] for [`ArrayRef`]),
785/// returning `AppendChild` still causes the executor to drive the *entire* array to
786/// completion via [`execute_into_builder`] in one call — this can do significantly more
787/// work than a single `ExecuteSlot` step.
788pub enum ExecutionStep {
789 /// Request that the scheduler execute the slot at the given index, using the provided
790 /// [`DonePredicate`] to determine when the slot is "done", then replace the slot in this
791 /// array and re-enter execution.
792 ///
793 /// Use [`ExecutionResult::execute_slot`] instead of constructing this variant directly.
794 ExecuteSlot(usize, DonePredicate),
795
796 /// Detach the slot at the given index, append that child into the current activation's
797 /// canonical builder, and keep the returned parent as `current_array`.
798 ///
799 /// `Done` finalizes that builder and turns it into the result of the activation.
800 ///
801 /// **Note:** In the single-step executor ([`Executable`] for [`ArrayRef`]), this variant
802 /// drives the entire parent to completion in one call via [`execute_into_builder`], which
803 /// may perform substantially more work than a single `ExecuteSlot` step.
804 AppendChild(usize),
805
806 /// Execution is complete. If no builder is active, the array in the accompanying
807 /// [`ExecutionResult`] is the result. Otherwise, the scheduler finalizes the active
808 /// builder and uses that finished array instead.
809 ///
810 /// The scheduler will continue executing if it has not yet reached the target form.
811 Done,
812}
813
814impl fmt::Debug for ExecutionStep {
815 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
816 match self {
817 ExecutionStep::ExecuteSlot(idx, _) => f.debug_tuple("ExecuteSlot").field(idx).finish(),
818 ExecutionStep::AppendChild(idx) => f.debug_tuple("AppendChild").field(idx).finish(),
819 ExecutionStep::Done => write!(f, "Done"),
820 }
821 }
822}
823
824/// The result of a single execution step on an array encoding.
825///
826/// Combines an [`ArrayRef`] with an [`ExecutionStep`] to tell the scheduler both what to do next
827/// and what array to work with.
828pub struct ExecutionResult {
829 array: ArrayRef,
830 step: ExecutionStep,
831}
832
833impl ExecutionResult {
834 /// Signal that execution is complete with the given result array.
835 pub fn done(result: impl IntoArray) -> Self {
836 Self {
837 array: result.into_array(),
838 step: ExecutionStep::Done,
839 }
840 }
841
842 /// Request execution of slot at `slot_idx` until it matches the given [`Matcher`].
843 ///
844 /// The provided array is the (possibly modified) parent that still needs its slot executed.
845 pub fn execute_slot<M: Matcher>(array: impl IntoArray, slot_idx: usize) -> Self {
846 let array = array.into_array();
847 Self {
848 array,
849 step: ExecutionStep::ExecuteSlot(slot_idx, M::matches),
850 }
851 }
852
853 /// Like [`execute_slot`](Self::execute_slot), but with a [`DonePredicate`] chosen at runtime.
854 pub(crate) fn execute_slot_until(
855 array: ArrayRef,
856 slot_idx: usize,
857 done: DonePredicate,
858 ) -> Self {
859 Self {
860 array,
861 step: ExecutionStep::ExecuteSlot(slot_idx, done),
862 }
863 }
864
865 /// Request that the child slot at `slot_idx` be detached, appended into the current
866 /// activation's canonical builder, and leave the returned parent as the next
867 /// `current_array`.
868 pub fn append_child(array: impl IntoArray, slot_idx: usize) -> Self {
869 let array = array.into_array();
870 Self {
871 array,
872 step: ExecutionStep::AppendChild(slot_idx),
873 }
874 }
875
876 /// Returns a reference to the array.
877 pub fn array(&self) -> &ArrayRef {
878 &self.array
879 }
880
881 /// Returns a reference to the step.
882 pub fn step(&self) -> &ExecutionStep {
883 &self.step
884 }
885
886 /// Decompose into parts.
887 pub fn into_parts(self) -> (ArrayRef, ExecutionStep) {
888 (self.array, self.step)
889 }
890}
891
892impl fmt::Debug for ExecutionResult {
893 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
894 f.debug_struct("ExecutionResult")
895 .field("array", &self.array)
896 .field("step", &self.step)
897 .finish()
898 }
899}
900
901/// Require that a child array matches `$M`. If the child already matches, returns the same
902/// array unchanged. Otherwise, early-returns an [`ExecutionResult`] requesting execution of
903/// child `$idx` until it matches `$M`.
904///
905/// ```ignore
906/// let array = require_child!(array, array.codes(), 0 => Primitive);
907/// let array = require_child!(array, array.values(), 1 => AnyCanonical);
908/// ```
909#[macro_export]
910macro_rules! require_child {
911 ($parent:expr, $child:expr, $idx:expr => $M:ty) => {{
912 if !$child.is::<$M>() {
913 return Ok($crate::ExecutionResult::execute_slot::<$M>(
914 $parent.clone(),
915 $idx,
916 ));
917 }
918 $parent
919 }};
920}
921
922/// The scalar function counterpart of [`require_child!`]: require that input `$idx` of `$args`
923/// matches `$M`. If it does not, early-returns a
924/// [`ScalarFnExecutionResult`](crate::scalar_fn::ScalarFnExecutionResult) asking the executor to
925/// execute that input until it matches, so the function is stepped again with the executed input.
926///
927/// ```ignore
928/// require_input!(args, 0 => AnyColumnar);
929/// ```
930#[macro_export]
931macro_rules! require_input {
932 ($args:expr, $idx:expr => $M:ty) => {
933 if !$args.input_matches($idx, <$M as $crate::matcher::Matcher>::matches)? {
934 return Ok($crate::scalar_fn::ScalarFnExecutionResult::execute_input::<
935 $M,
936 >($idx));
937 }
938 };
939}
940
941/// Like [`require_child!`], but for optional children. If the child is `None`, this is a no-op.
942/// If the child is `Some` but does not match `$M`, early-returns an [`ExecutionResult`] requesting
943/// execution of child `$idx`.
944///
945/// Unlike `require_child!`, this is a statement macro (no value produced) and does not clone
946/// `$parent` - it is moved into the early-return path.
947///
948/// ```ignore
949/// require_opt_child!(array, array.patches().map(|p| p.indices()), 1 => Primitive);
950/// ```
951#[macro_export]
952macro_rules! require_opt_child {
953 ($parent:expr, $child_opt:expr, $idx:expr => $M:ty) => {
954 if $child_opt.is_some_and(|child| !child.is::<$M>()) {
955 return Ok($crate::ExecutionResult::execute_slot::<$M>($parent, $idx));
956 }
957 };
958}
959
960/// Require that patch slots (indices, values, and optionally chunk_offsets) are `Primitive`.
961/// If no patches are present (slots are `None`), this is a no-op.
962///
963/// Like [`require_opt_child!`], `$parent` is moved (not cloned) into the early-return path.
964///
965/// ```ignore
966/// require_patches!(
967/// array,
968/// MySlots::PATCH_INDICES,
969/// MySlots::PATCH_VALUES,
970/// MySlots::PATCH_CHUNK_OFFSETS
971/// );
972/// ```
973#[macro_export]
974macro_rules! require_patches {
975 ($parent:expr, $indices_slot:expr, $values_slot:expr, $chunk_offsets_slot:expr) => {
976 $crate::require_opt_child!(
977 $parent,
978 $parent.slots()[$indices_slot].as_ref(),
979 $indices_slot => $crate::arrays::Primitive
980 );
981 $crate::require_opt_child!(
982 $parent,
983 $parent.slots()[$values_slot].as_ref(),
984 $values_slot => $crate::arrays::Primitive
985 );
986 $crate::require_opt_child!(
987 $parent,
988 $parent.slots()[$chunk_offsets_slot].as_ref(),
989 $chunk_offsets_slot => $crate::arrays::Primitive
990 );
991 };
992}
993
994/// Require that the validity slot is a [`Bool`](crate::arrays::Bool) array. If validity is not
995/// array-backed (e.g. `NonNullable` or `AllValid`), this is a no-op. If it is array-backed but
996/// not `Bool`, early-returns an [`ExecutionResult`] requesting execution of the validity slot.
997///
998/// Like [`require_opt_child!`], `$parent` is moved (not cloned) into the early-return path.
999///
1000/// ```ignore
1001/// require_validity!(array, MySlots::VALIDITY);
1002/// ```
1003#[macro_export]
1004macro_rules! require_validity {
1005 ($parent:expr, $idx:expr) => {
1006 $crate::require_opt_child!(
1007 $parent,
1008 $parent.slots()[$idx].as_ref(),
1009 $idx => $crate::arrays::Bool
1010 );
1011 };
1012}
1013
1014/// Extension trait for creating an execution context from a session.
1015pub trait VortexSessionExecute {
1016 /// Create a new execution context from this session.
1017 fn create_execution_ctx(&self) -> ExecutionCtx;
1018}
1019
1020impl VortexSessionExecute for VortexSession {
1021 fn create_execution_ctx(&self) -> ExecutionCtx {
1022 ExecutionCtx::new(self.clone())
1023 }
1024}
1025
1026#[cfg(test)]
1027mod tests {
1028 use static_assertions::assert_impl_all;
1029 use vortex_session::SessionExt;
1030 use vortex_session::VortexSession;
1031
1032 use super::*;
1033 use crate::VTable as _;
1034 use crate::VortexSessionExecute;
1035 use crate::arrays::Bool;
1036 use crate::arrays::BoolArray;
1037 use crate::arrays::Primitive;
1038 use crate::memory::BufferAllocatorRef;
1039 use crate::memory::MemorySession;
1040 use crate::memory::MemorySessionExt;
1041 use crate::optimizer::kernels::ExecuteParentFn;
1042 use crate::optimizer::kernels::KernelSession;
1043 use crate::optimizer::kernels::execute_parent_key;
1044
1045 assert_impl_all!(ExecutionCtx: Send, Sync);
1046
1047 fn noop_execute_parent(
1048 _child: &ArrayRef,
1049 _parent: &ArrayRef,
1050 _child_idx: usize,
1051 _ctx: &mut ExecutionCtx,
1052 ) -> VortexResult<Option<ArrayRef>> {
1053 Ok(None)
1054 }
1055
1056 #[test]
1057 fn execution_ctx_snapshots_execute_parent_kernels_at_creation() {
1058 let session = VortexSession::empty().with_some(KernelSession::empty());
1059 let key = execute_parent_key(Bool.id(), Primitive.id());
1060
1061 let before_registration = session.create_execution_ctx();
1062 assert!(
1063 !before_registration
1064 .execute_parent_kernels
1065 .contains_key(&key)
1066 );
1067
1068 let kernels = session.kernels();
1069 kernels.register_execute_parent(
1070 Bool.id(),
1071 Primitive.id(),
1072 &[noop_execute_parent as ExecuteParentFn],
1073 );
1074
1075 assert!(
1076 !before_registration
1077 .execute_parent_kernels
1078 .contains_key(&key)
1079 );
1080
1081 let after_registration = session.create_execution_ctx();
1082 assert!(after_registration.execute_parent_kernels.contains_key(&key));
1083 }
1084
1085 #[test]
1086 fn execution_ctx_snapshot_marks_parents_with_kernels() {
1087 let session = VortexSession::empty().with_some(KernelSession::empty());
1088 let bool_array = BoolArray::from_iter([true, false]).into_array();
1089 let primitive = vortex_buffer::buffer![1i32, 2].into_array();
1090
1091 let before = session.create_execution_ctx();
1092 assert!(!has_execute_parent_kernels(
1093 &before.execute_parent_kernels,
1094 &bool_array
1095 ));
1096
1097 session.kernels().register_execute_parent(
1098 Bool.id(),
1099 Primitive.id(),
1100 &[noop_execute_parent as ExecuteParentFn],
1101 );
1102
1103 let after = session.create_execution_ctx();
1104 assert!(has_execute_parent_kernels(
1105 &after.execute_parent_kernels,
1106 &bool_array
1107 ));
1108 assert!(!has_execute_parent_kernels(
1109 &after.execute_parent_kernels,
1110 &primitive
1111 ));
1112 }
1113
1114 #[test]
1115 fn execution_ctx_allocator_override() {
1116 let first = BufferAllocatorRef::new(vortex_buffer::StaticBufferAllocator);
1117 let second = BufferAllocatorRef::new(vortex_buffer::StaticBufferAllocator);
1118 let third = BufferAllocatorRef::new(vortex_buffer::StaticBufferAllocator);
1119 let session = VortexSession::empty()
1120 .with::<MemorySession>()
1121 .with_allocator(first.clone());
1122 let ctx = session.create_execution_ctx();
1123
1124 session
1125 .get_mut::<MemorySession>()
1126 .set_allocator(third.clone());
1127
1128 assert!(session.allocator().ptr_eq(&third));
1129 assert!(ctx.allocator().ptr_eq(&third));
1130
1131 let ctx = ctx.with_allocator(second.clone());
1132 session.get_mut::<MemorySession>().set_allocator(first);
1133
1134 assert!(ctx.allocator().ptr_eq(&second));
1135 }
1136}