Instant quantile by (host, job) next to windowed quantiles: no scan sharing, no panes, no ingest-time variant, 100-group default #840

Activity

1. milindsrivastava1997

   added

   questionFurther information is requestedFurther information is requested

   cost-modelCost formulas, statistics, ranking, and selectionCost formulas, statistics, ranking, and selection

   optimizerWorkload optimization and plan selectionWorkload optimization and plan selection

   on Oct 21, 2026
2. milindsrivastava1997 commented on Oct 21, 2026

   

   milindsrivastava1997

   on Oct 21, 2026

   CollaboratorAuthor

   More actions

   Adding Q4 quantile by (job) (0.5, data)

   Add this query to repeating_queries in the workload above:

   {"query": "quantile by (job) (0.5, data)", "demand": {"fixed_interval": 10000},
    "requirements": {"accuracy": {"max_error": 0.01, "failure_probability": 0.001}},
    "predictability": {"predictable": {"known_at": null}}}

   Run with the same command and --max-displayed 100000. Stage 1 goes from 150 to 450 logical plans and Stage 2 from 294 to 882 physical plans. Like Q3, Q4 only adds its own choice of exact, KLL or DDSketch.

   5. Q3 and Q4 don't share their scan. Both are instant scans of data with a 15 s lookback, and their Scan and TimeRange nodes appear identical. Even so, none of the 450 logical plans shares anything except shared Scan (Q1, Q2). Should Q3 and Q4 share these nodes?
   6. No rollup from (host, job) to (job). A KLL per (host, job) could be merged per job to answer Q4, but no plan does that. Should the summary-capability rule offer it? fix: one finest-grain stored summary serves several groupings (quantiles at the estimate level, sums at the state level) #804 covers stored summaries, but Q3 has no plan that stores state at ingestion time (question 3).
