Tracking: restructure ASAPPlanner tests around layers and independent oracles #1253

Problem, by example

Example 1: a cost bug no test catches. o11y q21 is a range query over an offset:

sum_over_time(m[5m] offset 1h)   # every 60 s; a 60 s tumbling-window chain is selected

Before the fix in #1237 (#1207 PR 7), the selected plan's TimeRange 5m over TimeShift 1h over the chain was costed as if it read raw rows. Its cost line said merge 1000 states into 1000; the 5 windows it selects should give merge 5000 states into 1000. The plan cost was 0.8939/s instead of 0.9020/s, from asap_planner --run-until stage3 on the o11y snapshot. Every test passed, including the MILP objective = plan_cost equality test. Stage 3 and plan_cost call the same node_resource_usage_and_cost, so they were equally wrong and the equality still held.

Example 2: a design change fails a large share of the suite. During the #1207 stack, PR 4 (#1234) ran 1160 passed / 188 failed / 9 ignored, and the failures were carried up the stack. Most failures were full-pipeline tests asserting what a later PR changes. A real regression among 188 expected failures is easy to miss.

Why it happens

• No independent oracle. Tests check the planner against itself: equality between two costings that share code, or plans pinned by hand. No test computes an expected cost by hand from the concepts doc formulas. No test executes the selected plan and compares its answers with an exact evaluation.

• The core stages have few unit tests. Test counts per crate at refactor: tools and snapshots over the #1207 memo, edges and contexts (#1207 PR 9) #1239's head (#[test] + #[tokio::test]):

  Part	Tests
  frontends (PromQL, SQL, MetricSQL incl. vendored parser)	~720
  executor	281
  types	200
  Pass 1 / Pass 2 / Stage 2 / Stage 3	32 / 26 / 13 / 15
  integration-tests (each runs the whole pipeline)	156
  devtools (snapshots, fuzz, CLI)	92

  Rules are mostly covered only through the whole pipeline, so one design change turns many tests red without pointing at a rule.

• Assertions are on shapes, not properties. Exact plans, candidate counts and selections live in hand-written tests as well as in snapshots.

• Some test helpers bypass the production lowering, which has produced wrong conclusions before (for example, dropped series identity).

• Slow tests. The heap top-k reference test takes 233 s in a debug build and is now ignored.

Goal

1. Layers, each asserting one kind of thing:
   • Rule unit tests in each stage crate: a minimal memo plus one rule, built with a shared builder through the production frontends and Stage 0.
   • Contracts: invariants checked on every corpus workload:
     • ids resolve, and every candidate's inputs exist;
     • every selected edge is logically and physically admissible;
     • MILP objective = plan_cost;
     • costs are ≥ 0;
     • every query root is served;
     • (K) holds on the plan.
   • Oracles, independent of the planner's own costing:
     • hand-computed costs for canonical shapes (Scan, chain, offset range, merge);
     • execution of the selected plan on synthetic data, compared with exact evaluation (exact queries equal; approximate queries within ε for at least 1 − δ of values, checked empirically);
     • exhaustive search on small workloads, compared with the MILP.
   • Metamorphic relations, with fixed seeds from planner_fuzz:
     • adding a query never lowers cost;
     • tightening accuracy never lowers cost;
     • duplicating a query adds ≈ 0;
     • scaling rates scales cost as expected.
   • Regressions: one minimal workload per issue, with a name that states the behavior.
   • Snapshots: the only place that pins full plans and costs. One command regenerates them, and a PR lists old → new costs.
2. One corpus registry read by contracts, snapshots and fuzz: o11y, MVP, the planner-layering examples, and the ASAPWorkloads workloads that run in-repo.
3. Tiers by marker, fast / full / nightly (fuzz, exhaustive search, execution oracle, planning-time trend recorded but not asserted). CI wiring is owned separately; these PRs only mark tests.
4. Stack hygiene: a stacked PR carries no newly failing test. It either fixes the test or marks it #[ignore = "<issue or PR>"] with the reason.

Plan (one PR each)

