Physical properties: replace Materialization with timing × lifetime (None / OneEvaluation / AcrossEvaluations) and a schedule for shareable results, with r^phys and α^phys #1200

Example

sum_over_time(http_requests_total[1h]), exact, every 10 s, over a tumbling-window chain of 10 s windows. Consecutive evaluations share 359 of their 360 windows. There are three ways to run the chain:

Today one enum value, Materialization, encodes both when a node runs and how long its output lives. MatAtQueryKeptAcrossEvaluations mixes the two, and timing is stored a second time next to it.

Representation, rules, enumeration

• (a) Representation. Each physical candidate stores $p^{\mathrm{phys}} = (\tau, \ell)$:

  • timing;
  • lifetime None / OneEvaluation(medium) / AcrossEvaluations(medium).

  The invalid combination cannot be constructed (PhysicalProperties::new). Materialization is deleted.

• (b) Rules. No logical rules change. Stage 2's expansion step creates, for each logical candidate, one physical candidate per valid (timing, lifetime) pair. There is no schedule dimension (decided 2026-11-06).

• (c) Enumeration.

  • Stage 3 picks among these alternatives.
  • $\alpha^{\mathrm{phys}}$ restricts which producers a consumer input may pick: it is a function of the consumer's own $p^{\mathrm{phys}}_c$ (timing and lifetime). Stage 3 checks alignment per context (below).

Formulation

A candidate's physical properties are $p_v^{\mathrm{phys}} = (\tau_v, \ell_v)$, exactly the paper's. There is no schedule property (decided 2026-11-06):

$$\tau_v \in {\mathrm{IngestionTime}, \mathrm{QueryTime}}, \qquad \ell_v \in {\mathrm{None}, \mathrm{OneEvaluation}, \mathrm{AcrossEvaluations}}.$$

• $\ell = \mathrm{None}$: the output is discarded after its consumer's execution completes.
• $\ell = \mathrm{OneEvaluation}$: kept until all consumers within one evaluation finish.
• $\ell = \mathrm{AcrossEvaluations}$: kept throughout the evaluation period, so later evaluations reuse it.
• $\text{materialized}(v) \iff \ell_v \ne \mathrm{None}$, derived, not stored.
• $r^{\mathrm{phys}}_{c,i}$ is not stored: it is a function of the consumer's own $p^{\mathrm{phys}}c$ (decided 2026-11-05). $\alpha^{\mathrm{phys}}{u,c,i}$ = producer_satisfies_physical_requirements$(u, c)$ takes the two candidates, not bare properties, and checks timing and lifetime:

Reusing an earlier evaluation's work is the producer's $\ell$, a cost choice, not a requirement, so there is no "later evaluation" row.

• Cost: $w_v$ adds $C^{\text{one}}{\text{retain}}(v)$ for OneEvaluation and $C^{\text{across}}{\text{retain}}(v)$ for AcrossEvaluations.

No schedule property (decided 2026-11-06; replaces the 2026-11-04 schedule $\sigma_v$). When a result can be read follows from its lifetime and window layout $\omega_v$:

