[Design] Support a Separate Optimization Pass Besides the Current One For Grey-Box Users

[Selvomega]

This issue is one half of #423, which bundled two separate requirements. It is split into a user-facing issue on the single-command interface and a developer-facing issue (this one). #423 is superseded by the two and should be closed.

Problem

Grey-box user or developer requirement: I use ASAPPlanner as an optimization framework with pluggable optimization, not as a magic black box. I want an extension point that specifies only reasonable input and output and makes no assumption about the optimization I want to run. Say, input is pre-ASAP-IR + cost-model + lifecycle-info + accuracy-requirement + blah; output is post-ASAP-DAG + deployment + blah.

Further elaboration: Why a pluggable algorithm is needed. Either task below requires a separate optimization pass:

1. Using the ASAP IR and DAG language, implement other optimization algorithms as baselines for my system.
2. While developing ASAPPlanner, compare the current major algorithm against alternatives to understand what is still problematic in current method.

Further elaboration: Why freedom beyond the e2e type is needed.

1. When implementing baselines, we do not want implementation restrictions beyond the end-to-end input-output language.
2. ASAPPlanner may eventually leave the 2-phase paradigm. Whether we want flexibility for that, or just free exploration of other strategies before formally changing the major (unified) algorithm, we need that freedom.

Illustration: Where this requirement sits.

The grey-box users or developers want the inner box to be pluggable — this issue.

┌─────────────────────── ASAPPlanner -- R1's single command ───────────────────┐
│                                                                              │
│ raw query  (SQL / PromQL / MetricsQL)       other planner inputs             │
│                   │                         cost model                       │
│                   ▼                         lifecycle info                   │
│   ┌───────────────────────────────┐         accuracy requirement             │
│   │ FRONTEND -- not pluggable     │         ...                              │
│   │ parse ▸ bind ▸ canonicalize   │                   │                      │
│   └───────────────┬───────────────┘                   │                      │
│                   │ pre-ASAP IR                       │                      │
│                   ▼                                   ▼                      │
│       ╔═══════════╧═══════════════════════════════════╧══════════════╗       │
│       ║ OPTIMIZATION PASS -- the slot                                ║       │
│       ║ pick exactly ONE of these                                    ║       │
│       ║                                                              ║       │
│       ║ ┌───────────────┐  ┌───────────────┐  ┌───────────────┐      ║       │
│       ║ │    current    │  │    greedy     │  │    my own     │  ... ║       │
│       ║ │    2-phase    │  │      MQO      │  │   baseline    │      ║       │
│       ║ └───────────────┘  └───────────────┘  └───────────────┘      ║       │
│       ║                                                              ║       │
│       ╚═══════════════════════════════╤══════════════════════════════╝       │
│                                       ▼                                      │
│                          post-ASAP DAG + deployment                          │
└───────────────────────────────────────┬──────────────────────────────────────┘
                                        ▼
                        ASAPQuery-backend / ASAPCollector
                    (downstream -- out of this issue's scope)

Current State and Why It Is Unsatisfying

Current optimization is strictly 2-phase: phase 1 generates candidates, phase 2 selects the best among them. New rules can be added, but they must respect that paradigm.

For developers and grey-box users both the hard-coded 2-phase paradigm and the typed rules are manual impediments to plugging in new algorithms.

Example: a new MQO algorithm that greedily merges two queries at a time until nothing is left to merge. Whether we add it as a baseline or use it to understand the current algorithm by comparison, we need it to have the same e2e behavior as the current one. That is cumbersome because:

1. The algorithm has no candidate-generation phase at all. Fitting it into the paradigm is unnecessary (we are NOT saying it is undoable).
2. The restriction that users may only add rules to the current paradigm adds further difficulty.

Both difficulties are manual and unnecessary. This is just one example — mentally extrapolate to algorithms that fit the paradigm even worse.

Diagram illustration below:

TODAY -- the only two places we can plug into
────────────────────────────────────────────
                    ┌───────────── hard-coded pipeline ─────────────┐
    pre-ASAP IR ──▶ │  PHASE 1               PHASE 2                │ ──▶ post-ASAP DAG
                    │  generate   ──▶        select the best        │
                    │  candidates            among them             │
                    │    ▲                     ▲                    │
                    └────┼─────────────────────┼────────────────────┘
                         │                     │
                    add a rule         add a cost model

both slots live INSIDE the 2-phase paradigm


THE ALGORITHM WE WANT TO PLUG IN -- greedy MQO
─────────────────────────────────────────────
    pre-ASAP IR ──▶ merge 2 queries ──▶ merge 2 queries ──▶ ... ──▶ post-ASAP DAG
                    └────── one loop, no phases at all ───────┘

the only supported way in is to disguise the loop as a rule and pretend it has the two phases it does not have.

Proposed Roadmap

For the developer's requirement: define a Rust trait specifying the e2e behavior from pre-ASAP-IR to post-ASAP-DAG, then move the current major algorithm inside by implementing it. Adding a separate pass is then just another implementation of that trait.

Worth noting: the pluggable part's e2e behavior should be IR to DAG, not SQL to DAG. Keep out factors unrelated to optimization.

Pushing-Back's

This section pushes back some potential objections.

"Isn't this over-engineering?"

No, it is not for the following two reasons

1. It is a real need.
2. It needs little engineering or refactoring — ideally just one added layer of unified e2e abstraction. Code may be moved heavily but will not be modified heavily.

"Why not just build the DAG yourself if you want a separate pass? All input and output types are public."

We admit that it is possible, but it not encouraged since it is a hacky rather than a robust and maintainable solution. Specifically,

1. The developer guide's extension map (docs/developer_docs/ASAP-aware-mapping-developer-guide.md， Part 3 §7) has no row for it. Every extension point it lists sits inside the 2-phase paradigm.
2. Those fields are set public because authors want downstream (ASAPQuery-backend, ASAPCollector) to be able to read the contract, not for allowing third parties to author one.
3. Even if we have implemented the hacky solution, there is no official harness in the main repo for registering/integrating separate optimization passes.

So the gap is unsupported rather than impossible.

"Why you are so eager replacing the current algorithm?"

Don't get us wrong. Current algorithm is still good. We just need an extension point with enough freedom alongside it.

Why allowing multiple separate optimization passes to co-exsit? This deviates from the unified solution vision!

We should still end up with one unified algorithm, and the current major algorithm remains the mainstream of development. We are just calling for a unified interface and extension point for other (minor and small) optimizations for baselines or temporary development requirement.