T0 → T1 → T2 → T4 are stacked on top of the #1207 stack (on #1239), in that order, and are not inserted inside it. They mostly add new files, so restacks of the #1207 PRs carry them along, and their oracles check the #1207 code before it merges. A bug they find is fixed in the #1207 PR that introduced it; the test PR only adds the test. T3 and T5 edit files the #1207 PRs still change, so they start from main after the stack merges.

• T0: testing strategy doc (docs/develop_docs/testing.md): the layers and what each asserts, the oracles, naming, ignore policy, tiers, and a coverage matrix. The matrix crosses query language × operator (aggregation, quantile, topk, distinct, rate, binary operations, offset, @, subquery) × time shape (instant / range / repeating) × accuracy (exact / ε) × data facts (cardinality known or unknown, ordering) × deployment capabilities, each cell naming its test.
• T1: shared infrastructure.
  • The corpus registry.
  • Workload builders that go only through the production path (the memo builder for rule unit tests moves to T5, with its first caller).
  • Delete the duplicate helpers.
• T2: contracts suite, replacing scattered per-test checks of the same invariants.
• T3: classify the 156 integration tests. Each is turned into a stage unit test, turned into a property assertion, folded into a snapshot, kept as a regression, or deleted as a duplicate. T3 also deletes the integration tests' own planning helpers fixtures::lower_promql (which drops the series identity) and run_all_stages, moving their callers to T1's registry builders. The PR body has one table row per test with its reason. Start with the tests that failed in every Tracking: implement the optimization formulation (memo candidates, properties, edges y_{u,c,i}, MILP) as named code per stage #1207 design round; the per-PR failure lists are in that stack's test logs.
• T4: oracles.
  • Hand-computed costs first; Example 1 must fail without the refactor(stage3): select over execution contexts: x_{κ,v}, y_{κ,u,c,i}, h_v and constraint (R) (#1207 PR 7) #1237 fix.
  • Then the execution oracle on synthetic data.
• T5: rule unit tests for Pass 1, Pass 2, Stage 2 and Stage 3, filling the coverage matrix's gaps, with a memo builder for them (a minimal memo plus one rule, built through the production path). Add an exhaustive search on small workloads compared against the MILP. Add the two metamorphic relations planner_fuzz does not check yet: tightening accuracy never lowers cost, and scaling a source's rate scales the cost it drives.

Scope and acceptance

• In scope: test structure, test infrastructure, new oracles, the strategy doc, and deleting redundant tests.
• Out of scope: CI configuration, and planner behavior changes. A bug an oracle finds gets its own issue and fix PR.
• Done when:
  • every corpus workload passes the contracts;
  • hand-computed cost tests cover the canonical shapes, including Example 1, which fails on the pre-fix code;
  • the execution oracle runs on synthetic data for exact and approximate queries;
  • every integration test is classified;
  • the fast tier runs in minutes.

Status and related work

• Decided (2026-11-10):
  • this plan and its PR order;
  • synthetic data for the execution oracle in the first version;
  • T3 deletes duplicates with a per-test reason in the PR body.
• Decided (2026-11-10): T0, T1, T2 and T4 are stacked on refactor: tools and snapshots over the #1207 memo, edges and contexts (#1207 PR 9) #1239; T3 and T5 wait for the Tracking: implement the optimization formulation (memo candidates, properties, edges y_{u,c,i}, MILP) as named code per stage #1207 stack (docs(concepts): memo groups, properties, requirements, per-stage interfaces and rules #1224, refactor: define every stage's interfaces from #1207 and delete the ones they replace (#1207 PR 0) #1226–refactor: tools and snapshots over the #1207 memo, edges and contexts (#1207 PR 9) #1239) to merge. Each test PR gets an independent review by a reviewer that did not write it.
• Related:
  • Tracking: implement the optimization formulation (memo candidates, properties, edges y_{u,c,i}, MILP) as named code per stage #1207 (formulation refactor);
  • refactor(stage3): select over execution contexts: x_{κ,v}, y_{κ,u,c,i}, h_v and constraint (R) (#1207 PR 7) #1237 (the q21 cost fix in Example 1);
  • test: ignore every test whose result depends on a wall-clock budget or deadline (#1067) #1180 (wall-clock tests ignored).