GitHub user Xiao-zhen-Liu added a comment to the discussion: Design and merge plan: operator output port result cache (MVP)
Summary and next steps from our November 10 discussion (@chenlica, @Yicong-Huang): ### 1. What we agreed on - **Workflow-wide backward propagation is required in any method:** Regardless of how reuse is scheduled, the planner must propagate reuse decisions backward across the workflow before pricing regions. Without backward propagation, a plan hits the two invalid cases in Section 1 above: 1. *Wasted work:* an upstream operator (`A`) runs and produces output even though its only consumer (`B`) reads a saved result instead. 2. *Unsatisfied input:* propagating only within a single region (`R1`) can skip an uncached operator (`A`) whose output is still needed by an operator (`E`) in a downstream region (`R2`). - **Two-step planning under the eager-reuse assumption:** Under the **eager-reuse assumption** (where reading a saved result is always cheaper than recomputing it), the two-step approach in #8731 to #8734 (run backward propagation across the workflow first to prune skipped operators, then run `CostBasedScheduleGenerator` on the remaining operators) is simple and natural. - **Relaxing eager reuse and choosing Unified Search (BFS) over Two-Layer Search (DFS):** We want to relax the eager-reuse assumption in Texera because recomputing and pipelining can beat reading a saved result when that saved result sits on slow storage while an upstream saved result sits on fast storage (as in `A -> B (fast) -> C -> D (slow) -> E` in Section 4 above). Relaxing eager reuse requires searching over both **which saved results to read** and **which links to pipeline or materialize**, giving two options: - **Two-Layer Search (DFS):** an outer search picks which saved results to read (using backward propagation to prune upstream branches), and for each choice the existing 2-state `CostBasedScheduleGenerator` searches `Materialized` vs. `Pipelined` links on the remaining sub-DAG. - **Unified Search (BFS):** a single `CostBasedScheduleGenerator` search assigns each link one of four states (`Materialized`, `Pipelined`, `Cache-Read`, or `Unused`) in one queue, triggering a backward propagation jump to `Unused` whenever an operator's outputs are all `Cache-Read` or `Unused`. - **Direction:** We want to go with **Unified Search** for its generality (its search space covers every plan that Two-Layer Search can explore), provided we develop stronger pruning and exploration strategies so Unified Search explores the 4-state space efficiently under a planning budget. - **Incremental path to merge the eager-reuse MVP sooner:** Because the eager-reuse plan is the starting state of Unified Search (where every link with a saved result starts as `Cache-Read`, backward propagation marks unneeded upstream links `Unused`, and the scheduler takes zero reuse-flip expansion steps), we can implement the backward propagation pass as part of the Unified Search framework. That allows the eager-reuse MVP (#8731 to #8734) to merge sooner and extend cleanly into full Unified Search later. ### 2. Open technical question to verify - **Equivalence of two Unified Search implementations:** @chenlica and @Yicong-Huang view two ways of implementing Unified Search as equivalent: (1) the 4-link-state search in `CostBasedScheduleGenerator` before `createRegions`, and (2) deciding whether an operator reuses a saved result (`0` workers) or computes (`>= 1` workers) inside `ResourceAllocator`. I am not fully convinced they are equivalent yet (for example, because `createRegions` runs before `CostEstimator` and `ResourceAllocator`, switching an operator from reuse to recompute can change which links pipeline and how regions are formed across the workflow) and will check whether they are equivalent or where they diverge. ### 3. Next Steps / TODOs 1. **Verify equivalence of the two Unified Search designs:** Check whether deciding reuse inside `ResourceAllocator` is truly equivalent to the 4-link-state search in `CostBasedScheduleGenerator`, or construct concrete examples showing where they differ (such as cross-region propagation or region formation when pipelining across a recomputed operator). 2. **Develop optimization and exploration strategies for Unified Search:** Bring the pruning and exploration optimizations from Two-Layer Search (starting from the eager-reuse seed state, stepping out of slow saved results with immediate backward propagation, and applying bridge/chain pipelining rules on the pruned graph) into Unified Search so it finds good plans quickly under a planning time budget. 3. **Design the MVP-to-Unified-Search path:** Structure the backward propagation pass as the base step of Unified Search so the eager-reuse MVP (#8731 to #8734) can merge first and extend to full Unified Search with minimal changes. GitHub link: https://github.com/apache/texera/discussions/5880#discussioncomment-19536682 ---- This is an automatically sent email for [email protected]. To unsubscribe, please send an email to: [email protected]