• OneEvaluation belongs to one evaluation context $\kappa$. Queries with equal recurrence and range evaluation are evaluated together, and that evaluation's consumers share the result. When it runs is the context's recurrence, and Stage 3 chooses it through $x_{\kappa,v}$, just as for $\ell$ = None. Its cost stays fixed at $\rho_\kappa \times$ its run cost. Sharing across differently scheduled queries via a gcd schedule is dropped: it is rarely beneficial and wastes runs.
• Every tumbling-window grid is anchored at phase 0 (the epoch). The phase is absorbed by the width $\omega_v$ (logical): width candidates come from the gcd closure of the queries' ranges, steps and phases. For example, phases 0 and 5 s with $w = 10$ s give $w = 5$ s. Each window is built when it ends and can be read from then on.
• $\alpha^{\mathrm{phys}}_{u,c,i}$ = producer_satisfies_physical_requirements is the timing and lifetime table above only. The alignment condition in this table is checked per context in Stage 3 by delivers_on with $\kappa$ (Stage 3 MILP: implement the formulation variables x, y, z, t and rows (A)–(I) as named code over explicit edges #1204).
• Every recurrence is supported (decided 2026-11-06; replaces the 2026-11-04 periodic-only scope). An evaluation context is the workload's own QueryRecurrence and RangeEvaluation (Stage 3 MILP: implement the formulation variables x, y, z, t and rows (A)–(I) as named code over explicit edges #1204); a one-off query is the context of its OneTime recurrence. Where its evaluation times are not known, its consumers get no AcrossEvaluations producer and read $\ell$ = None or OneEvaluation candidates.
• Today: the schedule of a shared result is chosen in the MILP (schedule groups z[m, G], [Feature] Stage 3: no execution-scope copies, exact candidate-level MILP, one cost formula #1095). A materialized chain has one candidate whatever the phases of the queries reaching it, so queries of different phases cannot both read it (IncompatibleOutputs, Stage 3 MILP: implement the formulation variables x, y, z, t and rows (A)–(I) as named code over explicit edges #1204).

Invalid combination of $(\tau, \ell)$. PhysicalProperties::new rejects exactly one:

Valid pairs, and how Stage 3 runs each:

Data structures and interfaces per stage

Types (crates/types/src/physical/):

pub enum ExecutionTiming { IngestionTime, QueryTime }            // exists

/// ℓ_v. Only a materialized result has a medium.
pub enum Lifetime { None, OneEvaluation(StorageMedium), AcrossEvaluations(StorageMedium) }

/// p_v^phys = (τ, ℓ). `new` rejects only (IngestionTime, OneEvaluation).
pub struct PhysicalProperties { timing: ExecutionTiming, lifetime: Lifetime }
impl PhysicalProperties {
    pub fn new(timing: ExecutionTiming, lifetime: Lifetime) -> Result<Self, PhysicalPropertiesError>;
    pub fn timing(&self) -> ExecutionTiming;
    pub fn lifetime(&self) -> Lifetime;
    pub fn is_materialized(&self) -> bool;                       // ℓ ≠ None
}

impl PhysicalCandidate {
    /// Whether a consumer running in `context` can read this producer (the alignment
    /// table above): for a windowed AcrossEvaluations producer, w (read from its logical
    /// window layout ω_v) divides every evaluation time of the context; true for ℓ = None,
    /// and for OneEvaluation in the same context.
    pub fn delivers_on(&self, memo: &Memo, context: &ExecutionContext) -> bool;
}

/// α^phys_{u,c,i} = r^phys_{c,i} as a function of the consumer's own p^phys_c
/// (no PhysicalRequirement struct): timing and lifetime only (table above).
/// Stage 3 checks `delivers_on(κ)` per context (#1204).
pub fn producer_satisfies_physical_requirements(producer: &PhysicalCandidate, consumer: &PhysicalCandidate) -> bool;

Stage 1: no change. Pass 1 and Pass 2 produce logical candidates without physical properties.

Stage 2 (physical-asap-optimization):

• PhysicalCandidate { timing, materialization } becomes PhysicalCandidate { logical_candidate_id: CandidateForMemoGroupId, physical_properties: PhysicalProperties }; likewise PhysicalCandidateKey.
• Candidate generation enumerates valid $(\tau, \ell)$ pairs.
• compatible_timing becomes producer_satisfies_physical_requirements(producer, consumer); there is no per-input requirement to store. PhysicalCandidate has no input_requirements.
• may_keep_across_evaluations_per_sole_reader_query (memo_candidates.rs:85) reads Lifetime::AcrossEvaluations.

Stage 3 (plan-selection): run_kind (groups.rs:346) takes PhysicalProperties:

$$\text{RunKind}(v) = \begin{cases} \text{PerContext} & \tau = \text{query},\ \ell \in {\text{None}, \text{OneEvaluation}} \ \text{Ingestion} & \tau = \text{ingestion},\ \ell = \text{None} \ \text{Materialized} & \ell = \text{AcrossEvaluations} \end{cases}$$

OneEvaluation moves to PerContext (one result per evaluation context); the other branches match today's.

Stage 3: a OneEvaluation candidate's rate is its context's $\rho_\kappa$, not a schedule-group choice. The MILP side, contexts for (QueryTime, None) and (QueryTime, OneEvaluation) candidates, is #1204.

Cost (asap-cost): matches on Lifetime for the retention terms, and prices a OneEvaluation candidate at its context's rate $\rho_\kappa$.

Export (crates/types/src/ir/physical_export.rs): writes timing and lifetime. Either the backend's wire format keeps materialization, mapped at export, or it changes together with the backend.

Current vs proposed

How much is retained stays a Stage 3 decision. The number of tumbling windows an AcrossEvaluations chain keeps depends on the longest range among the queries reading it. The MILP already chooses it. Making it a property would copy each candidate once per retention amount, the redundancy #1199 describes.

Alternative considered: drop query-time retention. Reuse across evaluations would then come only from ingestion-time chains. Rejected:

• a deployment without ingestion pipelines could no longer reuse across evaluations;
• for sparse queries, a query-time chain that keeps only recent data can be cheaper.

Scope and acceptance

In scope:

• ExecutionTiming, Lifetime, PhysicalProperties, PhysicalCandidate::delivers_on, producer_satisfies_physical_requirements;
• Stage 2 generation and producer filtering;
• Stage 3's run_kind;
• asap-cost;
• the export.

Out of scope:

• the MILP's variables and constraints (Stage 3 MILP: implement the formulation variables x, y, z, t and rows (A)–(I) as named code over explicit edges #1204);
• the edge set (Producer–consumer edges (u, c, i): make the edge set explicit after Pass 2 and Stage 2, with α^log and α^phys, as the domain of y_{u,c,i} #1201).

Acceptance:

• Deletes what it replaces in the same PR, with no dead code, fallback, flag, shim or reuse of an old abstraction; the PR body lists what it deleted (Tracking: implement the optimization formulation (memo candidates, properties, edges y_{u,c,i}, MILP) as named code per stage #1207, Policy).
• Order: see Tracking: implement the optimization formulation (memo candidates, properties, edges y_{u,c,i}, MILP) as named code per stage #1207, "Order (rewritten 2026-11-06: interfaces first, baseline before extensions)". This issue's parts are PRs 0, 1, 5 and 7. Regression test for alignment: two 10 s queries at phases 0 s and 5 s both read one 5 s chain anchored at phase 0.
• Timing is stored once per candidate.
• No code matches on a combined materialization value to find the timing.
• PhysicalProperties::new rejects the invalid combination 1, with a test.

Related

• Tracking: Tracking: implement the optimization formulation (memo candidates, properties, edges y_{u,c,i}, MILP) as named code per stage #1207.
• Producer–consumer edges (u, c, i): make the edge set explicit after Pass 2 and Stage 2, with α^log and α^phys, as the domain of y_{u,c,i} #1201: edges use $\alpha^{\mathrm{phys}}$.
• [Feature] Stage 3: no execution-scope copies, exact candidate-level MILP, one cost formula #1095 / feat(plan-selection): group selection MILP over execution contexts as Stage 3's default search (#1095) #1144: execution contexts, RunKind, retention constraints.
• Stage 3 MILP vs the memo formulation: one choice costs several binaries, sizes and targets are groups, and the group graph is cyclic #1199: how materialization and reuse across evaluations are modeled in the MILP.
• docs: propose workload-wide planning, summary sharing, and materialization #509 §Materialization.