asap-aware-mapping: Cascades/Volcano-style candidate-plan search engine over ReplacementStrategy

[zzylol]

Part of #33.

What

Implement the Cascades/Volcano-style candidate-plan search docs/asap_aware_mapping.md has stubbed as pseudocode since #206/#211 ("Pseudocode for Replacement Plan Searching (not yet implemented)"), driven by the ReplacementStrategy trait from the sub-issue that generalizes Implementation/CSE selection.

Design

Fixed-point search over the workload's pre-ASAP roots (after rewrite + CSE, see the other sub-issues under #33):

candidate_plans = { input_workload_plan }
loop:
    new_plans = {}
    for plan in candidate_plans:
        for site in plan.bindable_sites():       // every TargetSubDAG in this plan
            for strategy in registered_strategies:
                if strategy.matches(site):
                    for replacement in strategy.replacements(site):
                        new_plans += substitute(plan, site, replacement)
    new_plans -= candidate_plans   // dedup
    candidate_plans += new_plans
until new_plans is empty

return candidate_plans.sorted_by(cost_model)

Two things to get right that the doc's original pseudocode leaves open:

1. Dedup must be structural-hash-based, reusing pre_asap::cse's existing InternTable/structural_hash machinery (hash as a filter, PartialEq as the actual decision — same non-negotiable rule cse.rs already documents), not Vec containment on a full plan.
2. MEMO-style sharing across candidate plans, not a flat plan list. A naive "list of whole candidate plans" duplicates every untouched sibling subtree across every candidate — a workload with N independently-choosable sites produces up to 2^N flat plans. Represent each distinct TargetSubDAG as a MEMO group holding its alternative ReplacementSubDAGs (the actual Cascades data structure), so two candidate plans that differ at only one site share every other node by Rc, the same way share_common_subtrees already shares identical subtrees today.

Cost-based selection

The final sorted_by(cost_model) step is the existing CostModel/asap-plan-external extension point — this issue is scored on producing the correctly-deduped candidate space, not on shipping a real cost function (no deployment cost model exists in this crate today, by design — see cost_model.rs's own doc on why).

Depends on

The ReplacementStrategy sub-issue (needs the trait to search over). Blocks: making the semantic-rewrite, roll-up, and SharedMultiSubpopulation sub-issues actually reachable by a real search rather than each needing its own bespoke "is this better" heuristic.

Reconciling with docs/cse-cost-model-decision.md (#237)

That decision explicitly chose a direct cost comparison over "full Volcano/Cascades-scale infrastructure" for one binary, single-candidate-pair decision (share a CSE'd subtree or don't), reasoning that "this repo has no plan-enumeration/DP-search engine anywhere" and didn't need one for that narrow question. This issue is where that stops being true — not a contradiction of #237's reasoning, but the scope change #237 itself flagged as the reason a full engine wasn't needed yet: once multiple interacting axes exist (sketch family/kind, roll-up vs. recompute, SharedMultiSubpopulation vs. per-key, semantic rewrite) at once, a per-decision-point heuristic can't see interactions across sites the way a real candidate-plan search can.

CostModel::cse_share_decision's existing recompute-vs-maintenance comparison doesn't get thrown away — it becomes the cost function backing SharedSubtreeStrategy's two ReplacementSubDAG candidates (share vs. recompute-independently) in this engine, so the search's final sorted_by(cost_model) step reuses it rather than re-solving the same comparison a second way.

[zzylol]

Related open work

• Core search-engine work under optimizer umbrella Add logic to detect which optimizations are applicable to a query workload #33.
• asap-aware-mapping: rebuild applicability.rs findings as a view over the search's candidate-plan space #257 should rebuild applicability reporting over this search space.
• The physical degrees of freedom enumerated in Tracking issue for "degree of freedom" we should add when converting from L3 to L4 #152 become candidate families consumed by this search.
• Cross-consumer accuracy reconciliation is tracked separately by Cross-consumer accuracy reconciliation for CSE sharing (near-duplicate AggIntents with different AccuracyTarget) #273.

[zzylol]

Closing as completed after a current-code audit.

Evidence:

• search_workload / search_workload_with build a workload-wide PlanSpace.
• PlanSpace stores one pointer-identity-keyed MemoGroup per discovered TargetSubDAG, avoiding a flat exponential whole-plan list.
• rewrite dedup uses structural_hash only as a filter and PartialEq as the decision, with explicit preservation of share-vs-recompute identity.
• search runs CSE first, discovers targets, applies registered strategies in a bounded fixpoint frontier, discovers targets exposed by rewrites, and integrates workload-dependent roll-up/top-k reuse strategies.
• PlanSpace::cost_sorted exposes per-group cost-model ranking; global_selection subsequently adds interacting whole-workload selection.
• asap-aware-mapping: rebuild applicability.rs findings as a view over the search's candidate-plan space #257, the reporting-view follow-up blocked on this issue, is implemented and closed.

The implementation evolved from the issue pseudocode into a MEMO group/fixpoint design, but satisfies the stated structural sharing, deduplication, extensibility, and cost-ranking goals.