planner-layering.md: the memo through the stages, and the memo to candidate DAGs algorithm #1007

Problem, by example

Example workload: one query, evaluated every minute, with max_error 0.01 and failure_probability 0.001:

avg by (job) (quantile_over_time(0.5, data[5m]) / quantile_over_time(0.5, data[5m]) + quantile_over_time(0.9, data[5m]))

The memo the planner builds for it on main (0f7465c96), measured with LogicalMemo::from_roots, try_populate_pass1 and the expanded_memo test helper:

G2 and G3 are separate groups because share_common_sub_dags (crates/types/src/ir/cse.rs) shares a non-ASAP node only when its schema has a provable unique key, and this per-series quantile's output schema has none.

A reader of docs/design_docs/proposals/planner-layering.md can't predict these tables. The section "The stages over a memo of sub-expressions" says what each stage decides over groups, but it is out of date:

• it names crates/plan-selection/src/search/memo/, brute_force::memo and brute_force::brute_force, which no longer exist;
• it gives no worked example of a memo through the stages;
• it doesn't say how the memo maps back to the vector of candidate DAGs the stage table describes.

Proposal

Rewrite that section. Prose the author wrote elsewhere stays unchanged, and the section cites no PR numbers. It covers:

• Components:
  • LogicalMemo and MemoGroup (Stage 0 hash-consing, including when two equal nodes stay separate groups);
  • CandidateMemo, ImplementationCandidate and CandidateOrigin (which rule adds which candidates).
• The example above through each step: groups, candidates and candidate-DAG counts per step, as the code produces them.
• Algorithm, memo to candidate DAGs: MemoChoice, memo::enumerate and memo::compose, and why the count is not a product over groups (shared groups, fused candidates, groups needed only under some choices).
• Code interface: current paths and entry points.

Scope and acceptance

• Every type, function and path the section cites exists on main.
• The numbers in the example match the stage_pipeline memo-section test.
• Lands after docs(planner-layering): stage inputs and outputs, whole-workload candidates and memo #977 (stage inputs and outputs) and Memo: convert memo-group candidates into the vector of all candidate DAGs #1002.