Skip to content

KLL merge and estimate are charged the same for every k, so equal-cost ties pick a sketch that merges up to 2.8x slower #1361

Closed

Description

@zzylol

Problem, by example

quantile_over_time(0.99, latency[1h]) with a 1% rank target (δ = 0.01), over 1,000 gauge series sampled at 1 Hz, evaluated every 10 s, raw_data_retained: false, default CostInputs, with the measured unit costs of #1355. Stage 2 offers two stored KLL candidates of the same shape (SummaryTumblingWindowChain(10 s) → TimeRange(1h) → SummaryMerge → SummaryEstimate) that differ only in k:

Candidate Predicted cost/s Predicted query ms Measured query CPU per evaluation Measured cost/s Worst rank error
KLL k = 1,404 (selected) 295.66 2,559 5,734 ms 589 0.37%
KLL k = 547 295.66 2,559 2,040 ms 240 0.64%
  • Today: both candidates cost exactly the same, so the MILP picks one arbitrarily. Here it picks k = 1,404 and pays 2.45× the measured cost of k = 547. The same tie costs 1.61–2.05× in three more cells of the same grid (1h × 1 Hz × 60 s, 1h × 10 Hz × 10 s, 5m × 10 Hz × 10 s; all rank target, raw data not kept).
  • Expected: the planner charges the larger k more for its merge and estimate, and picks k = 547 (or a plan measured within 1.05 of it).

Measured on a release build, one pinned core, synthetic exponential latency data; the cost is cost model 1's illustrative prices applied to measured CPU and memory.

Why it happens

  • merge_operations_per_state (crates/cost/src/node/operations_per_unit.rs) charges every KLL state the flat KLL_MERGE_OPERATIONS_PER_STATE = 7,000, whatever k. KLL_ESTIMATE_OPERATIONS_PER_GROUP = 35,000 is flat too.
  • The state bytes are also equal: each 10-row window holds far fewer items than either k, so sketch_shape charges both the same bytes.
  • The executor's merge cost grows with the items the merged sketch holds, which grow towards k: merging 360 windows per series into one sketch takes 1.7 ms per series at k = 547 and 4.8 ms at k = 1,404 (1.7 s against 4.8 s per evaluation over 1,000 series). Over the 4 cells, the larger k merges 1.9–2.8× slower.

Proposal

  • Charge a KLL merge by the items the merged (output) state holds, min(KLL capacity at k, rows merged so far), with a measured per-item constant; charge the estimate by the same item count.
  • Alternative: break exact cost ties toward the smaller sketch parameter. This fixes the tie but not the magnitude, so a larger k would still be under-charged against other plan kinds.

Scope and acceptance

  • In scope: the KLL SummaryMerge and SummaryEstimate CPU charge.
  • Acceptance: a cost test where the k = 1,404 candidate of the example is charged more than the k = 547 one for the same merge, and the four cells above select k = 547 or an arm measured within 1.05.

Related

Activity

  1. added
    bugSomething isn't working
    cost-modelCost formulas, statistics, ranking, and selection
    on Nov 16, 2026
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    bugSomething isn't workingcost-modelCost formulas, statistics, ranking, and selection

    Type

    No type

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions