Repository navigation
SQL top-k by COUNT(*): sketch candidates are misplaced (per-host CMS/UnivMon, heap over exact counts); no CMS+heap over raw rows #886
Description
Workload
One repeating SQL query on 0fe2cc44, every 10 s with ε=0.01, δ=0.001: the 5 hosts with the most rows in the last 5 minutes.
SELECT host, COUNT(*) AS c FROM metrics WHERE ts > now() - INTERVAL '5' MINUTE GROUP BY host ORDER BY c DESC LIMIT 5Save as wl.json:
{"query_workload": {"language": {"sql": "datafusion_sql"}, "query_batch": null, "repeating_queries": [
{"query": "SELECT host, COUNT(*) AS c FROM metrics WHERE ts > now() - INTERVAL '5' MINUTE GROUP BY host ORDER BY c DESC LIMIT 5",
"demand": {"fixed_interval": 10000}, "requirements": {"accuracy": {"max_error": 0.01, "failure_probability": 0.001}},
"predictability": {"predictable": {"known_at": null}}}]},
"data_workload": {"arrival": {"ingesting": {"rows_per_second": 666.67}}, "sources": {"metrics": {"series_count": 100}}}}cargo run -p asap-devtools --bin stage_pipeline -- --workload wl.json --exhaustive --out out.json \
--table '{"name": "metrics", "columns": [{"name": "ts", "type": "timestamp", "nullable": false}, {"name": "city", "type": "utf8"}, {"name": "host", "type": "utf8"}, {"name": "value", "type": "float64"}], "time_index": 0}'Plans (Stage 2, nothing materialized)
- Exact (selected):
Scan → TimeRange(5m) → SummaryAgg(exact Count, per host) → FinalizeExactAccumulator → Project → Sort → Limit 5 Q1 Cms:Scan → TimeRange(5m) → SummaryAgg(Cms, per host) → SummaryEstimate(PointCount) → Project → Sort → Limit 5Q1 UnivMon: the same asQ1 Cms, with UnivMon per host.Q1 CMS+heap (Count acc):Scan → TimeRange(5m) → SummaryAgg(exact Count, per host) → FinalizeExactAccumulator → Project → SummaryAgg(CmsWithHeap) → SummaryEstimate(TopK k=5)
Questions
Q1 CmsandQ1 UnivMonmight be incorrect. They keep one sketch per host, and each sketch only ever sees its own host's rows before being asked for that host's count. They are also rejected asexecutor_cannot_compile(unsupported weighted frequency family;summary update type is unsupported by its family).Q1 CMS+heapalso seems wrong. It builds the CMS+heap over the already-exact(host, count)rows, so the top 5 is already known before the sketch runs. Its weights are thecountcolumn, which is why it is rejected withcount_min_weights_not_proven_non_negative, even thoughCOUNT(*)is never negative.CountSketch+heaphas the same shape and fails withexecutor_cannot_compile: summary update column missing or ambiguous.- The expected top-k sketch plan is missing. No candidate builds one CMS+heap (or CountSketch+heap) over the raw rows keyed by
hostand reads its top 5.
Activity
milindsrivastava1997 commentedon Oct 22, 2026
Overlap check (still reproduces on
4535c957):ORDER BY c DESC LIMIT k) does not bind #619, item 2: the heap candidates for this same query shape. In SQL top-k ordered by an alias (ORDER BY c DESC LIMIT k) does not bind #619 they failed to compose; they now compose, but stacked on the exact counts instead of over the raw rows.Related: #657 (the top-k rewrite's output shape), #773 and #832 (the same rejection and the same missing fused heap, fixed for PromQL).
zzylol commentedon Oct 23, 2026
Deferred until the memo search (#879, #888) lands. This sharing/reuse rule will be added as a memo transformation rather than to the legacy search.
zzylol commentedon Oct 27, 2026
Confirmed a specific candidate-generation gate in the current planner (base main
7680b6bc). The original SQL COUNT-ranked TopK inventory hasfused=None, even though the keyed-additive realization already knows how to build a global heap over raw rows with host as the item and constant weight 1.per_computation_candidates.rs::whole_expression_inputrejects closed-schema inputs when!reads_only_time_series(realized.child). Its comment explicitly keeps SQL heaps over the per-key result. This excludes SQL raw-row fusion. The new regression asserting a fused SQL heap fails before removing that SQL-only exclusion and passes afterward. The resulting candidates use raw input and unit weights, and compile through the executor when accuracy enforcement is disabled.This is not yet a complete fix: with the issue's epsilon/delta target enforced, the newly exposed fused candidates are still rejected as NoAccuracyGuarantee. That remaining accuracy propagation/contract needs to be addressed before claiming they are selectable. The test distinguishes candidate existence/compilation from accuracy acceptance.
Also, a CMS per host is not automatically a wrong-answer plan merely because each sketch sees one host: it can be a wasteful representation of a count. The original family/update compilation problems and the missing raw-row fusion are separate concerns; they should not be conflated.
All changes/regressions are local and uncommitted. No PR/commit has been published; keep the issue open.
zzylol commentedon Oct 27, 2026
Implemented in PR #943. SQL count-ranked CMS/CountSketch heaps now fuse over raw rows keyed by the grouping columns with unit weights, absorbing the inner count. Both heaps compile and execute. Unsupported per-group SQL count-sketch realizations are explicitly pruned, with exact counters retained. Tests cover integer keys, a key named value, and partitioned TopK. Frequency bounds still do not certify TopK membership, so the accuracy gate correctly remains in force.
Final local validation: 690 focused tests passed, plus workspace format and all-target/all-feature Clippy checks.