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]

Reply via email to