[Design] Support Adding Separate Optimization Pass Besides the Current One

[Selvomega]

This issue should be deprecated since it is now decoupled into #429 and #430

=============== ! NO NEED TO READ THE FOLLOWINGS ! ===============

Problem

Two kinds of users are underserved:

1. R1 - Black-box user: I want one command that takes all the input I prepared and gives me the optimal DAG.
2. R2 - Grey-box user or developer: 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.

Elaboration for R2: 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.

Elaboration for R2: Why freedom beyond the e2e type is needed.

1. When implementing baselines, I 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 do the two requirements sit.

As shown in the following diagram:

1. R1's single command has to cover the whole outer box.
2. R2 means that we want the inner box to be pluggable.

┌─────────────────────── 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 black-box users there is no one-command solution.

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 I add it as a baseline or use it to understand the current algorithm by comparison, I 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 (I am 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 I 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 I WANT TO PLUG IN -- greedy MQO
─────────────────────────────────────────────
    pre-ASAP IR ──▶ merge 2 queries ──▶ merge 2 queries ──▶ ... ──▶ post-ASAP DAG
                    └────── one loop, no phases at all ───────┘

phase-1 slot?  nothing here generates a candidate set.
phase-2 slot?  nothing here picks one alternative out of many.

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

Proposed Mental Roadmap

For the user's requirement: add a new binary wrapping everything.

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.

Why this is not over-engineering:

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.

What I Am NOOOOOT Proposing

Not demolishing the current 2-phase algorithm. It is still good; we just need an extension point with enough freedom alongside it.

Not diverging on optimization algorithms. We should still end up with one unified algorithm, and the current major algorithm remains the mainstream of development. I am calling for a unified interface and extension point for other (minor and small) optimizations.