Prune the candidate search space early without discarding a possibly-best valid plan #673

Problem

plan_stages, the planner pipeline facade from the upper-stack consolidation (G1), enumerates every combination of per-computation candidates, then composes, physically optimizes and prices each one before plan selection picks one. This is deliberate for now: there is no cap, and selection always runs over the full set. But the number of combinations is the product of every target's candidate count, so it grows exponentially with the number of targets. For example, Example 3a already has 243 combinations, and a dashboard with dozens of aggregations would have millions.

Goal

Shrink the search space early, without ever discarding a candidate that could be the best valid plan. That is #509's rule: only plan selection may discard valid candidates, and any earlier pruning must remove only candidates that are provably invalid or provably dominated.

Directions to evaluate

• Prune per target before taking the cross product. Drop a candidate that can never meet its target, for example one with no possible guarantee and no deployment evidence under an exact target. Each prune records a reason.
• Dominance pruning. Within a target, drop a candidate that costs at least as much as another candidate with at least the same guarantee, for every consumer. This is only safe when its cost and accuracy don't depend on choices made for other targets. Sharing (Pass 2) and materialization (Stage 2) make it conditional.
• Decompose independent targets. Targets that share no sub-DAG and no materialization decision can be optimized separately and combined, so their costs add instead of their choice counts multiplying. Only shared parts need joint enumeration.
• Branch and bound. Enumerate in cost order, and stop expanding a partial plan once a lower bound on its cost exceeds the best complete valid plan found so far.
• Exact DP over shared nodes, or a MILP. See the survey in Planning roadmap: move ASAPQuery planning into ASAPPlanner, MILP plan selection over shared DAGs, benchmark-based accuracy #671: fix the choices at shared nodes, then run an exact DP on the tree-shaped rest; or formulate a MILP.
• Report the size first. Report the combination count before enumerating, so a caller knows how big the search space is.

Done when

• Workloads with many targets plan in bounded time.
• On every workload where full enumeration is feasible, the selected plan is identical to the one full enumeration selects. A test compares the two on Examples 1–4 and on generated wide workloads.
• Every pruned candidate carries a reason.

Related: #509, #671 (plan-search survey: DP, Cascades, MILP), #576 (plan selection), the G1 facade.