Repository navigation
Sketch rollup: a regrouping SummaryMerge so mergeable sketches can roll up to coarser keys #719
Description
Problem, by example
A dashboard has two queries over the same latency metric, one per instance and one per job:
# Q_fine: p99 per (job, instance)
quantile by (job, instance) (0.99, latency_ms)
# Q_coarse: p99 per job
quantile by (job) (0.99, latency_ms)
Say there are 10 jobs with 100 instances each. Stage 1 can answer both with KLL sketches:
| Sketches built | Rows each sketch reads | |
|---|---|---|
| Q_fine | 1,000 KLLs, one per (job, instance) | that instance's samples |
| Q_coarse | 10 KLLs, one per job | that job's samples, i.e. the same rows again |
Every sample is read and inserted twice. KLL states merge (the family-capability table marks KLL SameAsUnionBuild). So Q_coarse could instead be answered by merging Q_fine's 100 per-instance KLLs of each job into one KLL per job, with no second pass over the raw samples:
today: with sketch rollup:
Scan ─▶ SummaryAgg(KLL by job,instance) Scan ─▶ SummaryAgg(KLL by job,instance) ─▶ Q_fine
Scan ─▶ SummaryAgg(KLL by job) └─▶ regroup-merge(by job) ─▶ Q_coarse
Why it isn't done today
- Exact accumulators already roll up. PR feat(planner): Pass 2 reuse rules (rollup, exact top-k reuse) and nested sum merge in Pass 1 (#680) #716 (for Pass 2 reuse rules: rollup, top-k reuse, nested sum merge #680) adds the Pass 2 rollup rule. For example,
sum by (job)is answered by summing the finersum by (job, instance)values, which is plain arithmetic on finalized numbers. - Sketches can't, because there is no operator for it. A sketch rollup has to merge states while changing the grouping from (job, instance) to job.
SummaryMergeonly merges states that have the same grouping, such as the tumbling panes of one group. No IR operator takes states grouped by K and produces states grouped by K' ⊂ K.
Proposal
- IR: a regrouping form of
SummaryMerge, or a dedicated operator. Its input is states grouped by keys K, its output is states grouped by K' ⊂ K, and it merges every input group whose projection onto K' matches. - Coverage: the output group covers the union of its input groups' rows. Those rows are disjoint, because the finer groups partition the rows.
- Stage 2 / Stage 3: timing and materialization like any summary merge. Pricing is one merge per input state, plus the output states' memory.
- Executor: reuse each family's existing merge kernel and add a group-by-key step.
- Guarantee: taken from the family-capability merged-error fact. KLL, DDSketch, CMS and CountSketch keep
SameAsUnionBuild; HLL and KMV allow overlap; heap top-k and UnivMon heap readouts are approximate, so they get no guarantee. - Pass 2: extend the rollup rule from exact accumulators to these sketches.
Why it's deferred
Decided on 2026-10-15. Reuse rarely wins until Stage 2 materialization (PR #717) lets the shared finer sketches be kept and charged once.
Activity
zzylol commentedon Oct 22, 2026
Started (2026-10-22). Plan, split into two PRs:
SummaryMergegets an optionalgroup_by(a rollup). Its coverage is the input build grouped by those keys, and the executor merges by the listed keys. The design doc lists the guarantee each family keeps.Motivation from the W-RollupHeavy eval: template 12 builds 15 KMV summaries per window, one per grouping, and template 13 builds 7 KLL summaries for one CUBE. Each summary reads the same raw rows again.
zzylol commentedon Oct 22, 2026
Coordination note from #857 (accuracy scope "groups holding at least a share of the records"): sizing for a summary several queries read goes through
resize_for_failure_probability, which now divides each query's δ bytarget.accuracy_scope.values_covered(G)(1 per value, ⌊1/share⌋ for a record share, G for the whole result) and keeps the smallest share per summary node. A finer summary that a regrouping merge feeds should be reached byapproximate_inputsfrom each coarser reader, so it gets the strictest reader's scope with no extra code. Please rebase onto #857 once it merges.zzylol commentedon Oct 22, 2026
#857 is merged (29278d9).
resize_for_failure_probabilitynow takes each reader'starget.accuracy_scope.max_values_covered(G), so a finer summary reached from several readers is sized for the smallest δ / (n · V). Please rebase onto main.