|
13 | 13 | //! rewrites the root node. |
14 | 14 | //! - [`ArrayOptimizer::optimize_ctx`] also consults the session's active |
15 | 15 | //! [`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. |
18 | 18 | //! - [`ArrayOptimizer::optimize_recursive`] is the same as [`ArrayOptimizer::optimize_ctx`]. |
19 | 19 | //! |
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. |
25 | 30 | //! |
26 | 31 | //! Each array records whether the optimizer has taken it to its fixpoint. A new array starts |
27 | 32 | //! unoptimized, and optimizing with a session marks the arrays it returns, so optimizing an array |
@@ -237,16 +242,26 @@ impl<'a> Optimizer<'a> { |
237 | 242 | Ok(optimized) |
238 | 243 | } |
239 | 244 |
|
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. |
242 | 247 | fn optimize(&mut self, array: ArrayRef) -> VortexResult<ArrayRef> { |
243 | 248 | if array.optimized_state().is_optimized() { |
244 | 249 | return Ok(array); |
245 | 250 | } |
246 | 251 |
|
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 | + } |
250 | 265 |
|
251 | 266 | // A rewrite keeps the logical values, so every statistic of the input stays valid. Lazy |
252 | 267 | // constructors such as `slice` put the statistics they carry over on the lazy node. |
|
0 commit comments