Skip to content

Commit 3f55648

Browse files
authored
Try reduce_parent rules after execute_parent rewrites the current node (#11310)
This changes is meant to catch and apply interleavings of execute and parent rules that otherwise have no chance to interact. Practical example of this is `Between(Slice(RunEnd))` combination. RunEnd has optimisations for both Slice and Between, however, Slice is an execute rule (since it pushes the slice to the values and needs to do binary search on runs) and between is an reduce rule. After Slice runs and reduces to `Between(RunEnd)` we never apply the reduce parent rule that pushes `Between` to the values of RunEnd. With this change we try to apply rule after execute_parent is done. --------- Signed-off-by: Robert Kruszewski <[email protected]>
1 parent 959f234 commit 3f55648

3 files changed

Lines changed: 128 additions & 0 deletions

File tree

‎vortex-array/src/arrays/runend/trace_tests.rs‎

Lines changed: 53 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -22,6 +22,9 @@ use crate::arrays::runend::RunEnd;
2222
use crate::assert_arrays_eq;
2323
use crate::optimizer::ArrayOptimizer;
2424
use crate::scalar::Scalar;
25+
use crate::scalar_fn::fns::between::Between;
26+
use crate::scalar_fn::fns::between::BetweenOptions;
27+
use crate::scalar_fn::fns::between::StrictComparison;
2528
use crate::scalar_fn::fns::binary::Binary;
2629
use crate::scalar_fn::fns::operators::Operator;
2730
use crate::session::ArraySession;
@@ -84,6 +87,56 @@ fn trace_compare_on_runend() -> VortexResult<()> {
8487
Ok(())
8588
}
8689

90+
/// Executing a slice over a run-end array yields the run-end array, whose parent-reduce rule then
91+
/// pushes the suspended between into the run values instead of decoding every row.
92+
#[test]
93+
fn trace_between_on_sliced_runend() -> VortexResult<()> {
94+
let sliced = runend_array()?.slice(1..8)?;
95+
let between = Between::try_new(
96+
sliced,
97+
ConstantArray::new(2i32, 7).into_array(),
98+
ConstantArray::new(3i32, 7).into_array(),
99+
BetweenOptions {
100+
lower_strict: StrictComparison::NonStrict,
101+
upper_strict: StrictComparison::Strict,
102+
},
103+
)?
104+
.into_array();
105+
106+
let traced = trace_op(|| {
107+
between
108+
.execute::<Canonical>(&mut execution_ctx())
109+
.map(IntoArray::into_array)
110+
})?;
111+
112+
assert_arrays_eq!(
113+
traced.output,
114+
BoolArray::from_iter([false, false, true, true, false, false, false]),
115+
&mut execution_ctx()
116+
);
117+
insta::assert_snapshot!(traced.trace.to_string(), @"
118+
execute_until target=AnyCanonical root=vortex.between(bool, len=7)
119+
iter 0 current=vortex.between(bool, len=7) builder_active=false
120+
ExecuteSlot slot=0 parent=vortex.between(bool, len=7) child=vortex.slice(i32, len=7)
121+
iter 1 current=vortex.slice(i32, len=7) stack_parent=vortex.between(bool, len=7) slot=0 builder_active=false
122+
child_execute_parent session[0]:execute_parent_fn slot=0 parent=vortex.slice(i32, len=7) child=vortex.runend(i32, len=9) -> vortex.runend(i32, len=7)
123+
iter 2 current=vortex.runend(i32, len=7) stack_parent=vortex.between(bool, len=7) slot=0 builder_active=false
124+
reduce_parent session[0]:RunEndScalarFnRule slot=0 parent=vortex.between(bool, len=7) child=vortex.runend(i32, len=7) -> vortex.runend(bool, len=7)
125+
iter 3 current=vortex.runend(bool, len=7) builder_active=false
126+
ExecuteSlot slot=1 parent=vortex.runend(bool, len=7) child=vortex.between(bool, len=3)
127+
iter 4 current=vortex.between(bool, len=3) stack_parent=vortex.runend(bool, len=7) slot=1 builder_active=false
128+
child_execute_parent session[0]:execute_parent_fn slot=0 parent=vortex.between(bool, len=3) child=vortex.primitive(i32, len=3) -> vortex.bool(bool, len=3)
129+
iter 5 current=vortex.bool(bool, len=3) stack_parent=vortex.runend(bool, len=7) slot=1 builder_active=false
130+
pop_frame slot=1 output=vortex.runend(bool, len=7)
131+
iter 6 current=vortex.runend(bool, len=7) builder_active=false
132+
Done array=vortex.bool(bool, len=7)
133+
iter 7 current=vortex.bool(bool, len=7) builder_active=false
134+
return output=vortex.bool(bool, len=7)
135+
");
136+
137+
Ok(())
138+
}
139+
87140
#[test]
88141
fn trace_filter_on_runend() -> VortexResult<()> {
89142
let runend = runend_array()?;

‎vortex-array/src/executor.rs‎

Lines changed: 61 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -144,6 +144,11 @@ impl ArrayRef {
144144
/// - root activation -> return current_array
145145
/// - ExecuteSlot frame -> pop, reattach child, resume parent
146146
///
147+
/// Step 1b: if current_array was rewritten under stack.top and no builder is active:
148+
/// reattach it, try its parent-reduce rules against the parent
149+
/// - rewritten -> pop, the result replaces the parent
150+
/// - none -> detach it again
151+
///
147152
/// Step 2: current_builder active?
148153
/// - yes -> skip Step 2a / 2b
149154
/// - no -> try parent kernels
@@ -194,6 +199,9 @@ impl ArrayRef {
194199
let mut current_array = optimizer.optimize_array(&self)?;
195200
let mut current_builder: Option<Box<dyn ArrayBuilder>> = None;
196201
let mut stack: Vec<StackFrame> = Vec::new();
202+
// Whether `current_array` was rewritten since its parent was suspended, so its
203+
// parent-reduce rules have not yet seen it under that parent.
204+
let mut child_rewritten = false;
197205
let kernels = ctx_kernels.execute_parent.as_ref();
198206
let max_iterations = max_iterations();
199207

@@ -235,12 +243,61 @@ impl ArrayRef {
235243
Some(frame) => {
236244
let _slot_idx = frame.slot_idx;
237245
(current_array, current_builder) = pop_frame(frame, current_array)?;
246+
child_rewritten = false;
238247
trace_op!(record_execute_until_pop_frame(_slot_idx, &current_array));
239248
continue;
240249
}
241250
}
242251
}
243252

253+
// Step 1b: parent-reduce rules against the suspended parent.
254+
//
255+
// Once execution rewrites the child into another encoding, its parent-reduce rules
256+
// can match where they did not before, such as a slice that executed into a run-end
257+
// array. Skipped while a builder is active at either level, as in Step 2a.
258+
if child_rewritten
259+
&& current_builder.is_none()
260+
&& stack
261+
.last()
262+
.is_some_and(|frame| frame.parent_builder.is_none())
263+
{
264+
child_rewritten = false;
265+
let frame = stack.pop().vortex_expect("just peeked");
266+
let slot_idx = frame.slot_idx;
267+
// SAFETY: `current_array` is the executed slot, so it has the slot's dtype and len.
268+
let parent = unsafe {
269+
frame
270+
.parent_array
271+
.put_slot_unchecked(slot_idx, current_array)
272+
}?;
273+
if let Some(reduced) = optimizer.reduce_parent_of_slot(&parent, slot_idx)? {
274+
let child = parent.slots()[slot_idx]
275+
.as_ref()
276+
.vortex_expect("slot was just put back");
277+
log_parent_rewrite(
278+
ctx,
279+
"stack_reduce_parent",
280+
slot_idx,
281+
&parent,
282+
child,
283+
&reduced,
284+
);
285+
reduced.statistics().inherit_from(parent.statistics());
286+
current_array = optimizer.optimize_array(&reduced)?;
287+
current_builder = frame.parent_builder;
288+
// The rewrite replaced the parent, which is the child of the next frame.
289+
child_rewritten = true;
290+
continue;
291+
}
292+
// SAFETY: the slot is put back unchanged before the parent leaves the executor.
293+
let (parent, child) = unsafe { parent.take_slot_unchecked(slot_idx) }?;
294+
stack.push(StackFrame {
295+
parent_array: parent,
296+
..frame
297+
});
298+
current_array = child;
299+
}
300+
244301
// Step 2a: execute_parent against the suspended parent from ExecuteSlot.
245302
//
246303
// When executing a child for ExecuteSlot, try execute_parent against
@@ -269,6 +326,7 @@ impl ArrayRef {
269326
trace_op!(record_execute_optimized(&result, &optimized));
270327
current_array = optimized;
271328
current_builder = frame.parent_builder;
329+
child_rewritten = !stack.is_empty();
272330
continue;
273331
}
274332
if current_builder.is_none() && stack.last().is_some() {
@@ -286,6 +344,7 @@ impl ArrayRef {
286344
let optimized = optimizer.optimize_array(&rewritten)?;
287345
trace_op!(record_execute_optimized(&rewritten, &optimized));
288346
current_array = optimized;
347+
child_rewritten = !stack.is_empty();
289348
continue;
290349
}
291350
if current_builder.is_none() {
@@ -319,6 +378,7 @@ impl ArrayRef {
319378
});
320379
current_array = optimizer.optimize_array(&child)?;
321380
current_builder = None;
381+
child_rewritten = false;
322382
}
323383
ExecutionStep::AppendChild(i) => {
324384
if current_builder.is_none() {
@@ -365,6 +425,7 @@ impl ArrayRef {
365425
// Kernels build their results with lazy constructors, such as a cast that only
366426
// changes nullability. Reduce them before execute-parent kernels see them.
367427
current_array = optimizer.optimize_array(&current_array)?;
428+
child_rewritten = !stack.is_empty();
368429
}
369430
}
370431
}

‎vortex-array/src/optimizer/mod.rs‎

Lines changed: 14 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -25,6 +25,7 @@ use std::sync::atomic::AtomicBool;
2525
use std::sync::atomic::Ordering;
2626

2727
use smallvec::SmallVec;
28+
use vortex_error::VortexExpect;
2829
use vortex_error::VortexResult;
2930
use vortex_error::vortex_bail;
3031
use vortex_error::vortex_ensure_eq;
@@ -309,6 +310,19 @@ impl<'a> Optimizer<'a> {
309310
Ok(optimized)
310311
}
311312

313+
/// Tries the parent-reduce kernels of the child in `slot_idx` against `parent`, without trying
314+
/// those of `parent`'s other children.
315+
pub(crate) fn reduce_parent_of_slot(
316+
&self,
317+
parent: &ArrayRef,
318+
slot_idx: usize,
319+
) -> VortexResult<Option<ArrayRef>> {
320+
let child = parent.slots()[slot_idx]
321+
.as_ref()
322+
.vortex_expect("parent-reduce needs a present slot");
323+
reduce_parent_with_kernels(self.kernels, parent, child, slot_idx)
324+
}
325+
312326
/// Optimizes `array` top down: first the root, then the descendants below it that were never
313327
/// optimized, then the root again while its children change. Marks the result.
314328
fn optimize(&mut self, array: ArrayRef) -> VortexResult<ArrayRef> {

0 commit comments

Comments
 (0)