Skip to content

Latest commit

 

History

History
155 lines (141 loc) · 9.33 KB

asap-aware-mapping-contracts.md

File metadata and controls

155 lines (141 loc) · 9.33 KB

ASAP-Aware Mapping contracts

Audience: developers changing the planner. This reference states the rules the stage code relies on: what each stage's input and output may contain, and which component owns each decision. Read the architecture first; use the extension guide when changing one. Field-level details are in the rustdoc (cargo doc -p asap-stage0-memo -p asap-stage1-pass1-per-computation-candidates -p asap-stage1-pass2-reuse-candidates -p asap-stage2-physical-optimization -p asap-stage3-plan-selection -p asap-types --no-deps).

1. IR at each stage

After The DAG holds Timing
Stage 0 (frontends) NonASAPOp nodes only; aggregates carry AggIntent measures with each query's AccuracyTarget as written none
Stage 1 (Pass 1 and Pass 2 rules) ASAPOp nodes where a candidate chose an exact accumulator or a summary (SummaryAgg, SummaryTumblingWindowChain, SummaryMerge, SummaryEstimate, FinalizeExactAccumulator); everything else stays NonASAPOp none: Stage 1 never decides when anything runs
Stage 2 (generate_physical_asap_memo_candidates) and Stage 3 (select_plan, which builds the plan) the same operators, with a timing and a Lifetime on each summary build every node of the plan timed from the physical candidate it was built from (selected_physical_candidate)
  • Structurally equal sub-DAGs are interned before Stage 1 (cse.rs in asap_stage0_memo), so Stage 1 compares nodes by structure and Pass 2 matches readers structurally, never by pointer.
  • Timing is applied with apply_physical_properties, which validates every data-state edge. A violation is an ExecutionDataStateError: for example QueryTimeValueUnderIngestionSummary (a query-time value beneath an ingestion-time build), ConflictingTiming (one shared node needs two timings; split_shared_by_timing copies it for one side first) or IllegalChildDataState. These are internal errors in a candidate the stages built, not bad user input.
  • A summary build's AggregateCoverage (which rows and time range its state represents) is a memo-group property, derived by the memo, never declared; a merge's inputs must be disjoint as its family's MergeInputRule requires, or coverage fails (InputsOverlap).

2. Stage 1 candidates

  • Targets. ComputationTarget is one measure of one Aggregate. Its ways_to_compute list the exact option first (ExactAccumulator when the intent has a mergeable exact state, else Exact), then each Summary(family) from summary_realization::summary_candidates. Candidates are unranked: Pass 1 never compares cost.
  • Ways not offered. A way the measure or the deployment cannot compute (the exact accumulator of an avg over a nullable input, a count sketch over relational rows, a summary the deployment does not support, a quantile summary outside [0, 1], a top-k heap over one row per item) is not offered, and Pass 1 records none. Accuracy is Pass 2's.
  • Fused computations. FusedComputation { absorbed_groups, ways_to_compute } replaces the operators beneath (the whole-expression top-k, the nested sum, min or max) in one appearance; its builds list absorbed_groups in fused_groups. It absorbs the aggregate beneath and, for a heap over the raw data samples beneath a grouped sum of per-series sums or counts, the per-series aggregate too.
  • Pass 2. Each rule adds candidates; none removes a Pass 1 candidate, adds a summary family, or adds a readout. So a deployment that does not support a family never sees it again after Pass 1.
  • Sizing. A summary shared by several readers is sized with each parameter's largest value among them. A summary is sized for ε in Stage 1; a δ that depends on data facts (a distinct-count bound, series counts) is left symbolic in its guarantee for Stage 3 to bind.

3. Accuracy

  • A summary's guarantee is the deployment's measurement (AccuracyEvidence::measured_guarantee) when there is one, else its algorithm's error formula (theoretical_guarantee); a θ whose formula can be deterministic (DDSketch's relative error α) keeps its formula; Pass 2 compares it with each readout's RequiredAccuracy (ErrorMetricsOfMemo::edge_meets_logical_requirements). It fails closed: no rule means no guarantee, and the edge is not admissible.
  • A target with no accuracy_metric accepts a guarantee in any metric that meets its ε, δ and scope; Stage 3 reports the metric it accepted (AcceptedAccuracy).
  • A query that composes several readouts gives each readout a level of an error and failure-probability grid, within the cap its path's consumers (asap_accuracy::ErrorContract) leave it.
  • Facts come only from the declared DataWorkload; an undeclared fact is unknown, never zero.

