Skip to content

Commit 9d6e6d6

Browse files
committed
Optimize each node top down and try it again when a child changes
The optimizer now tries the rules of a node before it optimizes the children of the node. Thus a rule that drops or replaces a child does not optimize the subtree of that child first. After the children are optimized, the optimizer tries the rules of the node again if a child changed. Thus a parent rule or kernel that is keyed on the final encoding of a child still applies, such as LIKE over a slice of an FSST array. When a rule rewrites a node, the optimizer still optimizes the nodes that the rule built before the next pass on the node. This stops two rules that are inverses of each other from rewriting a node back and forth. The trace snapshot of the stack parent kernel test now shows the parent optimized before its child. Signed-off-by: Robert Kruszewski <[email protected]>
1 parent 779e801 commit 9d6e6d6

2 files changed

Lines changed: 32 additions & 17 deletions

File tree

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

Lines changed: 27 additions & 12 deletions
Original file line numberDiff line numberDiff line change
@@ -13,15 +13,20 @@
1313
//! rewrites the root node.
1414
//! - [`ArrayOptimizer::optimize_ctx`] also consults the session's active
1515
//! [`kernels::ArrayKernels`] registry before static parent-reduce rules, so this is the entry
16-
//! point used by execution. It optimizes the root after the descendants below it that were
17-
//! never optimized.
16+
//! point used by execution. It optimizes the root, then the descendants below it that were
17+
//! never optimized, then the root again if a child changed.
1818
//! - [`ArrayOptimizer::optimize_recursive`] is the same as [`ArrayOptimizer::optimize_ctx`].
1919
//!
20-
//! With a session, optimizing a node first optimizes its children that were never optimized,
21-
//! bottom up: a parent rule or kernel keyed on a child's encoding sees that encoding rather than a
22-
//! lazy wrapper around it, such as a slice of an FSST array under a `LIKE`. Children already
23-
//! optimized are left without visiting their subtrees. Whenever a rule rewrites a node, the nodes
24-
//! the rule built are optimized the same way.
20+
//! With a session, the optimizer works top down. It first tries the rules of a node on its children
21+
//! as they are, so a rule that drops or replaces a child does not optimize that child first. Then
22+
//! it optimizes the children that were never optimized, and if any child changed, it tries the
23+
//! rules of the node again. Thus a parent rule or kernel keyed on a child's encoding still sees
24+
//! that encoding rather than a lazy wrapper around it, such as a slice of an FSST array under a
25+
//! `LIKE`. Children already optimized are left without visiting their subtrees.
26+
//!
27+
//! Whenever a rule rewrites a node, the nodes the rule built are optimized bottom up before the
28+
//! next pass on the node. Otherwise two rules that are inverses of each other, such as
29+
//! `slice(get_item(s))` and `get_item(slice(s))`, could rewrite the node back and forth.
2530
//!
2631
//! Each array records whether the optimizer has taken it to its fixpoint. A new array starts
2732
//! unoptimized, and optimizing with a session marks the arrays it returns, so optimizing an array
@@ -237,16 +242,26 @@ impl<'a> Optimizer<'a> {
237242
Ok(optimized)
238243
}
239244

240-
/// Optimizes `array` after the descendants below it that were never optimized, and marks the
241-
/// result.
245+
/// Optimizes the root of `array` top down: first the root, then the descendants below it that
246+
/// were never optimized, then the root again while its children change. Marks the result.
242247
fn optimize(&mut self, array: ArrayRef) -> VortexResult<ArrayRef> {
243248
if array.optimized_state().is_optimized() {
244249
return Ok(array);
245250
}
246251

247-
// Parent rules match on their children's encodings, so optimize the children first.
248-
let current_array = self.optimize_new_nodes(array.clone())?;
249-
let optimized = self.optimize_root(current_array)?;
252+
// The rules of the root get the first try, on children that can still be lazy, so a rule
253+
// that drops or replaces a child does not pay to optimize that child's subtree first.
254+
let mut optimized = self.optimize_root(array.clone())?;
255+
256+
for _ in 0..=MAX_OPTIMIZER_REWRITE_PASS {
257+
let with_children = self.optimize_new_nodes(optimized.clone())?;
258+
if ArrayRef::ptr_eq(&with_children, &optimized) {
259+
break;
260+
}
261+
262+
// A child changed its encoding, so a parent rule keyed on that encoding can apply now.
263+
optimized = self.optimize_root(with_children)?;
264+
}
250265

251266
// A rewrite keeps the logical values, so every statistic of the input stays valid. Lazy
252267
// constructors such as `slice` put the statistics they carry over on the lazy node.

‎vortex-array/src/test_harness/trace/tests.rs‎

Lines changed: 5 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -530,16 +530,16 @@ fn trace_execution_stack_parent_kernel_attempts(
530530
&mut ctx
531531
);
532532
insta::assert_snapshot!(traced.trace.to_string(), @"
533-
optimize root=vortex.test.stack-child(i32, len=3) session=true
534-
loop input=vortex.test.stack-child(i32, len=3)
535-
reduce none array=vortex.test.stack-child(i32, len=3)
536-
reduce_parent none array=vortex.test.stack-child(i32, len=3)
537-
done output=vortex.test.stack-child(i32, len=3) changed=false
538533
optimize root=vortex.test.stack-parent(i32, len=3) session=true
539534
loop input=vortex.test.stack-parent(i32, len=3)
540535
reduce none array=vortex.test.stack-parent(i32, len=3)
541536
reduce_parent none array=vortex.test.stack-parent(i32, len=3)
542537
done output=vortex.test.stack-parent(i32, len=3) changed=false
538+
optimize root=vortex.test.stack-child(i32, len=3) session=true
539+
loop input=vortex.test.stack-child(i32, len=3)
540+
reduce none array=vortex.test.stack-child(i32, len=3)
541+
reduce_parent none array=vortex.test.stack-child(i32, len=3)
542+
done output=vortex.test.stack-child(i32, len=3) changed=false
543543
execute_until target=AnyCanonical root=vortex.test.stack-parent(i32, len=3)
544544
iter 0 current=vortex.test.stack-parent(i32, len=3) builder_active=false
545545
done_check target=false canonical=false

0 commit comments

Comments
 (0)