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 up on TODO 3 from our November 10 summary 
(structuring reuse planning inside Unified Search so eager reuse extends 
cleanly to cost-based reuse), here is the updated design across **#8731 to 
#8734**.

Rather than running a separate pre-scheduling step on `WorkflowScheduler`, all 
reuse planning lives inside `CostBasedScheduleGenerator`, keeping Amber's 
`LogicalPlan -> PhysicalPlan -> RegionPlan -> Schedule` pipeline intact.

### 1. System overview: where cache reuse fits

![Workflow execution components with cache 
reuse](https://gist.githubusercontent.com/Xiao-zhen-Liu/0ab5fc9832b2688c2fa9aa46ec9f8f4a/raw/a4df10e705c98e8c33b978808c16a30bf1a6dcdf/fig1-execution-components.png)

**#8731 to #8734** cover scheduling and reconfiguration (blue); follow-up PRs 
add lookup, save, endpoints, retention (**#5885**), and zero-worker skip 
execution (**#5884**, yellow). On run start, the **#5885** lookup PR fills 
`WorkflowContext.matchedResults` (**#8731**) from `operator_port_cache` 
(**#5967**) on the computing unit only (editor requests carry no storage URIs; 
loop plans get `Map.empty`), before `CostBasedScheduleGenerator` (**#8732**, 
**#8733**) emits one extended `RegionPlan` for `ScheduleGenerator` (**#8731**).

### 2. Why `#8732` uses four link states instead of two

![Two-state link search on main vs. four-state SearchState for cache 
reuse](https://gist.githubusercontent.com/Xiao-zhen-Liu/0ab5fc9832b2688c2fa9aa46ec9f8f4a/raw/a4df10e705c98e8c33b978808c16a30bf1a6dcdf/fig2-main-vs-4state-search.png)

On `main`, `CostBasedScheduleGenerator` marks each `PhysicalLink` as 
**Materialized** (producer writes to storage across a `RegionLink` before 
downstream starts) or **Pipelined** (both run concurrently in one `Region`, 
passing tuples directly). Because blocking ports force materialization and 
valid region graphs are acyclic, `main` searches candidate subsets 
`Set[PhysicalLink]`.

With cache reuse (**#8731**, **#8732**), a link can also be **CacheRead** 
(consumer reads saved output from storage with no `RegionLink`) or **Unused** 
(consumer is skipped). Package `scheduling` adds `EdgeType` and `SearchState` 
(`linkTypes` plus `reusedOutputs`, tracking end-of-run outputs served from 
storage). `SearchState` checks via `require` that every `matchedResults` key is 
an output port of `physicalPlan`, leaving loop and warehouse eligibility to 
cache lookup.

### 3. Resolving required inputs and skipped branches 
(`resolveInputRequirements`)

![Resolving input requirements with resolveInputRequirements on the HashJoin 
example](https://gist.githubusercontent.com/Xiao-zhen-Liu/0ab5fc9832b2688c2fa9aa46ec9f8f4a/raw/a4df10e705c98e8c33b978808c16a30bf1a6dcdf/fig3-resolve-input-requirements.png)

Assigning an `EdgeType` locally to one link leaves upstream links out of sync 
with whether each operator runs (stopping a branch at `CacheRead` leaves its 
upstream producers active until cleared, and switching a `CacheRead` link back 
to recompute leaves skipped upstream links `Unused`). In one 
reverse-topological pass from sinks and required end-of-run outputs toward 
sources, `SearchState.resolveInputRequirements` resolves both directions 
together: a running operator keeps or fills any `Unused` input as `CacheRead` 
(if matched) or active (`Materialized`/`Pipelined`), while a skipped operator 
marks every incoming link `Unused`.

### 4. Extending `RegionPlan` and `Schedule` (`#8731`, `#8733`, `#8734`)

![Extended RegionPlan and Level 0 Schedule on the HashJoin 
example](https://gist.githubusercontent.com/Xiao-zhen-Liu/0ab5fc9832b2688c2fa9aa46ec9f8f4a/raw/a4df10e705c98e8c33b978808c16a30bf1a6dcdf/fig4-extended-region-plan-and-schedule.png)

**#8731** adds `skipped: Boolean = false` on `Region` and `cachedTupleCount` on 
`OutputPortConfig`. During search evaluation, `createRegions` (**#8733**) 
partitions running operators into active regions (attaching saved locations to 
`IntermediateInputPortConfig` in Pass 2), and `buildRegionPlan` appends 
disconnected skip regions to the winning region DAG. `ScheduleGenerator` checks 
via `require` that skip regions have no `RegionLink`s and places them at Level 
`0` ahead of active levels `1..k`. Because full-plan operators retain all 
original links, **#8731** (`Region.getSourceOperators`) and **#8734** 
(`FriesReconfigurationAlgorithm`) inspect `region.getLinks` instead.

> **Naming check:** Extending `Region` and `RegionPlan` keeps Amber's 
> four-layer pipeline intact, though `RegionPlan` holds non-pipelined skip 
> components beside active regions. Should we keep those names or rename them 
> once behavior settles?

### 5. Search pipeline and cost-based Unified Search

![CostBasedScheduleGenerator search pipeline and extension to cost-based 
Unified 
Search](https://gist.githubusercontent.com/Xiao-zhen-Liu/0ab5fc9832b2688c2fa9aa46ec9f8f4a/raw/a4df10e705c98e8c33b978808c16a30bf1a6dcdf/fig5-planning-flow.png)

`CostBasedScheduleGenerator` (**#8733**) starts from `eagerSeed`, holds 
`CacheRead` fixed, explores active `Materialized` vs. `Pipelined` choices with 
Amber's existing pruning rules, and isolates 
`DefaultResourceAllocator(fullPlan)` per reuse boundary while sharing loaded 
runtime statistics. Relaxing eager reuse later changes only the search inside 
package `scheduling` (`SearchState` and `CostBasedScheduleGenerator`: reuse 
transitions with upstream re-enabling, and pruning kept per retained plan) and 
`CostEstimator` (the cost of reading a saved result), keeping `Region`, 
`RegionPlan`, `ScheduleGenerator`, and `WorkflowScheduler` intact.

<details>
<summary>Secondary invariants (#8731 to #8734 and upcoming execution 
PRs)</summary>

| Area | Rule in the updated design |
| --- | --- |
| Graph precondition (`#8732`) | `SearchState` checks via `require` that every 
`matchedResults` key is an output port of `physicalPlan`; loop, workflow, and 
warehouse eligibility live on the computing-unit lookup. |
| Isolated search state (`#8733`) | Each distinct `(retainedPlan, 
readerUrisByInputPort)` boundary uses its own 
`DefaultResourceAllocator(fullPlan)`, memoization map, and 
`DefaultCostEstimator.withResourceAllocator` sharing loaded runtime statistics. 
|
| Saved counts and worker-free execution | `OutputPortConfig.cachedTupleCount` 
carries saved row counts on skip regions; upcoming execution PRs skip workers, 
mark `reused_from_cache = true`, and drop only newly written URIs on cleanup. |
| Editor settings and `PhysicalPlan` | `WorkflowContext.matchedResults` never 
appears on editor `WorkflowSettings`, and `WorkflowScheduler` keeps the full 
`PhysicalPlan` intact for downstream operator lookups. |

</details>


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

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

Reply via email to