4. Stage 2

  • Each logical candidate Pass 2 kept gets one PhysicalCandidate per offered timing and lifetime (PhysicalProperties): any candidate, not only a summary build, may get a lifetime. IngestionTime is offered to a time-independent group and its inputs (a counter state only over ordered rows); AcrossEvaluations to a chain, a group on a known evaluation grid and a time-independent group, unless the group is read under an absolute @ T; (IngestionTime, None) not to a summary build. A value not offered is not recorded. A group is time-independent when it reads no time relative to the evaluation time (GroupProperties::depends_on_evaluation_time is false): no TimeRange except one directly over an @ T, no time() or now(), and no @ start() or @ end() over a subtree that depends on the evaluation time, also under an @ T, which pins only its own time. Whether its rows keep arriving is not part of it.
  • Every physical alternative Stage 2 prunes is recorded in PhysicalASAPMemoCandidates::pruned_candidates as PrunedCandidate<PhysicalCandidate> with a PruneReason: an ingestion-time alternative without an ingestion pipeline (NoIngestionPipeline); a Count-Min build whose weights are not proven non-negative (CountMinWeightsNotProvenNonNegative); an alternative one of the deployment's exclusions matches (ExcludedByDeployment(source), from DeploymentCapabilities::exclusions: an unsupported summary type or readout, a scan of raw data the deployment does not retain, a query-time result kept across evaluations it does not retain, a counter semantics or a state merge its executor lacks, or a candidate the caller excludes); then an alternative no buildable input or query output can use (InputHasNoBuildableProducer, ReachesNoQueryOutput). Stage 2 makes no execution-scope copies.

5. Stage 3

  • select_plan validates its inputs first: ErrorSelectingPlan::InvalidSettings and EntryCount are bad input and fail the whole selection. The facade validates the deployment's capabilities before any stage (asap_planner::SelectionError::InvalidDeploymentCapabilities).
  • Each candidate is then either invalid or valid, recorded as a Rejection with its cause (RejectionCause) and reason: a failed check (AccuracyTargetMissed, CountMinWeightsNotProvenNonNegative, NoAccuracyGuarantee, LatencyBoundExceeded, LatencyOverRepeatInterval (a repeating query's latency per evaluation is over its repeat interval, checked with or without a latency bound), OverClusterCapacity under cost model 3, or CostNotRepresentable (its cost overflows)) or a loss under the cost model (Costlier, Slower, MoreMemory, TiedLostOnEnumerationOrder). Stage 3 never resizes a summary: a candidate whose Stage 1 sizes miss its composed accuracy target is rejected alone.
  • Usage (ResourceUsage) is measured without prices; the CostModel in CostInputs turns it into a choice. Ties keep enumeration order under every cost model.
  • Selection.plan is the selected candidate's roots with the weight requirements Stage 3 confirmed from the data facts.
  • A producer feeds a consumer only in a context it delivers on (PhysicalASAPMemoCandidates::delivers_on). A result stored across evaluations delivers on every context only when it is final, the same at every time it is read. This assumes no row arrives out of order: at evaluation time t, every row with ts <= t has arrived and never changes. A result is final when its group is time-independent and it is kept up to date at ingestion time, or its data is at rest (DataArrival::AtRest), or it reads no source. Any other stored result delivers only on its group's evaluation grid: one computed at query time over arriving rows (Unknown counts as arriving) is a snapshot of its own time, even over a window ending at a fixed E (@ T, ts BETWEEN a AND b), since a context carries no absolute time to compare with E.

6. Ownership

Decision Owner
What a query means the frontend (Stage 0)
Which computations exist and how each may be computed Pass 1
What is shared, split into tumbling windows or reused Pass 2
When each build runs and whether it is kept Stage 2
Which plan is valid and which is chosen Stage 3
What the executor can build, retain and how it is priced the deployment, through PlanningModels (DeploymentCapabilities, CostInputs, AccuracyEvidence)
Running the plan the executor (asap-executor), outside the planner