Skip to content

[Bug] DDSketch memory is charged at the 1e9 value-range bound, about 6.4× what the executor holds #1313

Open

Description

@zzylol

Example

quantile_over_time(0.99, latency[1h]), 1% relative error at δ = 0.01, evaluated every 60 s over 1,000 gauge series sampled at 10 Hz. The latency source is declared column_signs: {"value": "non_negative"}. Default CostInputs are used.

With raw_data_retained: false, the plan keeps DDSketch states (α = 0.01) in 60 s tumbling windows at ingestion time. There are 60 windows × 1,000 series of them.

Bytes per DDSketch state Stored windows, total
Planner charge (summary_shape) about 18,752 (bound for a 10⁹ value range) 1.14 GB average memory
Executor holds (DdSketch::memory_bytes) about 5,150 309 MB

At 1 Hz every 10 s (360,000 states of 10 samples each), the same query is charged 6.77 GB and holds 1.05 GB: 6.4×.

Because of this, at default unit costs, the planner never stores quantile state when raw data is retained:

Plan (10 Hz, every 60 s) Predicted cost/s Latency p50, measured
DDSketch built from raw data at query time (selected) 3.72 6,607 ms
Stored DDSketch windows 143.05, of which 142.98 is memory 186 ms
  • Today: quantile state is charged at the bound for values spanning nine decades, whatever the data. The stored plan, 35× faster, looks 38× more expensive.
  • Expected: average memory is charged near what the states hold for the declared data. The worst-case bound is kept only where a hard limit must hold.

Fixing the bytes alone does not flip this case. At 309 MB, the stored plan's memory costs about 38.7/s, while the query-time plan's CPU is predicted at 3.72/s but measures about 110/s (#1314). With both corrected, the stored plan is cheaper: about 43.7/s against 110/s.

Current behavior

sketch_shape in crates/cost/src/node/state_bytes/mod.rs prices a DDSketch with asap_sketchlib's DdSketch::estimated_memory_bytes(alpha, rows, 1.0, DDSKETCH_ASSUMED_VALUE_RANGE, negatives) (lines 163–171 at 59365ce80).

  • DDSKETCH_ASSUMED_VALUE_RANGE is the constant 1e9 (line 278). Its doc says it is "an assumption, not workload evidence: the data workload declares no value range".
  • At α = 0.01, that range spans 1,036 bucket indices.
  • estimated_memory_bytes is an upper bound over any order of inserts and merges: 2 × (span + 126) slots for three or more values. That gives 2,324 slots × 8 B plus the struct, 18,752 B, for any state with three or more samples.
  • The executor reports what the sketch actually allocated: DDSketchAccumulator::approx_memory_bytes returns self.inner.memory_bytes() (crates/executor/src/summary_kernels/dd_sketch.rs, line 47).

The overcharge depends on the data: values that really span nine decades would close the gap. The data here is synthetic, so the 6.4× is specific to its value range. The point is that the planner has no way to use a narrower range.

Expected behavior and invariant

The average-memory charge for a DDSketch state is within 1.5× of memory_bytes() for data matching the workload's declared value range. For comparison, retained raw data is charged within 1.13× of what is held in this measurement.

Minimal reproduction

  1. Plan the workload above with raw_data_retained: false, then read avg_memory_bytes and the SummaryTumblingWindowChain node's keeps … bytes detail in the plan cost.
  2. Run the plan over the synthetic data and sum memory_bytes() over the stored windows.

Impact

  • Under cost model 1, quantile queries over retained raw data always run at query time. That holds even when stored windows are much faster (35× here) and, once CPU is priced from measurement, cheaper.
  • The same bound inflates peak_memory_bytes. That rejects stored DDSketch plans under a memory limit they would fit.

Proposal

  1. A declared value range. Let the data workload state a value range per source column, next to column_signs (for example "value_range": [0.001, 10]). sketch_shape uses it in place of DDSKETCH_ASSUMED_VALUE_RANGE, and keeps the 10⁹ default when none is declared.
  2. Measured bytes. A measured memory_bytes_per_state (already a field of OperatorCost in crates/cost/src/measured.rs) overrides the formula. That fits the measured cost table issue.
  3. Two charges. The expected bytes for average memory (cost model 1), and the upper bound only where a hard limit is checked (cost model 3, executor memory limits).

These options combine. Bounding the span by the sample count alone does not work: a store allocates every bucket between its smallest and largest key, so 10 samples far apart still take the full span.

Regression test

A cost test builds DDSketch states from values in a declared range with asap_sketchlib and asserts that summary_shape's bytes are within 1.5× of memory_bytes(). Today it fails: 18,752 against about 2,900 B for 10 samples of this data.

End-to-end verification

Re-plan the example: the stored plan's predicted avg_memory_bytes is within 1.5× of the measured stored bytes.

Related

Activity

  1. added
    bugSomething isn't working
    cost-modelCost formulas, statistics, ranking, and selection
    on Nov 15, 2026
  2. zzylol commented on Nov 16, 2026

    @zzylol
    ContributorAuthor

    Measured on the 9 cells where this costs a regret (quantile and joint workloads at 10 Hz, raw data kept), with #1324 merged onto #1355 locally and the data generator's real value range declared (column_magnitudes: {"value": {"min_abs": 2.687e-8, "max_abs": 1104.2}}):

    • The charge per DDSketch state rises from 18,752 B to 21,728 B: the data spans 10.6 decades, more than the nine assumed. Every cell keeps its plan and its regret (1.17–2.38). The executor holds 4.3–5.4 KB per state.
    • A narrower, practical declaration ([0.01, 1200]) charges 11,536 B and moves 4 of the 5 joint cells, no quantile cell.

    The gap is the bound itself: estimated_memory_bytes is the worst case over any insert order (about twice the span), and a state spans the values it folds, not the column's range. #1363 charges the expected dense store over the state's own spread (2.7–6.6 KB for 10–36,000 latency-like rows against 2.9–6.7 KB held) and selects stored DDSketch in all 9 cells.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

Labels

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

Type

No type

Projects

No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions