Memo: identical derived producers are duplicated, so a shared finalized result or top-k cannot be stored once #979

Problem, by example

Two exact PromQL queries over m: 1,000,000 series, one sample every 15 s, 100 jobs, 15 minutes of rows held. Both are evaluated every minute. The test is rollup in crates/integration-tests/tests/memo_covers_whole_workload_pass2.rs.

sum by (job) (m)             # q0, the coarse sum
sum by (job, instance) (m)   # q1, the finer sum q0 can be read from

Both plans come from the same logical rollup: q0 reads q1's per-(job, instance) sums. They differ in what can be stored:

• The whole-workload winner finalizes q1's exact accumulator once (FinalizeExactAccumulator, node 3), stores those finalized rows, and has q0's rollup read them.
• The memo's plan keeps the summary state (node 2) and builds two identical FinalizeExactAccumulator { child: 2 } nodes (3 and 6): one inside the rollup candidate and one inside q1's own candidate. So "store the finalized rows once, read them twice" cannot be expressed. The memo's cost equals the whole-workload plan with the same rollup but the other materialization (fixture-3, 0.0137854).

A longer search does not help; the memo cannot express the cheaper plan.

The same pattern shows up in exact top-k reuse (topk_reuse in the same file):

topk by (job) (5, rate(m[1m]))
topk by (job) (10, rate(m[1m]))

The memo's plan stores the full Sort and builds two identical Limit(10) nodes over it (5 and 8), plus a redundant Limit(10) over Limit(10). The shared top-10 producer is never one node.

Why it happens

• A memo rule that reads another group's result puts the derived node (the finalize, the Limit(k_max)) among its candidate's private nodes, under the shared child group.
• The reader's own candidate builds an equal node privately too.
• Private nodes are not hash-consed across candidates, so Stage 2 sees two producers and can store neither one for both readers.
• The whole-workload path rewrites one whole DAG, where identical nodes are interned once, so it can.

Proposal

Intern derived producers as memo groups, so that equal derived nodes over the same child group are one group with several readers. Two places to do it:

• Where a rule creates the node: append_producer already does this for the top-k ranking's Sort and Limit(k_max). Check why the plan still duplicates them, and extend the same treatment to the rollup's finalize.
• After all rules run: hash-cons the candidates' private nodes, turning equal private subtrees over equal child groups into shared groups. Do this before Stage 2, so materialization can choose to store such a group once.

Then Stage 2's existing "two or more readers → MatAtQuery/stored" choice applies to it.

Scope and acceptance

• Acceptance: rollup and topk_reuse in memo_covers_whole_workload_pass2.rs pass, with the memo costing no more than the whole-workload path, and their #[ignore] is removed.
• No change in selected plans or costs on the other memo suites.
• Blocks: deleting the whole-workload Pass 2 (Reorganize by stage: one memo-based Pass 2, Stage 1 finishes the memo, deployment inputs split by stage, asap-planner as the only entry point #958 step 4).

Related

• Reorganize by stage: one memo-based Pass 2, Stage 1 finishes the memo, deployment inputs split by stage, asap-planner as the only entry point #958 (one Pass 2)
• One shared-producer rule: cover every reader's need, derive each reader (top-k, summary size, panes, ranks, …) #954 (shared-producer rule)
• PR test(optimizer): check the memo search against the whole-workload Pass 2 #975 (the differential test)