Tracking: plan every whole evaluation workload within 3 minutes (exact pruning, memo-group search) #879

Problem, by example

The paper's evaluation workloads do not plan under the default search in reasonable time. Measured on origin/main (default search, raw data retained, cost model 1, 56-core server):

With the exact pruning in progress (dominance plus interchangeable candidates, branch feat/joint-search-dominance), quantiles-24h@60s drops to 153k candidates in 92 s. Whole W-RollupHeavy still has no plan after 25 min.

Goal: every whole paper workload (W-RangeHeavy, W-RollupHeavy, W-Mixed, and the 8-user versions) plans under the default search within 5 minutes, and selects the same plan as --exhaustive would.

Why it happens

• Stages 1–3 hand whole-plan candidates downstream. Each candidate's physical DAG is built and priced by Stage 3, at about 0.6–1 ms each (profile on quantiles-24h@60s). The count is the cross product of every query's choices within a component.
• Components no longer split the work. A shared scan built once per evaluation (feat(stage2): offer a shared non-summary node built once per evaluation #855), SQL windows as TimeRange (fix(sql): lower a trailing window on the time index to a TimeRange (panes, ingestion-time builds, window-priced scans) #866) and sketch rollup (feat(pass2): coarse sketch groupings roll up from the finest build (sketch rollup, part 2) #869) link most queries over one source into one sharing component.
• Identical queries, quantiles that differ only in q, pane-chain variants (per-query, finest-width, gcd-width) and widened scans each multiply the space, even when most variants can never be part of the best plan.

Proposal

Exact pruning first, then a memo-group search:

1. Exact pruning (v5).
   • Merge interchangeable candidates: identical queries, and quantiles over the same input and window that differ only in q.
   • Drop a variant that another variant in the same sharing group matches or beats on every usage component (CPU, scanned bytes, memory byte-seconds, peak memory, disk, each reader's latency).
2. Memo groups.
   • One group per hash-consed logical sub-expression or target.
   • Each group enumerates its own alternatives once and references child groups instead of taking cross products of whole plans.
3. Cheapest per sharing signature.
   • A candidate's sharing signature is the shareable nodes it builds or reads: family, sizing-relevant parameters, timing, pane grid.
   • Within a group, keep the cheapest candidate per signature, priced locally and cached per group.
   • A candidate whose signature nothing else can use collapses to the group's single cheapest. Where a group shares nothing, the local optimum is the global one.
4. Joint choice only inside sharing clusters.
   • Enumerate signature combinations (exact DP or branch and bound) only among groups that can share a node.
   • A shared node is priced once, sized for its strictest reader.
5. Build late. Build the full physical DAG and run the executor compile check only for the selected plan and a few runners-up.

The memo work lands behind the current search until a switch-over PR, so main never regresses.

Scope and acceptance

• In scope: the search between Stage 1 and Stage 3 selection, its caches, and the joint-search design doc.
• Out of scope: approximate or heuristic caps. Any rule not proven exact is listed as a follow-up instead of merged.
• Acceptance:
  • joint_search_equivalence (against --exhaustive) passes, including the ignored slow tests;
  • each whole paper workload plans within 5 minutes under the default search;
  • the planning time, peak RSS and candidates checked are reported per workload.

Tasks

• Exact pruning v5: dominance plus interchangeable candidates (branch feat/joint-search-dominance)
• Design and interfaces for memo groups, sharing signatures, local pricing and the cluster solver (joint-search design doc)
• Memo structure plus Stage 1/2 enumeration into groups
• Per-group, per-signature pricing and caching (local dominance)
• Joint selection inside sharing clusters; build and compile-check only the selection
• Switch-over: the default search uses memo groups; equivalence and timing acceptance
• Re-run the paper workloads whole and update the evaluation report

Status and related work

• 2026-10-22: the 3-minute target and the memo-group direction were decided. Each group enumerates its own candidates and keeps the cheapest wherever that does not hurt sharing.
• Related: Prune the candidate search space early without discarding a possibly-best valid plan #673 (prune the candidate space early), docs: ASAPPlanner memo-based joint optimization with MILP #776 (design: exact pruning for joint planning search), Planning roadmap: move ASAPQuery planning into ASAPPlanner, MILP plan selection over shared DAGs, benchmark-based accuracy #671 (planning roadmap), asap-aware-mapping: Cascades/Volcano-style candidate-plan search engine over ReplacementStrategy #252 (earlier Cascades-style search engine, closed), Pass 2: shared window grids (group-wide panes and long-window segments) #731 (pane sharing), feat(stage2): offer a shared non-summary node built once per evaluation #855, fix(sql): lower a trailing window on the time index to a TimeRange (panes, ingestion-time builds, window-priced scans) #866, feat(pass2): coarse sketch groupings roll up from the finest build (sketch rollup, part 2) #869.