GitHub user Xiao-zhen-Liu added a comment to the discussion: Design and merge 
plan: operator output port result cache (MVP)

@chenlica @Yicong-Huang Following the October 1 overview meeting, here is a 
summary of the design questions raised there, how the open PRs (#8731, #8732, 
#8733, #8734) address them, and how the design extends to cost-based reuse 
search.

### 1. Yicong's proposal at the October 1 meeting

On the join workflow from #5880, @Yicong-Huang asked whether we can omit 
`SkeletonGenerator` (#8731) and instead keep cached operators `B` and `D` at 0 
workers inside running regions `R1 = {A, B, C-Build}` and `R2 = {D, E, C-Probe, 
F, G}`, decided inside `CostEstimator` and `ResourceAllocator`:

![#5880 schedule vs. Yicong's proposal on the join 
workflow](https://gist.githubusercontent.com/Xiao-zhen-Liu/0ab5fc9832b2688c2fa9aa46ec9f8f4a/raw/0324b86815c4213da737b7ae04617e8df4951e14/fig01-yicong-schedule.png)

### 2. Why keeping 0-worker operators inside running regions and pricing per 
operator does not work

1. **Neither `Materialized` nor `Pipelined` models `B -> C-Build` when `B` is 
reused:** marking `B -> C-Build` `Materialized` creates a region dependency 
that forces `C-Build` to wait until slow `A` finishes, whereas marking `A -> B 
-> C-Build` `Pipelined` couples `A` and `C-Build` in one shared region and 
misses the storage-read cost on `B`.

![Neither Materialized nor Pipelined models B to C-Build when B is 
reused](https://gist.githubusercontent.com/Xiao-zhen-Liu/0ab5fc9832b2688c2fa9aa46ec9f8f4a/raw/0324b86815c4213da737b7ae04617e8df4951e14/fig02-design-edges.png)

2. **Per-operator pricing in `CostEstimator` cannot skip uncached upstream 
`A`:** when the user views only `G` and `B` is reused, inspecting `A` alone in 
`CostEstimator` runs `A` (`>= 1` worker) and discards its output; skipping `A` 
requires propagating reuse backward across links before regions are formed 
(#8731).

![Per-operator pricing in CostEstimator vs. backward reachability across links 
in 
#8731](https://gist.githubusercontent.com/Xiao-zhen-Liu/0ab5fc9832b2688c2fa9aa46ec9f8f4a/raw/0324b86815c4213da737b7ae04617e8df4951e14/fig03-design-upstream.png)

3. **Reuse is per link / input port, not 0 workers on the producer operator:** 
on a multi-output `Split` (#5880 Fig. 4) where Port 0 (to `A`) has a cached 
result and Port 1 (to `B`) does not, setting `Split` to 0 workers starves `B`; 
`Split` must run (`>= 1` worker) for `B` while the link `Split(Port 0) -> A` 
reads the cached result (#8731, #8732).

![Multi-output Split cannot have 0 workers when only Port 0 is 
cached](https://gist.githubusercontent.com/Xiao-zhen-Liu/0ab5fc9832b2688c2fa9aa46ec9f8f4a/raw/0324b86815c4213da737b7ae04617e8df4951e14/fig04-design-split.png)

4. **Keeping 0-worker `B` inside running region `R1` breaks engine invariants 
and creates a false barrier:** mixing 0-worker `B` into `R1 = {A, B, C-Build}` 
breaks `ResourceAllocator`, channel wiring, `RegionExecutionManager` storage 
and barriers, and `FriesReconfigurationAlgorithm` (#8734); and even if `Region` 
were generalized to allow 0-worker operators, a `Region` is one shared 
completion barrier, so keeping `{A, B(0w), C-Build}` in `R1` blocks `R2` for 60 
s waiting on slow `A` instead of starting `R5` as soon as `C-Build` finishes 
(#8733).

![0-worker B inside running region R1 breaks 4 engine 
invariants](https://gist.githubusercontent.com/Xiao-zhen-Liu/0ab5fc9832b2688c2fa9aa46ec9f8f4a/raw/0324b86815c4213da737b7ae04617e8df4951e14/fig05-complexity.png)

![Splitting at 0-worker cut B avoids the false completion 
barrier](https://gist.githubusercontent.com/Xiao-zhen-Liu/0ab5fc9832b2688c2fa9aa46ec9f8f4a/raw/0324b86815c4213da737b7ae04617e8df4951e14/fig06-generalize-region.png)

### 3. How the 5 execution, parallelism, and history requirements are satisfied

- **Requirements 1 to 3 (intact `PhysicalPlan`, no new `SKIPPED` state, and 
0-worker schedule):** `WorkflowScheduler` keeps `physicalPlan` intact (#8731, 
#8733), reused operators report `COMPLETED` with `reused_from_cache = true` 
(#6729), and skipped operators stay in `Schedule` as Level 0 skip regions `R1 = 
{B}` and `R2 = {D}` that complete in 0 s with 0 workers (#8733 and the 
skip-regions PR).

![Requirements 1 to 3 satisfied by Level 0 skip 
regions](https://gist.githubusercontent.com/Xiao-zhen-Liu/0ab5fc9832b2688c2fa9aa46ec9f8f4a/raw/0324b86815c4213da737b7ae04617e8df4951e14/fig07-reqs-1-to-3.png)

- **Requirement 4 (parallel execution of `R3 = {A}` and `R4 = {C-Build}`):** in 
#8733, `R3 = {A}` and `R4 = {C-Build}` both have `inDegree = 0` with no 
dependency edge between them, so `ScheduleGenerator` and 
`WorkflowExecutionManager` already launch them in parallel when 
`schedule-generator.max-concurrent-regions > 1`.

![R3 = {A} and R4 = {C-Build} have inDegree = 0 and run in 
parallel](https://gist.githubusercontent.com/Xiao-zhen-Liu/0ab5fc9832b2688c2fa9aa46ec9f8f4a/raw/0324b86815c4213da737b7ae04617e8df4951e14/fig08-req-4-parallel.png)

- **Requirement 5 (do not skew `CostEstimator` and Ramen history with 0-worker 
runs):** persisting `reused_from_cache` in `ResultSchema` and filtering out 
`reused_from_cache = true` rows in `PastExecutionStatistics` prevents 0-worker, 
0.0 s reuse rows from overwriting an operator's real compute runtime and worker 
count.

![Filtering reused_from_cache rows in 
PastExecutionStatistics](https://gist.githubusercontent.com/Xiao-zhen-Liu/0ab5fc9832b2688c2fa9aa46ec9f8f4a/raw/0324b86815c4213da737b7ae04617e8df4951e14/fig09-req-5-history.png)

### 4. Extending to cost-based reuse search (Two-Layer Search vs. One-Layer 
Search)

- **Option A (Two-Layer Search):** an outer search branches `SkeletonGenerator` 
across matched ports into candidate `RunSkeleton`s and runs the existing 
2-state `CostBasedScheduleGenerator` (`Pipelined`, `Materialized`) with 
`ReuseCostEstimator` and Ramen on each candidate.

![Option A: Two-Layer Search generalizes the Eager Reuse 
MVP](https://gist.githubusercontent.com/Xiao-zhen-Liu/0ab5fc9832b2688c2fa9aa46ec9f8f4a/raw/0324b86815c4213da737b7ae04617e8df4951e14/fig10-two-layer.png)

- **Option B (One-Layer Search):** replaces only the 2-state search loop with a 
4-state edge search loop (`Pipelined`, `Materialized`, `Reuse`, `Unused`) that 
jumps backward to mark unneeded upstream links `Unused` and evaluates each 
candidate via `RunSkeleton` (#8731), `CacheReadInputs` (#8732), and 
`ReuseCostEstimator`.

![Option B: One-Layer Search replaces only the 2-state search 
loop](https://gist.githubusercontent.com/Xiao-zhen-Liu/0ab5fc9832b2688c2fa9aa46ec9f8f4a/raw/0324b86815c4213da737b7ae04617e8df4951e14/fig11-one-layer.png)

- **Compatibility with Peanut and Ramen:** both search options keep #8731 to 
#8734 intact, plan Peanut's mini-operators (`U_train -> U_predict`) without 
changes to Peanut, and pass only running regions (`>= 1` worker per operator) 
to `ReuseCostEstimator` and Ramen.

![Compatibility with Peanut 
U-plans](https://gist.githubusercontent.com/Xiao-zhen-Liu/0ab5fc9832b2688c2fa9aa46ec9f8f4a/raw/0324b86815c4213da737b7ae04617e8df4951e14/fig12-compat-peanut.png)

![Compatibility with Ramen 
(ResourceAllocator)](https://gist.githubusercontent.com/Xiao-zhen-Liu/0ab5fc9832b2688c2fa9aa46ec9f8f4a/raw/0324b86815c4213da737b7ae04617e8df4951e14/fig13-compat-ramen.png)

We have built both Two-Layer Search and One-Layer Search on a branch and are 
benchmarking them across workflow shapes and time budgets to compare with 
@Yicong-Huang and @chenlica.


GitHub link: 
https://github.com/apache/texera/discussions/5880#discussioncomment-19505621

----
This is an automatically sent email for [email protected].
To unsubscribe, please send an email to: [email protected]

Reply via email to