Design the extension contract for new ASAP primitives and sketch algorithms

[zzylol]

Following #509, we need a complete design document explaining how to add a new ASAP primitive, sketch algorithm, or related summary algorithm to ASAPPlanner.

Fundamental assumption

The algorithm and its replacement strategy are supplied by an algorithm developer, not invented by ASAPPlanner. The developer supplies the algorithm's semantics, applicability conditions, guarantees, and implementation knowledge. ASAPPlanner represents that knowledge, generates and combines legal alternatives, and selects plans using workload requirements, capabilities, and evidence.

Adding an algorithm must not require treating all its properties as one inseparable strategy or operator. The design must separate the following contracts.

A. Supported aggregation intents

• Which statistics/computations the algorithm supports and under what input, grouping, and domain assumptions.
• Window/time behavior, including temporal scope and any ordering or update assumptions.
• Accuracy guarantees, parameterization, and evidence needed to admit a result.
• How one algorithm can support multiple intents and how an intent can have multiple algorithm implementations.

B. Operations in the logical ASAP DAG

• Which existing summary operations the algorithm can implement, such as build/update, merge, evaluation, subtraction, or deletion, with explicit preconditions and compatibility rules.
• Whether it requires a new logical summary operation, and the criteria for adding one rather than encoding an implementation detail in the logical DAG.
• How algorithm-developer-provided replacement strategies map ordinary computation to these operations and compose with existing strategies.
• Schema, typed-state, and identity contracts, referencing the universal ASAP primitive table design in Design a universal ASAP primitive table: schema, physical data, and summary state #545.

C. Materialization and execution timing

• Whether outputs/state can be materialized, retained, reused, restored, or rebuilt, and what capabilities/metadata those choices require.
• Whether any ingestion-time-only restriction is a genuine semantic/implementation constraint or merely an efficient usage pattern. Document query-time reconstruction/evaluation where legal, even if costly.
• Keep feasibility distinct from cost: an expensive legal alternative is not automatically unsupported.
• Explain how these capabilities feed the materialization/timing exploration in docs: propose workload-wide planning, summary sharing, and materialization #509, rather than hard-coding one placement in the replacement strategy.

D. Physical operator implementation

• The concrete physical operators/kernels, runtime state representation, supported input/output layouts, codecs/versioning where needed, and deployment bindings.
• How multiple physical implementations can satisfy the same logical operation and algorithm contract.
• Capability registration, cost/accuracy evidence, validation, execution, and failure behavior.
• Ownership boundaries between the algorithm developer, ASAPPlanner/shared runtime, and deployment/storage integrations.

End-to-end examples and acceptance

Provide concrete API/type sketches and a complete extension walkthrough from developer-supplied algorithm/strategy through registration, workload matching, logical candidates, physical/materialization alternatives, selection, and execution with expected results.

Include:

1. An algorithm using existing aggregation intents and logical summary operations.
2. An algorithm that genuinely requires a new operation or capability, explaining why and what changes.
3. A legal ingestion-time versus query-time/materialization comparison, with assumptions and costs made explicit.

The document must identify the implementation/test changes required, link to executable examples where available, and mark unimplemented proposals. It should let an algorithm developer add support without conflating aggregation semantics, logical operations, materialization decisions, and physical implementation.

References: planning architecture in #509, and #545 for the schema/physical-data/summary-state contract.