asap-aware-mapping: define optimization strategies, cost model, and nested-summary error propagation

[zzylol]

Context

Follow-up to PR #298, which reorganized the ASAP-aware mapping design documentation. The reorganized docs describe the current concepts and plan search, but several foundational design questions remain open before the documentation can serve as an implementation contract.

This is an umbrella/design issue. It should align with the existing candidate-plan search work in #252 and whole-plan cost-based selection in #271, while avoiding duplicating their implementation scope.

Scope

1. Optimization and replacement strategies

Document and prioritize additional optimization/replacement strategies beyond the currently described set. For each strategy, specify:

• the applicability conditions and required statistics/capabilities;
• the input and output summary families or physical representations;
• the accuracy and semantic guarantees;
• state, update, readout, and maintenance implications;
• whether the strategy composes with nested summaries and shared subplans.

Define the algorithm used to search for the minimum-cost plan when these strategies are available, including candidate generation, pruning/dominance rules, shared-state accounting, and how the search handles incompatible accuracy targets. State the asymptotic and practical complexity in terms of query/DAG size, number of strategies, and candidate-plan count, including any approximation or bounded-search mode.

2. Cost definitions

Add a canonical cost vocabulary and definitions for the dimensions used by planning and strategy comparison, such as:

• ingestion/update and maintenance cost;
• query/readout and merge cost;
• state/storage cost;
• raw recomputation or scan cost;
• network/materialization cost where applicable;
• one-shot versus recurring workload cost.

Each cost should define units, scope, aggregation rules, required inputs, uncertainty/unknown handling, and provenance/model version. Add an optional summary-family cost reference documenting the expected cost components and formulas for each supported exact/sketch/structured summary family.

3. Nested-summary accuracy and error propagation

Add a design document for composing accuracy guarantees when a summary consumes another summary, including exact-over-approximate, approximate-over-exact, and approximate-over-approximate cases. Define:

• the guarantee types and error domains/norms;
• propagation rules for merge, arithmetic, filtering, aggregation, and nonlinear operators;
• independence/correlation assumptions and shared error sources;
• budget allocation across nested plans;
• fail-closed behavior when no sound propagation rule exists;
• distinction between deterministic, probabilistic, and posterior/empirical evidence.

The design must explain how propagated guarantees affect candidate legality, strategy selection, serialization, explainability, and DAG export.

Deliverables

• Update docs/design_docs/asap-aware-mapping/README.md with links and status for the resulting documents.
• Add focused design docs for strategy search/complexity, cost definitions (with summary-family coverage where useful), and nested-summary accuracy/error propagation.
• Cross-link the docs to the relevant implementation/tracking issues, especially Propagate end-to-end accuracy guarantees for approximate-over-approximate plans #172, asap-aware-mapping: Cascades/Volcano-style candidate-plan search engine over ReplacementStrategy #252, asap-aware-mapping: whole-plan (cross-group) cost-based selection over the search's candidate-plan space #271, and Advanced nonlinear and correlation-aware error propagation #297.
• Keep terminology consistent with the existing ASAP-aware mapping documents.

Acceptance criteria

• Every documented strategy has explicit applicability, guarantee, and cost metadata.
• The optimal-cost search algorithm and its complexity are stated precisely enough to guide implementation and testing.
• Cost definitions use consistent units and do not encode unknown inputs as zero.
• At least one cost table or formula set covers each currently supported summary family, or explicitly records why a family is not yet estimable.
• Nested-summary examples show sound propagation and identify cases that must remain unsupported/fail closed.
• The README index links all new documents, and all links resolve.

Related

• PR docs: reorganize ASAP-aware mapping documentation #298 — reorganizes the ASAP-aware mapping design documentation.
• asap-aware-mapping: Cascades/Volcano-style candidate-plan search engine over ReplacementStrategy #252 — candidate-plan search engine over ReplacementStrategy.
• asap-aware-mapping: whole-plan (cross-group) cost-based selection over the search's candidate-plan space #271 — whole-plan cost-based selection over candidate plans.
• Propagate end-to-end accuracy guarantees for approximate-over-approximate plans #172 — baseline end-to-end accuracy guarantees for approximate-over-approximate plans.
• Advanced nonlinear and correlation-aware error propagation #297 — advanced nonlinear and correlation-aware error propagation.