Repository navigation
Tracking: make the rqe-optimizer cost export fit the per-phase cost model #147
Description
Goal
Make the rqe-optimizer cost table (scripts/export_rqe_optimizer_costs.sh → out/rqe_atomic_costs.json) fit how #145's cost model uses it.
The model applies each row's costs and accuracy to real deployments, whose instances differ a lot from the benchmark's. A row carries only sketch, sketch_config, four per-op costs and an accuracy map. It records none of the conditions it was measured under, so the model can't rescale it or sanity-check it.
Phases are as in #145: ingest (open windows), merge (folding a query's windows), query (reading the merged result) and storage (closed windows, no CPU). Memory in every phase is a multiple of the row's mem_bytes_per_instance.
Measurement conditions the model can't see
Each row below says which families a condition affects, and whether it affects CPU, memory or accuracy, in which phases. "Expected" marks effects inferred from how the sketch works rather than checked against measurements.
Items inserted per instance
- Benchmark: 1,000,000 values per instance (
--size); 200,000 rows for the column-spec runs. - Real deployment:
λ × x / card(G)per window, often far fewer.
| Families | Affects | Phases |
|---|---|---|
| CMS+heap, CountSketch+heap, UnivMon (top-k and cardinality) | Accuracy: counter error grows with load, so lighter instances are more accurate (expected) | — |
| KLL | CPU: merge and query cost grow with retained items, up to the k bound |
merge, query |
| KLL | Memory: the exported formula 4 × k × 8 ignores n; real size grows slowly with n |
ingest, merge, storage |
| DDSketch | Memory: buckets are capped by the number of values | ingest, merge, storage |
| HLL, exact accumulators | No effect expected | — |
Keys (groups) per instance
- Benchmark:
groups_per_instance, only for exact accumulators, and carried in the accuracy map (about 9.9k groups forhydra_columns.yaml). - Real deployment:
card(G).
| Families | Affects | Phases |
|---|---|---|
| Exact sum, min, max, increase | Memory: the export divides by groups_per_instance, assuming linear scaling |
ingest, merge, storage |
| Exact sum, min, max, increase | CPU: merge is divided per group; query is already per group | merge |
| Shared families such as HydraKLL (#142) | Accuracy: depends on how many groups share one instance | — |
Value range
- Benchmark: the zipf data's range.
- Real deployment: the metric's own range, e.g. latencies in seconds.
| Families | Affects | Phases |
|---|---|---|
| DDSketch | Memory: buckets = log-range / log((1+α)/(1−α)) | ingest, merge, storage |
| DDSketch | CPU: merge walks the buckets (expected) | merge |
Size of each merge operand
- Benchmark: 62,500 items per shard (12,500 rows for spec runs), folded into a growing accumulator, averaged over 15 folds.
- Real deployment: one window,
λ × x / card(G)items.
| Families | Affects | Phases |
|---|---|---|
| KLL, DDSketch | CPU: fold cost grows with operand size, up to their bounds | merge |
| Exact accumulators | CPU: fold cost grows with keys per operand | merge |
| CMS, CountSketch, HLL, UnivMon | No effect expected: fixed-size arrays | — |
Windows merged per query (L / x)
- Benchmark: accuracy is measured on one full-stream instance; Measure accuracy after merging m shards #131 can measure after merging m shards.
- Real deployment:
L / xwindows.
| Families | Affects | Phases |
|---|---|---|
| KLL; CMS+heap and CountSketch+heap (lossy heap merge); UnivMon | Accuracy: merging adds error (expected) | — |
| DDSketch, HLL, CMS counters, exact accumulators | No effect expected: lossless merges | — |
Data skew
- Benchmark: zipf
s = 1.1over a 100,000-key population. - Real deployment: the metric's real distribution.
| Families | Affects | Phases |
|---|---|---|
| CMS+heap, CountSketch+heap, UnivMon top-k | Accuracy: top-k depends strongly on skew. It was 0.0 precision under uniform data. | — |
| CMS+heap, CountSketch+heap | CPU: how often the heap is updated (expected) | ingest |
What the current export already records
The export writes three files:
out/rqe_atomic_costs_raw.jsonl: one record per benchmark run.out/rqe_atomic_costs_grid.jsonl: one merged record per configuration.out/rqe_atomic_costs.json: the reduced table rqe-optimizer reads.
The raw and grid records keep the full workload description and merge_shards. The reduction to AtomicCostEntry keeps only sketch, sketch_config, the four per-op costs and the accuracy map.
| Condition | In the raw and grid records? | In the table? |
|---|---|---|
| Items per instance | Yes: workload…row_num (1,000,000) |
No |
| Keys per instance | Synthetic runs: bounded by population_size (100,000). Spec runs: in the column specs. |
Only groups_per_instance, for exact accumulators, inside the accuracy map |
| Value range | No. Derivable for synthetic zipf from population_size, not for spec-file data. |
No |
| Merge operand size | Yes: row_num / merge_shards (16) |
No |
| Accuracy after merging | The schema has merge_accuracy since #131, but the export's accuracy run doesn't request merges, so it isn't measured. |
No |
| Data skew | Yes: distribution: {kind: zipf, skewness: 1.1, population_size} |
No |
So items per instance, merge operand size, skew and the synthetic key count only need carrying into the table. Value range in general, accuracy after merging and the size sweep need new measurements.
Work
- (atomic-costs: record the measurement conditions on each cost-table row #155) Record measurement conditions on each row: a
measured_atblock with items per instance, keys per instance, value range, merge shard size and dataset/skew. This is cheap, and makes every row checkable. - (rqe-optimizer: check accuracy at the query's merge count #154) Accuracy at several merge counts, building on Measure accuracy after merging m shards #131. The model checks accuracy at the query's
L / xinstead of the single-instance value. This affects feasibility, not just cost, so it matters most. - (moved to rqe cost export: sweep items per instance and re-export (follow-up to #147) #157) Sweep items per instance (
--sizegrid) for costs and accuracy. The model interpolates atλ × x / card(G). - (rqe-optimizer: size DDSketch memory from the metric's value range #152) Model side: add each metric's value range to
MetricFactsand size DDSketch from it.
Per-op fixes
These need no new fields:
- (rqe cost export: count top-k heaps, time top-k queries above the clock floor, add exact hash-table overhead #151) Top-k cost rows: CMS/CountSketch+heap exclude the heap from memory, UnivMon includes it #146: CMS/CountSketch+heap memory leaves out the heap while UnivMon counts it. Memory; ingest, merge, storage.
- (rqe cost export: count top-k heaps, time top-k queries above the clock floor, add exact hash-table overhead #151) Top-k query timing: one heap dump per pass sits at the timer floor. CMS/CountSketch+heap; CPU; query. Fix: repeat the call per pass, as HLL does.
- (rqe cost export: count top-k heaps, time top-k queries above the clock floor, add exact hash-table overhead #151) Exact accumulators' memory has no hash-table overhead. Memory; ingest, merge, storage.
Related
- rqe-optimizer: per-phase cost model, workload facts, weighted AUCCost objective #145: the per-phase cost model that consumes this table.
- Tracking: make rqe-optimizer the solver for ASAPQuery's planner #143: the tracking issue for making rqe-optimizer ASAPQuery's planner.
- rqe-optimizer: support shared multi-subpopulation sketches (HydraKLL) in the cost model #142: shared-instance families (HydraKLL).
- Measure accuracy after merging m shards #131: merged-shard accuracy.
🤖 Generated with Claude Code
Activity
rqe-optimizer: check both bracketing merge counts; skip partial grids
rqe cost export: count top-k heaps, repeat top-k queries, add exact h…
rqe-optimizer: size DDSketch memory from the metric's value range (#152)
atomic-costs: record each row's measurement conditions (measured_at)
atomic-costs: record the measurement conditions on each cost-table row (
rqe-optimizer: accuracy at the query's merge count
rqe-optimizer: check both bracketing merge counts; skip partial grids
rqe-optimizer: check accuracy at the query's merge count (#154)
zzylol commentedon Oct 6, 2026
Closing: every item is done except the items-per-instance sweep, which moves to #157 together with the first re-export of the cost table.
measured_aton every rowL/xMetricFacts.value_range; DDSketch memory sized from it, capped by values per instance (merge accumulator by the lookback)None of these has been through a full export yet; #157 tracks that.
🤖 Generated with Claude Code