[Bug] Stage 3 sizes a sketch's memory by its full capacity, not by the samples it holds #726

Example

#509 Example 4, Pattern B (pattern_b() in crates/devtools/src/planner_layering_examples.rs):

quantile_over_time(0.99, latency_ms[5m])   # every minute, rank error 0.01 at δ = 0.01

The data workload is 1,000,000 series arriving at 66,667 samples/s, one sample per series every 15 s. So a series has 20 samples in a 5-minute window and 4 in a 1-minute pane.

Plan selection (Stage 3) sizes every KLL state by the sketch's full capacity. This is summary_shape → 8 * kll_items(k), which sums max(ceil(k·(2/3)^i), 8) over all 61 levels. For this query that is 17,768 bytes per state. Numbers from stage_pipeline --example planner-layering-3b at #723:

So the sketch candidates look 100x to 500x larger than the values they hold. This flips decisions:

• Cost model 2 (provisioned capacity) selects P1 because P2's peak "17.8 GB" costs 3,221/s against P1's 1,024/s.
• Cost model 3 (own cluster) with 64 GB rejects B1 and B2 (P3) as over memory.
• Cost model 1 (usage over time) prices B1 at 13,326.53/s for "107 GB" of panes kept every second.

What should happen: a state's retained size should be capped by what it can hold, min(capacity, samples per state) × item size, at least for the KLL family.

Current behavior

price in crates/asap-aware-mapping/src/stage3_plan_selection.rs sets a SummaryAgg or PaneChain output to group_count × state_bytes, where state_bytes comes from summary_shape(family) and depends only on the sketch parameters. The rows the state absorbs (input.rows / group_count per state, or per pane) do not enter the size.

This mirrors the library as pinned (asap_sketchlib rev 3f44cf1). KLL::init_internal allocates vec![T::default(); compute_max_capacity(k, m)] up front, so today a KLL over 20 samples really does allocate its full capacity. The same pin also has KLLDynamic (sketches/kll_dynamic.rs), which starts from a 3·k-item buffer and grows.

Expected behavior and invariant

A summary state's modeled memory is at most what the library allocates for the samples it holds. Each family (KLL, DDSketch bins, KMV/Theta) is sized by min(capacity, samples per state) items, and fixed-size families (CMS, Count Sketch, HLL) keep their full size.

Options:

1. Cap in the model and run a growing implementation (KLLDynamic, or make KLL allocate lazily upstream), so the model and the runtime agree.
2. Cap in the model only. This understates memory with today's eager KLL, so it is acceptable only together with option 1.
3. Keep the full capacity and document it as the worst case. This leaves the Example 4 decisions as they are.

Per the rule to use asap_sketchlib implementations, any allocation change goes upstream or through the pin, not into a local copy.

Minimal reproduction

stage_pipeline --example planner-layering-3b --cost-model provisioned-capacity --out run.json
# stage3_plan_selection.costs.P2.usage.peak_memory_bytes = 17768000096

Impact

Cost models 2 and 3 rank by peak memory, and cost model 1 prices kept memory. Every Example 4 choice that involves a KLL over a sparse series depends on this overstatement: cost model 2 selecting P1, cost model 3 rejecting B1 and B2 at 64 GB, and cost model 1 pricing B1 at 13,326.53/s.

Regression test

In stage3_plan_selection tests: a per-series KLL over 20 samples per state has peak_memory_bytes of at most groups × 20 × 8 plus fixed overhead, not groups × 8 × kll_items(k). The test fails today.

End-to-end verification

Rerun stage3_plan_selection_b_cost_models_choose_differently in crates/integration-tests/tests/planner_layering_example4.rs and update the expected choices, with the new figures in the PR body.

Status and related work

Found in the review of #723 (cost models 1–3). That PR lists it under Limitations, and its Example 4 results depend on it. Related: #683 (cost models 1 and 2), #660 (cost model 3), #509 Example 4.