3. zzylol commented on Oct 21, 2026

   

   zzylol

   on Oct 21, 2026

   Last edited by zzylol

   Contributor

   More actions

   Reproduced on 14394ada with the issue's workload and command, without and with Q4:

   Workload	Logical plans	Physical plans	Selected plan	Cost per second
   Q1–Q3	150	294	Q1 KLL · Q2 KLL · Q3 KLL	0.1622
   Q1–Q4	450	882	Q1 KLL · Q2 KLL · Q3 KLL · Q4 KLL	0.1700

   The only sharing in either run is shared Scan (Q1, Q2). Q3 and Q4 are both priced at 100 groups.

   Q1 and Q5: no scan sharing with Q3 or Q4

   Gap; will be fixed. The PromQL frontend projects into each Scan only the labels the query uses: Q1/Q2 read ts, value, $promql_series_identity, Q3 adds host, job, Q4 adds job. Structural CSE shares two nodes only when their schemas are equal, so these scans (and Q3's and Q4's instant TimeRange nodes above them) never match. Other rules already treat such scans as the same rows; the identical-expression rule doesn't yet.

   Fix: widen each scan of a metric to the union of the labels its readers use, and add a Project above each reader to restore its own columns. Structural CSE then finds the shared scans and time ranges unchanged. This comes right after #839's Stage 2 fix (a shared scan built once at query time), in the same line of work. Before that fix a shared scan is charged once per reader, at the longest window, so sharing would only add plans that lose.

   Q2: no panes for Q3

   Intended. Q3 is an instant selector: it keeps only the latest sample of each series within the 15 s lookback. Panes split a range window into slices whose states merge; merging panes would keep every sample in the lookback, not only the latest per series, and change the answer. The reason will be stated in the window-composition rule's docs.

   Q3: no ingestion-time variant for Q3

   Intended. When a new sample arrives, it replaces that series' previous value in Q3's answer, and series drop out once they go stale. An ingestion-time summary per (host, job) would have to delete old values; KLL cannot, and a DDSketch could only next to a per-series last-value table, which is the raw store itself. The gain would also be small: Q3's whole query-time path costs about 0.009 per second of 0.17. Today the plan is rejected with the generic WindowNotFixed reason, which stage_pipeline does not show. It will get its own reason ("instant selector: the latest sample per series replaces earlier ones") and one sentence in the Stage 2 and planner-layering.md materialization docs.

   Q4: the 100-group default

   It is a placeholder: DEFAULT_GROUP_COUNT = 100 in plan selection, used for every by (...) with at least one label and for partitioned sorts and limits. Nothing in the workload can override it today.

   Fix (PR in progress): the data workload declares the number of distinct values per label:

   "sources": {"data": {"series_count": 10000, "metric_type": "gauge", "sample_interval": 15000,
                        "distinct_values": {"host": 1000, "job": 10}}}

   Stage 3 estimates the groups of by (K) as min(product of distinct_values over K, series_count). If a label in K is undeclared, it falls back to 100, capped at series_count.

   Q6: no rollup from (host, job) to (job)

   Out of the current scope; tracked in #719. The rollup rule handles exact accumulators (sum, count, min, max) only; sketches have no regrouping merge in the IR yet. #719 adds one, after the cardinality work in Q4, since a rollup cannot be priced fairly while both groupings count as 100 groups. For this workload the benefit would be small anyway: Q3 keeps no state between evaluations (Q3 above), and merging ten-sample KLLs per (host, job) costs about as much as inserting the samples directly.

   New finding: exact grouped quantile plans don't compile

   Every plan with Q3 or Q4 exact (490 of the 882) is rejected with executor_cannot_compile: aggregate intent has no native implementation. The executor's grouped aggregate has no exact quantile, so the exact baseline for quantile by (...) is never compared. #846 tracks adding it; a PR is in progress.

   Order

   1. Declared distinct values per label (Q4).
   2. Exact grouped quantile in the executor.
   3. Explicit reasons for instant selectors (Q2, Q3).
   4. Shared non-summary nodes built once at query time (Two windowed quantiles over one metric: shared scan costs more, and nested-window KLL panes are never shared #839), then label-union scan sharing (Q1, Q5).
   5. Sketch rollup (Sketch rollup: a regrouping SummaryMerge so mergeable sketches can roll up to coarser keys #719, Q6).
4. zzylol

   added 12 commits that reference this issue on Oct 21, 2026

   fix(executor): compile an exact instant quantile by (G) to the groupe…

   ...

   4c2aabb

   fix(executor): answer a NaN quantile φ as Prometheus; address review

   ...

   9aaa800

   feat(plan-selection): price a grouping from declared per-label distin…

   ...

   cc0aabe

   fix(executor): compile an exact instant quantile by (G) to the groupe…

   ...

   078efc0

   feat(plan-selection): price a grouping from declared per-label distin…

   ...

   db9d8c2

   feat(plan-selection): price groupings from declared per-label distinc…

   ...

   939e6ed

   feat(pass2): share scans of one metric that project different labels

   ...

   8c25da4

   feat(pass2): share scans of one metric that project different labels (#…

   ...

   1b4d6c1

   test(devtools): the #840 workload selects Q4's KLL rolled up from Q3's

   06da69e

   test(devtools): the #840 workload selects Q4's KLL rolled up from Q3's

   12d7c4b

   test(devtools): the #840 workload selects Q4's KLL rolled up from Q3's

   b994c0d

   feat(plan-selection): memo over logical sub-expressions with a brute-…

   ...

   89a5ada
5. zzylol commented on Oct 23, 2026

   

   zzylol

   on Oct 23, 2026

   Contributor

   More actions

   Status of the six questions on main:

   1. Q3's scan shared with Q1/Q2: fixed. Scans of one metric that project different labels can now be shared (feat(pass2): share scans of one metric that project different labels #868). In this workload the shared variant is offered but loses on cost (0.2068/s vs 0.1702/s), so Q1/Q2 keep their shared scan.
   2. No panes for Q3: intended. An instant selector reads only the latest sample.
   3. No ingestion-time variant for Q3: intended. A sketch can't drop a series' old value.
   4. The 100-group default: fixed.
      • Groupings are priced from declared per-label distinct values (feat(plan-selection): price groupings from declared per-label distinct values #849) and declared label-set counts (Price groupings from declared distinct counts of label sets (hierarchical labels) #897).
      • There is no invented default any more (fix(plan-selection): price groupings from facts only, with no default group count #882, fix(plan-selection): price only from declared facts; no default series, rate or look-back #889).
      • Whole-result targets over groups are bounded by the declared counts (fix(plan-selection): bound a grouped result's values by its keys' declared distinct values #867).
   5. Q3 and Q4 share no scan: fixed. Same as 1 (feat(pass2): share scans of one metric that project different labels #868).
   6. No rollup from (host, job) to (job): fixed. Coarse sketch groupings roll up from the finest build (feat(ir, executor): SummaryMerge regroups states by a subset of their group keys (sketch rollup, part 1) #856, feat(pass2): coarse sketch groupings roll up from the finest build (sketch rollup, part 2) #869). The workload now selects KLL for Q4 rolled up from Q3.

   Also found here: exact quantile by plans did not compile. That is fixed by #847 (issue #846).
6. zzylol

   closed this as completedon Oct 23, 2026
7. zzylol

   added 3 commits that reference this issue on Oct 23, 2026

   plan-selection: memo MILP stays a lower bound with shared slots and w…

   ...

   43afd7a

   plan-selection: memo MILP lower bound across groups and rollups

   ...

   7dc270e

   feat(plan-selection): experimental MILP search over the sub-expressio…

   ...

   6e53384