Repository navigation
Description
Example
SQL top-k by count over the synthetic clicks table (1,000 URLs, 100,000 rows/s), every 60 s, with an L1-normalized target:
SELECT url, COUNT(*) AS c FROM clicks
WHERE ts >= now() - INTERVAL '3600 seconds'
GROUP BY url ORDER BY c DESC LIMIT 10
-- accuracy: absolute_stream_l1, max_error 0.01, failure_probability 0.05, whole_resultThe memo offers Count-Min + heap and Count Sketch + heap readouts for it, but Pass 2 prunes all 560 sketch candidates (280 of each family, one per parameter choice) by the metric rule with no accepted metric:
CmsWithHeap { width: 28, depth: 5, heap_size: 10 } <- MetricRule { producer_metric: Absolute { scale: Some(StreamL1) }, accepted_metrics: [] }
CountSketchWithHeap { width: 300, depth: 47, heap_size: 10 } <- MetricRule { producer_metric: Absolute { scale: Some(StreamL2) }, accepted_metrics: [] }
The selected plan is exact (6.31 /s). The PromQL form of the same question, topk(10, sum by (url) (rate(http_requests_total[1h]))), does plan a CMS + heap.
The same happens to the SQL frequency-moment idioms, which never plan UnivMon:
-- L2 of the per-client_ip counts: accuracy relative 0.1, δ 0.1
SELECT SQRT(SUM(CAST(c AS DOUBLE) * CAST(c AS DOUBLE)))
FROM (SELECT client_ip, COUNT(*) AS c FROM clicks
WHERE ts >= now() - INTERVAL '3600 seconds' GROUP BY client_ip)
-- entropy of the per-client_ip counts: accuracy absolute 0.1, δ 0.1
SELECT -SUM(p * LN(p))
FROM (SELECT COUNT(*) * 1.0 / SUM(COUNT(*)) OVER () AS p FROM clicks
WHERE ts >= now() - INTERVAL '3600 seconds' GROUP BY client_ip)| Query | Pass 2 prune cause of every UnivMon readout | Selected plan |
|---|---|---|
| L2 | MetricRule { producer_metric: Relative, accepted_metrics: [] } (all 40 UnivMon candidates) |
exact, 3,839.6 /s |
| entropy | NoGuarantee (all 40 UnivMon candidates) |
exact, 3,839.6 /s |
In the PromQL form (l2_over_time(dns_query_client[24h])), UnivMon is selected at 2.7× to 6.3× lower cost than exact.
Measured with the planning driver of the sketch-heavy workload study (run_stages_until(.., Stage2) then select_plan, default deployment and cost model) on main 2f3664d1f. The workloads are in tools/dag-viewer/workloads/sketch-heavy/ (blocked-sql-topk-count-urls__…, blocked-sql-l2-client-ip__…, blocked-sql-entropy-client-ip__…, blocked-sql-topk-bytes-urls__…), added by #1388.
Why it happens
An approximate readout survives Pass 2 only if every operator between it and the query root has an error contract that says how the readout's error reaches the output. Two operators that the SQL shapes put above the readout have none, so the accepted metric set on the readout's edge is empty:
- The top-k readout's cast. The estimated top-k weight is Float64, and an exact top-k of a SQL
COUNTranks Int64 values. Pass 1's top-k projection therefore casts the estimate to Int64 (stage1-pass1-per-computation-candidates/src/candidates/measure_output.rs:335-345):Project [Cast { Column(1), to: Int64 } AS topk_10, Column(0) AS url].keeps_error(accuracy/src/error_contract/mod.rs:280) accepts a copy, a literal,promql_drop_metric_name, 1-Lipschitz functions and constant scaling, but noCast, so it rejects this projection in every metric. - The NULL-on-empty
Join.sql_frequency_result(frontend-sql/src/frequency.rs:332) rewrites the L2 and entropy idioms asCross Join(statistic, exact population_count)underProject CASE WHEN population_count = 0 THEN NULL ELSE statistic END, so that an empty window returns SQL's NULL (frequency.rs:355). TheJoinhas no error contract, so no metric passes it.
For the entropy idiom, a second gap shows first: UnivMon certifies only L2 and the exact total (accuracy/src/guarantee/univmon/mod.rs), so its entropy readout has no guarantee. The Join gap remains once an entropy guarantee exists.
A related case with different causes: SUM top-k. For SELECT url, SUM(bytes) AS b … ORDER BY b DESC LIMIT 10 (same target), the projection has no cast. The readouts are still pruned:
- Count-Min + heap:
ValuesPerEvaluationUnknown(stage1-pass2-reuse-candidates/src/edges.rs:79). The whole-result δ has no per-value split, because the number of values one evaluation returns is unknown on this path. - Count Sketch + heap: by the metric rule with
accepted_metrics: [Absolute { scale: Some(StreamL1) }]. That one is correct, since an L2 sketch cannot meet an L1 target.
Proposal
- Cast: give
keeps_errora rule for a numericCast.- A widening cast (Int64 → Float64) keeps the error in every metric.
- A Float64 → Int64 cast rounds, adding at most 1 in absolute error. That is negligible against a stream-normalized ε, but it is not β = 1 for an unscaled absolute target.
- Alternatives: (a) treat the rounding as an additive term in the contract; (b) do not cast an approximate top-k estimate, and let the approximate result keep Float64 where the output schema allows it.
- Join: give the error contract a rule for this
Joinshape. A cross join with a single exact row on one side, where only the exact side feeds theCASEcondition, passes the other side's error through unchanged (β = 1) in every metric.- Alternative: express NULL-on-empty in a way the contract already covers, for example a
Projectwith aCASEover an exact count read from the same input.
- Alternative: express NULL-on-empty in a way the contract already covers, for example a
SUMtop-k: find why the number of values per evaluation is unknown on the SQLSUMpath but known for PromQLsum by (url). Theclickssource declaresdistinct_values_per_label.url = 1000. Fix that in this issue, or split it into its own.
Scope and acceptance
- In scope: the error contracts of the numeric cast and of the NULL-on-empty join, and the
SUMtop-k per-value split. - Out of scope: an entropy guarantee for UnivMon. That is a separate accuracy-model change.
- Acceptance, with one test per shape that fails today:
- the
COUNTtop-k example has at least one surviving heap readout and selects a heap sketch where it is cheaper; - the L2 example's UnivMon readouts are no longer pruned by
MetricRule; - the
SUMtop-k's Count-Min + heap readouts are no longer pruned byValuesPerEvaluationUnknown.
Pin each with asketch_plan_snapshotsentry once a sketch is selected.
- the
Related
- Found by the sketch-heavy workload study; the workloads are added by test(devtools): sketch-heavy workload set, five family snapshots, and a rollup test that selects a KLL #1388.
- SQL top-k by COUNT(*): sketch candidates are misplaced (per-host CMS/UnivMon, heap over exact counts); no CMS+heap over raw rows #886 (closed): SQL top-k by
COUNT(*)sketch-candidate placement, which put the heap readout in place. - IR: set-op and aggregate nullability, and the SQL top-k rewrite's output shape #657: the SQL top-k rewrite's output shape.
Activity